##################################################################### ##VGPileGames.txt: Save this file as VGPileGames.txt # ## To use it, stay in the # ##same directory, get into Maple (by typing: maple ) # ##and then type: read VGPileGames.txt # ##Then follow the instructions given there # ## # ##Written by Doron Zeilberger, Rutgers University , # #DoronZeil at gmail dot com # ###################################################################### #Created: July-Aug. 2019 print(`Created: July-Aug. , 2019`): print(` This is VGPileGames.txt `): print(`It is one of the Maple packages that accompany the article `): print(` "A Multi-Computational Exploration of Some Games of Pure Chance" `): print(`by Thotsaporn Aek Thanatipanonda and Doron Zeilberger`): print(`and also available from Zeilberger's website`): print(``): print(`Please report bugs to DoronZeil at gmail dot com `): print(``): print(`The most current version of this package and paper`): print(` are available from`): print(`http://sites.math.rutgers.edu/~zeilberg/ .`): print(`---------------------------------------`): print(`For a list of the Supporting procedures type ezra1();, 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 STORY procedures type ezraSt();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): print(`---------------------------------------`): print(`For a list of the MAIN procedures type ezra();, for help with`): print(`a specific procedure, type ezra(procedure_name); .`): print(``): print(`---------------------------------------`): with(combinat): ezraSi:=proc() if args=NULL then print(` The Simulations procedures are: OneGame, OneRoll, ManyGames `): print(``): else ezra(args): fi: end: ezraSt:=proc() if args=NULL then print(` The STORY procedures are: BookEk1, BookEk1J, BookEk2, BookEk2J, BookNum, BookNum2E, BookSet, BookSet2E `): print(`Paper, PaperEk1, PaperEk1J, PaperEk2, PaperEk2J, PaperNum, PaperSet `): print(` Prop, PropEk1, PropEk1J, PropEk2, PropEk2J, PropNum, PropSet `): print(``): else ezra(args): fi: end: ezra1:=proc() if args=NULL then print(` The supporting procedures are: AlgToSeq, Alpha, Ave1NuId, Eqab, FairGame, Momk, MOMStoScaled, NuMoms, NgfSlow, NSgf, NuWs, ScToSeq, ScabE `): print(``): else ezra(args): fi: end: ezra:=proc() if args=NULL then print(`The main procedures are: Ave1, Ave1Nu, ExF2m1, MyIden, MOMSk, MOMSkN, Ngf, NgfG, NuW, Scab, ScPR, ScX, Soab, SoabE , SoABOVE, SoABOVEp `): elif nargs=1 and args[1]=AlgToSeq then print(`AlgToSeq(F,f,t,K): inputs a polynomial F in t and f, variables t, and f, and a positive integer K, outputs`): print(`the first K+1 terms, starting at n=1 for the coefficients of the formal power series f(t) satisfying`): print(`F(f(t),t)=0. It is asumed that it can be written as f=C+t*Q(f,t)`): elif nargs=1 and args[1]=Alpha then print(`Alpha(f,x,N): Given a probability generating function`): print(`f(x) (a polynomial, rational function and possibly beyond)`): print(` returns a list, of length N, whose `): print(` (i) First entry is the average `): print(`(ii): Second entry is the variance `): print(`for i=3...N, the i-th entry is the so-called alpha-coefficients`): print(`that is the i-th moment about the mean divided by the`): print(`variance to the power i/2 (For example, i=3 is the skewness`): print(` and i=4 is the Kurtosis) `): 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(`Alpha(((1+x)/2)^100,x,4); `): elif nargs=1 and args[1]=Ave1 then print(`Ave1(N,P,f1): The polynomial in f1 one of whose root is the expected duration of the N,P game. Try:`): print(`Ave1({[1,2/3]},{[1,1/3]},f1);`): elif nargs=1 and args[1]=Ave1NuId then print(`Ave1NuId(N,P,,K1,n0): An approximation for the expected number of rounds for generalized (N,P) game for reaching >=n0 for the first time. `): print(`It uses the truncated prob. generating function up to K1 terms. It also tries to identify the number`): print(`Try: `): print(` Ave1Nu({[1,1/2]},{[2,1/2]},1000,1); `): print(`[seq(Ave1NuId(FairGame({2,-1}),2000,i),i=1..4)]; `): elif nargs=1 and args[1]=Ave1Nu then print(`Ave1Nu(N,P,,K1,n0): An approximation for the expected number of rounds for generalized (N,P) game for reaching >=n0 for the first time. `): print(`It uses the truncated prob. generating function up to K1 terms. It does not try to identify the number `): print(`Try: `): print(` Ave1Nu({[1,1/2]},{[2,1/2]},1000,1); `): elif nargs=1 and args[1]=BookEk1 then print(`BookEk1(L,t,K): Inputs a positive integer L and outsputs all the propositions of the form PropEk1(N,P,t,K,MIS) (q.v.)`): print(`for each non-empty subsets N,P, of of {1, ...,L}. Try:`): print(`BookEk1(3,t,40);`): elif nargs=1 and args[1]=BookEk1J then print(`BookEk1J(L,K): Inputs a positive integer L and outsputs all the propositions of the form PropEk1J(N,P,K,MIS) (q.v.)`): print(`for each non-empty subsets N,P, of of {1, ...,L}. Try:`): print(`BookEk1J(5,40);`): elif nargs=1 and args[1]=BookEk2 then print(`BookEk2(L,t,K): Inputs a positive integer L and outsputs all the propositions of the form PropEk2(n,p,t,K,MIS) (q.v.)`): print(`for all 1<=n0. try:`): print(`BookNum2E(10,2,300,500);`): elif nargs=1 and args[1]=BookSet then print(`BookSet(L,k,K1,K2,f,eps): outputs a book with all the PropSet(S,k,K1,K2,f,eps,MIS) (q.v.) where S consists of`): print(`all the possible non-empty subsets of {-1, ..., -L} union all non-empty subsets of {1,...,L}. Try:`): print(`BookSet(2,2,300,500,f,0.1);`): elif nargs=1 and args[1]=BookSet2E then print(`BookSet2E(L,k,K1,K2,f,eps): outputs a book with all the PropSet(S,k,K1,K2,f,eps,MIS) (q.v.) where S consists of`): print(`one negative ane one positive integer from 1 to L and their sum is positive. Try: `): print(`BookSet2E(2,2,300,500,f,0.1);`): elif nargs=1 and args[1]=Eqab then print(`Eqab(a,b,f,x,Down,Up): inputs non-negative integers a and b, symbols f and x, and sets of positive integers Down and Up`): print(` outputs the algebraic equation for f[a,b], the weight-enumerator of walks that start at [0,-a] and end at [n,-b], `): print(`for some n following the down steps of Down and up steps of Up, and always staying weakly below the x-axis. It expressed f[a,b] in`): print(`terms of f[c,d]'s for other (or the same [a,b]). It also returns the "children" those f[c,d] used. Try: `): print(` Eqab(0,0,f,x,{1},{1}); `): elif nargs=1 and args[1]=ExF2m1 then print(`ExF2m1(n): The exact formula (obtained by semi-rigorous experimental mathematics) for the expected number of`): print(`moves in a "one step forward two steps backwards random walk" until reaching a location >=n for the first time.`): print(`In terms of the Golden ratio`): print(`Try:`): print(`ExF2m1(10);`): elif nargs=1 and args[1]=FairGame then print(`FairGame(S): Given a set of positive and negative integers, outputs the pair N,P such they are all equally likley. Try:`): print(`FairGame({1,2,-3});`); elif nargs=1 and args[1]=ManyGames then print(`ManyGames(N,P,n1,K1,K2,k), plays OneGame(N,P,n1,K1) K2 times and returns the statistical information. `): print(`a list of length 2, the first is the`): print(`the statistical information [expectation, variance, ...] and the second is the probability of succeeding in K2 moves`): print(`Try: `): print(`ManyGames({[1,1/2]},{[1,1/2]},1,100,3000,4); `): elif nargs=1 and args[1]=Momk then print(`Momk(N,P,fk,k): The polynomial in f1 one of whose root is the k-th moment of the r.v. "duration". Try:`): print(`Momk({[1,2/3]},{[1,1/3]},f2,2);`): elif nargs=1 and args[1]=MOMSk then print(`MOMSk(N,P,f,k): inputs N and P (prob. distribution for negative set N and positive set P), a symbol f, and a positive integer k`): print(`outputs a list of length k+1 whose first entry is the algebraic equation in f[0] for the probability`): print(`(one of whose roots should be 1 if the expected progress is positive), followed by the algebraic equations in f[i] for`): print(`the i-th moment, for i from 1 to K. Note: NOT moment about the mean. Try:`): print(`MOMSk({[1,2/3]},{[1,1/3]},f,4);`): elif nargs=1 and args[1]=MOMSkN then print(`MOMSkN(N,P,f,k,eps): Like MOMSk(N,P,f,k) (q.v.) but in addition it gives the numerical value of each moment. eps is a "tolerance parameter". Try:`): print(`The output consists of a list of length 2.`): print(`The first entry is the list of pairs [Algebaric Equation satisfied by i-th moment,Floating Point value] for i=0 (i.e. the pob. of succeeding)`): print(`followed by (possibly conditional) expectation, variance all the way to the K-th moment.`): print(`The second item is a list of length 2. The first one is a summary of the numerical values of the exepctation, etc., and the second`): print(`is the prob. if winning (in other words the second entry of the first entry of the first entry. If it fails to pin-point the`): print(`numerical value, it just returns MOMSk(N,P,f,K). You can try and make eps larger. Try: `): print(`MOMSkN({[1,2/3]},{[1,1/3]},f,4,0.1);`): elif nargs=1 and args[1]=MOMSkNA then print(`MOMSkNA(N,P,k,K1): An approximation to MOMSkN(N,P,f,k,eps)[2] (q.v.) using the first K1 terms of the`): print(`the probability generating function. MUCH faster than MOMSkN. This is one of the main points of our article. Try:`): print(`MOMSkNA({[1,1/3]},{[1,2/3]},4,300);`): elif nargs=1 and args[1]=MOMSkNSi then print(`MOMSkNSi(N,P,k,K1,K2): A very crude approximation to MOMSkN(N,P,f,k,eps)[2] (q.v.) using simulations `): print(`up to K1 rounds, with K2 games`): print(`MOMSkNSi({[1,1/3]},{[1,2/3]},4,300,1000);`): elif nargs=1 and args[1]=MOMStoScaled then print(`MOMStoScaled(L): inputs a list of moments converts it to scaled moments about the mean. Try`): print(`MOMStoScaled([1,4,6,100]);`): elif nargs=1 and args[1]=MyIden then print(`MyIden(alpha,N,K): inputs a floating-point number alpha, and a positive non-square pos. integer N, outputs the`): print(`pair [a,b] such that a*sqrt(N)-b-alpha is closest wotj b<=K, where a= round((a+b)/sqrt(N)):`): elif nargs=1 and args[1]=Ngf then print(`Ngf(N,P,t,K): the truncated probability generating function, up to t^K, of the (N,P) walk until reaching >=1 for the first time. Try:`): print(`Ngf({[1,1/2]},{[1,1/2]},t,300);`): elif nargs=1 and args[1]=NgfG then print(`NgfG(N,P,t,K,n0): the truncated probability generating function, up to t^K, of the (N,P) walk until reaching >=n0 for the first time. Try:`): print(`NgfG({[1,1/2]},{[1,1/2]},t,20,2);`): elif nargs=1 and args[1]=NgfSlow then print(`NgfSlow(N,P,t,K): the first K terms of the probability generating function of the (N,P) walk. SLOW way. Try:`): print(`NgfSlow({[1,1/2]},{[1,1/2]},t,10);`): elif nargs=1 and args[1]=NSgf then print(`NSgf(P,K,t,n0): inputs a probability distributions P and N each of the form [i,Pi] where i is a positive and negative integer respectively`): print(` and Pi is the prob. of getting i dollars, and the game ends as soon as you have have >=n0 dollars`): print(`computes the first K terms of the probability generating function, in t, for the first time it gets above ground`): print(`NSgf([[1,2/3],[-1,1/3]],50,t,1);`): elif nargs=1 and args[1]=NuMoms then print(`NuMoms(N,P,K1,K2): An approximation to the values of MOMSk(N,P,f,K1) using Ngf(N,P,t,K2). Try: `): print(`NuMoms(FairGame({2,-1}),4,200);`): elif nargs=1 and args[1]=NuW then print(`NuW(a,b,N,P,K): inputs sets of positive integers, N and P, and a posiive inetger K, outputs the list of the first K`): print(`terms, starting at n=1 of the sequence enumerating words of length n in the alphabet -N, P, such that the`): print(`it starts at (0,-a) and ends in (n,-b) and always stays weakly below the x-axis. Done the FAST way, using the scheme.`): print(`Try: `): print(`NuW(0,0,{1,2},{1,2},20); `): elif nargs=1 and args[1]=NuWs then print(`NuWs(a,b,N,P,K): inputs sets of positive integers, N and P, and a posiive inetger K, outputs the list of the first K`): print(`terms, starting at n=1 of the sequence enumerating words of length n in the alphabet -N, P, such that the`): print(`it starts at (0,-a) and ends in (n,-b) and always stays weakly below the x-axis. Done the SLOW way, by first finding the algebaric eqution satisfied`): print(`by the generating function. Try:`): print(`NuWs(0,0,{1,2},{1,2},20); `): elif nargs=1 and args[1]=OneGame then print(`OneGame(N,P,n1,K): inputs sets N of P where N consists of pairs [i,ProbOf(-i)] and P consists of pairs [i,Prob(i)]`): print(`plays up to to reaching n1, using <=K rounds. Try:`): print(`OneGame({[1,1/2]},{[1,1/2]},1,100);`): elif nargs=1 and args[1]=OneRoll then print(`OneRoll(L): inputs a list of positive rational mumbers that add up to 1 and outputs`): print(` a random outcome from 1 to nops(L) according to this prob. dist.`): print(` Try: `): print(`OneRoll([2/3,1/4,1/12]);`): ###Start help for Papers elif nargs=1 and args[1]=Paper then print(`Paper(N,P,k,K1,K2,f,eps): Inputs sets N and P whose elements are {[i,pi]} where in N the pair [i,pi] means`): print(`that the probability of -i is pi, and [i,pi] in P means that the probability of i is pi, a (not too large) positive`): print(`integer k, and fairly large positive integers K1 and K2, a symbol f, and a small (but no too small) positive number eps`): print(`for the input of MOMSkN(N,P,k,f,eps)). Outputs a computer-generated game about the duration of reaching a goal of`): print(`having POSITIVE capital, if you start with 0 capital, and at each round you gain or lose according`): print(`to the "roulette", and your goal in life is reach a positive capital, and you quit as soon as that happens. Try:`): print(` Paper({[1,1/3]},{[1,2/3]}, 4,200,300,f,0.1); `): print(` Paper({[1,1/3],[2,1/3]},{[2,1/3]}, 2,200,300,f,0.1);`): print(`Paper({[1,1/4],[2,1/8]},{[1,1/4],[2,3/8]}, 2,200,300,f,0.1);`): elif nargs=1 and args[1]=PaperEk1 then print(`PaperEk1(N,P,t,K): inputs sets of positive integers N and P, a variable t and a positive integer K outputs`): print(`an article about the generating function of the sequece for the number of walks starting at the origin with steps -n (for n in N) and p (or p in P) `): print(`ending at the origin and NEVER going above it, as well as first K terms. Try:`): print(`PaperEk1({1},{1},t,40);`): elif nargs=1 and args[1]=PaperEk1J then print(`PaperEk1J(N,P,K): An article about the first K terms of the `): print(` the sequece for the number of walks starting at the origin with steps -n (for n in N) and p (or p in P) `): print(`ending at the origin and NEVER going above it, as well as first K terms. Try:`): print(`PaperEk1J({1},{1},40);`): elif nargs=1 and args[1]=PaperEk2 then print(`PaperEk2(n,p,t,K): inputs positive integers n and p, a variable t and a positive integer K outputs`): print(`an article about the generating function of the sequece for the number of walks starting at the origin with steps -n and p `): print(`ending at the origin and NEVER going above it, as well as first K terms. Try:`): print(`PaperEk2(2,3,t,30);`): elif nargs=1 and args[1]=PaperEk2J then print(`PaperEk2J(n,p,K): inputs positive integers n and p, a variable t and a positive integer K outputs`): print(`an article about the first K terms of the sequece for the number of walks starting at the origin with steps -n and p `): print(`ending at the origin and NEVER going above it. Try:`): print(`PaperEk2J(2,3,30);`): elif nargs=1 and args[1]=PaperNum then print(`PaperNum(N,P,k,K1,K2): Inputs sets N and P whose elements are {[i,pi]} where in N the pair [i,pi] means`): print(`that the probability of -i is pi, and [i,pi] in P means that the probability of i is pi, a (not too large) positive`): print(`integer k, and fairly large positive integers K1 and K2, a symbol f, and a small (but no too small) positive number eps`): print(`Outputs a computer-generated game about the duration of reaching a goal of`): print(`having POSITIVE capital, if you start with 0 capital, and at each round you gain or lose according`): print(`to the "roulette", and your goal in life is reach a positive capital, and you quit as soon as that happens. `): print(`It is Purely Numeric, using the Naive approximation algorithm, hence can do much more.Try:`): print(`PaperNum({[1,1/3]},{[1,2/3]}, 4,200,300);`): elif nargs=1 and args[1]=PaperSet then print(`PaperSet(S,k,K1,K2,f,eps): Inputs a set of positive and negative integers `): print(`outputs a paper about the game where each member of S is equally likely. Try:`): print(`PaperSet({2,-1}, 4,200,300,f,0.1);`): print(`PaperSet({3,-1}, 2,200,300,f,0.1);`): print(`PaperSet({3,-2}, 2,200,300,f,0.1);`): ###end help for Papers ###Start help for Prop elif nargs=1 and args[1]=Prop then print(`Prop(N,P,k,K1,K2,f,eps,MIS): Inputs sets N and P whose elements are {[i,pi]} where in N the pair [i,pi] means`): print(`that the probability of -i is pi, and [i,pi] in P means that the probability of i is pi, a (not too large) positive`): print(`integer k, and fairly large positive integers K1 and K2, a symbol f, and a small (but no too small) positive number eps`): print(`for the input of MOMSkN(N,P,k,f,eps)). Outputs a PROPOSITION numbered MIS, that computer-generated proposition about the duration of reaching a goal of`): print(`having POSITIVE capital, if you start with 0 capital, and at each round you gain or lose according`): print(`to the "roulette", and your goal in life is reach a positive capital, and you quit as soon as that happens. Try:`): print(`Prop({[1,1/3]},{[1,2/3]}, 4,200,300,f,0.1,10);`): elif nargs=1 and args[1]=PropEk1 then print(`PropEk1(N,P,t,K,MIS): Like PaperEk1(N,P,t,K) (q.v.), but instead of a paper, outputs a proposition numbered MIS. Try:`): print(`PropEk1({1},{1},t,40,5);`): elif nargs=1 and args[1]=PropEk1J then print(`PropEk1J(N,P,K,MIS): Like PaperEk1J(N,P,t,K) (q.v.), but instead of a paper, outputs a proposition numbered MIS. Try:`): print(`PropEk1J({1},{1},40,11);`): elif nargs=1 and args[1]=PropEk2 then print(`PaperEk2(n,p,t,K,MIS): inputs positive integers n and p, a variable t and a positive integer K outputs`): print(`an article about the generating function of the sequece for the number of walks starting at the origin with steps -n and p `): print(`ending at the origin and NEVER going above it, as well as first K terms. Try:`): print(`PropEk2(2,3,t,30,10);`): elif nargs=1 and args[1]=PaperEk2J then print(`PropEk2J(n,p,K,MIS): Like PaperEk2J(n,p,K) but as Prop. numbered MIS. Try:`): print(`PropEk2J(2,3,30,11);`): elif nargs=1 and args[1]=PropNum then print(`PropNum(N,P,k,K1,K2,MIS): Like PaperNum(N,P,k,K1,K2) (q.v.) but instead of a paper, the output is a proposition numered MIS. Try:`): print(`PropNum({[1,1/3]},{[1,2/3]}, 4,200,300,3);`): elif nargs=1 and args[1]=PropSet then print(`PropSet(S,k,K1,K2,f,eps,MIS): Inputs a set of positive and negative integers `): print(`outputs a proposition numbered, MIS, about the game where each member of S is equally likely. Try:`): print(`PropSet({2,-1}, 4,200,300,f,0.1,5);`): ###End help for Prop elif nargs=1 and args[1]=Scab then print(`Scab(a,b,f,x,Down,Up): inputs non-negative integers a and b, symbols f and x and sets of positive integers Down and Up`): print(` outputs the pair of lists L1,L2 where L1 is the list whose first entry is f[a,b], and the remaining entries`): print(`are all the f[c,d] needed, and the second list are the corresponding equations. Try:`): print(`Scab(0,0,f,x,{1},{1}); `): elif nargs=1 and args[1]=ScX then print(`ScX(f,x,Down,Up,X): inputs symbols f and x and sets of positive integers Down and Up`): print(` and a symbol X for the desired quantity`): print(`outputs the pair of lists L1,L2 where L1 is the list whose first entry is the weight-enumerator that`): print(`start at (0,0), use the steps (1,-d), (1,u) for d in Down and u in Up and always stay weakly below the x-axis`): print(`EXCEPT the very last step whose endpoint is ABOVE the x-axis. Try:`): print(`ScX(f,x,{1},{1},X);`): elif nargs=1 and args[1]=ScabE then print(`ScabE(a,b,f,t,Down,Up): Like Scab(a,b,f,x,Down,Up) but with x[-n] and x[p] replaced by t. Try:`): print(`ScabE(0,0,f,t,{1},{1});`): elif nargs=1 and args[1]=ScToSeq then print(`ScToSeq(L1,L2,t,K): Given a scheme L1,L2, in terms of the variable t, finds the first K terms. Try:`): print(`ScToSeq(ScabE(0,0,f,t,{1},{1}),t,20);`): elif nargs=1 and args[1]=ScPR then print(`ScPR(f,t,N,P): The scheme for N and P for the probability generating function for duration. TryL`): print(`ScPR(f,t,{[1,2/3]},{[1,1/3]});`): elif nargs=1 and args[1]=Soab then print(`Soab(a,b,f,x,N,P): The algebraic equation in f(x), where f(x) is the generating function of the sequence of walks, according to weight`): print(`starting at (0,-a) and ending at (n,-b) for some n, and never going above the x-axis. Try:`): print(`Soab(0,0,f,x,{1},{1});`): elif nargs=1 and args[1]=SoabE then print(`SoabE(a,b,f,t,N,P): solves the enumeartion problem only keeping track of the number of steps but not their individual nature. Try:`): print(`SoabE(0,0,f,t,{1},{1});`): elif nargs=1 and args[1]=SoABOVE then print(`SoABOVE(f,x,N,P): The algebraic equation in f(x), where f(x) is the (ordinary) generating function enumerating walks, according to the weights`): print(`x[-n] in in N, x[p] p in P that start at 0, never go above the x-axis EXCEPT for the last step, that must end above the x-axis. Try`): print(`starting and ending at x-axis and never going above the x-axis. Try:`): print(`SoABOVE(f,x,{1},{1});`): print(` `): elif nargs=1 and args[1]=SoABOVEp then print(`SoABOVEp(f,t,N,P): The algebraic equation in f=f(t), where f(t) is the probability `): print(`generating function of the random variable, number of walks until reaching a positive amount for the first time`): print(`where the walk is according to the distribution given by N and P`): print(`where N is a set of pairs [n,prob. of -n], and P is a set of pairs [p,prob. of p]. Try:`): print(`SoABOVEp(f,t,{[1,2/3]},{[1,1/3]});`): else print(`There is no ezra for`,args): fi: end: ###From HISTABRUT #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: #Alpha(f,x,N): Given a probability generating function #f(x) (a polynomial, rational function and possibly beyond) #returns a list, of length N, whose #(i) First entry is the average #(ii): Second entry is the variance #for i=3...N, the i-th entry is the so-called alpha-coefficients #that is the i-th moment about the mean divided by the #variance to the power i/2 (For example, i=3 is the skewness #and i=4 is the Kurtosis) #If f(1) is not 1, than it first normalizes it by dividing #by f(1) (if it is not 0) . #For example, try: #Alpha(((1+x)/2)^100,x,4); Alpha:=proc(f,x,N) local gu,i: gu:=AveAndMoms(f,x,N): if gu=FAIL then RETURN(gu): fi: if gu[2]=0 then print(`The variance is 0`): RETURN(FAIL): fi: [gu[1],gu[2],seq(gu[i]/gu[2]^(i/2),i=3..N)]: end: #MOMStoScaled(L): inputs a list of moments converts it to scaled moments about the mean. Try # MOMStoScaled:=proc(L) local mu,k,L1,n: if not (type(L,list) and nops(L)>=2) then RETURN(FAIL): fi: mu:=L[1]: L1:=[mu,seq(add(binomial(n,k)*(-mu)^k*L[n-k],k=0..n-1)+(-mu)^n,n=2..nops(L))]: if L1[2]=0 then RETURN(FAIL): fi: [op(1..2,L1),seq(L1[n]/L1[2]^(n/2),n=3..nops(L1))]: end: MOJustToTry:=proc(f,x,K) local lu,L,i: lu:=f/subs(x=1,f): L:=[]: for i from 1 to K do lu:=x*diff(lu,x): L:=[op(L),subs(x=1,lu)]: od: L: end: ###End from HISTABRUT Digits:=20: #Eqab(a,b,f,x,Down,Up): inputs non-negative integers a and b, symbols f and x, and sets of positive integers Down and Up #integers P, outputs the algebraic equation for f[a,b] the weight-enumerator of walks that start at [0,-a] and end at [n,-b] #for some n following the set of steps N union P, and always staying weakly below the x-axis. It expressed f[a,b] in #terms of f[c,d]'s for other (or the same [a,b]). It also returns the "children" those f[c,d] used #Try: #Eqab(0,0,f,x,{-1},{1}); Eqab:=proc(a,b,f,x,N,P) local n,p: if not (type(a,integer) and type(b,integer) and type(f,symbol) and type(x,symbol) and type(N,set) and type(P,set) ) then print(`bad input`): RETURN(FAIL): fi: if not (a>=0 and b>=0 and min(op(P))>=1 and min(op(N))>=1) then print(`bad input`): RETURN(FAIL): fi: if a=0 and b=0 then 1+ (add(add(x[-n]*f[n-1,p-1]*x[p],n in N), p in P))*f[0,0], {seq(seq( [n-1,p-1],n in N), p in P)}: elif a>0 and b>0 then f[a-1,b-1]+add(f[a-1,p-1]*x[p], p in P)*f[0,b], {[a-1,b-1], seq( [a-1,p-1], p in P),[0,b]}: elif a=0 and b>0 then f[0,0]*add(x[-n]*f[n-1,b-1],n in N), {seq( [n-1,b-1], n in N),[0,0]}: elif a>0 and b=0 then add(f[a-1,p-1]*x[p], p in P)*f[0,0] , {seq( [a-1,p-1], p in P), [0,0]}: else FAIL: fi: end: #Scab(a,b,f,x,Down,Up): inputs non-negative integers a and b, symbols f and x and sets of positive integers Down and Up # outputs the pair of lists L1,L2 where L1 is the list whose first entry is f[a,b], and the remaining entries #are all the f[c,d] needed, and the second list are the corresponding equations. Try: #Scab(0,0,f,x,{1},{1}) Scab:=proc(a,b,f,x,N,P) local gu,T,StillToDo, AlreadyDone,AllGuys,g,lu,L1,L2,i1: option remember: AlreadyDone:={}: StillToDo:={[a,b]}: while StillToDo<>{} do g:=StillToDo[1]: lu:=Eqab(op(g),f,x,N,P): AlreadyDone:=AlreadyDone union {g}: T[g]:=lu[1]: StillToDo:=(StillToDo union lu[2] ) minus AlreadyDone: od: AllGuys:=AlreadyDone minus {[a,b]}: L1:=[f[a,b],seq(f[op(AllGuys[i1])],i1=1..nops(AllGuys))]: L2:=[T[[a,b]],seq(T[AllGuys[i1]],i1=1..nops(AllGuys))]: L1,L2: end: #ScabE(a,b,f,t,Down,Up): Like Scab(a,b,f,x,Down,Up) but with x[-n] and x[p] replaced by t. Try: #ScabE(0,0,f,t,{1},{1}) ScabE:=proc(a,b,f,t,N,P) local x,gu,n,p: option remember: gu:=Scab(a,b,f,x,N,P): gu[1],subs({seq(x[-n]=t, n in N),seq(x[p]=t, p in P)},gu[2]): end: #Soab(a,b,f,x,N,P): The algebraic equation in f(x), where f(x) is the generating function of the sequence of walks, according to weight #starting at (0,-a) and ending at (n,-b) for some n, and never going above the x-axis. Try: #Soab(0,0.f,x,{1},{1}); Soab:=proc(a,b,f,x,N,P) local gu,var,eq,i: option remember: gu:=Scab(a,b,f,x,N,P): var:=gu[1]: var:=[op(2..nops(var),var),var[1]]: eq:={seq(gu[1][i]-gu[2][i],i=1..nops(var))}: subs(f[a,b]=f,Groebner[Basis](eq,plex(op(var)))[1]); end: #SoabE(a,b,f,t,N,P): solves the enumeartion problem only keeping track of the number of steps but not their individual nature. Try: #SoabE(0,0,f,t,{1},{1}); SoabE:=proc(a,b,f,t,N,P) local x,gu,var,eq,i,n,p: gu:=Scab(a,b,f,x,N,P): var:=gu[1]: var:=[op(2..nops(var),var),var[1]]: eq:={seq(gu[1][i]-gu[2][i],i=1..nops(var))}: eq:=subs({seq(x[-n]=t,n in N),seq(x[p]=t,p in P)},eq): subs(f[a,b]=f,Groebner[Basis](eq,plex(op(var)))[1]); end: #NuWs(a,b,N,P,K): inputs sets of positive integers, N and P, and a posiive inetger K, outputs the list of the first K #terms, starting at n=1 of the sequence enumerating words of length n in the alphabet -N, P, such that the #it starts at (0,-a) and ends in (n,-b) and always stays weakly below the x-axis. Done the SLOW way, by first finding the algebaric eqution satisfied #by the generating function. Try: #NuWs(0,0,{1,2},{1,2},20); NuWs:=proc(a,b,N,P,K) local f,t: AlgToSeq(SoabE(a,b,f,t,N,P),f,t,K): end: #AlgToSeq(F,f,t,K): inputs a polynomial F in t and f, variables t, and f, and a positive integer K, outputs #the first K+1 terms, starting at n=1 for the coefficients of the formal power series f(t) satisfying #F(f(t),t)=0. It is asumed that it can be written as f=C+t*Q(f,t) AlgToSeq:=proc(F,f,t,K) local gu,i,Q,lu1,lu2,lu3: gu:=coeff(coeff(F,f),t,0): if gu=0 then RETURN(FAIL): fi: Q:=(gu*f-F)/gu: lu1:=1: lu2:=expand(subs(f=lu1,Q)): lu2:=add(coeff(lu2,t,i)*t^i,i=0..K): while lu1<>lu2 do lu3:=taylor(subs(f=lu2,Q),t,K+1): lu3:=add(coeff(lu3,t,i)*t^i,i=0..K): lu1:=lu2: lu2:=lu3: od: [seq(coeff(lu2,t,i),i=1..K)]: end: Trunc1:=proc(P,t,K) local i,gu: gu:=taylor(P,t=0,K+1): add(coeff(gu,t,i)*t^i,i=0..K):end: #ScToSeq(L1,L2,t,K): Given a scheme L1,L2, in terms of the variable t, finds the first K terms. Try: #ScToSeq(ScabE(0,0,f,t,{1},{1}),t,20); ScToSeq:=proc(L1,L2,t,K) local lu1,lu2,lu3,i: lu1:=[1,0$(nops(L1)-1)]: lu2:=subs({seq(L1[i]=lu1[i],i=1..nops(L1))},L2): lu2:=[seq(Trunc1(lu2[i],t,K),i=1..nops(lu2))]: while lu1<>lu2 do lu3:=subs({seq(L1[i]=lu2[i],i=1..nops(L1))},L2): lu3:=[seq(Trunc1(lu3[i],t,K),i=1..nops(lu3))]: lu1:=lu2: lu2:=lu3: od: [seq(coeff(lu2[1],t,i),i=1..K)]: end: #NuW(a,b,N,P,K): inputs sets of positive integers, N and P, and a posiive inetger K, outputs the list of the first K #terms, starting at n=1 of the sequence enumerating path from (0,-a) to (n,-b) never going above the x-axis. Try: #NuW(0,0,{1,2},{1,2},30); NuW:=proc(a,b,N,P,K) local gu,f,t: gu:=ScabE(a,b,f,t,N,P): ScToSeq( gu, t,K): end: #ScX(f,x,Down,Up,X): inputs symbols f and x and sets of positive integers Down and Up #integers P, and a symbol X for the desired quantity #outputs the pair of lists L1,L2 where L1 is the list whose first entry is the weight-enumerator that #start at (0,0), use the steps (1,-d), (1,u) for d in Down and u in Up and always stay weakly below the x-axis #EXCEPT the very last step whose endpoint is ABOVE the x-axis. Try #ScX(f,x,{1},{1},X); ScX:=proc(f,x,N,P,X) local gu,L1,L2,i,KA,p: gu:=Scab(0,0,f,x,N,P): L1:=gu[1]: L2:=gu[2]: if {seq(seq(f[0,i],i=0..p-1),p in P)} minus convert(L1,set)<>{} then RETURN(FAIL): fi: KA:=add(x[p]*add(f[0,i],i=0..p-1),p in P): L1:=[X,op(L1)]: L2:=[KA,op(L2)]: L1,L2: end: #SoABOVE(f,x,N,P): The algebraic equation in f(x), where f(x) is the generating function of the sequence of walks, according to the weights #x[-n] in in N, x[p] p in P that start at 0, never go above the x-axis EXCEPT for the last step, that must end above the x-axis. Try #starting and ending at x-axis and never going above the x-axis. Try: #SoABOVE(f,x,{1},{1}); SoABOVE:=proc(f,x,N,P) local X,gu,var,eq,i: gu:=ScX(f,x,N,P,X): var:=gu[1]: var:=[op(2..nops(var),var),var[1]]: eq:={seq(gu[1][i]-gu[2][i],i=1..nops(var))}: subs(X=f,Groebner[Basis](eq,plex(op(var)))[1]); end: #SoABOVEpSLOW(f,t,N,P): The algebraic equation in f=f(t), where f(t) is the probability #generating function of the sequence of walks, according to the distribution given by N and P #where N is a set of pairs [n,prob. of -n], and P is a set of pairs [p,prob. of p]. Try: #SoABOVEpSLOW(f,t,{[1,2/3]},{[-1,1/3]}); SoABOVEpSLOW:=proc(f,t,N,P) local N1,P1,x,gu,n,p: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: N1:={seq(n[1],n in N)}: P1:={seq(p[1],p in P)}: gu:=SoABOVE(f,x,N1,P1): subs({seq(x[-n[1]]=t*n[2], n in N),seq(x[p[1]]=t*p[2], p in P)},gu): end: #Ave1(N,P,f1): The polynomial in f1 one of whose root is the expected duration of the N,P game. Try: #Ave1({[1,2/3]},{[1,1/3]},f1); Ave1:=proc(N,P,f1) local gu,f,t,gu1,lu: gu:=SoABOVEp(f,t,N,P) : gu1:=t*diff(gu,t)+diff(gu,f)*f1: lu:=Groebner[Basis]({gu1,gu},plex(f,f1))[1]; subs(t=1,lu): end: #Momk(N,P,fk,k): The polynomial in f1 one of whose root is the k-th moment of the r.v. "duration". Try: #Momk({[1,2/3]},{[1,1/3]},fk,2); Momk:=proc(N,P,fk,k) local gu,f,t,gu1,lu,f1,k1: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: gu:=SoABOVEp(f,t,N,P) : f1:=normal(-diff(gu,t)/diff(gu,f)): lu:=t*f1: for k1 from 2 to k do lu:=normal(t*diff(lu,t)+t*diff(lu,f)*f1): od: gu1:=numer(normal(lu-fk)): lu:= eliminate({gu1,gu},f)[2][1]; while subs(t=1,lu)=0 do lu:=normal(lu/(t-1)): od: subs(t=1,lu): end: #MOMSk(N,P,f,k): inputs N and P (prob. distribution for negative set N and positive set P, a symbol f, and a positive integer k #outputs a list of length K+1 whose first entry is the algebraic equation in f[0] for the probability #(one of whose roots should be 1 if the expected progress is positive), followed by the algebraic equations in f[i] for #the ith moment, for i from 1 to k. Note: NOT moment about the mean. Try: #MOMSk{[1,2/3]},{[1,1/3]},f,4); MOMSk:=proc(N,P,f,k) local k1,t,F: option remember: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: factor([subs(F=f[0],subs(t=1,SoABOVEp(F,t,N,P))), seq(subs(F=f[k1],Momk(N,P,F,k1)), k1=1..k)]) : end: #ScPR(f,t,N,P): The scheme for N and P for the probability generating function for duration/ #ScPR(f,t,{[1,2/3]},{[1,1/3]}); ScPR:=proc(f,t,N,P) local N1,P1,x,gu,n,p,X: option remember: if add(n[2], n in N)+add(p[2], p in P)<>1 then RETURN(FAIL): fi: N1:={seq(n[1],n in N)}: P1:={seq(p[1],p in P)}: gu:=ScX(f,x,N1,P1,X): gu[1],subs({seq(x[-n[1]]=t*n[2], n in N),seq(x[p[1]]=t*p[2], p in P)},gu[2]): end: #NgfSlow(N,P,t,K): The first K terms in the Maclaurin expansion of the prob. generating function in the game (N,P) and reaching positive for the first time #Try: #NgfSlow({[1,1/2]},{[1,1/2]},t,40); NgfSlow:=proc(N,P,t,K) local gu,f,i: gu:=ScToSeq( ScPR(f,t,N,P), t,K): add(gu[i]*t^i,i=1..K): end: #NSgf(P,K,t,n0): inputs a probability distributions P and N each of the form [i,Pi] where i is a positive and negative integer respectively # and Pi is the prob. of getting i dollars, and the game ends as soon as you have have >=n0 dollars #computes the first K terms of the probability generating function, in t, for the first time it gets above ground #NSgf([[1,2/3],[-1,1/3]],50,t,1); NSgf:=proc(P,K,t,n0) local gu,x,mu,lu,kha,i,j: option remember: lu:=add(P[i][2]*x^P[i][1],i=1..nops(P)): mu:=lu: gu:=0: for i from 1 to K do kha:=add(coeff(mu,x,j)*x^j,j=n0..degree(mu,x)): gu:=gu+subs(x=1,kha)*t^i: mu:=mu-kha: mu:=expand(mu*lu): od: gu: end: #Ngf(N,P,t,K): the first K terms of the probability generating function of the (N,P) walk. Try: #Ngf({[1,1/2]},{[1,1/2]},t,10); Ngf:=proc(N,P,t,K) local n: NSgf([seq([-n[1],n[2]],n in N),op(P)],K,t,1): end: #NgfG(N,P,t,K,n0): the first K terms of the probability generating function of the (N,P) walk until reaching >=n0 for the first time. Try: #NgfG({[1,1/2]},{[1,1/2]},t,10,2); NgfG:=proc(N,P,t,K,n0) local n: NSgf([seq([-n[1],n[2]],n in N),op(P)],K,t,n0): end: #FairGame(S): Given a set of positive and negative integers, outputs the pair N,P such they are all equally likley FairGame:=proc(S) local s,N,P,k: if not (type(S,set) and {seq(type(s,integer), s in S)}={true}) or member(0,S) then print(`Bad input`): RETURN(FAIL): fi: k:=nops(S): N:={}: P:={}: for s in S do if s<0 then N:=N union {[-s,1/k]}: else P:=P union {[s,1/k]}: fi: od: N,P: end: #HakhiKarov(L,a,eps): inputs a list L and a number a, finds the member of L that is closet to a and checks that its difference from a is #<=eps in absolute value. Try: #HakhiKarov([3.14159,2.718,1.618],evalf(Pi),0.01); HakhiKarov:=proc(L,a,eps) local si, aluf,hal,i: if not (type(L,list) and type(a,numeric) and type(eps, numeric) and eps>0 and nops(L)>0) then print(`Bad input`): RETURN(FAIL): fi: aluf:=L[1]: si:=abs(1-a/L[1]): for i from 2 to nops(L) do hal:=abs(1-a/L[i]): if hal=eps then print(aluf, `did not make it`): RETURN(FAIL): fi: aluf: end: #NuMoms(N,P,K1,K2): An approximation to the values of MOMSk(N,P,f,K1) using Ngf(N,P,t,K2). Try: #NuMoms(FairGame({2,-1},4,200,20); NuMoms:=proc(N,P,K1,K2) local lu,ku,i,t: lu:=Ngf(N,P,t,K2): ku:=[subs(t=1,lu)]: for i from 1 to K1 do lu:=t*diff(lu,t): ku:=evalf([op(ku),subs(t=1,lu)]): od: ku: end: #MOMSkN(N,P,f,k,eps): Like MOMSk(N,P,f,k), but each algebraic equation has also the relevant root in floating-point with D1 digits MOMSkN:=proc(N,P,f,k,eps) local lu,kha,ku,i,mu,muPlus,t,ju,L,hakol: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: mu:=MOMSk(N,P,f,k): if mu=FAIL then RETURN(FAIL): fi: lu:=Ngf(N,P,t,200): ku:=[subs(t=1,lu)]: for i from 1 to k do lu:=t*diff(lu,t): ku:=evalf([op(ku),subs(t=1,lu)]): od: muPlus:=[]: L:=[]: for i from 0 to k do ju:=[fsolve(mu[i+1],f[i])]: if ju=[] then RETURN(mu): else kha:=HakhiKarov(ju,ku[i+1],eps): if kha=FAIL then RETURN(FAIL): else L:=[op(L),kha]: muPlus:=[op(muPlus),[mu[i+1],kha] ]: fi: fi: od: hakol:=L[1]: if hakol=0 then RETURN(FAIL): fi: L:=[op(2..nops(L),L)]/hakol: L:=MOMStoScaled(L): muPlus,[L,muPlus[1][2]]: end: ###Start simulation #OneRoll(L): inputs a list of positive rational mumbers that add up to 1 and outputs # a random outcome from 1 to nops(L) according to this prob. dist. #Try #OneRoll([2/3,1/4,1/12]); OneRoll:=proc(L) local i,M,L1,j,ra: if convert(L,`+`)<>1 then RETURN(FAIL): fi: if min(op(L))<0 then RETURN(FAIL): fi: M:=lcm(seq(denom(L[i]),i=1..nops(L))): L1:=[seq(M*L[i],i=1..nops(L))]: L1:=[seq(add(L1[j],j=1..i),i=1..nops(L))]: L1: M:=L1[nops(L1)]: ra:=rand(1..M)(): for j from 1 to nops(L1) while ra>L1[j] do od: j: end: #OneGame1(G,n1,K): #Given a prob. distrubution of steps (all forward) and a positive integer n1, simulates one game with the goal of getting to >=n1 . #OneGame1([[1,1/3],[3,1/3],[-4,1/3]],3,100): OneGame1:=proc(G,n1,K) local j,co,L,i1,i: j:=0: co:=0: L:=[seq(G[i1][2],i1=1..nops(G))]: for i from 1 to K while j1 and K2>1) then print(`Bad input`): RETURN(FAIL): fi: gu:=Ngf(N,P,t,K2): [evalf(Alpha(gu,t,K1)),evalf(subs(t=1,gu))]: end: #MOMSkNSi(N,P,k,K1,K2): A very crude approximation to MOMSkN(N,P,f,k,eps)[2] (q.v.) using simulations #up to K1 rounds, with K2 games #MOMSkNSi({[1,1/3]},{[1,2/3]},4,300,1000); MOMSkNSi:=proc(N,P,k,K1,K2): ManyGames(N,P,1,K1,K2,k): end: ################Start Papers #Paper(N,P,k,K1,K2,f,eps): Inputs sets N and P whose elements are {[i,pi]} where in N the pair [i,pi] means #that the probability of -i is pi, and [i,pi] in P means that the probability of i is pi, a (not too large) positive #integer k, and fairly large positive integers K1 and K2, a symbol f, and a small (but no too small) positive number eps #for the input of MOMSkN(N,P,k,f,eps)). Outputs a computer-generated game about the duration of reaching a goal of #having POSITIVE capital, if you start with 0 capital, and at each round you gain or lose according #to the "roulette", and your goal in life is reach a positive capital, and you quit as soon as that happens. Try: #Paper({[1,1/3]},{[1,2/3]}, 4,200,300,f,0.1); Paper:=proc(N,P,k,K1,K2,f,eps) local t0,gu,i,kama,k1,mu,lu,ku,vu,t: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: if not (type(k,integer) and k>1) then print(k, `should be an integer larger than 1`): RETURN(FAIL): fi: if not type(K1,integer) and type(K2,integer) and K1>10 and K2>10 then print(K1,K2, `should be integers larger than 10`): RETURN(FAIL): fi: if not type(f,symbol) then print(f, `should be a symbol`): RETURN(FAIL): fi: if not (type(eps,numeric) and eps>0 and eps<1) then print(eps, `should be a number between 0 and 1`): RETURN(FAIL): fi: t0:=time(): print(``): print(`Statistical Analysis of the number of Rounds until you have at least ONE dollar`): print(`In a Casino with a Certain Roulette `): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`Once upon a time there was a casino with a strange roulette, where there were`, nops(N)+ nops(P), `possible outcomes as follows. `): print(``): print(`Regarding losing`): print(``): for i from 1 to nops(N) do print(`You lose`, N[i][1] , `dollars with probability`, N[i][2]): od: print(``): print(`Regarding winning`): print(``): for i from 1 to nops(P) do print(`You win`, P[i][1] , `dollars with probability`, P[i][2]): od: kama:=-add(N[i][1]*N[i][2],i=1..nops(N))+add(P[i][1]*P[i][2],i=1..nops(P)): print(`You start with a capital of 0 dollars, and have unlimited credit. Your goal in life is to gain a POSITIVE amount, and`): print(`you quit as soon as you reach that goal.`): print(`Note that the expected gain in ONE round is`, kama): if kama>0 then print(`Since it is positive, sooner or later you will reach your goal.`): elif kama=0 then print(`Since it is zero, sooner or later you will reach your goal, but it may take a long time but the exepctation and the higher moments are infinite`): print(`We do not treat this case`): RETURN(FAIL): else print(`Since it is negative, you may not be able to reach your goal.`): fi: vu:=SoABOVEp(f,t,N,P): print(`The probability generating function, let's call it f=f(t), for the random variable "duration of game" `): print(`in other words, the formal power series whose coefficient of, t^n is the probability of ending after n rounds satisfies the`): print(`following algebraic equation `): print(``): print(vu=0): print(``): print(`and in Maple notation`): print(``): lprint(vu=0): print(``): gu:=MOMSkN(N,P,f,k,eps): if gu=FAIL then print(`This ends this paper, since the parameter`, eps, `is too small`): RETURN(): fi: mu:=gu[2]: gu:=gu[1]: if kama>0 then print(`The expected duration, let's call it`, f[1], `is one of the roots of the polynomial `): print(factor(gu[2][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[2][1])): print(``): print(`and its numerical value is`): print(``): print(gu[2][2]): if k>=2 then print(`The second moment of the duration, let's call it`, f[2], `is one of the roots of the polynomial `): print(factor(gu[3][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[3][1])): print(``): print(`and its numerical value is`): print(``): print(gu[3][2]): print(``): print(`It follows that the variance is`, mu[1][2]): print(``): print(`and hence the standard-deviation is`, sqrt(mu[1][2])): fi: for k1 from 3 to k do print(`The `, k1, ` -th moment of the duration, let's call it`, f[k1], `is one of the roots of the polynomial `): print(factor(gu[k1+1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[k1+1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[k1+1][2]): print(``): print(`It follows that the scaled `, k1, `-th moment about the mean is`, mu[1][k1]): print(``): od: print(`To summarize the statistical data, expectation, variance, ... etc. is`): print(``): print(mu[1]): print(``): print(`Just to make sure, let's compare it with the much faster way of truncating the prob. generating function up to`, K1, `rounds `): lu:=MOMSkNA(N,P,k,K1): print(`The corresponding approximation is`): print(``): print(lu[1]): print(``): print(`and the probability that the goal is reached within`, K1, `rounds is `, lu[2]): print(``): print(`Finally, let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(`The corresponding crude approximation is`): print(``): print(ku[1]): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): fi: if kama<0 then print(`The probability of reaching your goal let's call it`, f[0], `is one of the roots of the polynomial `): print(factor(gu[1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[1][2]): print(`The (unconditoinal) expected duration, let's call it`, f[1], `is one of the roots of the polynomial `): print(factor(gu[2][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[2][1])): print(``): print(`and its numerical value is`): print(``): print(gu[2][2]): if k>=2 then print(`The second moment of the (unconditoinal) duration (before conditioning on success), let's call it`, f[2], `is one of the roots of the polynomial `): print(factor(gu[3][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[3][1])): print(``): print(`and its numerical value is`): print(``): print(gu[3][2]): print(``): print(`It follows that the (CONDITIONED upon success) variance is`, mu[1][2]): print(``): print(`and hence the standard-deviation is`, sqrt(mu[1][2])): fi: for k1 from 3 to k do print(`The (unconditoinal)`, k1, ` -th moment of the duration (before conditioning), let's call it`, f[k1], `is one of the roots of the polynomial `): print(factor(gu[k1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[k1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[k1][2]): print(``): print(`It follows that the CONDITIONED scaled `, k1, `-th moment about the mean is`, mu[1][k1]): print(``): od: print(`The probability that you would reach your goal is`,mu[2]): print(`and the statistical data, expectation, variance, ... etc. is`): print(``): print(mu[1]): print(``): print(`Just to make sure, let's compare it with the much faster way of truncating the prob. generating function up to`, K1, `rounds `): lu:=MOMSkNA(N,P,k,K1): print(`The corresponding approximation is`): print(``): print(lu[1]): print(``): print(`and the probability that the goal is reached within`, K1, `rounds is `, lu[2]): print(``): print(`Finally, let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(`The corresponding crude approximation is`): print(``): print(ku[1]): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): fi: if kama>0 then print(`So far we considered the Solitaire game. Now suppose that two players take turns, and the first player to reach`): print(`the goal of having positive capital is declared the winner. Assuming that they each are give at most`,K1, `turns `): print(`the probability of the first-to-move player winning is`): print(``): ku:=Ngf(N,P,t,K1): ku:=evalf((1+add(coeff(ku,t,i)^2,i=0..K1))/2): print(ku): print(``): fi: print(``): print(`This ends this article that took`, time()-t0, `seconds to generate. `): end: #PaperSet(S,k,K1,K2,f,eps): Inputs a set S of positive and negative numbers #and talks about a gambling game where each of them are equally likely #PaperSet({-1,2}, 4,200,300,f,0.1); PaperSet:=proc(S,k,K1,K2,f,eps) local bu,t0,gu,i,kama,k1,mu,lu,ku,N,P,vu,t: bu:=FairGame(S): if bu=FAIL then RETURN(FAIL): fi: N:=bu[1]: P:=bu[2]: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: if not (type(k,integer) and k>1) then print(k, `should be an integer larger than 1`): RETURN(FAIL): fi: if not type(K1,integer) and type(K2,integer) and K1>10 and K2>10 then print(K1,K2, `should be integers larger than 10`): RETURN(FAIL): fi: if not type(f,symbol) then print(f, `should be a symbol`): RETURN(FAIL): fi: if not (type(eps,numeric) and eps>0 and eps<1) then print(eps, `should be a number between 0 and 1`): RETURN(FAIL): fi: t0:=time(): if gu=FAIL then RETURN(FAIL): fi: print(``): print(`Statistical Analysis of the number of Rounds until you have at least ONE dollar`): print(`In a Casino with a Certain Roulette `): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`Once upon a time there was a casino with a strange roulette, where there were`, nops(N)+ nops(P), `possible outcomes as follows. `): print(``): print(`Regarding losing`): print(``): for i from 1 to nops(N) do print(`You lose`, N[i][1] , `dollars with probability`, N[i][2]): od: print(``): print(`Regarding winning`): print(``): for i from 1 to nops(P) do print(`You win`, P[i][1] , `dollars with probability`, P[i][2]): od: kama:=-add(N[i][1]*N[i][2],i=1..nops(N))+add(P[i][1]*P[i][2],i=1..nops(P)): print(``): print(`You start with a capital of 0 dollars, and have unlimited credit. Your goal in life is to gain a POSITIVE amount, and`): print(`you quit as soon as you reach that goal.`): print(``): print(`Note that the expected gain in ONE round is`, kama): if kama>0 then print(`Since it is positive, sooner or later you will reach your goal.`): elif kama=0 then print(`Since it is zero, sooner or later you will reach your goal, but it may take a long time but the exepctation and the higher moments are infinite`): print(`We do not treat this case`): RETURN(FAIL): else print(`Since it is negative, you may not be able to reach your goal.`): fi: vu:=SoABOVEp(f,t,N,P): print(`The probability generating function, let's call it f=f(t), for the random variable "duration of game" `): print(`in other words, the formal power series whose coefficient of, t^n is the probability of ending after n rounds satisfies the`): print(`following algebraic equation `): print(``): print(vu=0): print(``): print(`and in Maple notation`): print(``): lprint(vu=0): print(``): gu:=MOMSkN(N,P,f,k,eps): mu:=gu[2]: gu:=gu[1]: if kama>0 then print(`The expected duration, let's call it`, f[1], `is one of the roots of the polynomial `): print(factor(gu[2][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[2][1])): print(``): print(`and its numerical value is`): print(``): print(gu[2][2]): if k>=2 then print(`The second moment of the duration, let's call it`, f[2], `is one of the roots of the polynomial `): print(factor(gu[3][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[3][1])): print(``): print(`and its numerical value is`): print(``): print(gu[3][2]): print(``): print(`It follows that the variance is`, mu[1][2]): print(``): print(`and hence the standard-deviation is`, sqrt(mu[1][2])): fi: for k1 from 3 to k do print(`The `, k1, ` -th moment of the duration, let's call it`, f[k1], `is one of the roots of the polynomial `): print(factor(gu[k1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[k1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[k1][2]): print(``): print(`It follows that the scaled `, k1, `-th moment about the mean is`, mu[1][k1]): print(``): od: print(`To summarize the statistical data, expectation, variance, ... etc. is`): print(``): print(mu[1]): print(``): print(`Just to make sure, let's compare it with the much faster way of truncating the prob. generating function up to`, K1, `rounds `): lu:=MOMSkNA(N,P,k,K1): print(`The corresponding approximation is`): print(``): print(lu[1]): print(``): print(`and the probability that the goal is reached within`, K1, `rounds is `, lu[2]): print(``): print(`Finally, let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(`The corresponding crude approximation is`): print(``): print(ku[1]): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): fi: if kama<0 then print(`The probability of reaching your goal let's call it`, f[0], `is one of the roots of the polynomial `): print(factor(gu[1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[1][2]): print(`The expected duration, let's call it`, f[1], `is one of the roots of the polynomial `): print(factor(gu[2][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[2][1])): print(``): print(`and its numerical value is`): print(``): print(gu[2][2]): if k>=2 then print(`The second moment of the duration (before conditioning on success), let's call it`, f[2], `is one of the roots of the polynomial `): print(factor(gu[3][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[3][1])): print(``): print(`and its numerical value is`): print(``): print(gu[3][2]): print(``): print(`It follows that the (conditional upon success) variance is`, mu[1][2]): print(``): print(`and hence the standard-deviation is`, sqrt(mu[1][2])): fi: for k1 from 3 to k do print(`The `, k1, ` -th moment of the duration (before conditioning), let's call it`, f[k1], `is one of the roots of the polynomial `): print(factor(gu[k1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[k1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[k1][2]): print(``): print(`It follows that the conditioned scaled `, k1, `-th moment about the mean is`, mu[1][k1]): print(``): od: print(`The probability that you would reach your goal is`,mu[2]): print(`and the statistical data, expectation, variance, ... etc. is`): print(``): print(mu[1]): print(``): print(`Just to make sure, let's compare it with the much faster way of truncating the prob. generating function up to`, K1, `rounds `): lu:=MOMSkNA(N,P,k,K1): print(`The corresponding approximation is`): print(``): print(lu[1]): print(``): print(`and the probability that the goal is reached within`, K1, `rounds is `, lu[2]): print(``): print(`Finally, let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(`The corresponding crude approximation is`): print(``): print(ku[1]): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): fi: if kama>0 then print(`So far we considered the Solitaire game. Now suppose that two players take turns, and the first player to reach`): print(`the goal of having positive capital is declared the winner. Assuming that they each are give at most`,K1, `turns `): print(`the probability of the first-to-move player winning is`): print(``): ku:=Ngf(N,P,t,K1): ku:=evalf((1+add(coeff(ku,t,i)^2,i=0..K1))/2): print(ku): print(``): fi: print(``): print(`This ends this article that took`, time()-t0, `seconds to generate. `): end: #PaperNum(N,P,k,K1,K2): Inputs sets N and P whose elements are {[i,pi]} where in N the pair [i,pi] means #that the probability of -i is pi, and [i,pi] in P means that the probability of i is pi, a (not too large) positive #integer k, and fairly large positive integers K1 and K2, a symbol f, and a small (but no too small) positive number eps #Outputs a computer-generated game about the duration of reaching a goal of #having POSITIVE capital, if you start with 0 capital, and at each round you gain or lose according #to the "roulette", and your goal in life is reach a positive capital, and you quit as soon as that happens. #It is Purely Numeric, using the Naive approximation algorithm, hence can do much more.Try: #PaperNum({[1,1/3]},{[1,2/3]}, 4,200,300); PaperNum:=proc(N,P,k,K1,K2) local t0,i,kama,lu,ku,t: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: if not (type(k,integer) and k>1) then print(k, `should be an integer larger than 1`): RETURN(FAIL): fi: if not type(K1,integer) and type(K2,integer) and K1>10 and K2>10 then print(K1,K2, `should be integers larger than 10`): RETURN(FAIL): fi: t0:=time(): print(``): print(`Numerical Statistical Analysis of the number of Rounds until you have at least ONE dollar`): print(`In a Casino with a Certain Roulette `): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`Once upon a time there was a casino with a strange roulette, where there were`, nops(N)+ nops(P), `possible outcomes as follows. `): print(``): print(`Regarding losing`): print(``): for i from 1 to nops(N) do print(`You lose`, N[i][1] , `dollars with probability`, N[i][2]): od: print(``): print(`Regarding winning`): print(``): for i from 1 to nops(P) do print(`You win`, P[i][1] , `dollars with probability`, P[i][2]): od: print(``): print(`You start with a capital of 0 dollars, and have unlimited credit. Your goal in life is to gain a POSITIVE amount, and`): print(`you quit as soon as you reach that goal.`): print(``): kama:=-add(N[i][1]*N[i][2],i=1..nops(N))+add(P[i][1]*P[i][2],i=1..nops(P)): print(`Note that the expected gain in ONE round is`, kama): if kama>0 then print(`Since it is positive, sooner or later you will reach your goal.`): elif kama=0 then print(`Since it is zero, sooner or later you will reach your goal, but it may take a long time but the exepctation and the higher moments are infinite`): print(`We do not treat this case`): RETURN(FAIL): else print(`Since it is negative, you may not be able to reach your goal.`): fi: lu:=MOMSkNA(N,P,k,K1): print(``): print(`The probability that the goal is reached within`, K1, `rounds is `, lu[2]): print(``): print(`The approximate expectation, variance, and scaled moments up to the`,k, `-th are `): print(``): print(lu[1]): print(`Let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): print(`The crude approximations for the expectation, variance etc. are`): print(``): print(ku[1]): if kama>0 then print(`So far we considered the Solitaire game. Now suppose that two players take turns, and the first player to reach`): print(`the goal of having positive capital is declared the winner. Assuming that they each are give at most`,K1, `turns `): print(`the probability of the first-to-move player winning is`): print(``): ku:=Ngf(N,P,t,K1): ku:=evalf((1+add(coeff(ku,t,i)^2,i=0..K1))/2): print(ku): print(``): fi: print(``): print(`This ends this article that took`, time()-t0, `seconds to generate. `): end: #PaperEk1(N,P,t,K): inputs sets of positive integers N and P, a variable t and a positive integer K outputs #an article about the generating function of the sequece for the number of walks starting at the origin with steps -n (for n in N) and p (or p in P) #ending at the origin and NEVER going above it, as well as first K terms PaperEk1:=proc(N,P,t,K) local gu,a,n,mu,f,p,t0,lu: t0:=0: gu:=ScabE(0,0,f,t,N,P): mu:=ScToSeq(gu,t,K): print(``): print(`On the number of walks with set of steps`, {seq(-n, n in N), seq(p, p in P)}, `that start and end on the x-axis and never go above it`): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`Theorem: Let a(n) be the number of sequences of length n, in the alphabet`, {seq(-n, n in N), seq(p, p in P)}, `that add-up to zero and such that`): print(``): print(`their partial sums are NEVER positive. Then the first`, K, `terms are `): print(``): lprint(mu): print(``): lu:=SoabE(0,0,f,t,N,P): print(` The ordinary generating function, f=f(t)`): print(``): print(f(t)=Sum(a(n)*t^n,n=0..infinity)): print(``): print(`satisfies the algebraic equation `): print(``): print(lu=0): print(``): print(`and in Maple notation`): print(``): lprint(lu=0): print(``): print(`----------------------------------------`): print(``): print(`This ends this article that took`, time()-t0, `seconds to generate. `): print(``): end: #PaperEk2(n,p,t,K): inputs positive integers n and p, a variable t and a positive integer K outputs #an article about the generating function of the sequece for the number of walks starting at the origin with steps -n and p #ending at the origin and NEVER going above it, as well as first K terms. Try: #PaperEk2(2,3,t,30); PaperEk2:=proc(n,p,t,K) local gu,a,m,mu,f,t0,lu,i: t0:=0: gu:=ScabE(0,0,f,t,{n},{p}): mu:=ScToSeq(gu,t,(n+p)*K): mu:=[seq(mu[(n+p)*i],i=1..K)]: print(``): print(`On the number of walks with set of steps`, {-n,p}, `that start and end on the x-axis and never go above it`): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`Theorem: Let a(m) be the number of sequences of length`, (n+p)*m, `in the alphabet`, {-n,p}, `that add-up to zero and such that`): print(``): print(`their partial sums are NEVER positive. Then the first`, K, `terms are `): print(``): lprint(mu): print(``): lu:=SoabE(0,0,f,t,{n},{p}): lu:=simplify(subs(t=t^(1/(n+p)),lu)): print(` The ordinary generating function, f=f(t)`): print(``): print(f(t)=Sum(a(m)*t^m,m=0..infinity)): print(``): print(`satisfies the algebraic equation `): print(``): print(lu=0): print(``): print(``): print(`and in Maple notation`): print(``): lprint(lu=0): print(``): print(`----------------------------------------`): print(``): print(`This ends this article that took`, time()-t0, `seconds to generate. `): print(``): end: #PaperEk2J(n,p,K): inputs positive integers n and p, a variable t and a positive integer K outputs #an article about the number of walks starting at the origin with steps -n and p #ending at the origin and NEVER going above it, as well as first K terms. Try: #PaperEk2J(2,3,t,30); PaperEk2J:=proc(n,p,K) local gu,m,mu,f,t0,i,t: t0:=0: gu:=ScabE(0,0,f,t,{n},{p}): mu:=ScToSeq(gu,t,(n+p)*K): mu:=[seq(mu[(n+p)*i],i=1..K)]: print(``): print(`On the number of walks with set of steps`, {-n,p}, `that start and end on the x-axis and never go above it`): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`Theorem: Let a(m) be the number of sequences of length`, (n+p)*m, `in the alphabet`, {-n,p}, `that add-up to zero and such that`): print(``): print(`their partial sums are NEVER positive. Then the first`, K, `terms are `): print(``): lprint(mu): print(``): print(`----------------------------------------`): print(``): print(`This ends this article that took`, time()-t0, `seconds to generate. `): print(``): end: ################End Papers ################Start Propositions #Prop(N,P,k,K1,K2,f,eps,MIS): Inputs sets N and P whose elements are {[i,pi]} where in N the pair [i,pi] means #that the probability of -i is pi, and [i,pi] in P means that the probability of i is pi, a (not too large) positive #integer k, and fairly large positive integers K1 and K2, a symbol f, and a small (but no too small) positive number eps #for the input of MOMSkN(N,P,k,f,eps)). Outputs a computer-generated Proposition Numbered MIS, about the duration of reaching a goal of #having POSITIVE capital, if you start with 0 capital, and at each round you gain or lose according #to the "roulette", and your goal in life is reach a positive capital, and you quit as soon as that happens. Try: #Prop({[1,1/3]},{[1,2/3]}, 4,200,300,f,0.1,10); Prop:=proc(N,P,k,K1,K2,f,eps,MIS) local t0,gu,i,kama,k1,mu,lu,ku,vu,t: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: if not (type(k,integer) and k>1) then print(k, `should be an integer larger than 1`): RETURN(FAIL): fi: if not type(K1,integer) and type(K2,integer) and K1>10 and K2>10 then print(K1,K2, `should be integers larger than 10`): RETURN(FAIL): fi: if not type(f,symbol) then print(f, `should be a symbol`): RETURN(FAIL): fi: if not (type(eps,numeric) and eps>0 and eps<1) then print(eps, `should be a number between 0 and 1`): RETURN(FAIL): fi: t0:=time(): print(``): print(`---------------------------------------------`): print(``): print(`PROPOSITION No.`, MIS): print(``): print(`Suppose there is a casino with a strange roulette, where there were`, nops(N)+ nops(P), `possible outcomes as follows. `): print(``): print(`Regarding losing`): print(``): for i from 1 to nops(N) do print(`You lose`, N[i][1] , `dollars with probability`, N[i][2]): od: print(``): print(`Regarding winning`): print(``): for i from 1 to nops(P) do print(`You win`, P[i][1] , `dollars with probability`, P[i][2]): od: kama:=-add(N[i][1]*N[i][2],i=1..nops(N))+add(P[i][1]*P[i][2],i=1..nops(P)): print(``): print(`You start with a capital of 0 dollars, and have unlimited credit. Your goal in life is to gain a POSITIVE amount, and`): print(`you quit as soon as you reach that goal.`): print(``): print(`Note that the expected gain in ONE round is`, kama): if kama>0 then print(`Since it is positive, sooner or later you will reach your goal.`): elif kama=0 then print(`Since it is zero, sooner or later you will reach your goal, but it may take a long time but the exepctation and the higher moments are infinite`): print(`We do not treat this case`): RETURN(FAIL): else print(`Since it is negative, you may not be able to reach your goal.`): fi: vu:=SoABOVEp(f,t,N,P): print(`The probability generating function, let's call it f=f(t), for the random variable "duration of game" `): print(`in other words, the formal power series whose coefficient of, t^n is the probability of ending after n rounds satisfies the`): print(`following algebraic equation `): print(``): print(vu=0): print(``): print(`and in Maple notation`): print(``): lprint(vu=0): print(``): gu:=MOMSkN(N,P,f,k,eps): if gu=FAIL then print(`This ends this paper, since the parameter`, eps, `is too small`): RETURN(): fi: mu:=gu[2]: gu:=gu[1]: if kama>0 then print(`The expected duration, let's call it`, f[1], `is one of the roots of the polynomial `): print(factor(gu[2][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[2][1])): print(``): print(`and its numerical value is`): print(``): print(gu[2][2]): if k>=2 then print(`The second moment of the duration, let's call it`, f[2], `is one of the roots of the polynomial `): print(factor(gu[3][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[3][1])): print(``): print(`and its numerical value is`): print(``): print(gu[3][2]): print(``): print(`It follows that the variance is`, mu[1][2]): print(``): print(`and hence the standard-deviation is`, sqrt(mu[1][2])): fi: for k1 from 3 to k do print(`The `, k1, ` -th moment of the duration, let's call it`, f[k1], `is one of the roots of the polynomial `): print(factor(gu[k1+1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[k1+1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[k1+1][2]): print(``): print(`It follows that the scaled `, k1, `-th moment about the mean is`, mu[1][k1]): print(``): od: print(`To summarize the statistical data, expectation, variance, ... etc. is`): print(``): print(mu[1]): print(``): print(`Just to make sure, let's compare it with the much faster way of truncating the prob. generating function up to`, K1, `rounds `): lu:=MOMSkNA(N,P,k,K1): print(`The corresponding approximation is`): print(``): print(lu[1]): print(``): print(`and the probability that the goal is reached withing`, K1, `rounds is `, lu[2]): print(``): print(`Finally, let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(`The corresponding crude approximation is`): print(``): print(ku[1]): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): fi: if kama<0 then print(`The probability of reaching your goal let's call it`, f[0], `is one of the roots of the polynomial `): print(factor(gu[1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[1][2]): print(`The (unconditoinal) expected duration, let's call it`, f[1], `is one of the roots of the polynomial `): print(factor(gu[2][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[2][1])): print(``): print(`and its numerical value is`): print(``): print(gu[2][2]): if k>=2 then print(`The second moment of the (unconditoinal) duration (before conditioning on success), let's call it`, f[2], `is one of the roots of the polynomial `): print(factor(gu[3][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[3][1])): print(``): print(`and its numerical value is`): print(``): print(gu[3][2]): print(``): print(`It follows that the (CONDITIONED upon success) variance is`, mu[1][2]): print(``): print(`and hence the standard-deviation is`, sqrt(mu[1][2])): fi: for k1 from 3 to k do print(`The (unconditoinal)`, k1, ` -th moment of the duration (before conditioning), let's call it`, f[k1], `is one of the roots of the polynomial `): print(factor(gu[k1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[k1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[k1][2]): print(``): print(`It follows that the CONDITIONED scaled `, k1, `-th moment about the mean is`, mu[1][k1]): print(``): od: print(`The probability that you would reach your goal is`,mu[2]): print(`and the statistical data, expectation, variance, ... etc. is`): print(``): print(mu[1]): print(``): print(`Just to make sure, let's compare it with the much faster way of truncating the prob. generating function up to`, K1, `rounds `): lu:=MOMSkNA(N,P,k,K1): print(`The corresponding approximation is`): print(``): print(lu[1]): print(``): print(`and the probability that the goal is reached within`, K1, `rounds is `, lu[2]): print(``): print(`Finally, let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(`The corresponding crude approximation is`): print(``): print(ku[1]): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): fi: if kama>0 then print(`So far we considered the Solitaire game. Now suppose that two players take turns, and the first player to reach`): print(`the goal of having positive capital is declared the winner. Assuming that they each are give at most`,K1, `turns `): print(`the probability of the first-to-move player winning is`): print(``): ku:=Ngf(N,P,t,K1): ku:=evalf((1+add(coeff(ku,t,i)^2,i=0..K1))/2): print(ku): print(``): fi: print(``): print(`This ends this Proposition No.`, MIS, `that took `, time()-t0, `seconds to generate. `): print(``): print(`---------------------------------------------`): print(``): end: #PropSet(S,k,K1,K2,f,eps,MIS): Inputs a set S of positive and negative numbers #and talks about a gambling game where each of them are equally likely #PropSet({-1,2}, 4,200,300,f,0.1,MIS); PropSet:=proc(S,k,K1,K2,f,eps,MIS) local bu,t0,gu,i,kama,k1,mu,lu,ku,N,P,vu,t: bu:=FairGame(S): if bu=FAIL then RETURN(FAIL): fi: N:=bu[1]: P:=bu[2]: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: if not (type(k,integer) and k>1) then print(k, `should be an integer larger than 1`): RETURN(FAIL): fi: if not type(K1,integer) and type(K2,integer) and K1>10 and K2>10 then print(K1,K2, `should be integers larger than 10`): RETURN(FAIL): fi: if not type(f,symbol) then print(f, `should be a symbol`): RETURN(FAIL): fi: if not (type(eps,numeric) and eps>0 and eps<1) then print(eps, `should be a number between 0 and 1`): RETURN(FAIL): fi: t0:=time(): if gu=FAIL then RETURN(FAIL): fi: print(``): print(``): print(`---------------------------------------------`): print(``): print(`Proposition No.`, MIS): print(``): print(`In a certain casino, with a strange roulette, where there were`, nops(N)+ nops(P), `possible outcomes as follows. `): print(``): print(`Regarding losing`): print(``): for i from 1 to nops(N) do print(`You lose`, N[i][1] , `dollars with probability`, N[i][2]): od: print(``): print(`Regarding winning`): print(``): for i from 1 to nops(P) do print(`You win`, P[i][1] , `dollars with probability`, P[i][2]): od: kama:=-add(N[i][1]*N[i][2],i=1..nops(N))+add(P[i][1]*P[i][2],i=1..nops(P)): print(``): print(`You start with a capital of 0 dollars, and have unlimited credit. Your goal in life is to gain a POSITIVE amount, and`): print(`you quit as soon as you reach that goal.`): print(``): print(`Note that the expected gain in ONE round is`, kama): if kama>0 then print(`Since it is positive, sooner or later you will reach your goal.`): elif kama=0 then print(`Since it is zero, sooner or later you will reach your goal, but it may take a long time but the exepctation and the higher moments are infinite`): print(`We do not treat this case`): RETURN(FAIL): else print(`Since it is negative, you may not be able to reach your goal.`): fi: vu:=SoABOVEp(f,t,N,P): print(`The probability generating function, let's call it f=f(t), for the random variable "duration of game" `): print(`in other words, the formal power series whose coefficient of, t^n is the probability of ending after n rounds satisfies the`): print(`following algebraic equation `): print(``): print(vu=0): print(``): print(`and in Maple notation`): print(``): lprint(vu=0): print(``): gu:=MOMSkN(N,P,f,k,eps): if gu=FAIL then RETURN(FAIL): fi: mu:=gu[2]: gu:=gu[1]: if kama>0 then print(`The expected duration, let's call it`, f[1], `is one of the roots of the polynomial `): print(factor(gu[2][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[2][1])): print(``): print(`and its numerical value is`): print(``): print(gu[2][2]): if k>=2 then print(`The second moment of the duration, let's call it`, f[2], `is one of the roots of the polynomial `): print(factor(gu[3][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[3][1])): print(``): print(`and its numerical value is`): print(``): print(gu[3][2]): print(``): print(`It follows that the variance is`, mu[1][2]): print(``): print(`and hence the standard-deviation is`, sqrt(mu[1][2])): fi: for k1 from 3 to k do print(`The `, k1, ` -th moment of the duration, let's call it`, f[k1], `is one of the roots of the polynomial `): print(factor(gu[k1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[k1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[k1][2]): print(``): print(`It follows that the scaled `, k1, `-th moment about the mean is`, mu[1][k1]): print(``): od: print(`To summarize the statistical data, expectation, variance, ... etc. is`): print(``): print(mu[1]): print(``): print(`Just to make sure, let's compare it with the much faster way of truncating the prob. generating function up to`, K1, `rounds `): lu:=MOMSkNA(N,P,k,K1): print(`The corresponding approximation is`): print(``): print(lu[1]): print(``): print(`and the probability that the goal is reached withing`, K1, `rounds is `, lu[2]): print(``): print(`Finally, let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(`The corresponding crude approximation is`): print(``): print(ku[1]): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): fi: if kama<0 then print(`The probability of reaching your goal let's call it`, f[0], `is one of the roots of the polynomial `): print(factor(gu[1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[1][2]): print(`The expected duration, let's call it`, f[1], `is one of the roots of the polynomial `): print(factor(gu[2][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[2][1])): print(``): print(`and its numerical value is`): print(``): print(gu[2][2]): if k>=2 then print(`The second moment of the duration (before conditioning on success), let's call it`, f[2], `is one of the roots of the polynomial `): print(factor(gu[3][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[3][1])): print(``): print(`and its numerical value is`): print(``): print(gu[3][2]): print(``): print(`It follows that the (conditional upon success) variance is`, mu[1][2]): print(``): print(`and hence the standard-deviation is`, sqrt(mu[1][2])): fi: for k1 from 3 to k do print(`The `, k1, ` -th moment of the duration (before conditioning), let's call it`, f[k1], `is one of the roots of the polynomial `): print(factor(gu[k1][1])): print(``): print(`and in Maple notation`): lprint(factor(gu[k1][1])): print(``): print(`and its numerical value is`): print(``): print(gu[k1][2]): print(``): print(`It follows that the conditioned scaled `, k1, `-th moment about the mean is`, mu[1][k1]): print(``): od: print(`The probability that you would reach your goal is`,mu[2]): print(`and the statistical data, expectation, variance, ... etc. is`): print(``): print(mu[1]): print(``): print(`Just to make sure, let's compare it with the much faster way of truncating the prob. generating function up to`, K1, `rounds `): lu:=MOMSkNA(N,P,k,K1): print(`The corresponding approximation is`): print(``): print(lu[1]): print(``): print(`and the probability that the goal is reached withing`, K1, `rounds is `, lu[2]): print(``): print(`Finally, let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(`The corresponding crude approximation is`): print(``): print(ku[1]): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): fi: if kama>0 then print(`So far we considered the Solitaire game. Now suppose that two players take turns, and the first player to reach`): print(`the goal of having positive capital is declared the winner. Assuming that they each are give at most`,K1, `turns `): print(`the probability of the first-to-move player winning is`): print(``): ku:=Ngf(N,P,t,K1): ku:=evalf((1+add(coeff(ku,t,i)^2,i=0..K1))/2): print(ku): print(``): fi: print(``): print(`This ends Proposition`, MIS, `that took`, time()-t0, `seconds to generate. `): print(``): print(`---------------------------------------------`): print(``): end: #PropNum(N,P,k,K1,K2,MIS): Inputs sets N and P whose elements are {[i,pi]} where in N the pair [i,pi] means #that the probability of -i is pi, and [i,pi] in P means that the probability of i is pi, a (not too large) positive #integer k, and fairly large positive integers K1 and K2, a symbol f, and a small (but no too small) positive number eps #Outputs a computer-generated game about the duration of reaching a goal of #having POSITIVE capital, if you start with 0 capital, and at each round you gain or lose according #to the "roulette", and your goal in life is reach a positive capital, and you quit as soon as that happens. #It is Purely Numeric, using the Naive approximation algorithm, hence can do much more.Try: #PropNum({[1,1/3]},{[1,2/3]}, 4,200,300,MIS); PropNum:=proc(N,P,k,K1,K2,MIS) local t0,i,kama,lu,ku,t: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: if not (type(k,integer) and k>1) then print(k, `should be an integer larger than 1`): RETURN(FAIL): fi: if not type(K1,integer) and type(K2,integer) and K1>10 and K2>10 then print(K1,K2, `should be integers larger than 10`): RETURN(FAIL): fi: t0:=time(): print(``): print(``): print(`---------------------------------------------`): print(``): print(`Proposition Number`, MIS): print(``): print(`Consider a casino with a strange roulette, where there were`, nops(N)+ nops(P), `possible outcomes as follows. `): print(``): print(`Regarding losing`): print(``): for i from 1 to nops(N) do print(`You lose`, N[i][1] , `dollars with probability`, N[i][2]): od: print(``): print(`Regarding winning`): print(``): for i from 1 to nops(P) do print(`You win`, P[i][1] , `dollars with probability`, P[i][2]): od: print(``): print(`You start with a capital of 0 dollars, and have unlimited credit. Your goal in life is to gain a POSITIVE amount, and`): print(`you quit as soon as you reach that goal.`): print(``): kama:=-add(N[i][1]*N[i][2],i=1..nops(N))+add(P[i][1]*P[i][2],i=1..nops(P)): print(`Note that the expected gain in ONE round is`, kama): if kama>0 then print(`Since it is positive, sooner or later you will reach your goal.`): elif kama=0 then print(`Since it is zero, sooner or later you will reach your goal, but it may take a long time but the exepctation and the higher moments are infinite`): print(`We do not treat this case`): RETURN(FAIL): else print(`Since it is negative, you may not be able to reach your goal.`): fi: lu:=MOMSkNA(N,P,k,K1): print(``): print(`The probability that the goal is reached within`, K1, `rounds is `, lu[2]): print(``): print(`The approximate expectation, variance, and scaled moments up to the`,k, `-th are `): print(``): print(lu[1]): print(`Let's compare it to the results of simulating it`, K2, `times. Of course this changes from time to time`): ku:=MOMSkNSi(N,P,k,K1,K2): print(``): print(`and the fraction of the simulated games that for which the goal was reached within`, K1, `rounds is `, ku[2]): print(``): print(`The crude approximations for the expectation, variance etc. are`): print(``): print(ku[1]): if kama>0 then print(`So far we considered the Solitaire game. Now suppose that two players take turns, and the first player to reach`): print(`the goal of having positive capital is declared the winner. Assuming that they each are give at most`,K1, `turns `): print(`the probability of the first-to-move player winning is`): print(``): ku:=Ngf(N,P,t,K1): ku:=evalf((1+add(coeff(ku,t,i)^2,i=0..K1))/2): print(ku): print(``): fi: print(``): print(`This ends Proposition No.`, MIS, `that took`, time()-t0, `seconds to generate. `): print(``): print(`---------------------------------------------`): print(``): end: #PropEk1(N,P,t,K,MIS): Like Paper(N,P,t,K) (q.v.) but instead of a paper, it outputs a proposition numbered MIS. Try: #PropEk1({1},{1},t,30,3); PropEk1:=proc(N,P,t,K,MIS) local gu,a,n,mu,f,p,t0,lu: t0:=0: gu:=ScabE(0,0,f,t,N,P): mu:=ScToSeq(gu,t,K): print(``): print(`---------------------------------------------------------`): print(``): print(`Proposition No.`, MIS): print(``): print(` Let a(n) be the number of sequences of length n, in the alphabet`, {seq(-n, n in N), seq(p, p in P)}, `that add-up to zero and such that`): print(``): print(`their partial sums are NEVER positive. Then the first`, K, `terms are `): print(``): lprint(mu): print(``): lu:=SoabE(0,0,f,t,N,P): print(` The ordinary generating function, f=f(t)`): print(``): print(f(t)=Sum(a(n)*t^n,n=0..infinity)): print(``): print(`satisfies the algebraic equation `): print(``): print(lu=0): print(``): print(``): print(`and in Maple notation`): print(``): lprint(lu=0): print(``): print(`----------------------------------------`): print(``): print(`This ends Proposition`, MIS, `that took`, time()-t0, `seconds to generate. `): print(``): print(`---------------------------------`): print(``): end: #PaperEk1J(N,P,K): Like PaperEk1(N,P,t,K) but only the sequence. Try: #PaperEk1J({1},{1},30); PaperEk1J:=proc(N,P,K) local gu,n,mu,f,p,t0,t: t0:=0: gu:=ScabE(0,0,f,t,N,P): mu:=ScToSeq(gu,t,K): print(``): print(`The first`, K, `terms for the sequence enumerating `): print(`walks with set of steps`, {seq(-n, n in N), seq(p, p in P)}, `that start and end on the x-axis and never go above it`): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`Theorem: Let a(n) be the number of sequences, of length n ,in the alphabet`, {seq(-n, n in N), seq(p, p in P)}, `that add-up to zero and such that`): print(``): print(`their partial sums are NEVER positive. Then the first`, K, `terms are `): print(``): lprint(mu): print(``): print(`----------------------------------------`): print(``): print(`This ends this article that took`, time()-t0, `seconds to generate. `): print(``): end: #PropEk1J(N,P,K,MIS): Like PaperEk1J(N,P,t,K) but as a proposition numbered MIS. Try: #PropEk1J({1},{1},30,9); PropEk1J:=proc(N,P,K,MIS) local gu,n,mu,f,p,t0,t: t0:=0: gu:=ScabE(0,0,f,t,N,P): mu:=ScToSeq(gu,t,K): print(``): print(`Fact Number`, MIS): print(``): print(`Theorem: Let a(n) be the number of sequences, of length n ,in the alphabet`, {seq(-n, n in N), seq(p, p in P)}, `that add-up to zero and such that`): print(``): print(`their partial sums are NEVER positive. Then the first`, K, `terms are `): print(``): lprint(mu): print(``): print(`----------------------------------------`): print(``): print(`This ends Fact No. `, MIS. `that took`, time()-t0, `seconds to generate. `): print(``): end: #PropEk2(n,p,t,K,MIS): Like PropEk2(n,p,t,K) but as proposition numbered MIS. Try: #PropEk2(2,3,t,30,MIS); PropEk2:=proc(n,p,t,K,MIS) local gu,a,m,mu,f,t0,lu,i: t0:=0: gu:=ScabE(0,0,f,t,{n},{p}): mu:=ScToSeq(gu,t,(n+p)*K): mu:=[seq(mu[(n+p)*i],i=1..K)]: print(``): print(`----------------------------`): print(``): print(``): print(`Prop. No. `, MIS): print(``): print(`Let a(m) be the number of sequences of length`, (n+p)*m, `in the alphabet`, {-n,p}, `that add-up to zero and such that`): print(``): print(`their partial sums are NEVER positive. Then the first`, K, `terms are `): print(``): lprint(mu): print(``): lu:=SoabE(0,0,f,t,{n},{p}): lu:=simplify(subs(t=t^(1/(n+p)),lu)): print(` The ordinary generating function, f=f(t)`): print(``): print(f(t)=Sum(a(m)*t^m,m=0..infinity)): print(``): print(`satisfies the algebraic equation `): print(``): print(lu=0): print(``): print(``): print(`and in Maple notation`): print(``): lprint(lu=0): print(``): print(`----------------------------------------`): print(``): print(`This ends Prop.`, MIS, ` that took `, time()-t0, `seconds to generate. `): print(``): end: #PropEk2J(n,p,K,MIS): inputs positive integers n and p, a variable t and a positive integer K outputs #an article about the number of walks starting at the origin with steps -n and p #ending at the origin and NEVER going above it, as well as first K terms. Try: #PropEk2J(2,3,t,30,MIS PropEk2J:=proc(n,p,K,MIS) local gu,m,mu,f,t0,i,t: t0:=0: gu:=ScabE(0,0,f,t,{n},{p}): mu:=ScToSeq(gu,t,(n+p)*K): mu:=[seq(mu[(n+p)*i],i=1..K)]: print(``): print(`--------------------------------------------`): print(``): print(`Fact No.`, MIS): print(``): print(`Let a(m) be the number of sequences of length`, (n+p)*m, `in the alphabet`, {-n,p}, `that add-up to zero and such that`): print(``): print(`their partial sums are NEVER positive. Then the first`, K, `terms are `): print(``): lprint(mu): print(``): print(`----------------------------------------`): print(``): print(`This ends Fact No.`, MIS, `that took`, time()-t0, `seconds to generate. `): print(``): end: ################End Propositions ###Start Books #BookSet(L,k,K1,K2,f,eps): outputs a book with all the PropSet(S,k,K1,K2,f,eps,MIS) (q.v.) where S consists of #all the possible non-empty subsets of {-1, ..., -L} union all non-empty subsets of {1,...,L}. Try: #BookSet(2,4,300,500,f,0.1); BookSet:=proc(L,k,K1,K2,f,eps) local gu,i,S,MIS,gu1,gu2,t0: t0:=time(): gu:=powerset({seq(i,i=1..L)}) minus {{}}: print(`On Games Inspired by Gambler's Ruin with Unlimited Credit with many Gambling Scenarios`): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`In this book we will analyze ALL possible games given by sets of steps each of them between 1 and `, L, `in absolute value`): print(`and each containing at least one positive and at least one negative step, and once the set is decided`): print(`every step is equally likely. We only treat the case where the sum of the steps is not 0`): MIS:=0: for gu1 in gu do for gu2 in gu do if convert(gu1,`+`)convert(N,`+`) then print(``): print(`For the set`, P union {seq(-i, i in N)} ): print(``): print(`We have the following propositions`): print(``): MIS:=MIS+1: godel:=nops(P)+nops(N): N1:={seq([i,1/godel], i in N)}: P1:={seq([i,1/godel], i in P)}: PropNum(N1,P1,k,K1,K2,MIS): fi: od: od: print(``): print(`---------------------------------------------`): print(``): print(`This concludes this book, that took`, time()-t0, `seconds to generate`): print(``): end: #BookNum2E(L,k,K1,K2): outputs a book with all the PropNum({[n,1/2]},{[p,1/2]},k,K1,K2,MIS) #all the n and p {1,...,L} asuch that p-n>0. try: #BookNum2E(3,4,300,500); BookNum2E:=proc(L,k,K1,K2) local n,p,MIS,t0: t0:=time(): print(`Numerical Studties of Games Inspired by Gambler's Ruin with Unlimited Credit with One Positive and One Negative possible steps of size up to`, L): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`In this book we will analyze ALL possible games given by two-element sets of steps, one negative, one positive`): print(`where the sum of the two steps is positive, so that the game is guaranteed to finish, `): print(`every step is equally likely (hence prob. 1/2) `): MIS:=0: for n from 1 to L do for p from n+1 to L do print(``): print(`For the set`, {-n,p} ): print(``): print(`We have the following propositions`): print(``): MIS:=MIS+1: PropNum({[n,1/2]},{[p,1/2]} ,k,K1,K2,MIS): od: od: print(``): print(`---------------------------------------------`): print(``): print(`This concludes this book, that took`, time()-t0, `seconds to generate`): print(``): end: #BookEk1(L,t,K): Inputs a positive integer L and outsputs all the propositions of the form PropEk1(N,P,t,K,MIS) (q.v.) #for each non-empty subsets N,P, of of {1, ...,L}. Try #BookEk1(2,t,30); BookEk1:=proc(L,t,K) local i,gu,N,P,MIS,t0: t0:=time(): print(`Algebraic Equations satisfied by walks with given negative and positive steps that start and end at the x-axis and never`): print(`go above the x-axis`): print(``): print(`By Shalosh B. Ekhad `): print(``): print(`In this book we will present algebraic equations satisfied by the ordinary generating function of the sequences enumerating`): print(` ALL families of walks consisting of at least one negative step, at least one positive steps`): print(`where the size of each step is between 1 and`, L): print(`and that start and end at the x-axis, but never go above the x-axis`): print(`We also supply the first`, K, `terms of the enumerating sequence`): gu:=powerset({seq(i,i=1..L)}) minus {{}}: MIS:=0: for N in gu do for P in gu do if igcd(op(N),op(P))=1 then MIS:=MIS+1: PropEk1(N,P,t,K,MIS): fi: od: od: print(``): print(`-------------------------------------`): print(``): print(`This ends this book that took`, time()-t0, `seconds to generate. `): end: #BookEk2(L,t,K): Inputs a positive integer L and outsputs all the propositions of the form PropEk2(n,p,t,K,MIS) (q.v.) #for all 1<=n=n0 for the first time. #It uses the truncated prob. generating function up to K1 terms. #Try: #Ave1NuId({[1,1/2]},{[2,1/2]},1000,1); Ave1NuId:=proc(N,P,K1,n0) local gu,t: gu:=NgfG(N,P,t,K1,n0): identify(evalf(subs(t=1,diff(gu,t))/subs(t=1,gu))): end: #Ave1Nu(N,P,,K1,n0): An approximation for the expected number of rounds for generalized (N,P) game for reaching >=n0 for the first time. #It uses the truncated prob. generating function up to K1 terms. #Try: #Ave1Nu({[1,1/2]},{[2,1/2]},1000,1); Ave1Nu:=proc(N,P,K1,n0) local t: evalf(subs(t=1,diff(NgfG(N,P,t,K1,n0),t))): end: #MyIden(alpha,N,K): inputs a floating-point number alpha, and a positive non-square pos. integer N, outputs the #pair [a,b] such that a*sqrt(N)-b-alpha is closest wotj b<=K, where a= round((a+b)/sqrt(N)): MyIden:=proc(alpha,N,K) local a,b,aluf,si,hale: if not (type(N,integer) and (not type(sqrt(N),integer)) and type(K,integer) and K>0 ) then print(`Bad input`): RETURN(FAIL): fi: si:=1: aluf:=1: for b from -K to K do a:= round(evalf((alpha-b)/sqrt(N))): hale:=evalf(abs(a*sqrt(N)+b-alpha)): if hale10^(-11) then print(`Try to make`, K, `higher `): RETURN(FAIL): fi: aluf[1]*sqrt(N)+aluf[2]: end: #ExF2m1(n): The exact formula (obtained by semi-rigorous experimental mathematics) for the expected number of #moves in a "one step forward two steps backwards random walk" until reaching a location >=n for the first time. #In terms of the Golden ratio #Try: #ExF2m1(10); ExF2m1:=proc(n) local phi: phi:=(1+sqrt(5))/2: 2*(fibonacci(n+2)*phi-fibonacci(n+3) + 2 -phi +n): end: ################################new stuff #SoABOVEp(f,t,N,P): The algebraic equation in f=f(t), where f(t) is the probability #generating function of the sequence of walks, according to the distribution given by N and P #where N is a set of pairs [n,prob. of -n], and P is a set of pairs [p,prob. of p]. Try: #SoABOVEp(f,t,{[1,2/3]},{[-1,1/3]}); SoABOVEp:=proc(f,t,N,P) local N1,P1,x,gu,n,p,eq,var,gu2: if not (type(N,set) and type(P,set) and {seq(type(N[i],list),i=1..nops(N))}={true} and {seq(type(P[i],list),i=1..nops(P))}={true} and add(N[i][2],i=1..nops(N))+ add(P[i][2],i=1..nops(P))=1) then print(`Bad input`): RETURN(FAIL): fi: N1:={seq(n[1],n in N)}: P1:={seq(p[1],p in P)}: gu:=ScX(f,x,N1,P1,X): gu2:=subs({seq(x[-n[1]]=t*n[2], n in N),seq(x[p[1]]=t*p[2], p in P)},gu[2]): var:=gu[1]: var:=[op(2..nops(var),var),var[1]]: eq:={seq(gu[1][i]-gu2[i],i=1..nops(var))}: subs(X=f,Groebner[Basis](eq,plex(op(var)))[1]); end: