#####################################################################
##HIMURIM: Save this file as HIMURIM #
## To use it, stay in the #
##same directory, get into Maple (by typing: maple ) #
##and then type: read HIMURIM #
##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 x00
and IsValidStrat(BetS,N)) then
print(`Bad input`):
RETURN(FAIL):
fi:
x:=x0:
co:=0:
while x>0 and x=1 and x00
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]=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=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=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
if gu[j][3]FAIL and ru[3]gu then
gu:=gun:
if PrW(p,gu)[x*N]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 isi 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 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 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: