Random walks in 2D and 3D are fundamentally different (Markov chains approach)
Marcov chains
3 elements:
- State space
- Transition probabilities
- Initial distribution
1 property:
- Markov property
- 无记忆性
State space
where you can go
random walk: Lattice points
Transition probabilities
not static
赋予每个附近的state一个probability
e.g. 2-D random walk，晶格里面4个方向，每一个概率都是1/4。
e.g. 3-D random walk, each state has 6 neighbors, so the probabilities are all 1/6.
Initial distribution
assign a probability to each state, indicating how likely you are to start at that state.
e.g random walk: 1 at the origin, and 0 everywhere else.
Recurrence and transience
- Initial state recurrent:
- guaranteed to return
- P(return)=1
- transient state
- P(return)<1
In 2-D the origin is a recurrent state, so it will go back.
In 3-D the origin is a transient state.
P(return)
assumption: run random walk to infinity, even you have returned.
V=#returns to the origin, E(V): expectation
- RECURRENCE
∵Marcov property，forget that we’ve returned
∴P(V=∞)=1, E(V)=∞
- TRANSIENCE
E(V)
=P(V=1)+2_P(V=2)+3_P(V=3)+4*P(V=4)+…
=P(V=1)
+P(V=2)+P(V=2)
+P(V=3)+P(V=3)+(V=3)
+P(V=4)+P(V=4)+P(V=4)+P(V=4)
+…
add it by column:
=P(V≥1)+P(V≥2)+P(V≥3)+P(V≥4)+…
P(V≥1): return probability, denote it as r. That is, P(return)=r.
P(V≥2): return twice,and since you forget you returned before, P(V≥2)= $r^2$ .
In general, P(V≥k)= $r^k$ .
So E(V)=$r+r^2+r^3+…+r^k+…$
geometric series!
E(V)=$\frac{r}{1-r}$ (finite) if r<1(transient)
SO
- recurrent⇒ E(V)=∞
- transient⇒ E(V)<∞
充分必要条件；transient定性。
another way:
think of V=#returns as a tally.
Have you returned at Step 1? YES+1 NO+0
Have you returned at Step 2? YES+1 NO+0
Have you returned at Step 3? YES+1 NO+0
Have you returned at Step 4? YES+1 NO+0 …
$p_{00}^{(1)}=1×P(yes)+0×P(no)=P(yes)$
- 00: origin→origin
- 1: revisit at step 1
E(V)=$p_{00}^{(1)}+p_{00}^{(2)}+…$
recurrent定量。
- SO
- recurrent⇒ E(V)=∞ ($=p_{00}^{(1)} + p_{00}^{(2)}+…$)
- diverge
- transient⇒ E(V)<∞
- converge
- recurrent⇒ E(V)=∞ ($=p_{00}^{(1)} + p_{00}^{(2)}+…$)
Back to random walk
2-D case
上下左右步数应当相等，所以只有可能在偶数步回到原点
$$ p_{00}^{(n)}=0, \space \space if \space n \space odd. $$
- how can we calculate $p_{00}^{(2n)}$?
e.g. $p_{00}^{(18)}=(\frac{1}{4})^{18}$(each path)*(#return paths)
假设左右各i步，则上下各n-i步。
原排列出$(2n)!$个，但是是无序排列，所以要除inter-permutations：$i!i!(n-i)!(n-i)!$，那么：
$$ No.\space of \space return \space paths=\sum_{i=0}^n \frac{(2n)!}{i!i!(n-i)!(n-i)!} $$
finally:
$$ p_{00}^{(2n)}=(\frac{1}{4})^{2n}\sum_{i=0}^n \frac{(2n)!}{i!i!(n-i)!(n-i)!} $$
$p_{00}^{(2n)}~ \frac{1}{n}$ , diverge
3-D case
difference:
- 1/4→1/6
- i, n-i → i, j, n-i-j
SO:
$$ p_{00}^{(2n)}=(\frac{1}{6})^{2n}\sum_{i,j=0}^n\frac{(2n)!}{i!i!j!j!(n-i-j)!(n-i-j)!} $$
$p_{00}^{(2n)} ~ \frac{1}{n^{3/2}}$ , converge
数学计算在这里不予列出。
通俗解释：三维的“outer space”大一些，更容易找不着回来的路。
注意到这里又有一个”cutoff between 2D and 3D”，可以在further reading里面了解。
Further reading: Larry Brown’s paper:
http://stat.wharton.upenn.edu/~lbrown…
Using electric circuits to prove recurrence / trasience:
https://math.dartmouth.edu/~pw/math10…
More complicated, but more general proof:
https://sites.math.washington.edu/~mo…
Actual probability for 3D random walk to come back:
https://mathworld.wolfram.com/PolyasR...
本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。
