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

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…