# Random walks¶

## Simple random walk¶

Definition (Simple random walk) A simple random walk $$S_n$$ is a stochastic process, with index set $$\mathcal{I} = \{0, 1, 2, ...\}$$ taking values on the integers $$(..., -2, -1, 0, 1, 2, ...)$$, such that

\begin{split}\begin{align} S_{n + 1} = \begin{cases} S_n + 1 & \text{ with probability } p \\ S_n - 1 & \text{ with probability } 1 - p \end{cases} \end{align}\end{split}

where $$S_0 \in \{..., -2, -1, 0, 1, 2, ... \}$$ is the initial position of the walk. If $$p = \frac{1}{2}$$ we call the walk symmetric, and asymmetric otherwise.

Theorem (Return probability of a simple random walk) The probability $$u_n = \mathbb{P}(S_n = S_0)$$, that a simple random walk returns to its starting point at time $$n$$ is

\begin{split}\begin{align} u_n = \begin{cases} {2m \choose m} p^m (1 - p)^m & \text{ if } n = 2m \text{ is even}, \\ 0 & \text{ if } n \text{ is odd}. \\ \end{cases} \end{align}\end{split}

Proof: Return probability of a simple random walk

The only way for the random walk to return to its initial position at time $$n$$, is if it makes an equal number of forward and backward steps. This is not possible if $$n$$ is odd, so in this case $$u_n = 0$$. If $$n = 2m$$ is even, there are $${2m \choose m}$$ ways to choose $$m$$ foward and $$m$$ backward steps and the probability of each of these is $$p^m(1-p)^m$$, hence

\begin{align} u_{2m} = {2m \choose m}p^m (1 - p)^m. \end{align}

## Recurrence and transience¶

Definition (Recurrent and transient walks) If a walk is bound to revisit its starting point, with probability $$1$$, it is called recurrent, otherwise it is called transient.

Theorem (Eventual return probability of a simple random walk) The probability that a simple random walk ever returns to its starting point is

\begin{align} \mathbb{P}(S_n = 0 \text{ for some } n = 1, 2, ... | S_0 = 0) = 1 - |p - q| \end{align}

where $$q = 1 - p$$. Hence the walk is recurrent if and only if $$p = q = \frac{1}{2}$$.

Proof: Eventual return probability of a simple random walk

Let $$A_n = \{S_n = 0\}$$ be the event that the walk revisits its starting point at time $$n$$ and

\begin{align} B_n = \{S_n = 0, S_k \neq 0 \text{ for } 1 \leq k \leq n - 1\} \end{align}

be the event that the first return of the walk occurs at time $$n$$. If $$A_n$$ occurs, exactly one of $$B_1, B_2, ..., B_n$$ occurs, so the events $$A_n \cap B_k$$ are disjoint and

\begin{align} \mathbb{P}(A_n) = \sum^N_{k = 1} \mathbb{P}(A_n \cap B_k). \end{align}

Further, since the steps of the walk are conditionally independent from each other, we have $$\mathbb{P}(A_n | B_k) = \mathbb{P}(A_{n - k})$$ and

\begin{align} \mathbb{P}(A_n \cap B_k) &= \mathbb{P}(A_n | B_k)\mathbb{P}(B_k) = \mathbb{P}(A_{n - k})\mathbb{P}(B_k), \end{align}

which together with the definitions $$u_n = \mathbb{P}(A_n)$$ and $$f_n = \mathbb{P}(B_n)$$ can be substituted in the summation formula to obtain

\begin{align} u_n = \sum^n_{k = 1} f_k u_{n - k} \text{ for } n = 1, 2, ... . \end{align}

Now introducing the generating functions of the two sequences

\begin{align} F(s) &= \sum_{n = 0}^\infty f_n s^n, ~~~ U(s) = \sum_{n = 0}^\infty u_n s^n, \end{align}

we can write

\begin{split}\begin{align} \sum_{n = 1}^\infty u_n s^n &= \sum^\infty_{n = 1} \sum^n_{k = 1} f_k s^k u_{n - k} s^{n - k} \\ &= \sum^\infty_{k = 1} \sum^\infty_{n = k} f_k s^k u_{n - k} s^{n - k} \\ &= \sum^\infty_{k = 1} f_k s^k \sum^\infty_{m = 0} u_m s^m \\ &= F(s)U(s). \end{align}\end{split}

Since $$u_0 = 1$$, the above expression yields

\begin{align} U(s) - 1 = F(s)U(s). \end{align}

Now we compute the expression for $$U(s)$$

\begin{align} U(s) &= \sum^\infty_{n = 0} u_n s^n = \sum^\infty_{m = 0} u_{2m} s^{2m} = \sum^\infty_{m = 0} {2m \choose m} (pqs^2)^m = (1 - 4pqs^2)^{-\frac{1}{2}}, \end{align}

and from this we obtain an expression for $$F(s)$$

\begin{align} F(s) = 1 - (1 - 4pqs^2)^{\frac{1}{2}}, \end{align}

arriving at the result

\begin{align} \sum^\infty_{n = 0} f_n &= \lim_{s \to 1} F(s) = 1 - (1 - 4pq)^{\frac{1}{2}} = 1 - |p - q|. \end{align}

## Random walks with absorption¶

Theorem (Gambler’s Ruin) Let $$S_n$$ be a simple random walk on $$\{0, 1, ..., N\}$$ with absorbing barriers at $$0$$ and $$N$$. If $$S_0 = a$$, where $$0 \leq a \leq N$$, then the probability $$v(a)$$ that the walk is absorbed at $$N$$ is

\begin{split}\begin{align} v(a) = \begin{cases} \frac{\left(\frac{q}{p}\right)^a - 1}{\left(\frac{q}{p}\right)^N - 1} & \text{ if } p \neq q \\ \frac{a}{N} & \text{ if } p = q = \frac{1}{2}, \end{cases} \end{align}\end{split}

where $$q = 1 - p$$.

Proof: Gambler's ruin

Let $$A$$ be the event that the walk is absorbed at $$N$$, $$X$$ be the value of the first step, which can be either $$-1$$ or $$1$$, and also let $$v(a) = \mathbb{P}(A | S_0 = a)$$. Then $$v(a)$$ follows the recursive relation

\begin{split}\begin{align} \mathbb{P}(A) &= \mathbb{P}(A | X = 1)\mathbb{P}(X = 1) + \mathbb{P}(A | X = -1)\mathbb{P}(X = -1)\\ v(a) &= p v(a + 1) + q v(a - 1), \end{align}\end{split}

which is a difference equation that can be solved by substituting the trial solution $$v(a) = C \lambda^a$$ and solving for $$\lambda$$ to obtain

\begin{split}\begin{align} v(a) = \begin{cases} \alpha + \beta \left(\frac{q}{p}\right)^a & \text{ if } p \neq q \\ \alpha + \beta a & \text{ if } p = q = \frac{1}{2}. \end{cases} \end{align}\end{split}

where $$\alpha$$ and $$\beta$$ are constants determined by the boundary conditions $$v(0) = 0$$ and $$v(N) = 1$$, giving

\begin{split}\begin{align} v(a) = \begin{cases} \frac{\left(\frac{q}{p}\right)^a - 1}{\left(\frac{q}{p}\right)^N - 1} & \text{ if } p \neq q \\ \frac{a}{N} & \text{ if } p = q = \frac{1}{2}. \end{cases} \end{align}\end{split}

Theorem (Recurrence/transience of bounded random walk) Let $$S_n$$ be a simple random walk on $$\{0, 1, ..., N\}$$ with absorbing barriers at $$0$$ and $$N$$. If $$S_0 = a$$, where $$0 \leq a \leq N$$, then the expected number $$e(a)$$ of steps before the random walk is absorbed at either $$0$$ or $$N$$ is given by

