#####################################################################
##HIMURIM:  Save this file as HIMURIM                                #
## To use it, stay in the                                            #
##same directory, get into Maple (by typing: maple <Enter> )         #
##and then type:  read HIMURIM<Enter>                                #
##Then follow the instructions given there.                          #
##                                                                   #
##Written by Doron Zeilberger, Rutgers University ,                  #
#zeilberg at math dot rutgers dot edu                                #
######################################################################
 
#Created: Aug. -Nov. 2011
 
print(`Created:  Aug.-Nov. 2011`):
print(` This is  HIMURIM`):
print(`a Maple package. It estimates and computes general winning probability `):
print(` expected life, and probability distributions  `):
print(`for discrete gambling problems, in the style`):
print(`of Dubins-Savage, Kelly, and Breiman. `):
print(`It uses three different approaches:`):
print(` Simulation (very inaccurate), exact linear algebra for`):
print(`specific boards, and (when possible) `):
print(`symbolic solving of recurrence equations`):
print(`for general, regular, scenarions.`):
print(`This Maple package  (along with the Maple package PURIM)`):
print(`accompanies the article `):
print(`"How to Gamble If You're In a Hurry" `):
print(`by Shalosh B. Ekhad and Doron Zeilberger,`):
print(`and also available from Zeilberger's website`):
print(``):
print(`Please report bugs to zeilberg at math dot rutgers dot edu`):
print(``):
 print(`The most current version of this  package and paper`):
 print(` are  available from`):
 print(`http://www.math.rutgers.edu/~zeilberg/tokhniot/HIMURIM  .`):


print(`----------------------------------------------------`):
 print(`For a list of the Checking procedures type ezraCh();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of the Contest procedures type ezraCo();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of  procedures regarding Deadlines type ezraDD();`):
print(`, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of the Proving procedures type ezraPr();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of the Ploting procedures type ezraPl();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of the Strategy procedures type ezraStr();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of  procedures that tell a story`):
 print(` type: ezraSto();`):
