Simple Random Walk

Let the state space be $\mathcal{S} = \Z$, a process $X_t$ has probability $p$ moving forward and probability $1-p$ moving backward (i.e. $p_{i, i+1} = p$ and $p_{i, i-1} = 1-p$). The process is called a simple random walk.

Gambler's Ruin

Gamblers's ruin is a very famous problem with a simple random walk.

Let $z$ be arbitrary state, then for each state $x$ we denote $\alpha(x) = P(X_n = z \text{ for some } n\ge 0|X_0 = x)$. Then we have $a(x) = (1-p)\alpha(x-1) + p\alpha(x+1)$.

To solve this difference equation we have:

$pa(x) + (1-p)a(x) = (1-p)\alpha(x-1) + p\alpha(x+1)\\ \implies p(a(x+1) - a(x)) = (1-p)(a(x) - a(x-1))$

Then $a(x+1) - a(x) = \frac{1-p}{p} (a(x) - a(x-1))$

$a(2) - a(1) = \frac{1-p}{p} (a(1) - a(0)) \implies a(2) - a(1) = \frac{1-p}{p} a(1)$

and $a(3) - a(2) = \frac{1-p}{p} (a(2) - a(1)) \implies a(3) - a(2) = (\frac{1-p}{p})^2 a(1)$

by induction, we have $a(n+1) - a(n) = (\frac{1-p}{p})^n a(1)$

And then we can have $a(n) - a(1) = a(n) - a(n-1) + a(n-1) - \cdots + a(2) - a(1) = a(1)\sum_{i=1}^{n-1}(\frac{1-p}{p})^i$

That is, $a(n) = \sum_{i=0}^{n-1}(\frac{1-p}{p})^i=\begin{cases} n a(1) & p = 0.5 \\ a(1)\frac{1-(\frac{1-p}{p})^{n}}{1-(\frac{1-p}{p})} & p\ne 0.5 \end{cases}$

By set $n = z$ we have $1 = a(n) = \begin{cases} n a(1) & p = 0.5 \\ a(1)\frac{1-(\frac{1-p}{p})^{n}}{1-(\frac{1-p}{p})} & p\ne 0.5 \end{cases}\implies a(1) = \begin{cases} 1/n & p = 0.5 \\ \frac{1-(\frac{1-p}{p})}{1-(\frac{1-p}{p})^{n}} & p\ne 0.5 \end{cases}$

That is, $\forall 1 \le i \le n, \alpha(i) = \begin{cases} i a(1) = i/n & p = 0.5 \\ a(1)\frac{1-(\frac{1-p}{p})^{i}}{1-(\frac{1-p}{p})} = \frac{1-(\frac{1-p}{p})}{1-(\frac{1-p}{p})^{n}}\frac{1-(\frac{1-p}{p})^{i}}{1-(\frac{1-p}{p})}=\frac{1-(\frac{1-p}{p})^{i}}{1-(\frac{1-p}{p})^{n}} & p\ne 0.5 \end{cases}$

Recurrence

In case to know if such process is transient, positive recurrent or negative recurrent, we will need to use the theorem: An irreducible MC is transient iff satisfies followed:

• $0 \le \alpha(x) \le 1$ for all $x \in S$.
• $\alpha(z) = 1\land \inf\{\alpha(x): x \in S\} = 0$.
• $\alpha(x) = \sum_{y \in S} p_{xy} \alpha(y)$ for all $x \in S, x\ne z$.

Since the 1st and 3rd conditions are automatically satisfied by the definition of $\alpha(x)$, we only need to check the 2nd condition and it's conditional on $p$.

If $p < 0.5$, then all conditions are satisfied, then it's transient where $\lim_{i \to \infty} \alpha(i) = \frac{1-(\frac{1-p}{p})^{i}}{1-(\frac{1-p}{p})^{n}} = 0$.

If $p = 0.5$, then this random walk is null recurrent.