Solving a symmetric random walk problem via generating functions

Question

Given a symmetric random walk on $\{0,1,2,\ldots,N\}$, and given a starting position $k$, the walker transitions to either $k-1$ or $k+1$ with equal probability. The absorption barriers $0$ and $N$ are “lose” and “win”, respectively. Denote by $p_k$ the probability of “winning” when starting from position $k$.

This yields the recurrence equation $$p_k = \frac{1}{2}(p_{k-1}+p_{k+1})$$ with boundary conditions $p_0 = 0$, and $p_N = 1$. It’s possible to think of this as a random walk on $\mathbb{Z}$ where $p_n = 1\,\forall n\ge N$ and $p_n = 0 \,\forall n\le 0$.

There is an elementary solution (and I know there are plenty of advanced theorems about random walks, too), but I’m stuck finding the solution via generating functions and would appreciate some help.

The elementary solution is:

• Note that the recurrence equation is equivalent to $p_{k+1}-p_k = p_k-p_{k-1} =: \Delta$ for $1\le k \le N-1$
• Therefore $p_N = p_N - p_{N-1}+p_{N-1} - p_{N-2} + p_{N-2} \mp \cdots -p_k+p_k = (N-k)\Delta + p_k$
• Plugging in the boundary conditions $p_N = 1$ and $p_0=0$ yields $\Delta = \frac{1}{N}$
• Thus $p_k = \frac{k}{N}$ for $0\le k\le N$ (or $p_k = \frac{\max\{0,\min\{k,N\}\}}{N}$ for $k\in\mathbb{Z}$).

How to solve this via generating functions? Because I know the solution I can guess a generating function for the $p_k$ by assembling it from well-known building blocks, namely $G(z) = \frac{z(1-z^N)}{N(1-z)^2}$ has the required coefficients. But it’s unclear how to get from the recurrence equation and boundary conditions to this $G(z)$. Any help or hints appreciated, thanks!

Answer 1

At first we start analysing the recurrence relation \begin{align*} \color{blue}{p_k}&\color{blue}{=\frac{1}{2}\left(p_{k-1}+p_{k+1}\right)}\qquad\qquad\color{blue}{1\leq k\leq N-1}\tag{1.1}\\ \color{blue}{p_0}&\color{blue}{=0, p_1=\frac{1}{N}}\tag{1.2}\\ \color{blue}{p_k}&\color{blue}{=0}\qquad\qquad\qquad\qquad\qquad\ \ \color{blue}{k<0}\tag{1.3}\\ \color{blue}{p_k}&\color{blue}{=1}\qquad\qquad\qquad\qquad\qquad\ \ \color{blue}{k>N}\tag{1.4} \end{align*}

• The recurrence relation (1.1) with initial condition (1.2) specifies $p_k$ in the range $0\leq k\leq N$.

• The boundary condition (1.3) is rather inconspicious since we are looking for a generating function \begin{align*} G(z)=\sum_{k=0}^{\infty}p_kz^k \end{align*} and (1.3) is fulfilled.

• It is the constraint (1.4) that needs special treatment, since the information $p_k=1, k>N$ is not part of the information contained in the recurrence relation (1.1) and (1.2), and we cannot expect to derive from (1.1) and (1.2) alone a generating function that satisfies (1.4).

• OP already stated a generating function which satifyies (1.1) to (1.4), namely \begin{align*} \color{blue}{G(z)}&\color{blue}{=\sum_{k=0}^{\infty}p_kz^k=\sum_{k=0}^{N}\frac{k}{N}z^k+\sum_{k=N+1}^{\infty}z^k}\\ &\color{blue}{=\frac{z\left(1-z^N\right)}{N(1-z)^2}}\tag{1.5} \end{align*} We will see what needs to be done to derive them based on the recursion relation (1.1) and (1.2).

For this purpose, we consider a strongly related recurrence relation with natural domain. We consider the recurrence relation \begin{align*} q_k&=\frac{1}{2}\left(q_{k-1}+q_{k+1}\right)& k\geq 1\tag{2.1}\\ q_0&=0, q_1=\frac{1}{N}\tag{2.2}\\ \end{align*} This recurrence relation looks similar to (1.1) and (1.2), but the domain of validity is not restricted to $0\leq k\leq N$. We can use the same derivation OP has used to find $p_k=\frac{k}{N}$ and obtain a generating function $H(z)$ with \begin{align*} \color{blue}{H(z)=\sum_{k=0}^{\infty}q_kz^k=\sum_{k=0}^{\infty}\frac{k}{N}z^n}\tag{2.3} \end{align*} Note, the upper limit of the sum in (2.3) is set to $\infty$ according to the range $k\geq 1$ in (2.1). Using (2.3) we can write $H(z)$ as rational function. We obtain \begin{align*} \color{blue}{H(z)}&=\frac{1}{N}\sum_{k=0}^{\infty}kz^k=\frac{z}{N}\sum_{k=1}^{\infty}kz^{k-1}\\ &=\frac{z}{N}\,\frac{d}{dz}\sum_{k=1}^{\infty}{z^k}=\frac{z}{N}\frac{d}{dz}\left(\frac{1}{1-z}\right)\\ &\,\,\color{blue}{=\frac{z}{N(1-z)^2}}\tag{2.4} \end{align*}

Here we could find a rational function for $H(z)$ according to OPs derivation of $p_k=\frac{k}{N}$. We will see at the end of this answer how to find the generating function solely from the recurrence relation (2.1) and (2.2). But at first we will look what's necessary to respect the boundary condition (1.4) and what to do to obtain $G(z)$ from $H(z)$.

• In oder to respect (1.4) we cancel all summands from $H(z)$ with index $k>N$ and add $z^k$ for each index $k>N$.

We obtain \begin{align*} \color{blue}{G(z)}&=H(z)-\sum_{k=N+1}^{\infty}\frac{k}{N}z^k+\sum_{k=N+1}z^k\\ &=H(z)-\sum_{k=0}^{\infty}\frac{k+N+1}{N}z^{k+N+1}+\sum_{k=0}^{\infty}z^{k+N+1}\tag{3.1}\\ &=H(z)-\sum_{k=0}^{\infty}\frac{k+1}{N}z^{k+N+1}\\ &=H(z)-z^{N+1}\sum_{k=0}^{\infty}\frac{k}{N}z^k+\frac{z^{N+1}}{N}\sum_{k=0}^{\infty}z^n\\ &=H(z)\left(1-z^{N+1}\right)+\frac{z^{N+1}}{N(1-z)}\\ &=\frac{z\left(1-z^{N+1}\right)}{N(1-z)^2}+\frac{z^{N+1}}{N(1-z)}\\ &\,\,\color{blue}{=\frac{z\left(1-z^N\right)}{N(1-z)^2}} \end{align*} in accordance with OP's derivation (1.5).

A generating function approach:

We can find a rational function for the recurrence relation (2.1) and (2.2) by recalling a theorem

Theorem: If a generating function has a representation as rational function of the form \begin{align*} A(z)=\sum_{k=0}^\infty a_k z^k=\frac{P(z)}{\color{blue}{Q(z)}}\tag{4.1} \end{align*} with $P(z), Q(z)$ polynomials, $\deg Q=q>\deg P$ and \begin{align*} \color{blue}{Q(z)=1+\alpha_1 z+\alpha_2 z^2+\cdots + \alpha_q z^q} \end{align*} then the coefficients $a_k$ follow the recurrence relation \begin{align*} \color{blue}{a_{k+q}+\alpha_1 a_{k+q-1}+\alpha_2 a_{k+q-2}+\cdots +\alpha_q a_{k}=0\qquad\qquad k\geq 0} \end{align*}

See for instance theorem 4.1.1 in Enumerative Combinatorics, Vol. I by R. P. Stanley. From the recurrence relation (2.1) with initial condition (2.2) and the theorem we set \begin{align*} H(z)=\frac{P(z)}{Q(z)} \end{align*} get $\alpha_1=-2, \alpha_2=1$ and obtain the denominator \begin{align*} \color{blue}{Q(z)=1-2z+z^2} \end{align*} In order to find $P(z)=a_0+a_1z$ we will use the initial condition (2.2). We also use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of a series. We obtain \begin{align*} \color{blue}{H(z)}&\color{blue}{=\frac{a_0+a_1z}{1-2z+z^2}}\\ \\ \color{blue}{a_0}&=[z^0]H(z)\left(1-2z+z^2\right)=[z^0]\left(q_0+q_1z+q_2z^2+\cdots\right)\left(1-2z+z^2\right)\\ &=q_0\,\,\color{blue}{=0}\\ \color{blue}{a_1}&=[z^1]H(z)\left(1-2z+z^2\right)=[z^1]\left(q_0+q_1z+q_2z^2+\cdots\right)\left(1-2z+z^2\right)\\ &=-2q_0+q_1\,\,\color{blue}{=\frac{1}{N}} \end{align*} and derive finally in accordance with (2.3): \begin{align*} \color{blue}{H(z)}=\frac{0+\frac{1}{N}z}{\left(1-2z+z^2\right)}\,\,\color{blue}{=\frac{z}{N\left(1-z\right)^2}} \end{align*}