print(`, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of the SUPPORTING procedures type ezraSu();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of the SIMULATION procedures type ezraSi();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of the Symbolic procedures type ezraSy();, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

print(`----------------------------------------------------`):
 print(`For a list of the Linear Algebra procedures type ezraLA();`):
print(`, for help with`):
 print(`a specific procedure, type ezra(procedure_name);   .`):
 print(``):
print(`----------------------------------------------------`):

with(combinat):


ezraGarbage:=proc()

if args=NULL then
 print(` The discarded procedures are: `):
 print(`  BstrNi, BstrNiD, BstrND, DeltaPr, GreedyBest, , GreedyBestD,`):
 print(` TestBH, TestBHrand `):
else
ezra(args):
fi:

end:

ezraCh:=proc()

if args=NULL then
 print(` The CHECKING procedures are: `):
 print(` BdokED, BdokGB, CheckBestStake  `):

else
ezra(args):
fi:

end:

ezraCo:=proc()

if args=NULL then
 print(` The Contest procedures are: BaB, BestBreiman, BreimanProfile,`):
 print(` BreimanContestx, BstrN, IsOptimal,`):
 print(` IsOptimalSubFair, IsOptimalSuperFair `):
 print(` KellyContestx, KellyProfile  `):

else
ezra(args):
fi:

end:


ezraLA:=proc()

if args=NULL then
 print(` The Linear Algebra procedures giving EXACT answers for numeric N `):
 print(`are: Dpgf, DpgfL, DpgfW, ED, EDl, EDw,  PrL, PrW `):

else
ezra(args):
fi:

end:


ezraDD:=proc()

if args=NULL then
 print(` The procedures for computing probabilities of winning,`):
 print(` expected duration`):
 print(`and probability generating functions with a deadline`):
 print(`BestBKdd, BestBreimanDD, BestKellyDD,  BestStake, BestStrat `):
 print(` EDdd, KellyProfileDD, PrWdd `):

else
ezra(args):
fi:

end:

ezraPl:=proc()

if args=NULL then
 print(` The ploting procedures are: `):
 print(` plotDist, plotED, plotEDw, plotPrW `):
 

else
ezra(args):
fi:

end:

ezraPr:=proc()

if args=NULL then
 print(` The proving procedures are: `):
 print(` RandPrDS `):
 

else
ezra(args):
fi:

end:

ezraSi:=proc()

if args=NULL then
 print(` The SIMULATION procedures are: GB, GB1, LC `):
 print(` SimulateBS, SimulateBSv `):

else
ezra(args):
fi:

end:

ezraStr:=proc()

if args=NULL then
 print(` The  procedures describing strategies are `):
 print(` AllS, BoS, BrS,  KS, RS, TS`):

else
ezra(args):
fi:

end:

ezraSto:=proc()

if args=NULL then
 print(` The  procedures telling a story are: BestBKddStory1`):
 print(` BestBKddStory, BestStratStory, BreimanContestStory `):
 print(` KellyContestStory, KellyContestStoryWB, KellyProfileStory `):

else
ezra(args):
fi:

end:


ezraSu:=proc()

if args=NULL then
 print(` The supporting procedures are: `):
 print(` AveAndMoms, AveAndNorMoms,  BestNei, `):
 print(` FirstBetter, GreedyBestN, GreedyBestND `):
 print(` IsBetter, IsBetterD,`):
 print(` IsValidStrat, OM1,  Skhenim, Vecs`):

else
ezra(args):
fi:

end:

ezraSy:=proc()

if args=NULL then
 print(` The SYMBOLIC procedures are: `):
 print(` CGRED, CGREDw, CGRpgf, CGRpgfL, CGRpgfW, CGRW `):

else
ezra(args):
fi:

end:


ezra:=proc()

if args=NULL then
 print(`The Help for the procedures is divided into the following: `):
print(` ezraCh(), ezraCo(), ezraDD(),`):
print(` ezraLA(), ezraPl(), ezraPr(), ezraSi(), `):
print(`ezraSto(), ezraStr(),ezraSu(),ezraSy()`):
 print(`ezraCh(): for Checking procedures`):
 print(`ezraCo(): for Contest procedures`):
 print(`ezraDD(): for  Linear Algebra procedures with a deadline`):
 print(`ezraLA(): for the Linear-Algebra (given EXACT results for numeric N)`):
 print(`ezraPl(): Plotting programs`):
 print(`ezraPr(): Proving programs`):
 print(`ezraSi(): Simulation programs`):
print(` ezraSto(), ezraStr(), ezraSu(), ezraSy()  `):
 print(`ezraSto(): programs that tell stories`):
 print(`ezraStr(): Strategy programs`):
 print(`ezraSu(): Supporting programs`):
 print(`ezraSy(): programs that output symbolic formulas for symbolic N`):
 print(`and i, whenever available`):
 print(`For example, to get a list of the Linear Algebra procedures`):
 print(`type: ezraLA();`):
 print(`-------------------------------`):
 print(`To get help on a specific procedure, type: ezra(ProcedureName);`):
 print(`For example: ezra(GB);`):



elif nops([args])=1 and op(1,[args])=AllS then
print(`AllS(N): the set of all strategies with N dollar cap`):
print(`For example, try:`):
print(`AllS(6);`):

elif nops([args])=1 and op(1,[args])=AveAndMoms then
print(`AveAndMoms(f,x,N): Given a probability generating function`):
print(`f(x) (a polynomial, rational function and possibly beyond)`):
print(`returns a list whose first entry is the average `):
print(`(alias expectation, alias mean)`):
print(`followed by the variance, the third moment (about the mean) and`):
print(`so on, until the N-th moment (about the mean).`):
print(`If f(1) is not 1, than it first normalizes it by dividing`):
print(`by f(1) (if it is not 0) .`):
print(`For example, try:`):
print(`AveAndMoms(((1+x)/2)^100,x,4);`):

elif nops([args])=1 and op(1,[args])=AveAndNorMoms then
print(`AveAndNorMoms(f,x,N): Given a probability generating function`):
print(`f(x) (a polynomial, rational function and possibly beyond)`):
print(`returns a list whose first entry is the average `):
print(`(alias expectation, alias mean)`):
print(`followed by the variance, and the normalized`):
print(`higher moment (about the mean) and`):
print(`so on, until the normalized N-th moment (about the mean).`):
print(`The normalized -rth moment is the r-th moment (about the mean)`):
print(`divided by the (r/2)-th power of the variance`):
print(`If f(1) is not 1, than it first normalizes it by dividing`):
print(`by f(1) (if it is not 0) .`):
print(`For example, try:`):
print(`AveAndNorMoms(((1+x)/2)^100,x,4);`):

elif nops([args])=1 and op(1,[args])=BaB then
print(`BaB(p,S): starting with a strategy S, and operating`):
print(`with subfair prob. p, keeps finding bolder and`):
print(`bolder strategies until it can't make it any  bolder`):
print(`It returns the ultimate strategy. For example, try:`):
print(`BaB(2/5,TS(10));`):

elif nops([args])=1 and op(1,[args])=BdokED then
print(`BdokED(p,BetS): checks the consistency of ED, EDw, EDl`):
print(`PrW, PrL, for the strategy BetS. For example, try:`):
print(`BdokED(3/5,[1$9]);`):

elif nops([args])=1 and op(1,[args])=BdokGB then
print(`BdokGB(p,x0,BetS,K): checks the simulation program`):
print(`GB(p,x0,BetS,K) against the exact prediction. For example try:`):
print(`BdokGB(1/2,2,[1$3],100);`):

elif nops([args])=1 and op(1,[args])=BestBKdd then
print(`BestBKdd(p,N,i,T,h): The best Breiman-Kelly Strategy if you have`):
print(`if you must win N dollars in <=T rounds, and your`):
print(` initial capital is i`):
print(`using resolution h`):
print(`It also returns the expected time`):
print(`until exit (either as a winner or loser). For example try:`):
print(`BestBKdd(3/5,100,60,30,1/20);`):

elif nops([args])=1 and op(1,[args])=BestBKddStory then
print(`BestBKddStory(p,N,h,t0,MaxF,M0): finds the Best strategy if`):
print(`the prob. of winning a single round is p, the exit capital`):
print(`is N, for various initial capitals, by increments of M0`):
print(` with resolution h for various`):
print(`starting times  with increments of t0, until MaxF times the `):
print(`expected duration of timid play.`):
print(`For example, try:`):
print(`BestBKddStory(3/4,50,1/10,10,1/4,10):`):

elif nops([args])=1 and op(1,[args])=BestBKddStory1 then
print(`BestBKddStory1(p,N,i,h,t0,MaxF): finds the Best strategy if`):
print(`the prob. of winning a single round is p, the exit capital`):
print(`is N, the initial capital i with resolution h for various`):
print(`starting times  with increments of t0, until MaxF times the `):
print(`expected duration of timid play.`):
print(`For example, try:`):
print(`BestBKddStory1(3/4,50,30,1/10,10,1/4):`):

elif nops([args])=1 and op(1,[args])=BestBreiman then
print(`BestBreiman(p,N,x,f,h,conf): The Best Breiman strategy`):
print(`with goal N, and initial capital x and factor f`):
print(`For example, try: `):
print(`BestBreiman(3/5,100,1/2,1/5,1/10,98/100);`):

elif nops([args])=1 and op(1,[args])=BestBreimanDD then
print(`BestBreimanDD(p,N,i,T,f,h): The best Breiman adjustment`):
print(`Strategy to Kelly strategy with factor f`):
print(`if you must win N dollars in <=T rounds, `):
print(` and your initial capital is i`):
print(`using resolution h`):
print(`until exit (either as a winner or loser). For example try:`):
print(`For example, try:`):
print(`BestBreimanDD(3/5,100,50,40,1/5,1/10); `):

elif nops([args])=1 and op(1,[args])=BestKellyDD then
print(`BestKellyDD(p,N,i,T,h): The best Kelly Strategy if you have`):
print(`if you must win N dollars in <=T rounds, `):
print(`and your initial capital is i`):
print(`using resolution h.`):
print(`For example, try:`):
print(`BestKellyDD(3/5,100,50,40,1/10); It also returns the expected time`):
print(`until exit (either as a winner or loser). For example try:`):
print(`BestKellyDD(3/5,100,60,30,1/20);`):

elif nops([args])=1 and op(1,[args])=BestNei then
print(`BestNei(p,S,i): the set of best neighbors of strategy S`):
print(`as far the prob. of ultimate win with a game with`):
print(`prob. of winning a dollar being p, if your current`):
print(`capital i dollars. Followed by the record. For example, try:`):
print(`BestNei(2/5,TS(5),3);`):

elif nops([args])=1 and op(1,[args])=BestStake then
print(`BestStake(p,i,N,T): Suppose that you are in a casino, `):
print(`with i dollars, and you exit as a winner as soon as`):
print(`you have N dollars, and at any round you can stake any`):
print(`amount <=min(i,N-i), and the prob. of winning a single`):
print(`round is p, and you want to maximize the probability of`):
print(`achieving your goal in <=T rounds (the deadline, if`):
print(`you don't have N dollars by that time the mafia will kill you)`):
print(`It outputs that optimal stake(s), and the probability`):
print(`of making it, if you play optimally.`):
print(`For example, try:`):
print(`BestStake(11/20,5,10,6);`):

elif nops([args])=1 and op(1,[args])=BestStrat then
print(`BestStrat(p,N,T): The best strategy with prob. of one round being`):
print(`p, exit capital N, and T rounds available`):
print(`For example, try:`):
print(`BestStrat(3/5,20,10);`):

elif nops([args])=1 and op(1,[args])=BestStratStory then
print(`BestStratStory(m0,N0,T0,K): All the Best strategies`):
print(`for various, probabilities (starting at (m0+1)/(2*m0)`):
print(`until 1-1/(2*m0)), various exit capitals, from N0`):
print(`to N0*K and various deadlines, from T0 to T0*K`):
print(`For example, try:`):
print(`BestStratStory(10,10,5,3);`):

elif nops([args])=1 and op(1,[args])=BoS then
print(`BoS(N): The Bold strategy when you exist with N dollars.`):
print(`For example, try:`):
print(`BoS(100);`):


elif nops([args])=1 and op(1,[args])=BreimanContestStory then
print(`BreimanContestStory(p,N,f,h,ConfL): The stories of`):
print(`the winners in the Breiman contest (with prob. p)`):
print(`and Kelly factor f, to minimize the expected`):
print(`duration if you want a prob. of winning for various`):
print(`starting capitals and various confidence levels ConfL`):
print(`h is the resolution`):
print(`For example, try:`):
print(`BreimanContestStory(3/5,100,1/5,1/10,[999/1000,99/100,9/10]): `):

elif nops([args])=1 and op(1,[args])=BreimanContestx then
print(`BreimanContestx(p,N,x,f,h,conf): The best Breiman `):
print(`bolding-modification to the Kelly strategy with factor f`):
print(`that minimizes the expected duration`):
print(`if you currently have x*N dollars in a game with  a loaded coin`):
print(`of prob. p, and the prob. of ultimately winning (with N dollars)`):
print(`is at least conf.`):
print(`with resolution h, starting at h.`):
print(`For example, try: `):
print(`BreimanContestx(3/5,100,1/2,1/5,1/10,98/100);`):

elif nops([args])=1 and op(1,[args])=BreimanProfile then
print(`BreimanProfile(p,N,x,f,h): The scores, Prob. of winning`):
print(`with goal N, and initial capital x`):
print(`followed by expected duration for Kelly strategy with factor f`):
print(`for various boldness-cut-offs, with resolution h`):
print(`For example, try: `):
print(`BreimanProfile(3/5,100,1/2,1/5,1/10);`):

elif nops([args])=1 and op(1,[args])=BrS then
print(`BrS(N,f,c): The Breiman strategy with factor f`):
print(`and parameter c (bet to N if your capital is more than Nc`):
print(`For example, try:`):
print(`BrS(100,1/5,9/10);`):


elif nops([args])=1 and op(1,[args])=BstrN then
print(`BstrN(N,p): The strategy that maximizes the probability of`):
print(`winning if the chance of winning in a single toss is p`):
print(`for all inital capital in [0,N]`):
print(`For example, try:`):
print(`BstrN(6,2/5);`):

elif nops([args])=1 and op(1,[args])=BstrND then
print(`BstrND(N,p): The strategy that maximizes the probability of`):
print(`winning if the chance of winning in a single toss is p`):
print(`for all inital capital in [0,N], and gets there the soonest`):
print(`For example, try:`):
print(`BstrND(6,2/5);`):

elif nops([args])=1 and op(1,[args])=BstrNi then
print(`BstrNi(N,i,p): The strategy that maximizes the probability of`):
print(`winning if the chance of winning in a single toss is p`):
print(`and right now you have i dollars in a game in [0,N].`):
print(`For example, try:`):
print(`BstrNi(6,3,p);`):

elif nops([args])=1 and op(1,[args])=BstrNiD then
print(`BstrNiD(N,i,p): The strategy that maximizes the probability of`):
print(`winning if the chance of winning in a single toss is p`):
print(`and right now you have i dollars in a game in [0,N].`):
print(`and to break ties, gets there as soon as possible`):
print(`For example, try:`):
print(`BstrNiD(6,3,p);`):

elif nops([args])=1 and op(1,[args])=CheckBestStake then
print(`CheckBestStake(p,i,N,T,K): checks procedure BestStake(p,i,N,T)`):
print(`by running K games. For example try:`):
print(`CheckBestStake(3/5,10,20,10,100);`):

elif nops([args])=1 and op(1,[args])=CGRED then
print(`CGRED(p,n,N): `):
print(`The explicit formula for the expected duration`):
print(` for classical gambler's ruin in [0,N]`):
print(`starting at n with prob. of winning a dollar being p.`):
print(` For example, try:`):
print(`CGRED(p,n,N);`):

elif nops([args])=1 and op(1,[args])=CGREDw then
print(`CGREDw(p,n,N): `):
print(`The explicit formula for the expected duration`):
print(` for classical gambler's ruin with exit capital N dollars,`):
print(` conditioned on ultimately winning,`):
print(`starting at n dollars with prob. of winning a dollar being p.`):
print(` For example, try:`):
print(`CGREDw(p,n,N);`):

elif nops([args])=1 and op(1,[args])=CGRpgf then
print(`CGRpgf(p,n,N,t): The explicit formula for the prob. generating`):
print(`function (using the variable t) for classical gambler's ruin in [0,N]`):
print(` The coeff. of t^i `):
print(` is the probability of the game lasting exactly i moves, `):
print(` if the game lasts until the gambler has either 0 or N dollars `):
print(` and he currently has n dollars. `):
print(`The prob. of winning a dollar is p (and losing is 1-p)`):
print(` For example, try:`):
print(`CGRpgf(p,n,N,t);`):

elif nops([args])=1 and op(1,[args])=CGRpgfL then
print(`CGRpgfL(p,n,N,t): Assuming that it ultimately lost`):
print(`The explicit formula for the prob. generating`):
print(`function (using the variable t) for classical gambler's ruin in [0,N]`):
print(` The coeff. of t^i `):
print(` is the probability of the game lasting exactly i moves, `):
print(` if the game lasts until the gambler has either 0 or N dollars `):
print(` and he currently has n dollars. `):
print(`The prob. of winning a dollar is p (and losing is 1-p)`):
print(` For example, try:`):
print(`CGRpgfL(p,n,N,t);`):

elif nops([args])=1 and op(1,[args])=CGRpgfW then
print(`CGRpgfW(p,n,N,t): Assuming that it ultimately won`):
print(`The explicit formula for the prob. generating`):
print(`function (using the variable t) for classical gambler's ruin in [0,N]`):
print(` The coeff. of t^i `):
print(` is the probability of the game lasting exactly i moves, `):
print(` if the game lasts until the gambler has either 0 or N dollars `):
print(` and he currently has n dollars. `):
print(`The prob. of winning a dollar is p (and losing is 1-p)`):
print(` For example, try:`):
print(`CGRpgfW(p,n,N,t);`):

elif nops([args])=1 and op(1,[args])=CGRW then
print(`CGRW(p,n,N): `):
print(`The explicit formula for the prob. of winning`):
print(` for classical gambler's ruin in [0,N]`):
print(`starting at n with prob. of winning a dollar being p.`):
print(` For example, try:`):
print(`CGRW(p,n,N);`):


elif nops([args])=1 and op(1,[args])=DeltaPr then
print(`DeltaPr(p,S,i): The difference in the prob. vectors when the`):
print(`strategy S is made bolder by one dollar when`):
print(`you have i dollars, in a game where`):
print(`the prob. of winning a dollar is p and you play in [0,N]`):
print(`where N=nops(S)+1.`):
print(`If S[i]=min(i,N-i) it returns FAIL since it can't be made any bolder`):
print(`For example, try:`):
print(`DeltaPr(2/5,TS(5),2);`):

elif nops([args])=1 and op(1,[args])=Dpgf then
print(`Dpgf(p,BetS,t): The list of Duration`):
print(`probability generating functions in`):
print(`a gambling game with a loaded coin of probabity p`):
print(`where you exit either when you are broke with 0 dollars`):
print(`or won your goal of N dollars. Here N=nops(BetS)+1.`):
print(`The i-th entry of the`):
print(`output list is the probability generating function`):
print(`in the variable t, whose coeff. of t^j tells you`):
print(`the probability that the game would last exactly j `):
print(`more coin-tosses`):
print(`until exiting (either as loser, or hopefully, as a winner)`):
print(`if right now you have i dollars.`):
print(`For example, for conservative play (classical gambler's ruin)`):
print(`with your goal being 10 dollars,Try`):
print(`Dpgf(3/5,[1$9],t);`):
print(`For the Kelly strategy try:`):
print(`Dpgf(3/5,KS(10,1/5),t);`):

elif nops([args])=1 and op(1,[args])=DpgfL then
print(`DpgfL(p,BetS,t): Like Dpgf(p,N,BetS,t): `):
print(`but under the pessimistic assumption that the player`):
print(`loses eventually. `):
print(`For example, for conservative play (classical gambler's ruin)`):
print(`with your goal being 10 dollars, and prob. of a win is 3/5, try`):
print(`DpgfL(3/5,[1$9],t);`):
print(`For the Kelly strategy try:`):
print(`DpgfL(3/5,KS(10,1/5),t);`):

elif nops([args])=1 and op(1,[args])=DpgfW then
print(`DpgfW(p,BetS,t): Like Dpgf(p,BetS,t): `):
print(`but under the optimistic assumption that the player`):
print(`wins eventually. `):
print(`For example, for conservative play (classical gambler's ruin)`):
print(`with your goal being 10 dollars,and prob. of a win being 3/5, try`):
print(`DpgfW(3/5,[1$9],t);`):
print(`For the Kelly strategy try:`):
print(`DpgfW(3/5,KS(10,1/5),t);`):

elif nops([args])=1 and op(1,[args])=ED then
print(`ED(p,BetS): The list of Expected Duration until`):
print(`either losing, or (hopefully), winning`):
print(`in a gambling game with a loaded coin of probabity p`):
print(`where you exit either when you are broke with 0 dollars`):
print(`or won your goal of N (=nops(BetS)+1) `):
print(`or more dollars. The i-th entry of the`):
print(`output list is the expected duration of the game`):
print(`if you currently have i dollars. `):
print(`For example, for conservative play (classical gambler's ruin)`):
print(`with your goal being 10 dollars, try: `):
print(`ED(3/5,[1$9]); `):
print(`For the (discretization of the) Kelly strategy try:`):
print(`ED(3/5,KS(10,1/5));`):

elif nops([args])=1 and op(1,[args])=EDdd then
print(`EDdd(p,S,i,T): Given a strategy S, (with a casino with exit capital`):
print(`nops(S)+1, and prob. of winning a single round p, and an integer i`):
print(`between 1 and N-1`):
print(`computes the expected duration if the games ends either`):
print(`when the player has N dollars, or is broke, or the time is up`):
print(`i.e. T rounds have passed.`):
print(`if the current capital is i. For example, try:`):
print(`EDdd(1/2,[1,1,1],1,3);`):

elif nops([args])=1 and op(1,[args])=EDl then
print(`EDl(p,BetS): Like ED(p,N,BetS)`):
print(`but under the pessimistic assumption that the gambler`):
print(`lost the game.`):
print(`For example, for conservative play (classical gambler's ruin)`):
print(`with your goal being 10 dollars, try: `):
print(`EDl(3/5,[1$9]); `):
print(`For the (discretization of the) Kelly strategy try:`):
print(`EDl(3/5,KS(10,1/5));`):

elif nops([args])=1 and op(1,[args])=EDw then
print(`EDw(p,BetS): Like ED(p,N,BetS)`):
print(`but under the optimistic assumption that the gambler`):
print(`won the game`):
print(`For example, for conservative play (classical gambler's ruin)`):
print(`with your goal being 10 dollars, try: `):
print(`EDw(3/5,[1$9]); `):
print(`For the (discretization of the) Kelly strategy try:`):
print(`EDw(3/5,KS(10,1/5));`):

elif nops([args])=1 and op(1,[args])=FirstBetter then
print(`FirstBetter(p,S): given a strategy S, finds the`):
print(`first bolder strategy (going from left to right)`):
print(`For example, try:`):
print(`FirstBetter(2/5,TS(10));`):

elif nops([args])=1 and op(1,[args])=GB then
print(`GB(p,x0,BetS,K): simulates K betting games `):
print(`GB1(p,x0,BetS), where one plays until being ruined`):
print(`with 0 dollars, or getting the goal of N dollars, `):
print(`if right now the gambler's capital is x0, and at every round`):
print(`the prob. of winning the stake is p, and losing the stake is 1-p`):
print(`BetS describes the strategy. It is`):
print(` a list of length N-1 where BetS[i] is the stake`):
print(`if the current fortune is i .`):
print(`The output consists of two lists of length 3.`):
print(`The first list is the number of times`):
print(`it won, with the average and s.d. of`):
print(`the number of rounds to get there`):
print(`followed by the number of times it got ruined `):
print(`followed by the average and s.d. of `):
print(`the number of rounds to get there`):
print(`For example, for conservative play (classical gambler's ruin)`):
print(`try with 100 games, try:`):
print(`GB(3/5,50,[1$99],100);`):
print(`For the Kelly strategy try:`):
print(`GB(3/5,50,KS(100,1/5),100);`):

elif nops([args])=1 and op(1,[args])=GB1 then
print(`GB1(p,x0,BetS): simulates ONE betting game with`):
print(`GENERAL BETTING. You have a`):
print(`loaded coin whose probability of winning is p. You start`):
print(`with a capital of x0 dollars, using a betting strategy,`);
print(`given by the list of length N-1, BetS, where BetS[i]`):
print(`(that must he strictly less than i and N-i, of course)`):
print(`tells you how many dollars to bet if your current`):
print(`capital is i dollars. It keeps going until`):
print(`it either gets broke, with 0 dollars, or gets N dollars.`):
print(`it returns the final outcome (0 or N) followed by`):
print(`the number of rounds needed to reach it`):
print(`For example, with the loaded coin being 3/5 in favor,`):
print(`and you start with 5 dollars and your goal is 10 dollars`):
print(`and you use the TIMID strategy (the most conservative one), type:`):
print(`GB1(3/5,5,[1$9]);`):


elif nops([args])=1 and op(1,[args])=GreedyBest then
print(`GreedyBest(p,S): Keeps trying to find better`):
print(`stategies among neighbors in a greedy way`):
print(`until it FAILS or gets to a valley`):
print(`For example, try:`):
print(`GreedyBest(2/5,TS(10));`):

elif nops([args])=1 and op(1,[args])=GreedyBestD then
print(`GreedyBestD(p,S): Keeps trying to find better`):
print(`stategies among neighbors in a greedy way`):
print(`until it FAILS or gets to a valley.`):
print(`Also considers duration.`):
print(`For example, try:`):
print(`GreedyBestD(2/5,TS(10));`):

elif nops([args])=1 and op(1,[args])=GreedyBestN then
print(`GreedyBestN(p,S): tries to find, if possible`):
print(`a better strategy than S (with prob. p) among its`):
print(`neighbors. For example, try:`):
print(`GreedyBestN(2/5,TS(10));`):

elif nops([args])=1 and op(1,[args])=GreedyBestND then
print(`GreedyBestND(p,S): tries to find, if possible`):
print(`a better strategy than S (with prob. p) among its`):
print(`neighbors. Also considering duration.For example, try:`):
print(`GreedyBestND(2/5,TS(10));`):

elif nops([args])=1 and op(1,[args])=IsBetter then
print(`IsBetter(p,S1,S2): Given two strategies S1 and S2`):
print(`decides whether S1 is better than S2 for all initial`):
print(`capitals for probability p. `):
print(`(in the sense that the prob. of ultimate win is always >=0`):
print(`for any initial capital`):
print(`For example, try:`):
print(`IsBetter(2/5,TS(5),BoS(5));`):

elif nops([args])=1 and op(1,[args])=IsBetterD then
print(`IsBetterD(p,S1,S2): Given two strategies S1 and S2`):
print(`decides whether S1 is better than S2 for all initial`):
print(`capitals for probability p. `):
print(`(in the sense that the prob. of ultimate win is always >=0`):
print(`for any initial capital`):
print(`AND if it is the same, then is faster to get there`):
print(`For example, try:`):
print(`IsBetterD(2/5,TS(5),BoS(5));`):


elif nops([args])=1 and op(1,[args])=IsOptimal then
print(`IsOptimal(p,S): checks whether strategy S is optimal`):
print(`with prob. of winning a stake being p. For example, try:`):
print(`IsOptimal(2/5,BoS(10));`):

elif nops([args])=1 and op(1,[args])=IsOptimalSubFair then
print(`IsOptimalSubFair(S): checks whether strategy S is optimal`):
print(`when the prob. is <=1/2 for `):
print(`symbolic p For example, try:`):
print(`IsOptimalSubFair(BoS(10));`):

elif nops([args])=1 and op(1,[args])=IsOptimalSuperFair then
print(`IsOptimalSuperFair(S): checks whether strategy S is optimal`):
print(`when the prob. is >=1/2 for `):
print(`symbolic p For example, try:`):
print(`IsOptimalSuperFair(TS(10));`):

elif nops([args])=1 and op(1,[args])=IsValidStrat then
print(`IsValidStrat(L,N): Given a list describing a gambling strategy,`):
print(`verifies that it is legal. For example, try:`):
print(`IsValidStrat([1,-1,3],4);`):

elif nops([args])=1 and op(1,[args])=KellyContestStory then
print(`KellyContestStory(p,N,h,ConfL): The stories of`):
print(`the winners in the Kelly contest (with prob. p)`):
print(`to minimize the expected`):
print(`duration if you want a prob. of winning for various`):
print(`starting capitals and various confidence levels `):
print(`(9/10,99/100, and 999/1000)`):
print(`h is the resolution and `):
print(`For example, try:`):
print(`KellyContestStory(3/5,100,1/10,[99/100,9/10]): `):

elif nops([args])=1 and op(1,[args])=KellyContestStoryWB then
print(`KellyContestStoryWB(p,N,h,ConfL): The stories of`):
print(`the winners in the Kelly contest (with prob. p)`):
print(`(also finding Breiman tweakings)`):
print(`to minimize the expected`):
print(`duration if you want a prob. of winning for various`):
print(`starting capitals and various confidence levels `):
print(`(9/10,99/100, and 999/1000)`):
print(`h is the resolution and `):
print(`For example, try:`):
print(`KellyContestStoryWB(3/5,100,1/10,[99/100,9/10]): `):

elif nops([args])=1 and op(1,[args])=KellyContestx then
print(`KellyContestx(p,N,x,h,conf): The best factor f in the`):
print(`Kelly strategy that minimizes the expected duration`):
print(`if you currently have x*N dollars in a game with  a loaded coin`):
print(`of prob. p, and the prob. of winning is at least conf.`):
print(`with resolution h, starting at h`):
print(`For example, try: `):
print(`KellyContestx(3/5,100,1/2,1/20,99/100);`):

elif nops([args])=1 and op(1,[args])=KellyProfile then
print(`KellyProfile(p,N,x,h): The list of triples`):
print(` [f,ProbOfWinning,ExpectedTimeToWin] for Kelly factors `):
print(` starting at 0 (timid strategy)`):
print(` with resolution h, if the prob. of winning`):
print(` any given round is p, the exist capital is N, and your initial `):
print(` capital is N*x .`):
print(` For example, try: `):
print(` KellyProfile(3/5,100,1/2,1/20); `):

elif nops([args])=1 and op(1,[args])=KellyProfileDD then
print(`KellyProfileDD(p,N,i,T,h): `):
print(`The list [f,ProbabilityOfWinning, ExpectedDuration]`):
print(`if you must win N dollars in <=T rounds, and your initial `):
print(`capital is i for all Kelly factors`):
print(`f from 0 (timid) to f=1 (bold) with resolution h.`):
print(`For example, try:`):
print(`KellyProfileDD(3/5,100,50,40,1/10);`):

elif nops([args])=1 and op(1,[args])=KellyProfileStory then
print(`KellyProfileStory(p,N,h,M): The stories of`):
print(`the Kelly profiles (with prob. p), exit capital N,`):
print(`resolution h, and various starting capitals (with resolution N/M)`):
print(`starting with N/2. For example, try:`):
print(`KellyProfileStory(3/5,100,1/10,10): `):

elif nops([args])=1 and op(1,[args])=KS then
print(`KS(N,f): The Kelly strategy with factor f`):
print(`For example, try:`):
print(`KS(100,1/5);`):

elif nops([args])=1 and op(1,[args])=LC then
print(`LC(p): inputs a rational number p and outputs`):
print(`1 with prob. p and 0 with prob. 1-p. For example`):
print(`try LC(3/5):`):

elif nops([args])=1 and op(1,[args])=OM1 then
print(`OM1(S,i): adds one dollar to the strategy S, if`):
print(`possible, or returns FAIL`):
print(`For example, try:`):
print(`OM1([1,1,1],1);`):

elif nops([args])=1 and op(1,[args])=plotDist then
print(`plotDist(f,x,K1,K2): Given a prob. gen. function f(x) that has a `):
print(`Taylor series for a discrete r.v.`):
print(`plots its normalized version (X-mu)/sig between mu-K1*sig and`):
print(`mu+K2*sig, For example, try:`):
print(`plotDist((1+x)^40,x,5,5);`):

elif nops([args])=1 and op(1,[args])=plotED then
print(`plotED(p,S): A plot of the expected life as a function of`):
print(`the initial capital with strategy S and prob. p, `):
print(`normalized so that`):
print(`the exit capital is 1. For example, try:`):
print(`plotED(p,S):`):

elif nops([args])=1 and op(1,[args])=plotEDw then
print(`plotEDw(p,S): A plot of the expected life until winning`):
print(`if this is the case, as a function of`):
print(`the initial capital with strategy S and prob. p, `):
print(`normalized so that`):
print(`the exit capital is 1. For example, try:`):
print(`plotEDw(p,S):`):

elif nops([args])=1 and op(1,[args])=plotPrW then
print(`plotPrW(p,S): A plot of the prob. of winning as a function`):
print(`of the initial capital with strategy S and prob. p, `):
print(`normalized so that`):
print(`the exit capital is 1. For example, try:`):
print(`plotPrW(p,S):`):

elif nops([args])=1 and op(1,[args])=PrL then
print(`PrL(p,BetS): The list of probabilities of losing in`):
print(`a gambling game with a loaded coin of probabity p`):
print(`where you exit either when you are broke with 0 dollars`):
print(`or won your goal of N dollars (N=nops(BetS)+1). The i-th entry of the`):
print(`output list is your probability of ultimately losing`):
print(`if right now you have i dollars.`):
print(`For example, for conservative play (classical gambler's ruin)`):
print(`with your goal being 10 dollars, try: `):
print(`PrL(3/5,[1$9]); `):
print(`For the (discretization of the) Kelly strategy try:`):
print(`PrL(3/5,KS(10,1/5));`):

elif nops([args])=1 and op(1,[args])=PrW then
print(`PrW(p,BetS): The list of probabilities of winning in`):
print(`a gambling game with a loaded coin of probabity p`):
print(`where you exit either when you are broke with 0 dollars`):
print(`or won your goal of N dollars. `):
print(`where N is the length of BetS plus one. `):
print(`The i-th entry of the`):
print(`output list is your probability of ultimately winning`):
print(`if right now you have i dollars.`):
print(`For example, for conservative play (classical gambler's ruin)`):
print(`with your goal being 10 dollars, try: `):
print(`PrW(3/5,[1$9]); `):
print(`For the (discretization of the) Kelly strategy try:`):
print(`PrW(3/5,KS(10,1/5));`):


elif nops([args])=1 and op(1,[args])=PrWdd then
print(`PrWdd(p,S,i,T): Given a strategy S, (with a casino with exit capital`):
print(`nops(S)+1), and prob. of winning a single round p, and an integer i`):
print(`between 1 and N-1`):
print(`computes the probability of winning in <=T rounds`):
print(`if the current capital is i. For example, try:`):
print(`PrWdd(1/2,[1,1,1],1,3);`):

elif nops([args])=1 and op(1,[args])=RandPrDS then
print(`RandPrDS(p,N,K): verifies empirically that K randomly`):
print(`chosen strategies in a game in [0,N] with prob. p`):
print(`are all worse than the bold strategy.`):
print(`For example, try:`):
print(`RandPrDS(2/5,40,10);`):

elif nops([args])=1 and op(1,[args])=RS then
print(`RS(N): a random strategy when the cap is N dollars`):
print(`For example, try:`):
print(`RS(10);`):

elif nops([args])=1 and op(1,[args])=SimulateBS then
print(`SimulateBS(p,i,N,T): Terse version`):
print(`Simulates one GAME, using the`):
print(`optimal strategy suggested by BestStake(p,j,N,T)`):
print(`where the probability of winning one round is p,`):
print(`you currently have i dollars, the exit capital is N`):
print(`and you must finish by T rounds,  or else you would`):
print(`be executed.`):
print(`Returns 1 if succesful (alive), 0 if not (dead)`):
print(` For example, try:`):
print(`SimulateBS(3/5,5,10,10);`):

elif nops([args])=1 and op(1,[args])=SimulateBSv then
print(`SimulateBSv(p,i,N,T): Verbose version`):
print(`Simulates one GAME, using the`):
print(`optimal strategy suggested by BestStake(p,j,N,T)`):
print(`where the probability of winning one round is p,`):
print(`you currently have i dollars, the exit capital is N`):
print(`and you must finish by T rounds,  or else you would`):
print(`be executed. For example, try:`):
print(`SimulateBSv(3/5,5,10,10);`):

elif nops([args])=1 and op(1,[args])=Skhenim then
print(`Skhenim(S): all the legal neighbors of a strategy S. For`):
print(`example, try: `):
print(`Skhenim(TS(4));`):

elif nops([args])=1 and op(1,[args])=TestBH then
print(`TestBH(p,N): Tests the hypothesis that for every strategy`):
print(`except the boldest you can make it better by making it bolder`):
print(`in one place for ALL strategies in [0,N] and subfair prob. p`):
print(`For example, try: TestBH(2/5,6);`):

elif nops([args])=1 and op(1,[args])=TestBHrand then
print(`TestBHrand(p,N,K): Tests the hypothesis that for every strategy`):
print(`except the boldest you can make it better by making it bolder`):
print(`in one place for K random strategies in [0,N] and subfair prob. p`):
print(`For example, try: TestBHrand(2/5,10,5);`):

elif nops([args])=1 and op(1,[args])=TS then
print(`TS(N): The timid strategy when the cap is N dollars`):
print(`always playing the minimum, 1 dollar`):
print(`For example, try:`):
print(`TS(10);`):

elif nops([args])=1 and op(1,[args])=Vecs then
print(`Vecs(L): all the vectors v[i] such that 1<=v[i]<=L[i]`):
print(`For example, try:`):
print(`Vecs([2,3,2]);`):


else
print(`There is no ezra for`,args):
fi:
 
end:


#LC(p): inputs a rational number p and outputs
#1 with prob. p and 0 with prob. 1-p. For example
#try LC(3/5):
LC:=proc(p) local N,D,ra,mu:
N:=numer(p):
D:=denom(p):
ra:=rand(1..D):
mu:=ra():
if mu<=N then
 RETURN(1):
else
  RETURN(0):
fi:
end:


#GB1(p,x0,BetS): simulates ONE betting game with
#GENERAL BETTING. You have
#loaded coin p (prob. of winning being p), starting
#with a capital of x0 dollars, using betting strategy
#given by the list of length N-1, BetS, where BetS[i]
#(that must he strictly less than i, of course)
#tells you how many dollars to bet on if you current
#capital is i dollars. It keeps going until
#it either gets broke, with 0 dollars, or gets >=N dollars
#For example, with the loaded coin being 3/5 in favor,
#and you start with 5 dollars and your goal is 10 dollars
#and with the most conservative strategy, 
#it returns the final outcome (0 or N) followed by
#the number of rounds needed to reach it
#For example, try:
#GB1(3/5,5,[1$9]);
GB1:=proc(p,x0,BetS) local N,gu,x,lu,co:

N:=nops(BetS)+1:
if not (type(N,integer) and type(x0,integer) and N>=1 and x0<N and x0>0
and IsValidStrat(BetS,N)) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

x:=x0:
co:=0:
while x>0 and x<N do
lu:=BetS[x]:
gu:=LC(p):
co:=co+1:
if gu=1 then
 x:=x+lu:
else
 x:=x-lu:
fi:
od:
[x,co]:
end:


#GB(p,x0,BetS,K): simulates K betting games 
#GB1(p,x0,BetS), returns, the number of times
#it got broke, with the average and s.d. of
#the number of rounds to get there
#and the number of times it ended a winner of N dollars
#followed by the average and s.d. of 
#the number of rounds to get there
#For example, for conservative play (classical gambler's ruin)
#try with 100 games, try:
#GB(3/5,50,[1$99],100);
#For the Kelly strategy try:
#GB(3/5,50,KS(100,1/5),100);
GB:=proc(p,x0,BetS,K) local N,guW,guL,i,lu,aveL,aveW,sdW,sdL:

N:=nops(BetS)+1:
if not (type(N,integer) and type(x0,integer) and N>=1 and x0<N and x0>0
and IsValidStrat(BetS,N)) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

guW:=[]:
guL:=[]:
for i from 1 to K do
lu:=GB1(p,x0,BetS):

if lu[1]=0 then
 guL:=[op(guL),lu[2]]:
else
 guW:=[op(guW),lu[2]]:
fi:
od:

if nops(guL)=0 then 
aveL:=0: sdL:=0:
else
aveL:=convert(guL,`+`)/nops(guL):
sdL:=sqrt(add((guL[i]-aveL)^2,i=1..nops(guL))/nops(guL)):
fi:

if nops(guW)=0 then 
aveW:=0: sdW:=0:
else
aveW:=convert(guW,`+`)/nops(guW):
sdW:=sqrt(add((guW[i]-aveL)^2,i=1..nops(guW))/nops(guW)):
fi:


evalf([nops(guW),aveW,sdW]),evalf([nops(guL),aveL,sdL]):

end:



#PrL(p,BetS): The list of probabilities of losing in
#a gambling game with a loaded coin of probabity p
#where you exit either when you are broke with 0 dollars
#or won your goal of N dollars. The i-th entry of the
#output list is your probability of ultimately losing
#if right now you have i dollars.
#For example, for conservative play (classical gambler's ruin)
#with your goal being 10 dollars,
#Try
#PrL(3/5,[1$9]);
#For the Kelly strategy try:
#PrL(3/5,KS(10,1/5));
PrL:=proc(p,BetS) local eq,var,x,i,N:
N:=nops(BetS)+1:
if not IsValidStrat(BetS,N) then
 RETURN(FAIL):
fi:


var:={seq(x[i],i=0..N)}:
eq:={x[0]=1,x[N]=0}:
eq:=eq union {seq(x[i]-p*x[i+BetS[i]]-(1-p)*x[i-BetS[i]],i=1..N-1)}:
var:=solve(eq,var):
[seq(subs(var,x[i]),i=1..N-1)]:
end: 

#PrW(p,BetS): The list of probabilities of winning in
#a gambling game with a loaded coin of probabity p
#where you exit either when you are broke with 0 dollars
#or won your goal of N dollars (N=nops(BetS)+1). The i-th entry of the
#output list is your probability of ultimately winning
#if right now you have i dollars.
#For example, for conservative play (classical gambler's ruin)
#with your goal being 10 dollars,
#Try
#PrW(3/5,[1$9]);
#For the Kelly strategy try:
#PrW(3/5,KS(10,1/5));
PrW:=proc(p,BetS) local eq,var,x,i,N:
option remember:
N:=nops(BetS)+1:
if not IsValidStrat(BetS,N) then
 RETURN(FAIL):
fi:


var:={seq(x[i],i=0..N)}:
eq:={x[0]=0,x[N]=1}:
eq:=eq union {seq(x[i]-p*x[i+BetS[i]]-(1-p)*x[i-BetS[i]],i=1..N-1)}:
var:=solve(eq,var):
[seq(subs(var,x[i]),i=1..N-1)]:
end: 



#ED(p,BetS): The list of Expected Duration of 
#a gambling game with a loaded coin of probabity p
#where you exit either when you are broke with 0 dollars
#or won your goal of N dollars. The i-th entry of the
#output list is the expected number of rounds lefts
#until exiting (either as loser, or hopefully, as a winner)
#if right now you have i dollars.
#For example, for conservative play (classical gambler's ruin)
#with your goal being 10 dollars,
#Try
#ED(3/5,[1$9]);
#For the Kelly strategy try:
#ED(3/5,KS(10,1/5));
ED:=proc(p,BetS) local eq,var,x,i,N:
option remember:
N:=nops(BetS)+1:

if not IsValidStrat(BetS,N) then
 RETURN(FAIL):
fi:

var:={seq(x[i],i=0..N)}:
eq:={x[0]=0,x[N]=0}:
eq:=eq union {seq(x[i]-p*x[i+BetS[i]]-(1-p)*x[i-BetS[i]]-1,i=1..N-1)}:
var:=solve(eq,var):
[seq(subs(var,x[i]),i=1..N-1)]:
end: 


#KS(N,f): The Kelly strategy with factor f
#For example, try:
#KS(100,1/5);
KS:=proc(N,f) local i:
[seq(min(trunc(f*i)+1,N-i,i),i=1..N-1)]:
end:

#KellyContestx(p,N,x,h,conf): The best factor f in the
#Kelly strategy that minimizes the expected duration
#if you currently have x*N dollars in a game with  a loaded coin
#of prob. p, and the prob. of winning is at least conf.
#with resolution h, starting at h
#For example, try: 
#KellyContestx(3/5,100,1/2,1/20,99/100);
KellyContestx:=proc(p,N,x,h,conf) local aluf, gu,j,f,si,halev:
if not type(N*x,integer) then
   print(`N times x should be an integer`):
  RETURN(FAIL):
fi:

aluf:=h:
gu:=KS(N,h):


if PrW(p,gu)[x*N]<conf then
 print(`conf is too high`):
 RETURN(FAIL):
fi:

si:=EDw(p,gu)[x*N]:



for j from 1  do
f:=h+j*h:
gu:=KS(N,f):
if PrW(p,gu)[x*N]<conf then
 RETURN([aluf,evalf(si)]):
else
 halev:=EDw(p,gu)[x*N]:
 if halev<si then
   aluf:=f:
    si:=halev:
 fi:
fi:
od:   

end:


#BrS(N,f,c): The Breiman strategy with factor f
#and c
#For example, try:
#BrS(100,1/5,1/2);
BrS:=proc(N,f,c) local i:
if c>=1 then
[seq(min(N-i,i,trunc(f*i)+1),i=1..N-1)]:
else
[seq(min(trunc(f*i)+1,N-i,i),i=1..trunc(N*c)), seq(min(i,N-i),i=trunc(N*c)+1..N-1)]:
fi:
end:


#TS(N): The timid strategy 
#For example, try:
#TS(100);
TS:=proc(N): [1$(N-1)]: end:

#BoS(N): The Bold strategy 
#For example, try:
#BoS(100);
BoS:=proc(N) local i: 
[seq(min(i,N-i),i=1..N-1)]: end:


#RS(N): A random strategy with N dollars cap
#For example, try:
#RS(100);
RS:=proc(N) local i: 
[seq(rand(1..min(i,N-i))(),i=1..N-1)]: end:

#Dpgf(p,BetS,t): The list of Duration
#probability generating functions in
#a gambling game with a loaded coin of probabity p
#where you exit either when you are broke with 0 dollars
#or won your goal of N dollars. The i-th entry of the
#output list is the probability generating function
#in the variable t, whose coeff. of t^j tells you
#the probability that the game would last exactly j 
#more coin-tosses
#until exiting (either as loser, or hopefully, as a winner)
#if right now you have i dollars.
#For example, for conservative play (classical gambler's ruin)
#with your goal being 10 dollars,Try
#Dpgf(3/5,[1$9],t);
#For the Kelly strategy try:
#Dpgf(3/5,KS(10,1/5),t);
Dpgf:=proc(p,BetS,t) local eq,var,x,i,N:
option remember:
N:=nops(BetS)+1:
if not IsValidStrat(BetS,N) then
 RETURN(FAIL):
fi:
var:={seq(x[i],i=0..N)}:
eq:={x[0]=1,x[N]=1}:
eq:=eq union {seq(x[i]-p*t*x[i+BetS[i]]-(1-p)*t*x[i-BetS[i]],i=1..N-1)}:
var:=solve(eq,var):
[seq(subs(var,x[i]),i=1..N-1)]:
end: 

#plotDist(f,x,K1,K2): Given a prob. gen. function f(x) that has a 
#Taylor series
#for a discrete r.v.
#plots its normalized version (X-mu)/sig between mu-K1*sig and
#mu+K2*sig
#For example, try:
#plotDist((1+x)^40,x,5,5);
plotDist:=proc(f,x,K1,K2) local mu,f1,lu,gu,sig,i,j1:
f1:=f/subs(x=1,f):
mu:=subs(x=1,diff(f1,x)):
gu:=f1/x^mu:
sig:=sqrt(subs(x=1,x*diff(x*diff(gu,x),x))):

lu:=taylor(f1,x=0,trunc(mu)+K2*trunc(sig)+10):

lu:=[seq([i,coeff(lu,x,i)],i=max(0,trunc(mu-K1*sig))..trunc(mu+K2*sig))]:

lu:=evalf([seq([(lu[j1][1]-mu)/sig,lu[j1][2]*sig],j1=1..nops(lu))]):

plot(lu,scaling=constrained):

end:


#AveAndMoms(f,x,N): Given a probability generating function
#f(x) (a polynomial, rational function and possibly beyond)
#returns a list whose first entry is the average 
#(alias expectation, alias mean)
#followed by the variance, the third moment (about the mean) and
#so on, until the N-th moment (about the mean).
#If f(1) is not 1, than it first normalizes it by dividing
#by f(1) (if it is not 0) .
#For example, try:
#AveAndMoms(((1+x)/2)^100,x,4);

AveAndMoms:=proc(f,x,N) local mu,F,memu1,gu,i:
mu:=simplify(subs(x=1,f)):

if mu=0 then
print(f, `is neither a prob. generating function nor can it be made so`):
RETURN(FAIL):
fi:

F:=f/mu:


memu1:=simplify(subs(x=1,diff(F,x))):

gu:=[memu1]:

F:=F/x^memu1:

F:=x*diff(F,x):
for i from 2 to N do
 F:=x*diff(F,x):
 gu:=[op(gu),simplify(subs(x=1,F))]:
od:

gu:

end:



#DpgfW(p,BetS,t): The list of Duration
#probability generating functions in
#a gambling game with a loaded coin of probabity p
#where you exit either when you are broke with 0 dollars
#or won your goal of N dollars. Conditioned on the fact that you won.
#The i-th entry of the
#output list is the probability generating function
#in the variable t, whose coeff. of t^j tells you
#the probability that the game would last exactly j 
#more coin-tosses (assuming that you eventually won)
#until exiting (as a winner)
#if right now you have i dollars.
#For example, for conservative play (classical gambler's ruin)
#with your goal being 10 dollars,Try
#DpgfW(3/5,[1$9],t);
#For the Kelly strategy try:
#DpgfW(3/5,KS(10,1/5),t);
DpgfW:=proc(p,BetS,t) local N,eq,var,x,i:
option remember:
N:=nops(BetS)+1:

if not IsValidStrat(BetS,N) then
 RETURN(FAIL):
fi:

var:={seq(x[i],i=0..N)}:
eq:={x[0]=0,x[N]=1}:
eq:=eq union {seq(x[i]-p*t*x[i+BetS[i]]-(1-p)*t*x[i-BetS[i]],i=1..N-1)}:
var:=solve(eq,var):
[seq(subs(var,x[i]),i=1..N-1)]:
end: 

#DpgfL(p,BetS,t): The list of Duration
#probability generating functions in
#a gambling game with a loaded coin of probabity p
#where you exit either when you are broke with 0 dollars
#or won your goal of N dollars. Conditioned on the fact that you lost.
#The i-th entry of the
#output list is the probability generating function
#in the variable t, whose coeff. of t^j tells you
#the probability that the game would last exactly j 
#more coin-tosses (assuming that you eventually lost)
#until exiting (as a loser)
#if right now you have i dollars.
#For example, for conservative play (classical gambler's ruin)
#with your goal being 10 dollars,Try
#DpgfL(3/5,[1$9],t);
#For the Kelly strategy try:
#DpgfL(3/5,KS(10,1/5),t);
DpgfL:=proc(p,BetS,t) local N,eq,var,x,i:
N:=nops(BetS)+1:

if not IsValidStrat(BetS,N) then
 RETURN(FAIL):
fi:

var:={seq(x[i],i=0..N)}:
eq:={x[0]=1,x[N]=0}:
eq:=eq union {seq(x[i]-p*t*x[i+BetS[i]]-(1-p)*t*x[i-BetS[i]],i=1..N-1)}:
var:=solve(eq,var):
[seq(subs(var,x[i]),i=1..N-1)]:
end: 



#EDl(p,BetS): Like ED(p,N,BetS), but assuming that
#the gambler ultimately loses
#For example, for conservative play (classical gambler's ruin)
#with your goal being 10 dollars,
#Try
#EDl(3/5,[1$9]);
#For the Kelly strategy try:
#EDl(3/5,KS(10,1/5));
EDl:=proc(p,BetS) local eq,var,x,i,m,lu,N:
N:=nops(BetS)+1:

if not IsValidStrat(BetS,N) then
 RETURN(FAIL):
fi:

lu:=PrL(p,BetS):
m:=max(seq(i+BetS[i],i=1..N-1)):
var:={seq(x[i],i=0..N+m)}:
eq:={x[0]=0,seq(x[i]=0,i=N..N+m)}:
eq:=eq union {seq(x[i]-p*x[i+BetS[i]]-(1-p)*x[i-BetS[i]]-lu[i],i=1..N-1)}:
var:=solve(eq,var):
[seq(subs(var,x[i])/lu[i],i=1..N-1)]:
end: 

#EDw(p,BetS): Like ED(p,N,BetS), but assuming that
#the gambler ultimately wins
#For example, for conservative play (classical gambler's ruin)
#with your goal being 10 dollars,
#Try
#EDw(3/5,[1$9]);
#For the Kelly strategy try:
#EDw(3/5,KS(10,1/5));
EDw:=proc(p,BetS) local eq,var,x,i,lu,N:
option remember:
N:=nops(BetS)+1:
if not IsValidStrat(BetS,N) then
 RETURN(FAIL):
fi:

lu:=PrW(p,BetS):

var:={seq(x[i],i=0..N)}:
eq:={x[0]=0,x[N]=0}:
eq:=eq union {seq(x[i]-p*x[i+BetS[i]]-(1-p)*x[i-BetS[i]]-lu[i],i=1..N-1)}:
var:=solve(eq,var):
[seq(subs(var,x[i])/lu[i],i=1..N-1)]:
end: 

#CGRpgf(p,n,N,t): The explicit formula for the prob. generating
#function (using the variable t) for classical gambler's ruin in [0,N]
#starting at n with prob. p of winning. The coeff. of t^i
#is the probability of the game lasting exactly i moves,
#if the game lasts until the gambler has either 0 or N dollars
#and he currently has n dollars.
#For example, try:
#CGRpgf(p,n,N,t);
CGRpgf:=proc(p,n,N,t) local a,b,lu,q,A,B,var:
option remember:
q:=1-p:
lu:=solve(1-q*t/a-p*t*a,a);
a:=lu[1]: b:=lu[2]:
var:=solve({1=A+B,1=A*a^N+B*b^N},{A,B}):
A:=subs(var,A):
B:=subs(var,B):
A*a^n+B*b^n:
end:


#CGRW(p,n,N,t): The explicit formula for the prob. of winning
#for classical gambler's ruin in [0,N]
#starting at n with prob. p of winning a dollar, until getting
#broke or exiting with N dollars.
#For example, try:
#CGRW(p,n,N,t);
CGRW:=proc(p,n,N) local a,b,lu,q,A,B,var:
option remember:
q:=1-p:
lu:=solve(1-q/a-p*a,a);
a:=lu[1]: b:=lu[2]:
var:=solve({0=A+B,1=A*a^N+B*b^N},{A,B}):
A:=subs(var,A):
B:=subs(var,B):
A*a^n+B*b^n:
end:

#CGRED(p,n,N,t): The explicit formula for the expected duration
#for classical gambler's ruin in [0,N]
#starting at n with prob. p of winning a dollar, until getting
#broke or exiting with N dollars.
#For example, try:
#CGRED(p,n,N,t);
CGRED:=proc(p,n,N) local gu,t:
gu:=CGRpgf(p,n,N,t):
simplify(subs(t=1,diff(gu,t))):
end:

#CGREDw(p,n,N,t): The explicit formula for the expected duration
#for classical gambler's ruin in [0,N], if it ultimately won
#starting at n with prob. p of winning a dollar, until getting
#broke or exiting with N dollars.
#For example, try:
#CGREDw(p,n,N,t);
CGREDw:=proc(p,n,N) local gu,t:
option remember:
gu:=CGRpgfW(p,n,N,t):
simplify(subs(t=1,diff(gu,t))/subs(t=1,gu)):
end:


#CGRpgfL(p,n,N,t): The explicit formula for the prob. generating
#function (using the variable t) for classical gambler's ruin in [0,N]
#starting at n with prob. p of winning. The coeff. of t^i
#is the probability of the game lasting exactly i moves,
#if the game lasts until the gambler has either 0 or N dollars
#and he currently has n dollars, assuming that it was ultimately losing
#For example, try:
#CGRpgfL(p,n,N,t);
CGRpgfL:=proc(p,n,N,t) local a,b,lu,q,A,B,var:
q:=1-p:
lu:=solve(1-q*t/a-p*t*a,a);
a:=lu[1]: b:=lu[2]:
var:=solve({1=A+B,0=A*a^N+B*b^N},{A,B}):
A:=subs(var,A):
B:=subs(var,B):
A*a^n+B*b^n:
end:

#CGRpgfW(p,n,N,t): The explicit formula for the prob. generating
#function (using the variable t) for classical gambler's ruin in [0,N]
#starting at n with prob. p of winning. The coeff. of t^i
#is the probability of the game lasting exactly i moves,
#if the game lasts until the gambler has either 0 or N dollars
#and he currently has n dollars, assuming that it was ultimately winning
#For example, try:
#CGRpgfW(p,n,N,t);
CGRpgfW:=proc(p,n,N,t) local a,b,lu,q,A,B,var:
q:=1-p:
lu:=solve(1-q*t/a-p*t*a,a);
a:=lu[1]: b:=lu[2]:
var:=solve({0=A+B,1=A*a^N+B*b^N},{A,B}):
A:=subs(var,A):
B:=subs(var,B):
A*a^n+B*b^n:
end:


#AveAndNorMoms(f,x,N): See ezra
AveAndNorMoms:=proc(f,x,N) local lu,i:
lu:=AveAndMoms(f,x,N):
evalf([lu[1],lu[2],seq(lu[i]/lu[2]^(i/2),i=3..nops(lu))]):
end:






#IsValidStrat(L,N): Given a list describing a gambling strategy,
#verifies that it is legal. For example, try:
#IsValidStrat([1,-1,3],4);
IsValidStrat:=proc(L,N) local i:
if not type(N,integer) or N<1 then
RETURN(false):
fi:

if not type(L,list) then
 RETURN(false):
fi:

if nops(L)<>N-1 then
RETURN(false):
fi:
if {seq(type(L[i],integer),i=1..N-1)}<>{true} then
    RETURN(false):
fi:
if {seq(evalb(L[i]>=0),i=1..N-1)}<>{true} then
    RETURN(false):
fi:

if {seq(evalb(L[i]<=i),i=1..N-1)}<>{true} then
    RETURN(false):
fi:

if {seq(evalb(L[i]<=N-i),i=1..N-1)}<>{true} then
    RETURN(false):
fi:

true:
end:


#BdokED(p,BetS): checks the consistency of ED, EDw, EDl
#PrW, PrL, for the strategy BetS. For example, try:
#BdokED(3/5,[1$9]);
BdokED:=proc(p,BetS) local gu,guW,guL,muW,muL,i,N:
N:=nops(BetS)+1:
gu:=ED(p,BetS):
guW:=EDw(p,BetS):
guL:=EDl(p,BetS):
muW:=PrW(p,BetS):
muL:=PrL(p,BetS):

evalb({seq(guW[i]*muW[i]+guL[i]*muL[i]-gu[i],i=1..N-1)}={0}):
end:


#BdokGB(p,x0,BetS,K): checks the simulation program
#GB(p,x0,BetS,K) against the exact prediction;
BdokGB:=proc(p,x0,BetS,K) local N,gu,guW,guL,muW,lu:
N:=nops(BetS)+1:
if not (type(N,integer) and N>=1) then
print(`N must be a positive integer`):
 RETURN(FAIL):
fi:

if not (type(p, numeric)  and p>=0 and p<=1) then
 print(`p must be a number between 0 and 1`):
 RETURN(FAIL):
fi:

if not (type(x0,integer) and 1<=x0 and x0<=N) then
print(`x0 must be an integer between 1 and N`):
 RETURN(FAIL):
fi:

if not IsValidStrat(BetS,N) then
 print(BetS, `is not a valid strategy`):
 RETURN(FAIL):
fi:

gu:=ED(p,BetS)[x0]:

guW:=EDw(p,BetS)[x0]:

guL:=EDl(p,BetS)[x0]:

muW:=PrW(p,BetS)[x0]:

lu:=GB(p,x0,BetS,K):

print(`Suppose that right now have`, x0, `dollars `):
print(`and at each turn you toss a coin with prob. of winning a dollar`):
print(` being `, p, `and of losing a dollar being`, 1-p):
print(`and you keep playing until either you have 0 dollars`):
print(`or you have`, N, `dollars. ` ):
print(`Your strategy, as a list of bets you place when having`):
print(`i dollars, i from 1 to `, N , `is given by the following list`):
print(BetS):
lu:=GB(p,x0,BetS,K):
print(`In a simulation involving`, K, `runs, the fraction of wins was`):
print(evalf(lu[1][1]/K)):
print(`the theoretial probability of winning is`, evalf(muW)):
print(`--------------------`):

print(`The average duration of the game was`):
print(evalf((lu[1][1]*lu[1][2]+lu[2][1]*lu[2][2])/K)):
print(`the theoretial expected duration is`, evalf(gu)):

print(`The average duration when the gambler won was`):
print(evalf(lu[1][2])):
print(`the theoretial expected duration when winning is`, evalf(guW)):

print(`The average duration when the gambler lost was`):
print(evalf(lu[2][2])):
print(`the theoretial expected duration when losing is`, evalf(guL)):

end:


#Vecs(L): all the vectors v[i] such that 1<=v[i]<=L[i]
#For example, try:
#Vecs([2,3,2]);
Vecs:=proc(L) local n,i,L1,mu,mu1:
option remember:
n:=nops(L):
if not type(L,list) then
 RETURN(FAIL):
fi:
if {seq(type(L[i],posint),i=1..n)}<>{true} then
 RETURN(FAIL):
fi:
if n=1 then
 RETURN({seq([i],i=1..L[1])}):
fi:
L1:=[op(1..n-1,L)]:
mu:=Vecs(L1):
{seq(seq([op(mu1),i],i=1..L[n]),mu1 in mu)}:
end:


#AllS(N): the set of all strategies with N dollar cap
#For example, try:
#AllS(6);
AllS:=proc(N) Vecs(BoS(N)): end:


#BstrNi(N,i,p): The strategy that maximizes the probability of
#winning if the chance of winning in a single toss is p
#and right now you have i dollars in a game in [0,N].
#For example, try:
#BstrNi(6,3,2/5);
BstrNi:=proc(N,i,p) local gu,alufim,si,halev,i1:
gu:=AllS(N):

alufim:={gu[1]}:
si:=PrW(p,gu[1])[i]:

for i1 from 2 to nops(gu) do

halev:=PrW(p,gu[i1])[i]:

if halev>si then
 alufim:={gu[i1]}:
 si:=halev:
elif halev=si then
 alufim:=alufim union {gu[i1]}:
fi:

od:
alufim, si:

end:



#BstrN(N,p): The strategy that maximizes the probability of
#winning if the chance of winning in a single toss is p
#for all i dollars in a game in [0,N]
#For example, try:
#BstrN(6,2/5);
BstrN:=proc(N,p) local i,gu:

gu:=BstrNi(N,1,p)[1]:

for i from 2 to N-1 do
 gu:=gu intersect BstrNi(N,i,p)[1] :
od:


gu:

end:



#BstrNiD(N,i,p): The strategy that maximizes the probability of
#winning if the chance of winning in a single toss is p
#and right now you have i dollars in a game in [0,N].
#and in case of ties getting there as soon as possible
#For example, try:
#BstrNiD(6,3,2/5);
BstrNiD:=proc(N,i,p) local gu,alufim,si,halev,i1,ku:

gu:=BstrNi(N,i,p):
ku:=gu[2]:
gu:=gu[1]:
alufim:={gu[1]}:
si:=EDw(p,gu[1])[i]:

for i1 from 2 to nops(gu) do

halev:=EDw(p,gu[i1])[i]:

if halev<si then
 alufim:={gu[i1]}:
 si:=halev:
elif halev=si then
 alufim:=alufim union {gu[i1]}:
fi:

od:
alufim, [ku,si]:

end:


#BstrND(N,p): The strategy that maximizes the probability of
#winning if the chance of winning in a single toss is p
#for all i dollars in a game in [0,N] and gets there soonest
#For example, try:
#BstrND(6,2/5);
BstrND:=proc(N,p) local i,gu:

gu:=BstrNiD(N,1,p)[1]:

for i from 2 to N-1 do
 gu:=gu intersect BstrNiD(N,i,p)[1] :
od:


gu:

end:

#IsBetter(p,S1,S2): Given two strategies S1 and S2
#decides whether S1 is better than S2 for all initial
#capitals 
#(in the sense that the prob. of ultimate win is always >=0)
#for probability p. For example, try:
#IsBetter(2/5,TS(5),BoS(5));
IsBetter:=proc(p,S1,S2) local N,i,lu1,lu2:

N:=nops(S1)+1:

if nops(S2)<>N-1 then
RETURN(FAIL):
fi:

if not (IsValidStrat(S1,N)  and IsValidStrat(S2,N)) then
RETURN(FAIL):
fi:

lu1:=PrW(p,S1):
lu2:=PrW(p,S2):

if {seq(evalb(lu1[i]>=lu2[i]),i=1..N-1)}={true} then
 true:
else
 false:
fi:

end:

#IsBetterD(p,S1,S2): Given two strategies S1 and S2
#decides whether S1 is better than S2 for all initial
#capitals for probability p and the duration is smaller 
#For example, try:
#IsBetterD(2/5,TS(5),BoS(5));
IsBetterD:=proc(p,S1,S2) local lu1,lu2,lu,N,i:
lu:=IsBetter(p,S1,S2):
if lu=FAIL then
 RETURN(FAIL):
fi:

if lu=false then
 RETURN(false):
fi:

if lu and not IsBetter(p,S2,S1) then
 RETURN(true):
fi:

N:=nops(S1)+1:

lu1:=EDw(p,S1):
lu2:=EDw(p,S2):

if {seq(evalb(lu1[i]<=lu2[i]),i=1..N-1)}={true} then
 true:
else
 false:
fi:

end:


#Skhenim(S): all the legal neighbors of a strategy S. For
#example, try: 
#Skhenim(TS(4));
Skhenim:=proc(S) local N,i,gu,lu1:
N:=nops(S)+1:

if not IsValidStrat(S,N) then
 RETURN(FAIL):
fi:

lu1:=BoS(N):
gu:={}:

for i from 1 to N-1 do

if S[i]+1<=lu1[i] then
 gu:= gu union {[op(1..i-1,S),S[i]+1,op(i+1..nops(S),S)]}:
fi:

if S[i]-1>=1 then
 gu:= gu union {[op(1..i-1,S),S[i]-1,op(i+1..nops(S),S)]}:
fi:
od:

gu:
end:

#BestNei(p,S,i): the set of best neighbors of strategy S
#as far the prob. of ultimate win with a game with
#prob. of winning a dollar being p, if your current
#capital i dollars. Followed by the record. For example, try:
#BestNei(2/5,TS(5),3);
BestNei:=proc(p,S,i) local N,halev,i1,alufim,gu,si:
N:=nops(S)+1:

if not IsValidStrat(S,N) then
 RETURN(FAIL):
fi:

if not (type(i,integer) and i>=1 and i<=N-1) then
 RETURN(FAIL):
fi:

gu:=Skhenim(S):

alufim:={S}:
si:=PrW(p,S)[i]:

for i1 from 1 to nops(gu) do
 halev:=PrW(p,gu[i1])[i]:
 
if halev>si then
  si:=halev:
  alufim:={gu[i1]}:
 elif halev=si then
  alufim:=alufim union {gu[i1]}:
 fi:
od:

alufim,si:

end:


#GreedyBestN(p,S): tries to find, if possible
#a better strategy than S (with prob. p) among its
#neighbors. For example, try:
#GreedyBestN(2/5,TS(10));
GreedyBestN:=proc(p,S) local gu,gu1:
gu:=Skhenim(S):

for gu1 in gu do
 if IsBetter(p,gu1,S) and not IsBetter(p,S,gu1) then
  RETURN(gu1):
 fi:
od:

if {seq(IsBetter(p,S,gu1),gu1 in gu)}={true} then
 RETURN(S):
else
 RETURN(FAIL):
fi:

end:



#GreedyBest(p,S): Keeps trying to find better
#stategies among neighbors in a greedy way
#until it FAILS or gets to a valley
#For example, try:
#GreedyBest(2/5,TS(10));
GreedyBest:=proc(p,S) local S1,S2,S3:
S1:=S:
S2:=GreedyBestN(p,S1):

while S2<>FAIL and S1<>S2 do
S3:=GreedyBestN(p,S2):
S1:=S2:
S2:=S3:
od:
S2:
end:



#GreedyBestND(p,S): tries to find, if possible
#a better strategy than S (with prob. p) among its
#neighbors also duration. For example, try:
#GreedyBestND(2/5,TS(10));
GreedyBestND:=proc(p,S) local gu,gu1:
gu:=Skhenim(S):

for gu1 in gu do
 if IsBetterD(p,gu1,S) and not IsBetterD(p,S,gu1) then
  RETURN(gu1):
 fi:
od:

if {seq(IsBetterD(p,S,gu1),gu1 in gu)}={true} then
 RETURN(S):
else
 RETURN(FAIL):
fi:

end:


#GreedyBestD(p,S): Keeps trying to find better
#stategies among neighbors in a greedy way
#until it FAILS or gets to a valley.
#Also considering duration
#For example, try:
#GreedyBestD(2/5,TS(10));
GreedyBestD:=proc(p,S) local S1,S2,S3:
S1:=S:
S2:=GreedyBestND(p,S1):

while S2<>FAIL and S1<>S2 do
S3:=GreedyBestND(p,S2):
S1:=S2:
S2:=S3:
od:
S2:
end:


#RandPrDS(p,N,K): verifies empirically that K randomly
#chosen strategies in a game in [0,N] with prob. p
#are all worse than the bold strategy.
#For example, try:
#RandPrDS(2/5,40,10);
RandPrDS:=proc(p,N,K) local lu,i,mu:
lu:=BoS(N):

for i from 1 to K do
mu:=RS(N):

if not IsBetterD(p,lu,mu) then
print(mu, `is better than bold`):
RETURN(false,mu):
fi:
od:


true:

end:

#DeltaPr(p,S,i): The difference in the prob. vectors when the
#strategy S is made bolder by one dollar when
#you have i dollars, in a game where
#the prob. of winning a dollar is p and you play in [0,N]
#where N=nops(S)+1.
#If S[i]=min(i,N-i) it returns FAIL since it can't be made any bolder
#For example, try:
#DeltaPr(2/5,TS(5),2);
DeltaPr:=proc(p,S,i) local gu,mu,N,S1,i1:
N:=nops(S)+1:

if not (type(i,integer) and i>=1 and i<N) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

if S[i]=min(i,N-i) then
 RETURN(FAIL):
fi:

gu:=PrW(p,S):

S1:=[op(1..i-1,S),S[i]+1,op(i+1..nops(S),S)]:

mu:=PrW(p,S1):

[seq(mu[i1]-gu[i1],i1=1..N-1)]:

end:


#OM1(S,i): adds one dollar to the strategy S, if
#possible, or returns FAIL
#For example, try:
#OM1([1,1,1],1);
OM1:=proc(S,i) local N:
N:=nops(S)+1:
if S[i]=min(i,N-i) then
 FAIL:
else
[op(1..i-1,S),S[i]+1,op(i+1..nops(S),S)]:
fi:
end:




#FirstBetter(p,S): given a strategy S, finds the
#first bolder strategy (going from left to right)
#For example, try:
#FirstBetter(2/5,TS(10));
FirstBetter:=proc(p,S) local i,N,j,gu,gu1,S1,i1:
N:=nops(S)+1:
gu:=PrW(p,S):
for j from 1 to N do
 for i from 1 to nops(S) do
  if S[i]+j<=min(i,N-i) then
   S1:=[op(1..i-1,S),S[i]+j,op(i+1..nops(S),S)]:
    gu1:=PrW(p,S1):
    if min(seq(gu1[i1]-gu[i1],i1=1..nops(gu)))>=0 then
      RETURN(S1):
    fi:
 fi:
od:
od:

FAIL:
end:

   

#BaB(p,S): starting with a strategy S, and operating
#with subfair prob. p, keeps finding bolder and
#bolder strategies until it can't make it any  bolder
#It returns the ultimate strategy. For example, try:
#BaB(2/5,TS(10));
BaB:=proc(p,S) local S1,S2,S3:
S1:=S:
S2:=FirstBetter(p,S1):

while S2<>FAIL do
S3:=FirstBetter(p,S2):
S1:=S2:
S2:=S3:
od:
S1:
end:



#TestBH(p,N): Tests the hypothesis that for every strategy
#except the boldest you can make it better by making it bolder
#in one place for ALL strategies in [0,N] and subfair prob. p
#For example, try: TestBH(2/5,6);
TestBH:=proc(p,N) local gu,gu1:
gu:=AllS(N) minus {BoS(N)}:
evalb(not member(FAIL,{seq(FirstBetter(p,gu1), gu1 in gu)})):
end:


#TestBHrand(p,N,K): Tests the hypothesis that for every strategy
#except the boldest you can make it better by making it bolder
#in one place for K randomly chosen strategies in [0,N] and subfair prob. p
#For example, try: TestBHrand(2/5,20,5);
TestBHrand:=proc(p,N,K) local gu,i:

for i from 1 to K do
 gu:=RS(N):
  if gu<>BoS(N) and FirstBetter(p,gu)=FAIL then
   RETURN(false, gu):
  fi:
od:
true:

end:

#IsOptimal(p,S): checks whether strategy S is optimal
#with prob. of winning a stake being p. For example, try:
#IsOptimal(2/5,BoS(10));
IsOptimal:=proc(p,S) local V,x,y,q:

if not IsValidStrat(S,nops(S)+1) then
print(`Bad input`):
RETURN(FAIL):
fi:

q:=1-p:
V:=PrW(p,S):
evalb(
{seq(seq(evalb(V[x]-p*V[x+y]-q*V[x-y]>=0),y=1..min(nops(S)-x-1,x-1)),
x=1..nops(S)-1)}={true}):
end:




#IsOptimalSubFair(S): checks whether strategy S is optimal
#when the prob. is <=1/2 for 
#symbloic p For example, try:
#IsOptimalSubFair(BoS(10));
IsOptimalSubFair:=proc(S) local V,x,y,q,p,gu,gu1,lu1,lu11:

if not IsValidStrat(S,nops(S)+1) then
print(`Bad input`):
RETURN(FAIL):
fi:

q:=1-p:
V:=PrW(p,S):

gu:={seq(seq(normal(V[x]-p*V[x+y]-q*V[x-y]),y=1..min(nops(S)-x-1,x-1)),
x=1..nops(S)-1)}:

for gu1 in gu do
 if gu1<>0 then
 lu1:={fsolve(diff(gu1,p)=0,p=0..1/2)} union {0,1/2}:
 if min(seq(subs(p=lu11,gu1),lu11 in lu1))<0 then
  RETURN(false):
 fi:
 fi:
od:
true:
end:


#IsOptimalSuperFair(S): checks whether strategy S is optimal
#when the prob. is >=1/2 for 
#symbloic p For example, try:
#IsOptimalSuperFair(TS(10));
IsOptimalSuperFair:=proc(S) local V,x,y,q,p,gu,gu1,lu1,lu11:

if not IsValidStrat(S,nops(S)+1) then
print(`Bad input`):
RETURN(FAIL):
fi:

q:=1-p:
V:=PrW(p,S):

gu:={seq(seq(normal(V[x]-p*V[x+y]-q*V[x-y]),y=1..min(nops(S)-x-1,x-1)),
x=1..nops(S)-1)}:

for gu1 in gu do
 if gu1<>0 then
 lu1:={fsolve(diff(gu1,p)=0,p=1/2..1)} union {1/2,1}:
 if min(seq(subs(p=lu11,gu1),lu11 in lu1))<0 then
  RETURN(false):
 fi:
 fi:
od:
true:
end:


#plotPrW(p,S): A plot of the prob. of winning as a function
#of the intial capital with strategy S and prob. p, normalized so that
#the exit capital is 1. For example, try:
#PlotPrW(p,S)
plotPrW:=proc(p,S) local gu,i,N:
gu:=PrW(p,S):
N:=nops(S)+1:
plot([seq([i/N,gu[i]],i=1..N-1)]):
end:

#plotED(p,S): A plot of the prob. of the expected time to finish
#of the intial capital with strategy S and prob. p, normalized so that
#the exit capital is 1. For example, try:
#PlotED(p,S)
plotED:=proc(p,S) local gu,i,N:
gu:=ED(p,S):
N:=nops(S)+1:
plot([seq([i/N,gu[i]],i=1..N-1)]):
end:

#plotEDw(p,S): A plot of the prob. of the expected time to winning finish
#of the intial capital with strategy S and prob. p, normalized so that
#the exit capital is 1. For example, try:
#PlotEDw(p,S)
plotEDw:=proc(p,S) local gu,i,N:
gu:=EDw(p,S):
N:=nops(S)+1:
plot([seq([i/N,gu[i]],i=1..N-1)]):
end:









#BreimanProfile(p,N,x,f,h): The scores, Prob. of winning`):
#with goal N, and initial capital x
#followed by expected duration for Kelly strategy with factor f`):
#for various boldness-cut-offs, with resolution h`):
#For example, try: `):
#BreimanProfile(3/5,100,1/2,1/5,1/10);`):
BreimanProfile:=proc(p,N,x,f,h) local j,gu,mu,c,i: 

if not type(x*N,integer) then
 RETURN(FAIL):
fi:

gu:=[]:

if trunc(1/h)<5 then
 print(`h is too large`):
 RETURN(FAIL):
fi:

for j from 0 to trunc(1/h) do
c:=j*h:
mu:=BrS(N,f,c):
gu:=[op(gu),[c,PrW(p,mu)[x*N],EDw(p,mu)[x*N]]]:
if mu=KS(N,f) then
for i from 1 while op(2..3,gu[i])=op(2..3,gu[1]) do od:
gu:=[op(i-1..nops(gu),gu)]:
mu:=KS(N,f):
gu:=[op(gu),[1,PrW(p,mu)[x*N],EDw(p,mu)[x*N]]]:
if op(2..3,gu[nops(gu)-1])=op(2..3,gu[nops(gu)]) then
  gu:=[op(1..nops(gu)-2,gu),gu[nops(gu)]]:
fi:
 RETURN(gu):
fi:
od:

end:




#BestBreiman(p,N,x,f,h,conf): The Best Breiman strategy
#with goal N, and initial capital x and factor f
#For example, try: 
#BestBreiman(3/5,100,1/2,1/5,1/10,98/100);
BestBreiman:=proc(p,N,x,f,h,conf) local gu,j,aluf,si:
gu:=BreimanProfile(p,N,x,f,h):

if max(seq(gu[j][2],j=1..nops(gu)))<conf then
RETURN(FAIL):
fi:

aluf:=0:
si:=infinity:

for j from 1 to nops(gu) do
if gu[j][2] >conf then
 if gu[j][3]<si then
    aluf:=j:
    si:=gu[j][3]:
 fi:
fi:
od:
[gu[aluf][1],gu[aluf][2],gu[aluf][3]]:
end:



#KellyContestStory(p,N,h,ConfL): The stories of
#the winners in the Kelly contest (with prob. p)
#to minimize the expected
#duration if you want a prob. of winning for various
#starting capitals and various confidence levels ConfL
#h is the resolution and 
#For example, try:
#KellyContestStory(3/5,100,1/10,[999/1000,99/100,9/10]): 
KellyContestStory:=proc(p,N,h,ConfL) local x,conf,mu,j,guW,guEDw,n1,N1:
print(`Explorations of the Discrete Kelly Strategy for Leaving the Casino (With High Probability as a Winner)  as Soon as Possible `):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):
print(`Suppose that your goal in life is to leave the casino with a fortune of  `, N, ` dollars `):
print(`and for each gamble you have a prob. of`, p, `of winning.`):
print(`According to your initial capital, we have the following options`):
print(``):
for x from trunc(N/2) by trunc(N/10) to trunc(8*N/10) do
print(`---------------------------------------------------------------------------------------`):
print(`If the initial capital is`, x, ` dollars, then of course the safest is`):
print(`to play timidly, and then your prob. of exiting a winner is`):
guW:=CGRW(p,n1,N1):
print(evalf(subs({n1=x,N1=N},guW))):
print(`but the expected time until you exit is`):
guEDw:=CGREDw(p,n1,N1):
print(evalf(subs({n1=x,N1=N},guEDw)), `rounds of gambling.`):

