#Ross Berkowitz hw22.txt #Posting Permission Granted. ########## 1 ########################## #Because our sequence a(i) giving the probability of winning satisfies the recurrence #0=p*a(i+1)-a(i)+(1-p)*a(i-1) it has form c_1 alpha^n+c_2 beta^n #where alpha and beta are the roots of the characteristic equation p-x+(1-p)x^2. #So let alpha=(1-sqrt(1-4p(1-p)))/(2(1-p)) and beta=(1+sqrt(1-4p(1-p)))/(2(1-p)) #The starting condition a(0)=0 gives c_1+c_2=0. The other starting condition gives #c_1 alpha^n-c_1beta^n=1. so c_1=1/(alpha^n-beta^n) #Our final solution is of the form 1/(alpha^n-beta^n)*alpha*n-1/(alpha^n-beta^n)*beta^n. ############# 3 ################################### #As noted in class we have that the expected duration satisfies the recurrence #d(i)=1+(1-p)*d(i-1)+p*d(i+1). So our homogeneous solution has alpha, beta as above. #Next we must find the particular solution. We note that if we have a sequence of the form #d(i)=c*i then p*d(i+1)-d(i)+(1-p)*d(i-1)=2p*c-c. So setting c=1/(2p-1) we get that #c*i satisfies the recurrence p*d(i+1)-d(i)+(1-p)*d(i-1)=-1. #So we have our solution is of the form d(i)=c_1 alpha^n+c_2 beta^n+i/(2p-1). #Lastly we must find c_1 and c_2. To do this we use that d(0)=0 and d(n)=0. #So we can conclude that c_1=-c_2 from the first condition. Plugging this into the second #we get c_1 alpha^n-c_1 beta^n+n/(2p-1)=0. Therefore c_1=n/((2p-1)(beta^n-alpha^n)). #################### 5 ################################### #Conditioning on winning satisfies almost the same recurrence modulo the assumption that # we never lose from 1 dollar. so we require Du(1)=1+Du(2). VDW:=proc(p,N) local Du,eq,unk,i,sol: unk:={ seq(Du[i],i=0..N)}: eq:={Du[N]=0,Du[1]=Du[2]+1, seq(Du[i]=p*Du[i+1]+(1-p)*Du[i-1]+1, i=2..N-1)}: sol:=solve(eq,unk): subs(sol, [seq(Du[i],i=1..N-1)]): end: ####################6 ################################ #After a few trials I feel pretty good about the guess VDW(1/2,N)[i]=(N-1+i)(N-1-i) #=(N-1)^2-(i-1)^2 ################## 7 ################################## #We can prove that this answer is correct simply be verifying that it satisfies the #necessary recurrences. Let A(i)=(N-1)^2-(i-1)^2 For the boundary condiditions we note that #A(N)=(N-1)^2-(N-1)^2=0. For the other side A(1)=(N-1)^2=(N-1)-1+1=A(2). #Lastly for all of the middle terms one can compute quickly by hand (or by maple) that #p*A(i+1)-A(i)+(1-p)A(i-1)=i(2-4p)+4p-3. Plugging in p=1/2 we get #p*A(i+1)-A(i)+(1-p)A(i-1)=-1. Which is exactly the recurrence we desire. So this proves #that (N-1)^2-(i-1)^2 is the expected duration of a winning game with a fair coin starting #with i dollars and ending at N. ############################# Class Stuff ############################# #April 15, 2013, starting gambling theory Help:=proc(): print(` LC(p) , GRgame(p,s,N) `): print(`ManyGames(p,s,N,HowMany), VW(p,N) , VD(p,N) `): end: #LC(p): simulating a loaded coin whose #that returns true with prob. p, p rational LC:=proc(p) local a,b,ra: a:=numer(p): b:=denom(p): ra:=rand(1..b)(): evalb(ra<=a): end: #GRgame(p,s,N):inputs prob. p of success (a rational number) #starting capital, and exit capital N (if you are a winner) #once you have 0 dollars you must leave the casino #Returns, true (false) if you won (or lost) followed #by the number of rounds it took GRgame:=proc(p,s,N) local ca,du,toss: ca:=s: du:=0: while ca>0 and ca=N), du: end: #ManyGames(p,s,N,HowMany): repeats GRgame(p,s,N) #HowMany times, and returns the percentage of times #the gambler won, and the average duration if it won, #followed by the average duration if it lost followed #by the average duration ManyGames:=proc(p,s,N,HowMany) local DUw, DUl, DU, W,i,jake: W:=0: DUw:=0: DUl:=0: DU:=0: for i from 1 to HowMany do jake:=GRgame(p,s,N): if jake[1] then W:=W+1: DUw:=DUw+jake[2]: DU:=DU+jake[2]: else DUl:=DUl+jake[2]: DU:=DU+jake[2]: fi: od: if W=0 or W=HowMany then print(`This is never going to happen`): RETURN(FAIL): fi: evalf(W/HowMany), evalf(DUw/W), evalf(DUl/(HowMany-W)), evalf(DU/HowMany): end: #VW(p,N): inputs prob. of winning one round, p #and the exit capital N, outputs the List of #size N-1 whose i-th entry is the EXACT prob. #of winning if you currently posses i dollars VW:=proc(p,N) local w,eq,unk,i,sol: #w[i]: prob. of ultimately winning with current capital i #in Gambler's ruin name unk:={ seq(w[i],i=0..N)}: eq:={w[0]=0, w[N]=1, seq(w[i]=p*w[i+1]+(1-p)*w[i-1], i=1..N-1)}: sol:=solve(eq,unk): subs(sol, [seq(w[i],i=1..N-1)]): end: #VD(p,N): inputs prob. of winning one round, p #and the exit capital N, outputs the List of #size N-1 whose i-th entry is the EXACT EXpected Duration #of winning if you currently posses i dollars VD:=proc(p,N) local Du,eq,unk,i,sol: #Du[i]: expected duration of #a gambler's ruin with max. cap N and porb. p of winning #a dolllar unk:={ seq(Du[i],i=0..N)}: eq:={Du[0]=0, Du[N]=0, seq(Du[i]=p*Du[i+1]+(1-p)*Du[i-1]+1, i=1..N-1)}: sol:=solve(eq,unk): subs(sol, [seq(Du[i],i=1..N-1)]): end: