Random Walk—1-Dimensional

Author

Eric W. Weisstein
March 3, 2009

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Statistics/RandomWalk1-Dimensional.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/RandomWalk1-Dimensional.html.

©2009 Wolfram Research, Inc. except for portions noted otherwise

Probabilty distribution of signed offset

P[N_,d_]:= Binomial[N,(d+N)/2]/2^N

(Subscript[μ', p])

V7

Sum[(d^p) P[n,d],{d,-n,n,2}]

Sum[(d^p) P[n,d],{d,-n,n,2},Assumptions->p>0&&p∈Integers]

Factor/@Table[Sum[(d^p) P[n,d],{d,-n,n,2}],{p,0,15}]

l=First/@Partition[%,2]

FindLinearRecurrence[l]

FindLinearRecurrence[Rest[l]/n]

μ==0

Table[Sum[d P[n,d],{d,-n,n,2}],{n,5}]

V5

Sum[d P[n,d],{d,-n,n,2}]

Simplify[%,n∈Integers]

Table[Sum[d 2^(-n)Binomial[n,(d+n)/2],{d,-n,n,2}],{n,5}]

{Sum[d P[n,d]/.n->2m,{d,-m,m}]/.m->n/2,Sum[d P[n,d]/.n->2m+1,{d,-m,m}]/.m->(n-1)/2}

V7

Sum[d P[n,d],{d,-n,n,2}]

(Subscript[(μ'), 2])==n

Table[Sum[d^2 P[n,d],{d,-n,n,2}],{n,5}]

V5

{Sum[d^2 P[n,d]/.n->2m,{d,-m,m}]/.m->n/2,Sum[d^2 P[n,d]/.n->2m+1,{d,-m,m}]/.m->(n-1)/2}

Simplify[Sum[d^2 P[n,d],{d,-n,n,2}] ]

Simplify[%,n∈Integers]

V7

Sum[d^2 P[n,d],{d,-n,n,2}]

(Subscript[(μ'), 3])==0

V5

Table[Sum[d^3 P[n,d],{d,-n,n,2}],{n,5}]

{Sum[d^3 P[n,d]/.n->2m,{d,-m,m}]/.m->n/2,Sum[d^3 P[n,d]/.n->2m+1,{d,-m,m}]/.m->(n-1)/2}

Simplify[Sum[d^3 P[n,d],{d,-n,n,2}] ]

Simplify[%,n∈Integers]

V7

Sum[d^3 P[n,d],{d,-n,n,2}]

(Subscript[(μ'), 4])==n (3 n-2)

Table[Sum[d^4 P[n,d],{d,-n,n,2}],{n,7}]

V5

Table[n(3n-2),{n,7}]

{Sum[d^4 P[n,d]/.n->2m,{d,-m,m}]/.m->n/2,Sum[d^4 P[n,d]/.n->2m+1,{d,-m,m}]/.m->(n-1)/2}

Simplify[Sum[d^4 P[n,d],{d,-n,n,2}] ]

Simplify[%,n∈Integers]

V7

Sum[d^4 P[n,d],{d,-n,n,2}]

Probabilty distribution of absolute offset

absdist[N_]:=Sum[Abs[d] Binomial[N,(d+N)/2]/2^N,{d,-N,N,2}]

absdist[n]

Table[absdist[n],{n,0,20}]

Denominator[%]

Sum[(Abs[d]) P(n,d),{d,-n,n,2}]

V5

(Subscript[μ, 1o])=(Sum[-d P[n,d],{d,-n,-1,2}]
+Sum[d P[n,d],{d,1,n,2}])

FullSimplify[(Subscript[μ, 1o])/.Floor[(n-1)/2]->(n-1)/2]

FunctionExpand[1+(((2^(2-n)) Gamma[1+n] Hypergeometric2F1Regularized[2,((3-n)/2),((5+n)/2),-1])/(Gamma[(1/2) (-1+n)]))]

Table[1+(((2^(2-n)) Gamma[1+n] Hypergeometric2F1Regularized[2,((3-n)/2),((5+n)/2),-1])/(Gamma[(1/2) (-1+n)])),{n,5}]

Simplify[(Subscript[μ, 1o]) /. n->2J+1]

FullSimplify[Sum[(2d-1)/(J+d-1)!/(J-d)!,{d,J}]N!/2^(N-1) /. N->(2J-1)]

(Subscript[μ, 1e])=FullSimplify[(Sum[-d P[n,d],{d,-n,-2,2}]
+Sum[d P[n,d],{d,0,n,2}])/.{Floor[n/2]->n/2,Floor[(n-2)/2]->n/2-1}]

Table[((2 Gamma[((1+n)/2)])/((Sqrt[π]) Gamma[(n/2)])),{n,5}]

(Subscript[μ, 2])=FullSimplify[Sum[d^2 P[n,d],{d,-n,n,2}] /. Floor[n]->n]

(Subscript[μ, 3])=FullSimplify[Sum[d^3 P[n,d],{d,-n,n,2}] /. Floor[n]->n]

(Subscript[μ, 4])=FullSimplify[Sum[d^4 P[n,d],{d,-n,n,2}] /. Floor[n]->n]

FullSimplify[Sum[d/(J+d)!/(J-d)!,{d,J}]]

FullSimplify[Gamma[n+1]/2^(n-2) n/2/2/Gamma[1+n/2]^2]

ew1[J_]:=(2J+1)!/2^(2J+1)Sum[Abs[d]/((2J+1+d)/2)!/((2J+1-d)/2)!,{d,-(2J+1),2J+1,2}]
ew2[J_]:=(2J+1)!/2^(2J)Sum[d/((2J+1+d)/2)!/((2J+1-d)/2)!,{d,1,2J+1,2}]
ew3[J_]:=(2J+1)!/2^(2J)Sum[(d+1)/((2J+2+d)/2)!/((2J-d)/2)!,{d,0,2J,2}]
ew4[J_]:=(2J-1)!/2^(2J-2)Sum[(2d-1)/(J+d-1)!/(J-d)!,{d,1,J}]
ew5[J_]:=(2J+1)!/2^(2J)Sum[(2d+1)/(J+d+1)!/(J-d)!,{d,0,J}]
ew6[j_]:=Gamma[2j](1+j-Hypergeometric2F1[1,-j,j,-1])/(2^(2j-2)Gamma[j]Gamma[1+j])+1
ew7[j_]:=2/Sqrt[Pi] Gamma[j+1/2]/Gamma[j](1+j-Hypergeometric2F1[1,-j,j,-1])/j+1

FullSimplify[{ew1[J],ew2[J],ew3[J],ew4[J],ew5[J],ew6[J],ew7[J]}]//ColumnForm

FullSimplify[(2J-1)!/2^(2J-2)Sum[(2d-1)/(J+d-1)!/(J-d)!,{d,J}]]

V7

s=Sum[Abs[d]P[n,d],{d,-n,n,2}]

(2^(1-n)) Binomial[n,Ceiling[(n/2)]] Ceiling[(n/2)]/.n->0

FullSimplify[s,Mod[n,2]==0]

Refine[s,Mod[n,2]==1]//FullSimplify

Table[(Piecewise[{{-(2^(-n)) n, n==0}, {(2^(1-n)) Binomial[n,Ceiling[(n/2)]] Ceiling[(n/2)], True}}]),{n,0,20}]

FullSimplify[FunctionExpand[(2^(1-n)) Binomial[n,Ceiling[(n/2)]] Ceiling[(n/2)]],n∈Integers]

FullSimplify[(2^(1-n)) Binomial[n,Ceiling[(n/2)]] Ceiling[(n/2)]-(((n-1)!!)/((n-2)!!)),Mod[n,2]==0]

FullSimplify[(2^(1-n)) Binomial[n,Ceiling[(n/2)]] Ceiling[(n/2)]-((n!!)/((n-1)!!)),Mod[n,2]==1]

FullSimplify[Refine[(2^(1-n)) Binomial[n,Ceiling[(n/2)]] Ceiling[(n/2)]-((n!!)/((n-1)!!)),Mod[n,2]==1],Mod[n,2]==1]

(∑_d^J)(d/((d+J)! (J-d)!))==(1/(2 (Gamma[J]) (Gamma[J+1])))

Sum[(d/((J+d)!(J-d)!)),{d,J}]//FullSimplify

(∑_d^J)((2 d-1)/((d+J-1)! (J-d)!))==(1/((Gamma[J])^2))

Sum[((2d-1)/((J+d-1)!(J-d)!)),{d,J}]//FullSimplify

Generating Function

Table[(2^(1-n)) Binomial[n,Ceiling[(n/2)]] Ceiling[(n/2)],{n,0,10}]

GeneratingFunction[(2^(1-n)) Binomial[n,Ceiling[(n/2)]] Ceiling[(n/2)],n,x]

...wrong...

Series[((2 (2+x-4 (x^2)-2 (x^3)-2 (Sqrt[1-x]) (Sqrt[1+x])-(Sqrt[1-x]) x (Sqrt[1+x])+2 (Sqrt[1-x]) (x^2) (Sqrt[1+x])+(Sqrt[1-x]) (x^3) (Sqrt[1+x])))/((Sqrt[1-x]) (x^2) (Sqrt[1+x]) (-1+(x^2)))),{x,0,10}]

Series[(x/(((1-(x^2)))^(3/2)))+x(x/(((1-(x^2)))^(3/2))),{x,0,10}]

FullSimplify[(x/(((1-(x^2)))^(3/2)))+x(x/(((1-(x^2)))^(3/2)))]

Series[(x/((((1-x))^(3/2))(Sqrt[1+x]))),{x,0,10}]

Refine[(2^(1-n)) Binomial[n,Ceiling[(n/2)]] Ceiling[(n/2)]/.n->2n,n∈Integers]

GeneratingFunction[(2^(1-2 n)) n Binomial[2 n,n],n,x]

Series[%,{x,0,10}]

SeriesCoefficient[(x/(((1-x))^(3/2)))l,{x,0,n}]

FullSimplify[%]

Asymptotic Series

ser=Normal[Series[Gamma[J+1/2],{J,Infinity,50}]]/
  Normal[Series[Gamma[J],{J,Infinity,50}]];

Normal[Series[ser,{J,Infinity,10}]/Sqrt[J]]

GammaRatio[J_]:=2/Sqrt[Pi]Sqrt[J](1-1/(8J)+1/(128J^2)+5/(1024J^3)-21/(32768J^4)-399/(262144J^5))

GammaRatio[J]/Sqrt[2]/Sqrt[N]*Sqrt[Pi] /. J->N/2

Normal[Series[GammaRatio[J] /. J->(N+1)/2,{N,Infinity,5}]/Sqrt[2N/Pi]]

Plots

RandomWalk[N_,p_:.5]:=Module[{l={{0,0}},x=0,i=0},
  While[i<N,
    x+=If[Random[]>p,1,-1];
    l=Append[l,{++i,x}]
  ];
  l
]

walk[N_,p_]:=ListPlot[RandomWalk[N,p],Joined->True,AxesOrigin->{0,0},DisplayFunction->Identity]

Show[GraphicsArray[{walk[200,.2],walk[200,.5],walk[200,.8]}],DisplayFunction->$DisplayFunction]

Show[{walk[500,.5],walk[500,.5],walk[500,.5]},DisplayFunction->$DisplayFunction]

Histogram

<<Statistics`DataManipulation`
<<Graphics`Graphics`

r[n_]:=Plus@@Table[Random[Real,{-.5,.5}],{n}]

h=BinCounts[Table[r[1000],{5000}],{-30,30,1}]

BarChart[h,BarGroupSpacing->0,PlotRange->All,Ticks->None]

Numerical

2RandomInteger[{0,1},10]-1

With[{n=10^7},{Abs[Total[2RandomInteger[{0,1},n]-1]],(Sqrt[((2.n)/π)])}]//Timing

With[{n=10^8},{Abs[Total[2.RandomInteger[{0,1},n]-1]],(Sqrt[((2.n)/π)])}]//Timing