print(`If you don't mind taking a small chance of NOT winning, then you may be able to leave the casino much sooner as follows.`):
print(``):
print(`For example, let's see what is going on with the`):
print(`following list of probabilities cut-offs`, ConfL):
print(`We can pursue the following strategies.`):
print(``):
for j from 1 to nops(ConfL) do
conf:=ConfL[j]:
print(`If you are willing to take a chance of  completely losing your current capital of`, x, `dollars, with a chance of up to`, 1- conf):
print(`then you can pursue a Kelly-type strategy`):
mu:=KellyContestx(p,N,x/N,h,conf):
if mu=FAIL then
 next:
fi:
print(`with factor`, mu[1], `that will let you expect to leave the casino`):
print(`in `, mu[2] , `rounds of gambling. `):
od:
od:

end:




#KellyContestStoryWB(p,N,h,ConfL): The stories of
#the winners in the Kelly contest also looking at
#Breiman-tweaking
#(with prob. p)
#to minimize the expected
#duration if you want a prob. of winning for various
#starting capitals and various confidence levels ConfL
#h is the resolution and 
#For example, try:
#KellyContestStoryWB(3/5,100,1/10,[999/1000,99/100,9/10]): 
KellyContestStoryWB:=proc(p,N,h,ConfL) local x,conf,mu,j,ru,guW,guEDw,n1,N1:
print(`Explorations of the Discrete Kelly-Breiman Strategies for Leaving the Casino (With High Probability as a Winner)  as Soon as Possible `):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):
print(`Suppose that your goal in life is to leave the casino with a fortune of  `, N, ` dollars `):
print(`and for each gamble you have a prob. of`, p, `of winning.`):
print(`According to your initial capital, we have the following options`):
print(``):
for x from trunc(N/2) by trunc(N/10) to trunc(8*N/10) do
print(`---------------------------------------------------------------------------------------`):
print(`If the initial capital is`, x, ` dollars, then of course the safest is`):
print(`to play timidly, and then your prob. of exiting a winner is`):
guW:=CGRW(p,n1,N1):
print(evalf(subs({n1=x,N1=N},guW))):
print(`but the expected time until you exit is`):
guEDw:=CGREDw(p,n1,N1):
print(evalf(subs({n1=x,N1=N},guEDw)), `rounds of gambling.`):

print(`If you don't mind taking a small chance of NOT winning, then you may be able to leave the casino much sooner as follows.`):
print(``):
print(`For example, with the prob. of winning being at least`, op(ConfL), `we can pursue the following strategies.`):
print(``):
for j from 1 to nops(ConfL) do
conf:=ConfL[j]:
print(`If you are willing to take a chance of  completely losing your current capital of`, x, `dollars, with a chance of up to`, 1- conf):
print(`then you can pursue a Kelly-type strategy`):
mu:=KellyContestx(p,N,x/N,h,conf):
if mu=FAIL then
 next:
fi:
print(`with factor`, mu[1], `that will let you expect to leave the casino`):
print(`in `, mu[2] , `rounds of gambling. `):

print(`The probability of winning is`,evalf(PrW(p,KS(N,mu[1]))[x])):
print(`which is indeed more than`, conf):

ru:=BestBreiman(p,N,x/N,mu[1],h,conf):


if ru<>FAIL and ru[3]<mu[2] then
 print(`If you play the Breiman strategy`, [mu[1],ru[1]], `then `):
 print(` you can expect to leave the casino (winning!) in`):
 print(evalf(ru[3]), `rounds of gambling, with prob.`, evalf(ru[2])):
 print(`even though this is a little riskier than the Kelly prob.` ):
 print(evalf(PrW(p,KS(N,mu[1]))[x])):
 print(`it is still in your safey net,  being above`, conf):
fi:

od:
od:

end:








#BreimanContestx(p,N,x,f,h,conf): The best Breiman 
#bolding-modification to the Kelly strategy with factor f
#that minimizes the expected duration
#if you currently have x*N dollars in a game with  a loaded coin
#of prob. p, and the prob. of ultimately winning (with N dollars)
#is at least conf.
#with resolution h, starting at h
#For example, try: 
#BreimanContestx(3/5,100,1/2,1/5,99/100,1/10);
BreimanContestx:=proc(p,N,x,f,h,conf) local aluf, gu,j,si,halev,gun,c:
if not type(N*x,integer) then
   print(`N times x should be an integer`):
  RETURN(FAIL):
fi:

aluf:=1:
gu:=BrS(N,f,aluf):

if PrW(p,gu)[x*N]<conf then
 print(`conf is too high`):
 RETURN(FAIL):
fi:

si:=EDw(p,gu)[x*N]:

for j from 1 to trunc(1/h)  do
c:=1-j*h:
gun:=BrS(N,f,c):
if gun<>gu then
gu:=gun:
if PrW(p,gu)[x*N]<conf then
 RETURN([aluf,evalf(si)]):
else
 halev:=EDw(p,gu)[x*N]:
 if halev<si then
   aluf:=c:
    si:=halev:
 fi:
fi:
fi:
od:   
[aluf,si]:
end:


#BreimanContestStory(p,N,f,h,ConfL): The stories of
#the winners in the Breiman contest (with prob. p)
#and Kelly factor f, to minimize the expected
#duration if you want a prob. of winning for various
#starting capitals and various confidence levels ConfL
#h is the resolution
#For example, try:
#BreimanContestStory(3/5,100,1/5,1/10,[999/1000,99/100,9/10]): 
BreimanContestStory:=proc(p,N,f,h,ConfL) local x,conf,mu,lu,j1:
print(`Explorations of the Discrete Breiman Strategy for Leaving the Casino (With High Probability as a Winner)  as Soon as Possible `):
print(`with Kelly factor`, f):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):
print(`Suppose that your goal in life is to leave the casino with a fortune of  `, N, ` dollars `):
print(`and for each gamble you have a prob. of`, p, `of winning.`):
print(`and you pursue a Kelly strategy with factor`, f):
print(`with Breiman bolding modifications.`):
print(`According to your initial capital, we have the following options`):
print(``):
for x from trunc(N/2) by trunc(N/10) to trunc(8*N/10) do
print(`---------------------------------------------------------------------------------------`):

print(`If your current capital is`, x, `then `):
mu:=BreimanProfile(p,N,x/N,f,h):
print(`The Breiman profile is`):
print(evalf(mu)):

for j1 from 1 to nops(ConfL) do
 
 conf:=ConfL[j1]:

lu:=BreimanContestx(p,N,x/N,f,h,conf):

print(`If the confidence level is`, conf,`then the best Breiman strategy is`):
print(lu):
od:
od:

end:

#KellyProfile(p,N,x,h): The list of triples
#[f,ProbOfWinning,ExpectedTimeToWin] for Kelly factors
#starting at 0 (timid strategy) with resolution h, if the prob. of winning
#any round is p, the exist capital is N, and your initial
#capital is N*x
#For example, try: 
#KellyProfile(3/5,100,1/2,1/20);
KellyProfile:=proc(p,N,x,h) local  gu,j,f,L,mu1,mu2,N1,n1:

if not type(N*x,integer) then
   print(`N times x should be an integer`):
   RETURN(FAIL):
fi:


mu1:=subs({N1=N,n1=N*x},CGRW(p,n1,N1)):
mu2:=subs({N1=N,n1=N*x},CGREDw(p,n1,N1)):
L:=[[0,mu1,mu2]]:

for j from 1 to trunc(1/h) do 
 f:=j*h:
 gu:=KS(N,f):
 L:=[op(L), [f,PrW(p,gu)[x*N],EDw(p,gu)[x*N]]]:
od:   

L:

end:



#KellyProfileStory(p,N,h,M): The stories of
#the Kelly profiles (with prob. p), exit capital N,
#resolution h, and various starting capitals (with resolution N/M)
#starting with N/2. For example, try:
#KellyProfileStory(3/5,100,1/10,10): 
KellyProfileStory:=proc(p,N,h,M) local x:

if not type(N/M,integer) then
print(`The second argument divided by the fourth argument`):
print(` must be an integer`):
RETURN(FAIL):
fi:

if not type(M/2,integer) then
print(`The fourth argument must be an even integer`):
RETURN(FAIL):
fi:

if not type(N/2,integer) then
print(`The second argument must be an even integer`):
RETURN(FAIL):
fi:

print(`Some Kelly Strategy Profiles `):
print(``):
print(`By Shalosh B. Ekhad `):
print(``):
print(`You start with a certain initial capital, and toss a loaded coin with probability`, p, ` of lending Heads.`):
print(`At every round, you can stake any amount (not exceeding your current fortune).`):
print(`If the coin lands Heads, you win the stake, otherwise you lose it.`):
print(`Suppose that your goal in life is to leave the casino with a fortune of  `, N, ` dollars. `):
if p>1/2 then
print(`Since the probability is superfair,`):
print(`if you are a chicken, and want to absolutely maximize your`):
print(`probability of leaving the casino as a winner, then, as`):
print(`Lester Dubins and Jimmie Savage tell us, your best strategy`):
print(`is to play timidly. Alas, this may take a very LONG time!`):
fi:

if p=1/2 then
print(`Since the probability is fair,`):
print(`if you are a chicken, and want to absolutely maximize your`):
print(`probability of leaving the casino as a winner, then, as`):
print(`Lester Dubins and Jimmie Savage tell us, your best strategy`):
print(`is to play timidly. Alas, this may take a very LONG time!`):
fi:

print(``):
print(`If you are willing to take a small chance of NOT winning,`):
print(`you could expect to leave the casino (as a winner) much sooner,`):
print(`by pursuing a Kelly-style strategy with factor f, for various f (NOT necessarily the Kelly recommendation of 2p-1=` , 2*p-1 , `.) `):
print(`Below we will list, for each f from 0 (timid strategy) to 1 (bold strategy) with resolution`, h, `the prob.`):
print(`of leaving the casino a winner, followed by the expected time it would take to get there,`):
print(`for various starting capitals.`):
print(`Note that it is not always the best to take Kelly's recommendation mentioned above`):
print(`f=`, 2*p-1 , `since this may be too risky for you, or conversely`):
print(`would take too long, and you are willing to take a higher risk`):
print(`of losing, but to reduce the expected time that it would take to win. So YOU can decide for yourself, looking at the`):
print(`data what suits you best in this trade-off between ultimately winning and winning as soon as possible.`):
print(``):

for x from N/2 by N/M to (M-2)*N/M do
print(`---------------------------------------------------------------------------------------`):
print(`If the initial capital is`, x, ` dollars, then the Kelly Profile is`):
print(evalf(KellyProfile(p,N,x/N,h))):
od:

end:




###start section with deadline
#PrWdd(p,S,i,T): Given a strategy S, (with a casino with exit capital
#nops(S)+1, and prob. of winning a single round p, and an integer i
#between 1 and N-1
#computes the probability of winning in <=T rounds
#if the current capital is i. For example, try:
#PrWdd(1/2,[1,1,1],1,3);
PrWdd:=proc(p,S,i,T) local N:
option remember:
N:=nops(S)+1:
if T=0 then
 if i=N then
  RETURN(1):
 else
  RETURN(0):
 fi:
fi:
if i=N then
 RETURN(1):
fi:
if i=0 then
 RETURN(0):
fi:
expand((1-p)*PrWdd(p,S,i-S[i],T-1)+p*PrWdd(p,S,i+S[i],T-1)):
end:


#EDdd(p,S,i,T): Given a strategy S, (with a casino with exit capital
#nops(S)+1, and prob. of winning a single round p, and an integer i
#between 1 and N-1
#computes the expected duration if the game ends in <=T rounds
#if the current capital is i. For example, try:
#EDdd(1/2,[1,1,1],1,3);
EDdd:=proc(p,S,i,T) local N:
option remember:
N:=nops(S)+1:
if T=0 then
  RETURN(0):
fi:
if i=N then
 RETURN(0):
fi:
if i=0 then
 RETURN(0):
fi:
expand((1-p)*EDdd(p,S,i-S[i],T-1)+p*EDdd(p,S,i+S[i],T-1)+1):
end:



