# Hw17 # Sunday 03.20.2014 # Ha Luu #Problem 1: #SIrec(L,Ini,n): The n-th term of the #solution of the linear recurrence equation #with constant coefficients #a(n)=L[1]*a(n-1)+L[2]*a(n-2)+ ... + L[-1]*a(n-nops(L)) #a(0)=Ini[1], ..., a(nops(Ini)-1)=Ini[-1] SIrec:=proc(L,Ini,f,m,n) local i: option remember: if nops(L)<>nops(Ini) then print(Ini, L, `should be lists of the SAME length `): RETURN(FAIL): fi: if n<0 then 0: elif nnops(Ini)+nops(Fini) then RETURN(FAIL): fi: var:={seq(a[i],i=0..N)}: eq:={seq(a[i]=Ini[i+1],i=0..nops(Ini)-1), seq(a[N-i]=Fini[i+1],i=0..nops(Fini)-1)}: eq:= eq union {seq(a[i]-add(L[j]*a[i-j],j=1..nops(L))-subs(n=i,f), i=nops(L)..N)}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): else subs(var,[seq(a[i],i=0..N)]): fi: end: ############################################################# # Problem 3: #GR(p,N) that inputs real number p, between 0 and 1 (or symbolic), #,and N as the goal #and outputting a list of length N+1, such G[i+1] #is your chance of exiting a winner in a casino : #if you enter a casino #with i dollars where at each step you win a dollar with a probability p #and lose a dollar with a probability 1-p, and you stop playing when you are wither broke #or got N dollars #The probability recurrence is Pr[N|i]=p*Pr[N|i+1]+(1-p)*Pr[N|i-1] #The characteristic polynomial is x^2-1/p*x+(1-p)/p=0 # x1= 1 or x2=(1-p)/p #Say Pr[N|0]=0 and Pr[N|N]=1 #Solving the general solution for the recurrence we have: #Pr[N|i]=(1-x2^i)/(1-x2^N) GR1:=proc(p,N) local i,L,x2,G, Gpro: G:=[]: x2:=(1-p)/p: for i from 0 to N do Gpro:=(1-x2^i)/(1-x2^N): G:=[op(G),Gpro]: od: G: end: # Solving it using the same method as dIBVP GR:=proc(p,N) local i, G: dBVP([1/p,(1-p)/p],[0],[1],N): end: #Comment: I think GR1 is the correct answer, however, I can't tell why GR is wrong ############################################################# # Problem 4: # The expected number of round to win or going broke with i dollars is # 1 (to go to next round) + the expected number or round of the successive # step (i+1 dollar or i-1 dollar) # ER[i]=1+p*ER[i+1]+(1-p)*ER[i-1] # The characteristic polynomial is x^2-1/p*x+(1/p+(1-p)/p)=0 # x^2 -1/p*x +(2-p)/p =0 # with x1:=(1+sqrt(4p^2-8p+1))/2p and x2:=(1-sqrt(4p^2-8p+1))/2p # Obviously ER[0]=ER[N]=0 # ER[i]=A*(x1)^i +B*(x2)^i # Thus A+B=0 and A*(x1)^h+B*(x2)^h=0 # --> A=-B and A(x1^h-x2^h)=0 # ?? from here I got A,B to be 0. # I am not sure why I can't use the same logic for the previous step. #Solving it using dIBVP: LGR:=proc(p,N): dIBVP([1/p,(1-p)/p],[0],[0],-1,n,N): end: ############################################################### ############################################################## #C17.txt: March 27, 2014 #Discrete Calculus Help:=proc(): print(` GPi(N) , Dsin(x,h) , Srec(L,Ini,n)`): print(` dBVP(L,Ini,Fini,N) `): end: #GPi(N): the geometrical discrete Pi #the number of lattice points (x,y) such #that x^2+y^2nops(Ini) then print(Ini, L, `should be lists of the SAME length `): RETURN(FAIL): fi: if n<0 then 0: elif nnops(Ini)+nops(Fini) then RETURN(FAIL): fi: var:={seq(a[i],i=0..N)}: eq:={seq(a[i]=Ini[i+1],i=0..nops(Ini)-1), seq(a[N-i]=Fini[i+1],i=0..nops(Fini)-1)}: eq:= eq union {seq(a[i]-add(L[j]*a[i-j],j=1..nops(L)), i=nops(L)..N)}: var:=solve(eq,var): if var=NULL then RETURN(FAIL): else subs(var,[seq(a[i],i=0..N)]): fi: end: