> In 1921, G. Poyla showed that the probability that a random walk will
> result in a return to the origin is 1 in one dimension, 1 in two
> dimensions, and <1 in three dimensions. As reported by Adam and Delbruck,
> the actual number is 0.3405 (determined by Montroll in 1964). From A/D:
This is only true for the limit of RWS (random walk
steps) going to infinity.
proof: d=dimension, p=probability to back to the origin
suppose d=1 and rws=1 them p=0
" " rws=2 " p=1/2
" " rws=3 " p=0
you may see that when rws is odd it's impossible to back to the
origin, and when it's even the number of steps taking you away from the
origin have to equal to the number of steps appxoximating you to the origin.
for d=1 rws=4 p=3/8=6/16=(C4,2)/z^(rws)
Cn,m=n!/m!(n-m)! and z=2 (number of nearest neighbors)
Here n=rws and m=n/2 for p not= 0.
d=1 --> z=2
d=2 --> z=4 for d-dimensional square lattices.
d=3 --> z=6
Now, m=n/2 and we'll call n/2=l so the probability for d=1 may be
written as :
p=(2l)!/{(l!)^2}*1/2^(2l)
taking ln at both sides:
lnp=ln(2l!) - 2lnl! - 2lln2
appling stirling's formula (ln(x!)=xlnx -x), valid only for large x:
lnp=2lln2l -2l -2(llnl -l) -2lln2
lnp=2lln2 +2llnl -2l -2llnl +2l -2lln2
ln(p)=0
exp(ln((p))=exp(0)
p=1 .
When we used stirling's formula we supposed rws=infinity.
A similar proof is applied to d=2.
I'd like to ask something :
Think the random walk in any dimension as the vectorial sum of
three components (x,y and z). Each of these components is the vectorial
sum of the projection of the unit move vectors in that axis. So I think
that a n-dimensional random walk may be reduced to n 1-dimensional random
walks and the proof given above applies to each so in three dimensions
the probability should be equal to 1 also.
*-----------------------------------------------------------------------------*
* Rafael Iosef Najmanovich Szeinfeld |SMAIL: Depto. de Bioquimica - B10 INF.*
* Dept. Biochemistry -Chemistry Inst. | Universidade de Sao Paulo *
* Dept. Math. Physics -Physics Inst. | Av. Prof. Lineu Prestes 748 *
* University of Sao Paulo | CEP 05508-900 *
* E-MAIL : szeinfel at snfma1.if.usp.br | Sao Paulo - SP - Brazil *
*-----------------------------------------------------------------------------*