#KellyProfileDD(p,N,i,T,h): The list [f,ProbabilityOfWinning, ExpectedDuration]
#if you must win N dollars in <=T rounds, and your initial capital is i
#for all Kelly factors
#f from 0 (timid) to f=1 (bold) with resolution h
#For example, try:
#KellyProfileDD(3/5,100,50,40,1/10);
KellyProfileDD:=proc(p,N,i,T,h) local gu,f, j,So,Sn:
gu:=[]:
So:=KS(N,0):
gu:=[[0,PrWdd(p,So,i,T),EDdd(p,So,i,T)]]:
for j from 1 to trunc(1/h) do
f:=j*h:
Sn:=KS(N,f):
if Sn<>So then
 gu:=[op(gu),[f,PrWdd(p,Sn,i,T),EDdd(p,Sn,i,T)]]:
 So:=Sn:
fi:
od:
gu:
end:


#BestKellyDD(p,N,i,T,h): The best Kelly Strategy if you have
#if you must win N dollars in <=T rounds, and your initial capital is i
#using resolution h
#For example, try:
#It also returns the expected time
#until exit (either as a winner or loser). For example try:
#BestKellyDD(3/5,100,60,30,1/20);
BestKellyDD:=proc(p,N,i,T,h) local aluf, si,muam,Sn,So,j,f:
aluf:=0:
So:=KS(N,0):
si:=PrWdd(p,So,i,T):
for j from 1 to trunc(1/h) do
f:=j*h:
Sn:=KS(N,f):
if Sn<>So then
 muam:=PrWdd(p,Sn,i,T):
 So:=Sn:
 if muam>si then
    aluf:=f:
    si:=muam:
 fi:
fi:
od:
[aluf,si,EDdd(p,KS(N,aluf),i,T)]:
end:

#BestBreimanDD(p,N,i,T,f,h): The best Breiman adjustment
#Strategy to Kelly strategy with factor f
#if you must win N dollars in <=T rounds, and your initial capital is i
#using resolution h
#until exit (either as a winner or loser). For example try:
#For example, try:
#BestBreimanDD(3/5,100,50,40,1/5,1/10); 
BestBreimanDD:=proc(p,N,i,T,f,h) local aluf, si,muam,Sn,So,j,c:
aluf:=0:
So:=BrS(N,f,0):
si:=PrWdd(p,So,i,T):
for j from 1 to trunc(1/h) do
c:=j*h:
Sn:=BrS(N,f,c):
if Sn<>So then
 muam:=PrWdd(p,Sn,i,T):
 So:=Sn:
 if muam>si then
    aluf:=c:
    si:=muam:
 fi:
fi:
od:
if BrS(N,f,aluf)=BrS(N,f,1) then
 aluf:=1:
fi:
[[f,aluf],si,EDdd(p,BrS(N,f,aluf),i,T)]:
end:



#BestBKdd(p,N,i,T,h): The best Breiman-Kelly Strategy if you have
#if you must win N dollars in <=T rounds, and your initial capital is i
#using resolution h
#For example, try:
#It also returns the expected time
#until exit (either as a winner or loser). For example try:
#BestBKdd(3/5,100,60,30,1/20);
BestBKdd:=proc(p,N,i,T,h) local aluf,muam,j,f:
aluf:=BestBreimanDD(p,N,i,T,0,h):
for j from 1 to trunc(1/h) do
f:=j*h:
muam:=BestBreimanDD(p,N,i,T,f,h):
 if muam[2]>aluf[2] then
    aluf:=muam:
 fi:
od:
aluf:
end:




#BestBKddStory1(p,N,i,h,t0,MaxF): finds the Best strategy if
#the prob. of winning a single round is p, the exit capital
#is N, the initial capital i with resolution h for various
#starting times  with increments of t0, until MaxF times the 
#expected duration of timid play.
#For example, try:
#BestBKddStory1(3/4,50,30,1/10,10,1/4):
BestBKddStory1:=proc(p,N,i,h,t0,MaxF) local T,mu,gu,j,i1,N1:

if not (type(N,integer) and type(i,integer) and N>=0 and i>=0 and i<=N) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

if not (p>=0 and p<=1) then
print(`Bad input`):
RETURN(FAIL):
fi:

print(`You walk into a casino with initial capital of `, i  , ` dollars `):
print(`Every round of gambling has a probability`,p, `of winning `):
print(`and you play until you are either broke or have`, N, `dollars.`):

if p<=1/2 then
print(`Since the prob. of winning one round `,p):
print(`is subfair, Dubins and Savage tell`):
print(`us to play bold. This will maximize our prob. of ultilmately winning`):
print(`and will get us out as soon as possible`):
fi:

mu:=subs({i1=i,N1=N},CGRED(p,i1,N1)):
print(`Since the prob. of winning one round `, p, `is superfair `):
print(`and we want to maximize our probability of exiting as a winner,`):
print(`Dubins and Savage tell us to play timidly, only betting`):
print(`one dollar at each round.`):
print(`Alas, the expected duration of this game is`, evalf(mu) , `rounds `):
print(`and since the duration has a fat tail, it may take even `):
print(`much longer than that.`):
print(`Suppose that you are in a rush, and you have to leave the casino`):
print(`much sooner. In that case you should follow the following`):
print(`Breiman-Kelly strategies, according to the allocated time.`):

for j from 1 to trunc(mu*MaxF/t0) do
 T:=t0*j:
print(`If you only can stay at the casino`, T, `rounds then your strategy`):
print(`should be the Kelly-Breiman strategy with parameters`):
gu:=BestBKdd(p,N,i,T,h):
print(gu[1]):
print(`whose probability of winning in less than`, T):
print(`rounds is`,evalf(gu[2]), `and the expected duration is`, evalf(gu[3])):
print(`rounds of gambling.`):
od:

end:


#BestBKddStory(p,N,h,t0,MaxF,M0): finds the Best strategy if
#the prob. of winning a single round is p, the exit capital
#is N, for various initial capitals, by increments of M0
# with resolution h for various
#starting times  with increments of t0, until MaxF times the 
#expected duration of timid play.
#For example, try:
#BestBKddStory(3/4,50,1/10,10,1/4,10):
BestBKddStory:=proc(p,N,h,t0,MaxF,M0) local T,mu,gu,j,i1,N1,i:

if not ( type(N,integer) and N>0) then
 print(`Bad input`):
 RETURN(FAIL):
fi:

if not (p>=0 and p<=1) then
print(`Bad input`):
RETURN(FAIL):
fi:


print(`You walk into a casino with a certain initial capital. `):
print(`Every round of gambling has a probability`,p, `of winning `):
print(`and you play until you are either broke or have`, N, `dollars.`):

if p<=1/2 then
print(`Since the prob. of winning one round `,p):
print(`is subfair, Dubins and Savage tell`):
print(`us to play bold. This will maximize our prob. of ultilmately winning`):
print(`and will get us out as soon as possible`):
fi:

for i from M0 by M0 to N-M0 do
mu:=subs({i1=i,N1=N},CGRED(p,i1,N1)):
if trunc(mu*MaxF/t0)>=1 then
print(`----------------------------------------------`):
print(`Suppose your initial capital is`, i, `dollars.`):




print(`Since the prob. of winning one round `, p, `is superfair `):
print(`timid play (betting one dollar at each round) maximizes your`):
print(`prob. of leaving the casino as a winner.`):
print(`Alas, the expected duration would be`, evalf(mu) , `rounds. `):
print(`Suppose that you are in a rush, and you have to leave the casino`):
print(`much sooner. In that case you should follow the following`):
print(`Breiman-Kelly strategies, according to the allocated time.`):

for j from 1 to trunc(mu*MaxF/t0) do
 T:=t0*j:
print(`If you only can stay at the casino`, T, `rounds then your strategy`):
print(`should be the Kelly-Breiman strategy with parameters`):
gu:=BestBKdd(p,N,i,T,h):
print(gu[1]):
print(`whose probability of winning in less than`, T):
print(`rounds is`,evalf(gu[2]), `and the expected duration is`, evalf(gu[3])):
print(`rounds of gambling.`):
od:
fi:
od:
end:



#BestStake(p,i,N,T): Suppose that you are in a casino, 
#with i dollars, and you exit as a winner as soon as
#you have N dollars, and at any round you can stake any
#amount <=min(i,N-i), and the prob. of winning a single
#round is p, and you want to maximize the probability of
#achieving your goal in <=T rounds (the deadline, if
#you don't have N dollars by that time the mafia will kill you)
#It outputs that optimal stake(s), and the probability
#of making it, if you play optimally.
#For example, try:
#BestStake(11/20,5,10,6);
BestStake:=proc(p,i,N,T) local gu,x,halevai,si:
option remember:
if i=N and T>=0 then
 RETURN({},1):
fi:

if i=0 and T>=0 then
 RETURN({},0):
fi:

if i<N and T=0 then
 RETURN({},0):
fi:

gu:={}:

si:=0:

for x from 1 to min(i,N-i) do
halevai:=(1-p)*BestStake(p,i-x,N,T-1)[2]+p*BestStake(p,i+x,N,T-1)[2]:
if halevai>si then
 gu:={x}:
 si:=halevai:
elif halevai=si then
 gu:=gu union {x}:
fi:
od:
gu,si:
end:



#SimulateBSv(p,i,N,T): Verbose version
#Simulates one GAME, using the
#optimal strategy suggested by BestStake(p,j,N,T)
#where the probability of winning one round is p,
#you currently have i dollars, the exit capital is N
#and you must finish by T rounds,  or else you would
#be executed. For example, try:
#SimulateBSv(3/5,5,10,10);
SimulateBSv:=proc(p,i,N,T) local ra,n,d,j,T1,coin,lu,lu1:
n:=numer(p):
d:=denom(p):
ra:=rand(1..d):

T1:=T:
j:=i:

print(`---------------------------------------------------------`):
print(`I have `, i, `dollars and I walk into  a casino`):
print(`where I can stake any amount, up to my current capital.`):
print(`I owe`, N, `dollars to a loan shark who would kill me`):
print(`if I don't give him my debt by`,T, `rounds. `):
print(`The probability of winning my stake at each round is`, p):
print(`I will play by following the optimal strategy.`):

while T1>0 and j>0 and j<N do
lu:=BestStake(p,j,N,T1):
lu1:=max(op(lu[1])):
print(`Right now I have`, j, `dollars and `, T1,  `rounds left .`):
print(`I am staking`, lu1, `dollars, my probability of staying alive`):
print(`is `, evalf(lu[2])):

print(`Let's toss the loaded coin`):
coin:=evalb(ra()<=n):
 if coin then
   print(`Yea, I won this round!`):
    j:=j+lu1:
   if j>=N then
      print(`Now I have `, j, `dollars! `): 
      print(`I made it!, I survived! and it only took me`, T-T1+1, `rounds!`):
      RETURN(1):
   fi:
 else
   print(`#**?#@! I lost this round!`):
   j:=j-lu1:
     if j<=0 then
        print(`Tarnations! I died., and it  took me`, T-T1+1, `rounds to die. `):
      RETURN(0):
     fi:
 fi:
T1:=T1-1:
od:

print(`My time is up!, The number of rounds is`, T, `and my current`):
print(`capital is`, j, `so I must die`):
RETURN(0):

end:



#SimulateBS(p,i,N,T): Terse version
#Simulates one GAME, using the
#optimal strategy suggested by BestStake(p,j,N,T)
#where the probability of winning one round is p,
#you currently have i dollars, the exit capital is N
#and you must finish by T rounds,  or else you would
#be executed. Returns 1 if the outcome is live
#and 0 if it is dead.
#For example, try:
#SimulateBS(3/5,5,10,10);
SimulateBS:=proc(p,i,N,T) local ra,n,d,j,T1,coin,lu,lu1:
n:=numer(p):
d:=denom(p):
ra:=rand(1..d):

T1:=T:
j:=i:

while T1>0 and j>0 and j<N do
lu:=BestStake(p,j,N,T1):
lu1:=max(op(lu[1])):
coin:=evalb(ra()<=n):
 if coin then
    j:=j+lu1:
   if j>=N then
      RETURN(1):
   fi:
 else

   j:=j-lu1:
     if j<=0 then
      RETURN(0):
     fi:
 fi:
T1:=T1-1:
od:
0:
end:


#CheckBestStake(p,i,N,T,K): checks procedure BestStake(p,i,N,T)
#by running K games. For example try:
#CheckBestStake(3/5,10,20,10,100);
CheckBestStake:=proc(p,i,N,T,K) local lu,mu,i1:
lu:=evalf(BestStake(p,i,N,T)[2]):
print(`If the prob. of winning a round is`, p):
print(`and you have`, i, `dollars, and the exit capital is`, N):
print(`and you need to get it in`, T, `rounds `):
print(`Then your probability of finishing alive is`, lu):
print(`Let's play this game`, K, ` times. The fraction that finished alive is`):
mu:=evalf(add(SimulateBS(p,i,N,T),i1=1..K)/K):
print(mu):
RETURN(lu,mu):
end:
###end section with deadline




#BestStrat(p,N,T): The best strategy with prob. of one round being
#p, exit capital N, and T rounds available
#For example, try:
#BestStrat(3/5,20,10);
BestStrat:=proc(p,N,T) local i:
[seq(max(BestStake(p,i,N,T)[1]),i=1..N-1)]:
end:


#BestStratStory(m0,N0,T0,K): All the Best strategies
#for various, probabilities (starting at (m0+1)/(2*m0)
#until 1-1/(2*m0)), various exit capitals, from N0
#to N0*K and various deadlines, from T0 to T0*K
#For example, try:
#BestStratStory(10,10,5,3);
BestStratStory:=proc(m0,N0,T0,K) local p,N,T,i,lu,TAB:

for i from m0+1 to 2*m0-1 do
 p:=i/m0/2:
for N from N0 by N0 to N0*K do
 for T from T0 by T0 to T0*K do
  lu:=BestStrat(p,N,T):
  print(`The Best strategy for p=`,p, `N= `, N, `T= `, T, `is : `):
  print(lu):
  TAB[p,N,T]:=lu:
 od:
od:
od:

TAB:
end: