[proofplan] We condition on the outcome of the first step of the random walk. With probability $p$ the gambler's fortune increases to $a + 1$, and with probability $q$ it decreases to $a - 1$. By the law of total probability and the Markov property of the walk, the ruin probability $r_a$ satisfies $r_a = p\,r_{a+1} + q\,r_{a-1}$. The boundary conditions encode the definitions of ruin and victory. [/proofplan] [step:Condition on the first step of the random walk] Let $r_a = \mathbb{P}(\text{ruin} \mid \text{start at } a)$ for $0 \le a \le N$. The boundary conditions are immediate from the definition: starting at $a = 0$ means the gambler is already ruined, so $r_0 = 1$; starting at $a = N$ means the gambler has already reached the target, so $r_N = 0$. For $1 \le a \le N - 1$, consider the first bet. Let $W$ denote the outcome: $\mathbb{P}(W = +1) = p$ and $\mathbb{P}(W = -1) = q = 1 - p$. After the first bet, the fortune is $a + W$. By the [law of total probability](/theorems/1113), conditioning on the first step: \begin{align*} r_a &= \mathbb{P}(\text{ruin} \mid \text{start at } a, W = +1)\,\mathbb{P}(W = +1) + \mathbb{P}(\text{ruin} \mid \text{start at } a, W = -1)\,\mathbb{P}(W = -1). \end{align*} [/step] [step:Apply the Markov property to identify the conditional ruin probabilities] After the first bet, the gambler's fortune is $a + 1$ (if $W = +1$) or $a - 1$ (if $W = -1$). The remaining game from fortune $a + 1$ or $a - 1$ is an independent copy of the original problem — the future evolution of the random walk depends only on the current state, not on the history. This is the Markov property of the random walk. Therefore: \begin{align*} \mathbb{P}(\text{ruin} \mid \text{start at } a, W = +1) &= r_{a+1}, \\ \mathbb{P}(\text{ruin} \mid \text{start at } a, W = -1) &= r_{a-1}. \end{align*} Substituting into the law of total probability: \begin{align*} r_a = p\,r_{a+1} + q\,r_{a-1}. \end{align*} [guided] The Markov property is the essential ingredient here. After one step, the gambler has fortune $a+1$ or $a-1$, and faces the same game (same $p$, same boundaries at $0$ and $N$) from the new fortune. The key point is that the probability of eventual ruin starting from any state $b$ depends only on $b$, not on how the gambler arrived at $b$. This is because each bet is independent of all previous bets. Therefore, $\mathbb{P}(\text{ruin} \mid \text{fortune is } a + 1 \text{ after one step}) = r_{a+1}$, and similarly $\mathbb{P}(\text{ruin} \mid \text{fortune is } a - 1 \text{ after one step}) = r_{a-1}$. The law of total probability then gives $r_a = p \cdot r_{a+1} + q \cdot r_{a-1}$, a second-order linear recurrence for the sequence $(r_a)$. [/guided] [/step]