\begin{split}\begin{align} v(a) = \begin{cases} \frac{1}{p - q} \left(N \frac{\left(\frac{q}{p}\right)^a - 1}{\left(\frac{q}{p}\right)^N - 1} - a\right) & \text{ if } p \neq q \\ a(N - a) & \text{ if } p = q = \frac{1}{2}, \end{cases} \end{align}\end{split}

where $$q = 1 - p$$.

Theorem (Absorption probability of left-bounded random walk) Let $$S_n$$ be a simple random walk on $$\{0, 1, ..., N\}$$ with an absorbing barrier at $$0$$. If $$S_0 = a \geq 0$$, then the probability that the walk is absorbed at $$0$$ is given by

\begin{split}\begin{align} v(a) = \begin{cases} \left(\frac{q}{p}\right)^a & \text{ if } p > q \\ 1 & \text{ if } p \leq q \end{cases} \end{align}\end{split}

where $$q = 1 - p$$.

Proof: Absorption probability of left-bounded random walk

Let $$A$$ be the event that the walk is absorbed at $$0$$, $$X$$ be the value of the first step, which can be either $$-1$$ or $$1$$, and also let $$\pi(a) = \mathbb{P}(A | S_0 = a)$$. Then $$\pi(a)$$ follows the recursive relation

\begin{split}\begin{align} \mathbb{P}(A) &= \mathbb{P}(A | X = 1)\mathbb{P}(X = 1) + \mathbb{P}(A | X = -1)\mathbb{P}(X = -1)\\ \pi(a) &= \pi(a + 1) p + \pi(a - 1) q, \end{align}\end{split}

which is a difference equation that can be solved by substituting the trial solution $$\pi(a) = C \lambda^a$$ and solving for $$\lambda$$ to obtain

\begin{split}\begin{align} \pi(a) = \begin{cases} \alpha + \beta \left(\frac{q}{p}\right)^a & \text{ if } p \neq q \\ \alpha + \beta a & \text{ if } p = q = \frac{1}{2}. \end{cases} \end{align}\end{split}

In this case however, we only have a single $$\pi(0) = 1$$ boundary condition, from which we obtain

\begin{split}\begin{align} \alpha + \beta &= 1 && \text{ if } p \neq q \\ \alpha &= 1 && \text{ if } p = q = \frac{1}{2}. \end{align}\end{split}

Using the additional constraint $$0 \leq \pi(a) \leq 1$$, we see that

\begin{split}\begin{align} &\alpha = 1, && \beta = 0, && \text{ if } p < q \\ & && \beta = 0, && \text{ if } p = q = \frac{1}{2}, \end{align}\end{split}

and $$\pi(a) = 1$$ if $$p \leq q$$. For the case $$p > q$$, the above constraint does not allow us to determine $$\alpha$$ and $$\beta$$. To proceed, consider an unconstrained simple random walk starting from $$0$$, let $$C$$ be the event that it revisits its starting point, and let $$Y$$ be its first transition. Also, use the notation $$\pi_{p, q}(a)$$ for the probability that a left-constrained random walk with right and left transition probabilities $$p$$ and $$q$$, is absorbed at $$0$$. Then $$\mathbb{P}(B | Y = -1) = \pi_{q, p}(1)$$ and

\begin{split}\begin{align} \mathbb{P}(B) &= \mathbb{P}(B | Y = 1)\mathbb{P}(Y = 1) + \mathbb{P}(B | Y = -1)\mathbb{P}(Y = -1)\\ &= p \pi_{p, q}(1) + q \pi_{q, p}(1). \end{align}\end{split}

We have already shown $$\pi_{q, p}(1) = 1$$ when $$q < p$$, so that

\begin{split}\begin{align} \mathbb{P}(B) = 1 - (p - q) = p \pi_{p, q}(1) + q\\ \implies \pi_{p, q}(1) = \frac{q}{p}. \end{align}\end{split}

This constraint, together with $$\alpha + \beta = 1$$ gives $$\pi(a) = \left(\frac{q}{p}\right)^a$$ for the case $$p < q$$, concluding the proof.