# restart; read `c:/Users/Asus/Google Drive/Aek # /Pile Game2/Pile2.txt`; # read `c:/Users/Asus/Google Drive/Guess.txt`; # First version: Sep 12,2019 # This Maple program # accompanied the paper # "Game of Pure Chance with # Restricted Boundary" by # Ho-Hon Leung and Aek ############################### # Section 1: Introduction # (restricted boundary # i.e. no negative chips), # Path Counting, # Generating functinos and # others statistics. # # Functions: # One-Player: # Path(n,k,s,v,S), NumE(n,k,s,v,S), # Num1(n,k,s,S), GuessGen(n,s,S,x), # SolveGen(n,S,P,x), Rec1(n,s,S,K), # Mo1(n,s,mo,S,P), # # Two-Player: # SolveT(n,S,P,x), # GenT(n,s1,s2,S,P,x), # SolveW(n,S,P,x), SolveL(n,S,P,x), # # NotWin1(n,k,s,S), # GuessW(n,s1,s2,S,x), # GuessL(n,s1,s2,S,x), # GuessT(n,s1,s2,S,x), # ################################ # Input: numeric n,k,s,v and # the choice list S # Output: The set of paths # up to turn k which end at # v and never get equal or # more than n chips starts # with s chips. # Try: # Path(1,3,0,0,[1,-1]); # Path(3,7,0,2,[1,-1]); Path := proc(n,k,s,v,S) option remember; local t,P,T; if k=0 then if s=v then return({[]}); else return({}); fi: elif s >= n then return({}); fi: T := {}; for t in S do T := T union {seq([max(0,s+t),op(P)] ,P in Path(n,k-1,max(0,s+t),v,S))}; od: T; end: # Input: numeric n,k,s,v and # the choice list S # Output: The number of paths # which arises from adding elements # from list S of total # k turns, never get to n chips, # at the end of k turns has exactly # v chips, and starts with s chips. # Try: # NumE(3,13,0,2,[2,-1]); # nops(Path(3,13,0,2,2,-1)); NumE := proc(n,k,s,v,S) option remember; local t; if k=0 then if s=v then return(1); else return(0); fi: elif s >= n then return(0); fi: add(NumE(n,k-1,max(0,s+t),v,S),t in S); end: # Input: numeric n,k,s and # the choice list S # Output: The number of paths # which arises from adding # chips from set S with total # of k-1 turns, never get to n chips, # at the end of k turns has n # chips or more. # Player starts with s chips. # Try: # Num1(30,30,2,[1,-1]); Num1 := proc(n,k,s,S) option remember; local i; if k=0 then if s >= n and s < n+max(op(S)) then return(1); else return(0); fi: elif s >= n then return(0); fi: add(Num1(n,k-1,max(s+t,0),S), t in S); end: # Input: numeric n,s, choice list S # and symbolic x # Output: Guessing Generating # function in x. # Starting with s chips, # Game ends when reaching at # least n chips for the first time, # each move is chosen from the set S # with equal probability # # Try: # [seq(GuessGen(n,0,[2,-1],x),n=0..10)]; # [seq(GuessGen(n,0,[1,0,-1],x),n=1..5)]; # [seq(GuessGen(7,2,[1,-2],x) # -GuessGen(7,m,[1,-2],x)*GuessGen(m,2,[1,-2],x),m=2..7)]; # [seq(simplify(GenG(n,3,-2,1/2,1/2,x) # -GuessGen(n,3,[1,-2],x)),n=3..10)]; GuessGen := proc(n,s,S,x) option remember; local k,A; A :=[seq(Num1(n,k,s,S),k=0..2*n+5)]; A := subs(x=x/nops(S),GuessGenRat(A,0,x)); factor(A); end: # Input: numeric n, choice list S, # probability list P and symbolic x # Output: Solve Generating # function in x for all # starting s chips. # Game ends when reaching at # least n chips for the first time, # each move is chosen from the set S # with probability from P. # Try: # SolveGen(2,[1,-1],[p,q],x); # SolveGen(2,[3,-1],[p,q],x); SolveGen := proc(n,S,P,x) option remember; local i,t,G,ma,eq,var; if nops(S) <> nops(P) then ERROR(BadSP); fi: ma := max(op(S)); eq := { seq(G[t]= x*add(P[i]*G[max(t+S[i],0)],i=1..nops(S)),t=0..n-1) ,seq(G[n-1+i]=1,i=1..ma)}; var := {seq(G[t],t=0..n-1+ma)}; var :=solve(eq,var); [seq(subs(var,G[t]),t=0..n-1+ma)]; end: # Input: numeric n,s, choice list S, # and symbolic K # Output: Annihilator in k of b_n(k,s), # number of paths when the game # ends at turn k, starting at s, # each move from the set S. # (This is to check Cor.3,10,13 # in the paper.) # Try: # [seq(Rec1(n,0,[1,-2],K),n=1..3)]; Rec1 := proc(n,s,S,K) option remember; local j,k,A; A :=[seq(Num1(n,k,s,S),k=1..2*n+5)]; expand(lhs(GuessC(A,K))); end: # Input: numeric n and variable x # prob. p # Output: Q_n(x) from corollary 3 # Try: # [seq(QCor3(n,x,p),n=0..5)]; QCor3 := proc(n,x,p) option remember; local q; q := 1-p; if n=0 then return(1); elif n=1 then return(1-q*x); fi: factor(QCor3(n-1,x,p)-q*p*x^2*QCor3(n-2,x,p)); end: # Input: numeric n,s,mo, # choice list S and probability list P # Output: mo-moment of X_{n,s} # each move is selected from # the set S with probability P # Try: # A:=[seq(Mo1(n,0,1,[1,-1],[1/2,1/2]),n=1..10)]; # [seq(evalf(add(k*Num1(n,k,0,[1,-1]) # /2^k,k=0..1000)),n=1..10)]; # A:=[seq(Mo1(n,0,1,[1,-1],[p,1-p]),n=1..10)]; # GuessC(A,N); # A:=[seq(Mo1(n,0,2,[1,-1],[p,1-p]),n=2..25)]; # GuessC(A,N); # A:=[seq(Mo1(n,0,1,[1,-2],[1/2,1/2]),n=1..20)]; # GuessC(A,N); Mo1 := proc(n,s,mo,S,P) option remember; local i,x,f; f := SolveGen(n,S,P,x)[s+1]; for i from 1 to mo do f := simplify(x*diff(f,x)) od: factor(subs({x=1},f)); end: ################################################ # Two-Player # Input: numeric n, choice list S, # probability list P and symbolic x # Output: Solve stopping prob. # generating function T in x for all # starting positions s1,s2. # Game ends when either player # reaches at least n chips # for the first time, # each move is chosen from the set S # with probability from P. # Try: SolveT(1,[1,-1],[1/2,1/2],x); SolveT := proc(n,S,P,x) option remember; local i,s1,s2,ma,T,eq,var,N; ma := max(op(S))-1; eq := { seq(seq(T[s1,s2]=x*add(P[i]*T[s2,max(0,s1+S[i])] ,i=1..nops(S)),s2=0..n-1),s1=0..n-1), seq(seq(T[n+i,s2]=1,s2=0..n-1),i=0..ma), seq(seq(T[s1,n+i]=1,s1=0..n-1),i=0..ma)}; var := {seq(seq(T[s1,s2],s2=0..n+ma) ,s1=0..n+ma)} minus {T[n+ma,n+ma]}; N :=solve(eq,var); Matrix( [seq([seq( factor( subs(N,T[s1,s2])),s2=0..n+ma)],s1=0..n+ma)]); end: # Input: numeric n,s1,s2, choice list S, # probability list P and symbolic x # Output: Stopping prob. generating # function starting at s1 and s2 # Try: # GenT(2,0,0,[1,-1],[1/2,1/2],x); # [seq(simplify(GenT(n,0,1,[1,-1],[1/2,1/2],x) # -GuessT(n,0,1,[1,-1],x)),n=1..5)]; GenT := proc(n,s1,s2,S,P,x) option remember; local A; if s1 > n+max(op(S)) or s2 > n+max(op(S)) then ERROR("BadInput"); fi: A := SolveT(n,S,P,x)[s1+1,s2+1]; end: # Input: numeric n, choice list S, # probability list P and symbolic x # Output: Solve winning prob. # generating function W in x for all # starting positions s1,s2. # Game ends when player one # be the first to reach # at least n chips, # each move is chosen from the set S # with probability from P. # Try: SolveW(1,[1,-1],[1/2,1/2],x); SolveW := proc(n,S,P,x) option remember; local i,j,s1,s2,ma,W,eq,var,N; ma := max(op(S))-1; eq := { seq(seq(W[s1,s2]=x*add(add(P[i]*P[j] *W[max(0,s1+S[i]),max(0,s2+S[j])] ,i=1..nops(S)),j=1..nops(S)) ,s2=0..n-1),s1=0..n-1), seq(seq(W[n+i,s2]=1,s2=0..n+ma),i=0..ma), seq(seq(W[s1,n+i]=0,s1=0..n-1),i=0..ma)}; var := {seq(seq(W[s1,s2],s2=0..n+ma) ,s1=0..n+ma)}; N :=solve(eq,var); Matrix( [seq([seq( factor( subs(N,W[s1,s2])),s2=0..n)],s1=0..n)]); end: # Input: numeric n, choice list S, # probability list P and symbolic x # Output: Solve losing prob. # generating function L in x for all # starting positions s1,s2. # Game ends when player two # be the first to reach # at least n chips, # each move is chosen from the set S # with probability from P. # Try: SolveL(1,[1,-1],[1/2,1/2],x); SolveL := proc(n,S,P,x) option remember; local i,j,s1,s2,ma,W,eq,var,N; ma := max(op(S))-1; eq := { seq(seq(W[s1,s2]=x*add(add(P[i]*P[j] *W[max(0,s1+S[i]),max(0,s2+S[j])] ,i=1..nops(S)),j=1..nops(S)) ,s2=0..n-1),s1=0..n-1), seq(seq(W[n+i,s2]=0,s2=0..n+ma),i=0..ma), seq(seq(W[s1,n+i]=1,s1=0..n-1),i=0..ma)}; var := {seq(seq(W[s1,s2],s2=0..n+ma) ,s1=0..n+ma)}; N :=solve(eq,var); Matrix( [seq([seq( factor( subs(N,W[s1,s2])),s2=0..n)],s1=0..n)]); end: ############################################ # Input: numeric n,k,s # and choice list S # Output: Number of ways # never hit n up to turn k, # starting at s # Try: # [seq(NotWin1(2,k,0,[1,-1]),k=0..10)]; NotWin1 := proc(n,k,s,S) option remember; local i; if s >= n then return(0); elif k=0 and s < n then return(1); fi: add(NotWin1(n,k-1,max(s+t,0),S), t in S); end: # Input: numeric n,s1,s2, # choice list S and symbolic x # Output: Guessing the winning prob. # generating function # starting at s1 and s2 # (player one hits n chips first) # Try: # GuessW(2,0,1,[1,-1],x); # SolveW(2,[1,-1],[1/2,1/2],x)[1,2]; GuessW := proc(n,s1,s2,S,x) option remember; local k,m,A; m := nops(S); if s1 >= n and s1 <= n-1+max(op(S)) and s2 < n then return(1); elif s2 >= n and s2 <= n-1+max(op(S)) and s1 < n then return(0); elif s1 >= n or s2 >= n then ERROR(BadInput); fi: A := [seq(Num1(n,k+1,s1,S)*NotWin1(n,k,s2,S) ,k=0..n^2+2*n+10)]; factor(x/m*subs(x=x/m^2,GuessGenRat(A,0,x))); end: # Input: numeric n,s1,s2, # choice list S and symbolic x # Output: Guessing the losing prob. # generating function # starting at s1 and s2 # (player two hits n chips first) # Try: # GuessL(2,0,1,[1,-1],x); # SolveL(2,[1,-1],[1/2,1/2],x)[1,2]; GuessL := proc(n,s1,s2,S,x) option remember; local k,m,A; m := nops(S); if s1 >= n and s1 <= n-1+max(op(S)) and s2 < n then return(0); elif s2 >= n and s2 <= n-1+max(op(S)) and s1 < n then return(1); elif s1 >= n or s2 >= n then ERROR(BadInput); fi: A := [seq( NotWin1(n,k,s1,S)*Num1(n,k,s2,S) ,k=1..n^2+2*n+10)]; factor(subs(x=x/m^2,GuessGenRat(A,1,x))); end: # Input: numeric n,s1,s2, # choice list S and symbolic x # Output: Guessing the stopping prob. # generating function starting at s1 and s2 # (Game ends when either player hits n chips.) # Try: # GuessT(2,0,0,[1,-1],x); # SolveT(2,[1,-1],[1/2,1/2],x); GuessT := proc(n,s1,s2,S,x) option remember; local F,G; F := GuessW(n,s1,s2,S,x); G := GuessL(n,s1,s2,S,x); if F = 1 then factor(1+subs(x=x^2,G)); else factor(1/x*subs(x=x^2,F)+subs(x=x^2,G)); fi: end: ################################# # Section 2: One player scenario # ################################# # Section 2.1: # Generating functions # # Functions: # GenG(n,s,b,p,q,x), DeQ(n,K), # ################################ # Generating functions by recurrences # for case {1,b}, b<0 # Input: numeric n,s,b,p,q and symbolic x # Output: Generating function using # recurrence, starting at s. # Game stops when reaching # n chips for the first time, # each move to add 1 or b # (negative) chips with prob. p and q. # Try: # [seq(GenG(n,0,-1,1/2,1/2,x),n=1..5)]; # SolveGen(2,[1,-1],[p,q],x); # [seq(GenG(2,s,-1,p,q,x),s=0..2)]; GenG := proc(n,s,b,p,q,x) option remember; local A; if b>=0 then ERROR(BadInput); fi: if n <= 0 then 1; elif s=0 then A:=1/x/p/GenG(n-1,s,b,p,q,x) -q/p/GenG(n-1+b,s,b,p,q,x); factor(A^(-1)); else factor(GenG(n,0,b,p,q,x)/GenG(s,0,b,p,q,x)); fi: end: # Relation of Denominator of G_{n,s}(x) # Input: numeric n and symbolic p,q,x # Output: denominator of G_{n,s}(x) # Try: # [seq(DeQ(n,1,1,x),n=1..2)]; # [seq(Rec1(n,0,[1,-1],K),n=1..6)]; # [seq(DeQ(n,p,q,x),n=1..2)]; DeQ := proc(n,p,q,x) option remember; if n=0 then return(1); elif n=1 then return(1-q*x); else simplify(DeQ(n-1,p,q,x)-q*p*x^2*DeQ(n-2,p,q,x)); fi: end: ################################## # Section 2.2: Averages # and Higher Moments # # Functions: # ForMo(mo,n,s), ForMoMean(mo,n,s), # ForAvg(n,s,p), # VeriMo2(), # ################################## # Polynomial solution when # S={1,-1}, p=q=1/2. # Proposition 4,5 # Input: moment mo, symbolic n and s # Output: Formula of the moments # Try: # ForMo(1,n,s); # ForMo(2,n,s); ForMo := proc(mo,n,s) option remember; local nn,ss,A; A:=[seq([seq(Mo1(nn,ss,mo,[1,-1],[1/2,1/2]) ,nn=2*mo+2..4*mo+3)],ss=0..2*mo+1)]; GuessPol2D(A,[2*mo+2,0],[n,s]); end: # Polynomial solution when # S={1,-1}, p=q=1/2. # # Proposition 6 # Input: moment mo, symbolic n and s # Output: Formula of moment about the mean # Try: ForMoMean(3,n,s); ForMoMean := proc(mo,n,s) option remember; local i,A; A := add((-1)^i*binomial(mo,i)*ForMo(mo-i,n,s) *ForMo(1,n,s)^i,i=0..mo); factor(A); end: # Input: symbolic n,s,p # Output: Solve for the formula for average # for {1,-1} with general probability # p and q (p <> 1/2). # Try: # A:=ForAvg(n,s,p); # a:=[seq(factor(subs({n=i,s=2},A)),i=2..15)]; # b:=[seq(Mo1(n,2,1,[1,-1],[p,1-p]),n=2..15)]; # a-b; ForAvg := proc(n,s,p) option remember; local i,j,a,b,A,eq,var; A :=[seq([seq(Mo1(j,i,1,[1,-1],[p,1-p]) ,j=11..20)],i=1..10)]; eq := {seq(seq( A[i,j]=a[1]+a[2]*i+a[3]*((1-p)/p)^i +b[2]*(j+10)+b[3]*((1-p)/p)^(j+10) ,i=1..nops(A)),j=1..10)}; var := {a[1],a[2],a[3],b[2],b[3]}; var := solve(eq,var); factor(subs(var,a[1]+a[2]*s+a[3]*((1-p)/p)^s +b[2]*n+b[3]*((1-p)/p)^n)); end: # Verified the formula of # the second moment in prop.5 # Try: VeriMo2(); VeriMo2 := proc() option remember; local n,s,mo1,mo2,r1,l1,r2,l2; mo1 := (n,s)->(n-s)*(n+s+1); mo2 := (n,s)->(n-s)*(n+s+1)*(5*n^2+5*n-s^2-s-1)/3; r1 := mo2(n,0); l1 := 1+mo1(n,1)+mo1(n,0)+(mo2(n,1)+mo2(n,0))/2; r2 := mo2(n,s); l2 := 1+mo1(n,s+1)+mo1(n,s-1)+(mo2(n,s+1)+mo2(n,s-1))/2; simplify([r1-l1,r2-l2]); end: ############################# # Section 2.3: Guessing # the formula of b_{n}(n+t,s) # # Functions: # ForB(n,t,s), Bi(n,k), # ############################# # Input: numeric or symbolic n # General formulas of b_{n}(n+t,s) # for case a=1 and b=-1. # Try: # ForB(n,3,3); # n:=27: # A:=[seq(ForB(n,-s+56,s),s=1..n)]; # B:=[seq(Num1(n,n-s+56,s,[1,-1]),s=1..n)]; # A-B; ForB := proc(n,t,s) option remember; if -n >= t or s>n then ERROR("BadInput"); fi: if (t+s) mod 2 = 0 and t-s <= 2*n then (n-s)/(n+t)*Bi(n+t,(t+s)/2); elif (t+s) mod 2 = 1 and t+s<2*n then (n+s+1)/(n+t)*Bi(n+t,(t-s-1)/2); else ERROR("NoCase"); fi: end: # Input: symbolic n and numeric k # Output: binomial(n,k) # Try: # Bi(n,3); Bi := proc(n,k) option remember; local i; if k<0 then return(0); fi: mul(n-i,i=0..k-1)/k!; end: ################################## # Section 3: Winning Probability # of the First player # Functions: # # ProbWin(n,S), # # Diagonal Technique: # GuessH(n,s,S,x), MyH(n,s,S,x), # TestWin(n,S), MyDiag(n,x), # # Moment Statistics: # WinMo(n,mo), WinMoMean(n,mo), # AllMo(n,mo), AllMoMean(n,mo), # ################################### # Input: the n chips goal, # and the choice set S # Output: The winning prob. of player one # i.e. 1/2+1/2*sum_k a_n(k)^2/4^k. # Try: # [seq(ProbWin(n,[3,-1]),n=1..5)]; # [seq(subs(x=1,GuessW(n,0,0,[3,-1],x)),n=1..5)]; ProbWin := proc(n,S) option remember; local x,A,m,G; m := nops(S); A := [seq(Num1(n,k,0,S)^2,k=0..n^2+3*n+10)]; G := GuessGenRat(A,0,x); 1/2+1/2*abs(subs(x=1/m^2,G)); end: #################################################### # Input: numeric n,s, # choice list S and symbolic x # Output: Generating function # starting at s, never hit n # up to turn k # Try: # GuessH(2,0,[1,-1],x); GuessH := proc(n,s,S,x) option remember; local k,A,H; A := [seq(NotWin1(n,k,s,S),k=0..2*n+5)]; H := subs(x=x/2,GuessGenRat(A,0,x)); factor(H); end: # Input: numeric n,s, # choice list S and symbolic x # Output: solve generating # function starting at s, # never hit n up to turn k # Try: # MyH(5,2,[1,-1],[1/2,1/2],x); # GuessH(5,2,[1,-1],x); MyH := proc(n,s,S,P,x) option remember; factor((1-SolveGen(n,S,P,x)[s+1])/(1-x)); end: # Check whether gen.func. W is correct # Test w=B.C in the paper # Input: numeric n and choice list S # Output: List of w and list of B.C # substracted # Try: # TestWin(2,[1,-1]); # TestWin(5,[2,-1]); TestWin := proc(n,S) option remember; local x,i,A,L,R1,R2,R; L := GuessW(n,0,0,S,x); R1 := SolveGen(n,S,[1/2,1/2],x)[1]; R2 := x*MyH(n,0,S,[1/2,1/2],x); L :=taylor(L,x=0,21); R1 :=taylor(R1,x=0,21); R2 :=taylor(R2,x=0,21); L := [seq(coeff(L,x,i),i=1..19)]; R := [seq(coeff(R1,x,i)*coeff(R2,x,i),i=1..19)]; print(L); return(L-R); end: # Find winning prob. gen func # from diagonal method # Kind of messy, not simple # Input: numeric n, choice list S # and symbolic x # Output: generating function W # Try: MyDiag(1,[1,-1],x); MyDiag := proc(n,S,x) option remember; local t,s,B,C,F,sol,res; print("Goal",GuessW(n,0,0,S,x)); B := SolveGen(n,S,[1/2,1/2],x)[1]; C := x*MyH(n,0,S,[1/2,1/2],x); F := factor(subs(x=x/t,B)*subs(x=t,C))/t; sol := simplify([solve(denom(F),t)]); res := 0; for s in sol do if not(type(s,constant)) then res := res+ residue(F,t=s); fi: od: factor(numer(res)/expand(denom(res))); end: ############################################# # Input: numeric n,mo, choice list S # Output: Straight moments from # winning probability generating # funciton up to mo-moment. # Try: # WinMo(1,10,[1,-1]); WinMo := proc(n,mo,S) option remember; local i,x,f,T; f := GuessW(n,0,0,S,x); T := [subs(x=1,f)]; for i from 1 to mo do f := simplify(x*diff(f,x)); T := [op(T),subs(x=1,f)]; od: T/T[1]; end: # Input: numeric n,mo, choice list S # Output: Moments about the mean # from winning probability # generating funciton # Try: # [seq(WinMoMean(1,r,[1,-1]),r=1..10)]; WinMoMean := proc(n,mo,S) option remember; local i,A; A := WinMo(n,mo,S); add((-1)^i*binomial(mo,i)*A[mo-i+1]*A[2]^i,i=0..mo); end: # Input: numeric n,mo, choice list S # Output: Straight moments from Total #(winning & losing) probability # generating funciton up to mo-moment. # Try: # AllMo(1,10,[1,-1]); AllMo := proc(n,mo,S) option remember; local i,x,f,T; f := GuessT(n,0,0,S,x); T := [subs(x=1,f)]; for i from 1 to mo do f := simplify(x*diff(f,x)); T := [op(T),subs(x=1,f)]; od: T; end: # Input: numeric n,mo, choice list S # Output: Moments about the mean from # total (winning & losing) # probability generating funciton # Try: # [seq(AllMoMean(1,r,[1,-1]),r=1..10)]; AllMoMean := proc(n,mo,S) option remember; local i,A; A := AllMo(n,mo,S); add((-1)^i*binomial(mo,i)*A[mo-i+1]*A[2]^i,i=0..mo); end: ################################### # Section 4: Case{1,-u} # # Functions: # C1(n,u), Avg12(s,n), # ################################### # Proposition 11: # E[X_{n,s}] for case{1,-u}. # E[X_{n,s}]=2(C(n)-C(s)). # Input: numeric n and u # Ouput: C(n,u) # Try: # u:=2:s:=0: # A:=[seq(2*(C1(n,u)-C1(s,u)),n=s..20)]; # B:=[seq(Mo1(n,s,1,[1,-u],[1/2,1/2]),n=s..20)]; C1 := proc(n,u) option remember; if n <= 0 then return(0); fi: 2*C1(n-1,u)+1-C1(n-u-1,u); end: # Proposition 12 # Input: numeric s and symbolic n # Output: E[X_{n,s}] for u=2, p=2/3, q=1/3 # for a given s. # Try: # Avg12(0,n); Avg12 := proc(s,n) option remember; local i,m,A,P,a,S; A := [seq(Mo1(m,s,1,[1,-2],[2/3,1/3]),m=s..20)]; P := a[1]*n^2+a[2]*n+a[3]+a[4]*(-1/2)^n: S := solve( {seq(subs(n=i,P)=A[i-s+1],i=s..20)} ,{a[1],a[2],a[3],a[4]}); subs(S,P); end: ################################### # Section 5: Case{2,-1} # # Functions: # Guess: # GuessP21(n,s,x), GuessQ21(n,s,x), # GuessG21(n,s,x), # # Compute from recurrences: # MyP21(n,s,p,q,x), MyQ21(n,s,p,q,x), # MyG21(n,s,p,q,x), # # Corollary: # AnnK21(n,K), LastDe(N), # MoP(n,s,mo,p,q), # ################################### # Input: numeric n,s and symbolic x # Output: Guessing generating function # starting with s chips. # Game ends when land on n chips # from n-2 chips for the first time, # each move to add 2 or -1 chips # with prob. 1/2 each. # Try: # [seq(GuessP21(n,0,x),n=0..10)]; GuessP21 := proc(n,s,x) option remember; local j,k,A,B; if s=n then return(1); elif s>n then return(0); fi: A :=[0,seq(NumE(n,k-1,s,n-2,[2,-1]),k=1..2*n+5)]; factor(subs(x=x/2,GuessGenRat(A,0,x))); end: # Input: numeric n,s and symbolic x # Output: Guessing generating function # starting with s chips. # Game ends when land on n+1 chips # from n-1 chips for the first time # (never reaches n chips), # each move to add 2 or -1 chips # with prob. 1/2 each. # [seq(GuessQ21(n,0,x),n=0..10)]; GuessQ21 := proc(n,s,x) option remember; local j,k,A,B; if s=n+1 then return(1); elif s=n or s>n+1 then return(0); fi: A :=[0,seq(NumE(n,k-1,s,n-1,[2,-1]),k=1..2*n+5)]; factor(subs(x=x/2,GuessGenRat(A,0,x))); end: # Input: numeric n,s and symbolic x # Output: Guessing generating function # starting with s chips. # Game ends when land at least n chips # for the first time, each move to add # 2 or -1 chips with prob. 1/2 each. # Try: # [seq(GuessG21(n,0,x),n=0..10)]; # [seq(factor(GuessG21(n,1,x) # -GuessP21(n,1,x)-GuessQ21(n,1,x)),n=1..10)]; GuessG21 := proc(n,s,x) option remember; GuessGen(n,s,[2,-1],x); end: ################################ # Compute from recurrences: # Input: numeric n,s,p,q and symbolic x # Output: generating function from recurrences # starting with s chips. # Game ends when land on n chips # from n-2 chips for the first time, # each move to add 2 or -1 chips # with prob. p and q. # Try: # MyP21(10,5,1/2,1/2,x); # GuessP21(10,5,x); MyP21 := proc(n,s,p,q,x) option remember; if s=n then 1; elif s>n then 0; elif s<0 then ERROR(BadS); elif n=1 and s=0 then 0; elif s=n-1 then factor(q/p*MyQ21(n,n-1,p,q,x)*MyQ21(n-1,n-2,p,q,x)); else factor(MyP21(n,n-1,p,q,x)*MyP21(n-1,s,p,q,x) +MyQ21(n-1,s,p,q,x)); fi: end: # Input: numeric n,s,p,q and symbolic x # Output: generating function from # recurrences starting with s chips. # Game ends when land on n+1 chips # from n-1 chips for the first time # (never hit n chips), # each move to add 2 or -1 chips # with prob. p and q. # Try: # MyQ21(10,5,1/2,1/2,x); # GuessQ21(10,5,x); MyQ21 := proc(n,s,p,q,x) option remember; if s=n+1 then 1; elif s=n or s >n+1 then 0; elif s<0 then ERROR(BadS); elif n=1 and s=0 then p*x/(1-q*x); elif s=n-1 then factor(p*x/(1-q*x*MyP21(n-1,n-2,p,q,x))); else factor(MyQ21(n,n-1,p,q,x)*MyP21(n-1,s,p,q,x)); fi: end: # Input: numeric n,s,p,q and symbolic x # Output: generating function from # recurrences starting with s chips. # Game ends when land with at least # n chips for the first time, # each move to add 2 or -1 chips # with prob. p and q. # Try: # MyG21(10,5,1/2,1/2,x); GuessG21(10,5,x); # SolveGen(4,[2,-1],[p,q],x)[2]; # MyG21(4,1,p,q,x); MyG21 := proc(n,s,p,q,x) option remember; factor(MyP21(n,s,p,q,x)+MyQ21(n,s,p,q,x)); end: ################################################# # Corollary 13: # Input: numeric n and symbolic K # Output: The recurrence of a_{n}(k) # of case [2,-1] # Try: # A:=[seq(AnnK21(n,K),n=1..11)]; # B:=[seq(Rec1(n,0,[2,-1],K),n=1..11)]; # seq(factor(A[i]/B[i]),i=1..11); AnnK21 := proc(n,K) option remember; if n=0 or n=-2 then return(1); elif n=-1 then return(0); else simplify(K*AnnK21(n-1,K)-AnnK21(n-3,K)); fi: end: # Input: symbolic N # Output: Verify the relationship # of denominators in corollary 13. # Try: # LastDe(11); LastDe := proc(N) option remember; local n,x,p,q,A,B,C; A:=[seq(denom(SolveGen(n,[2,-1],[p,q],x)[1]),n=1..N)]; B:=[seq(A[n]/coeff(A[n],x,0),n=1..N)]; C:= seq(factor(B[n-1]-p*q^2*x^3*B[n-3]),n=4..N); print(B); [seq(factor(B[n]-C[n-3]),n=4..N)]; end: # Moment of P_{n,s}(x) for {2,-1} # Input: numeric n,s,mo, # symbolic/numeric p,q # Output: mo-moment X_{n,s} of # P_{n,s}(x), each move adds 2 # chips or remove one chip with # probability p,q # Try: # A:=[seq(MoP(n,0,0,1/3,2/3),n=1..40)]; # A:=[seq(MoP(n,0,1,1/3,2/3),n=1..40)]; # GuessC(A,N); MoP := proc(n,s,mo,p,q) option remember; local i,x,f; f := MyP21(n,s,p,q,x); for i from 1 to mo do f := simplify(x*diff(f,x)) od: factor(subs({x=1},f)); end: