3.5 Random Walk Models

3.5.1 One Dimensional Random Walk

Consider a Markov chain with States Space \(\{0, \, \pm 1, \, \pm 2, \, \pm 3, \, \cdots \cdots \}\).

Suppose the transitions are done as follows \[P_{i\, i+1} = P\] \[P_{i\, i -1} = 1 - P\] This chain is called a one- dimensional random walk. \[P^{2n}_{00} = \binom {2n}{n} \, P^n\, (1 - P)^{n}\] Suppose that the chain is at \(E_0\). After \(2n\) transits, it can be in \(E_0\) if number of transition in the right direction have to be equal to the number of transition in the left direction \[P_{00}^{2n + 1} = 0\]

\[P^{2n}_{00} = \frac {(2n)!}{n!\, n!} \, \left (P(1-P)\right )^n\, \hspace {0.2cm} , \hspace {0.3cm} n = 1, \, 2, \, 3, \, \cdots \cdots \]

Sterling’s approximation for \(n!\) \[n!\approx n^{n + \frac {1}{2}}\, e^{-n}\, \sqrt {2\pi }.\]

Using Sterling’s approximation for \(n!\) \begin {align*} P^{2n}_{00} & = \frac {(2n)^{2n + \frac {1}{2}}\, e^{-2n}\, \sqrt {2\pi }}{n^{n +\frac {1}{2}}\, e^{-n}\, \sqrt {2\pi }\, n^{n + \frac {1}{2}}\, e^{-n}\, \sqrt {2\pi }}\, \times \, \left (P(1 - P)\right )^n\\ & = \frac {1}{\sqrt {\pi }}\, 2^{2n}\, \cdot \, n^{2n + \frac {1}{2} - n - \frac {1}{2} - n - \frac {1}{2}}\, \left (P(1 - P)\right )^n\\ & = \frac {1}{\sqrt {\pi n}}\, 4^n\, \left (P(1 -P)\right )^n. \end {align*}

\[\sum ^{\infty }_{n = 1} P^{2n}_{00} = \sum ^{\infty }_{n = 1} = \frac {1}{\sqrt {\pi n}}\, 4^n\, \left (P(1 -P)\right )^n.\]

Case (i): \(\, P = \frac {1}{2}\) \[\sum ^{\infty }_{n = 1} P^{2n}_{00} = \frac {1}{\sqrt {\pi }}\,\sum ^{\infty }_{n = 1} \frac {1}{\sqrt {n}} = \infty \] because \(\sum _n\dfrac {1}{n^p}\, p-\) series is divergent for \(0 < p < 1\).

When \(p = \frac {1}{2}\) all the States of one-dimensional random walk are recurrent implying state \(E_0\) is recurrent.

Case (ii): \(p \neq \frac {1}{2}\) 

Consider \(\, \hspace {0.3cm} 4P(1 - P) < 1\) \[4P -4P^2 < 1\] \[1 + 4P^2 - 4P < 0\] \[\text {i.e}\hspace {0.3cm} (2P - 1)^2 > 0\] The inequality is true if \(p\neq \frac {1}{2}\) \[\sum ^{\infty }_{n = 1} P^{2n}_{00} = \sum _n \frac {1}{\sqrt {\pi n}}\, 4^n\, \left (P(1 - P)\right )^n = \sum _n \frac {\left (4P(1 - P)\right )^n}{\sqrt {\pi n}}.\] We’ll apply ratio test to determine the convergence. \[a_n = \frac {\left (4P(1 - P)\right )^n}{\sqrt {\pi n}}\]

\[a_{n +1} = \frac {\left (4P(1 - P)\right )^{n + 1}}{\sqrt {\pi (n + 1)}}\]

\[\frac {a_{n + 1}}{a_n} = \frac {\left (4P(1 - P)\right )}{\sqrt {1 + \frac {1}{n}}}\]

\[\lim _{n \rightarrow \infty } \frac {a_{n + 1}}{a_n} = 4P(1 - p) < 1.\] Hence by ratio test \[\sum _n P^{2n}_{00} < \infty \] implying State \(E_0\) is transient. Hence all states will be transient.

3.5.2 Two Dimensional Symmetrical Random Walk

At each transition, chain moves one step up or down or left or right, each with probability \(\frac {1}{4}\). Hence the transition probabilities can be described as \[P_{(i,j),(i + 1, j)} = P_{(i,j),(i,j+1)} = P_{(i,j),(i-1,j)} = P_{(i,j),(i,j-1)} = \frac {1}{4}, \hspace {0.3cm} i,j = 0,\, \pm 1,\, \pm 2, , \cdots \] The Markov chain described by a two dimensional random variable is irreducible \[P^{2n}_{00} = \sum ^n_{i =0} \frac {(2n)!}{i!\, i!\, (n -i)!\, (n - i)!} \, \left (\frac {1}{4}\right )^{2n}.\]

\[P^{2n + 1}_{00} = 0\hspace {0.6cm} \forall \, n = 1, \, 2,\, \cdots \cdots \] \begin {align*} P^{2n}_{00} = & \sum ^n_{i = 0}\frac {(2n)!\, n!\, n!}{i!\, i!\, (n - i)!\, (n - i)!\, n!\, n!}\, \left (\frac {1}{4}\right )^{2n}\\ = & \sum ^n_{i = 0} C_n^{2n}\, C_i^n\, C_i^n\, \left (\frac {1}{4}\right )^{2n}\\ & \boxed {Note:\hspace {0.6cm}(x + y)^{2n} = (x + y)^n\cdot (x + y)^n\hspace {0.6cm}\text {and}\hspace {0.6cm} C^{2n}_n = \sum ^n_{i = 0} C^n_i\, C^n_{n - i}}\\ & = \left (\frac {1}{4}\right )^{2n}\, \binom {2n}{n}\, \sum _{i = 1}^n C^n_i\, C^n_{n - i}\\ & = \left (\frac {1}{4}\right )^{2n}\, \binom {2n}{n}\, \binom {2n}{n}\\ & \approx \sum _n \frac {1}{\pi \, n}. \end {align*}

Therefore \[\sum ^n_{i = 1} P^{2n}_{00} = \sum ^{\infty }_{n = 1} \frac {1}{\pi \, n}\] which diverges and hence \(E_0\) is recurrent.

3.5.3 Three Dimensional Symmetric Random Walk

A particle moves in space, taking jumps of one unit in any one of the size directions \((\pm x, \pm y\) or \(\pm z)\) with probability \(\frac {1}{6}\).
We describe this walk as a Markov chain with infinite number of states. We can argue as we did with one and two dimensional walks that the three dimensional random walk is also an irreducible Mark chain.
The State Space \(S = \{(i,j, k):\, i = 0, \pm 1, \, \pm 2, \cdots , \hspace {0.2cm} j = 0, \, \pm 1, \, \pm 2, \, \cdots \, , \, \hspace {0.2cm} k =0, \, \pm 1, \, \pm 2, \, \cdots \}\)
\(P^{2n + 1}_{00} = 0\,\) for \(n = 1, \, 2, \, \cdots \cdots \)

\begin {align*} P_{00}^{2n} & = \sum _{\substack {0\leq j + k \leq n\\ 0\leq j \leq n\\ 0\leq k \leq n}}\frac {(2n)!}{j!\, j!\, k!\, k!\, (n -j - k)! \, (n -j - k)!}\, \left (\frac {1}{6}\right )^{2n}\\ & = \left (\frac {1}{2}\right )^{2n}\, \binom {2n}{n}\, \sum _{0\leq j + k\leq n} \left (\frac {n!}{j!\, k!\, (n - j - k)!}\, \left (\frac {1}{3}\right )^n\right )^2 \end {align*}

Binomial Probability function \[ = \frac {n!}{j!\, (n - j)!} \, \left (\frac {1}{2}\right )^2.\]

Trinomial Probability function \[= \frac {n!}{j!\, k!\, (n - j - k)!}\, \left (\frac {1}{3}\right )^n = P\] Then \(\sum _{0\leq j + k \leq n} P = 1\) \[\sum _{0\leq j + k \leq n} P^2 = \sum _{0\leq j + k \leq n} P\, P \leq \sum \max P\cdot P = \max P \sum P = \max P.\] Thus \begin {align*} P^{2n}_{00} & = \left (\frac {1}{2}\right )^{2n}\, \binom {2n}{n}\, \sum P^2\\ & = \left (\frac {1}{2}\right )^{2n}\, \binom {2n}{n}\, \max P. \end {align*}

Thus \(P\) is maximum when \(j = \frac {n}{3}, \hspace {0.2cm} k = \frac {k}{3}\) \[P^{2n}_{00} \leq \left (\frac {1}{2}\right )^{2n}\, \binom {2n}{n}\, \frac {n!}{\left (\frac {1}{3}\right )!\, \left (\frac {n}{3}\right )!\, \left (\frac {n}{3}\right )!}\, \left (\frac {1}{3}\right )^n.\]

Simplify and use Sterling’s approximation for \(n!\) and show that \[P^{2n}_{00} \leq \, \text {constant}\, \leq \frac {1}{n^{\frac {3}{2}}}\] \[\sum P_{00}^{2n} \leq C \, \sum \frac {1}{n^{\frac {3}{2}}} < \infty .\] Therefore \(E_0\) is transient.

Questions on this section

Stuck on something here? Ask below and it stays attached to this topic.