#C15.txt, Pi Day; random walk (aka discrete Brownian motion)

Help:=proc(): print(`AllWalks(n,k) , GoodWalks(n,k)`): 
print(`PlotW(w), f(t) , g(t), a(t) `):
end:

#AllWalks(n,k): the set of ALL sequences of {1,-1}
#whose with n 1's and k -1's
AllWalks:=proc(n,k) local S1,S2,w:
option remember:

if n<0 or k<0 then
RETURN({}):
fi:

if k=0 then
RETURN({[1$n]}):
fi:

S1:=AllWalks(n-1,k):

 S2:=AllWalks(n,k-1):

{seq([op(w),1],w in S1),seq([op(w),-1],w in S2)}:
end:

#GoodWalks(n,k): the set of sequences of {1,-1}
#whose partial sums is NEVER negative, with n 1's and k -1's
GoodWalks:=proc(n,k) local S1,S2,w:
option remember:

if n<0 or k<0 then
RETURN({}):
fi:

if k=0 then
RETURN({[1$n]}):
fi:


if k>n then
RETURN({}):
fi:

S1:=GoodWalks(n-1,k):

 S2:=GoodWalks(n,k-1):

{seq([op(w),1],w in S1),seq([op(w),-1],w in S2)}:
end:

#PlotW(w): plots the random walk w
PlotW:=proc(w) local i:

plot([seq([i, convert([op(1..i,w)],`+`)],i=0..nops(w))]):

end:
#f(t): the generating function for good walks (never going
#below the x-axis) that break even (end at the x-axis)
f:=proc(t) 
(1-sqrt(1-4*t^2))/(2*t^2):
end:


#g(t): the generating function for good walks (never going
#below the x-axis)
g:=proc(t) 

1/(1-t-t^2*f(t)):
end:

#a(t): the generating function for ALL walks

a:=proc(t)

simplify(1/(1-2*t^2*f(t))*(1+2*t*g(t))):
end: