Random walk as a difference equation

Example

Let $\xi_1, \xi_2, \dots$ be independent and identically distributed random variables with $P(\xi_n = 1) = P(\xi_n = -1) = \tfrac{1}{2}$. The simple symmetric random walk on $\Z$ is the solution of the stochastic difference equation $$S_{n+1} = S_n + \xi_{n+1}, \qquad S_0 = 0.$$ It has the form $X_{n+1} = f(X_n, \xi_{n+1})$ with $f(x, e) = x + e$, so it is a stochastic difference equation. Solving the recursion gives $S_n = \xi_1 + \cdots + \xi_n$. Taking expectations in the equation gives the deterministic difference equation $E[S_{n+1}] = E[S_n]$, so $E[S_n] = 0$. Squaring gives $S_{n+1}^2 = S_n^2 + 2 S_n \xi_{n+1} + 1$, and since $\xi_{n+1}$ is independent of $S_n$ with mean $0$, $E[S_{n+1}^2] = E[S_n^2] + 1$, so $E[S_n^2] = n$.

Probabilities of the walk also solve difference equations. Fix an integer $N \ge 1$ and let $p_j$ be the probability that the walk started at $j \in \set{0, \dots, N}$ reaches $N$ before $0$. Conditioning on the first step gives $p_j = \tfrac{1}{2} p_{j+1} + \tfrac{1}{2} p_{j-1}$ for $0 < j < N$, with $p_0 = 0$ and $p_N = 1$. This linear recurrence has characteristic polynomial $(z - 1)^2$, so $p_j = a + bj$, and the boundary values give $p_j = j/N$.