Solve for closed form $a_j$ given $a_j = 1 + pa_{j+1} + (1-p)a_{j-1}$ where $a_1 = 0$.

Question

Solve for a closed form expression for $a_j$ given constant $p \in (0,1)$ and $q=1-p$ and: \begin{align*} a_j &= 1 + pa_{j+1} + qa_{j-1} \\ \end{align*} Given that $a_1 = 0$.

The text says to use the hint that $a_j = c(1-j)$, but where do we get that hint? If we plug in that hint, we get $a_j = \frac{1-j}{p-q} = \frac{1-j}{2p-1}$ which correctly satisfies the original equation. But how would I solve this without the given hint?

Is this matrix version of the original equation helpful in any way?

\begin{align*} \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ -\frac{1}{p} & \left(1 - \frac{1}{p}\right) & \frac{1}{p} \end{pmatrix} \begin{pmatrix} 1 \\ a_{j-1} \\ a_j \end{pmatrix} &= \begin{pmatrix} 1 \\ a_j \\ a_{j+1} \end{pmatrix} \\ \end{align*}

Answer 1

The intuition of the hint is that from state $j$ you need to "move to the left" a net total of $j-1$ times to reach the absorbing state $1$, and the expected number of steps to move one unit to the left is independent of $j$ because the transition probabilities are.

For an order-2 recurrence relation, you should be given two initial conditions, so I assume $a_2=1/(1-2p)$ in addition to $a_1=0$.

Without being given or recognizing the hint, one approach is to use generating functions. Let $A(z)=\sum_{j=1}^\infty a_j z^j$. The recurrence relation for $j \ge 2$ implies that \begin{align} A(z) - a_1 z^1 &= \sum_{j=2}^\infty \left(1 + p a_{j+1} + q a_{j-1}\right) z^j \\ &= \sum_{j=2}^\infty z^j + \frac{p}{z} \sum_{j=2}^\infty a_{j+1} z^{j+1} + q z \sum_{j=2}^\infty a_{j-1} z^{j-1} \\ &= \frac{z^2}{1-z} + \frac{p}{z} (A(z) - a_1 z^1 - a_2 z^2) + q z A(z) \\ &= \frac{z^2}{1-z} - p a_2 z + \left(\frac{p}{z} + q z\right) A(z). \end{align} So \begin{align} A(z) &= \frac{z^2/(1-z)-p a_2 z}{1-p/z-qz} \\ &= \frac{z^3-p a_2 z^2(1-z)}{(1-z)(z-p-qz^2)} \\ &= \frac{(1-2p)z^3-p z^2(1-z)}{(1-2p)(1-z)(z-p-(1-p)z^2)} \\ &= \frac{z^2}{(1-2p)(1-z)^2} \\ &= \frac{z^2}{1-2p}\sum_{j=0}\binom{j+1}{1}z^j \\ &= \frac{1}{1-2p}\sum_{j=2}\binom{j-1}{1}z^j, \end{align} which implies that $$a_j=\frac{j-1}{1-2p}.$$

Answer 2

Let $b_j = a_{j+1} - a_j$, $b_j$ satisfies $$-pb_{j} + qb_{j-1} = 1$$ Let $c_j = b_j - \frac{1}{q-p}$, $c_j$ satisfies $$c_j = \frac{q}{p}c_{j-1}$$ So $$c_{j} = c_1\left(\frac{q}{p}\right)^{j-1}$$ We deduce $$a_{j} = a_1 + \frac{j-1}{q-p} + c_1\sum_{k=0}^{j-2}\left(\frac{q}{p}\right)^{k}$$

with the convention $$\sum_{k=n}^m A_k = 0,\text{ if } m < n$$