# 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

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

## 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

## 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

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

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

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

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

Now introducing the generating functions of the two sequences

we can write

Since \(u_0 = 1\), the above expression yields

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

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

arriving at the result

## 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

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

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

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

**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

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

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

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

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

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

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

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

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