In gambler's ruin on a fair game, why is the chance of reaching N before 0 from k equal to k/N?

## The set-up A gambler starts with `k` units and bets one unit at a time on a fair coin. The fortune performs a random walk on the integers `0, 1, ..., N`. Play stops at `0` (ruin) or at `N` (target reached); both are **absorbing** states. Write `P(k)` for the probability of reaching `N` before `0`, starting from `k`. ## One-step conditioning Condition on the outcome of the very next bet. From `k` you land on `k+1` with probability 1/2 and on `k-1` with probability 1/2, and from wherever you land the problem looks exactly the same with a new starting fortune — the walk has no memory of how it got there. So for every interior state: ``` P(k) = 0.5 * P(k+1) + 0.5 * P(k-1), 0 < k < N P(0) = 0, P(N) = 1 ``` The boundary conditions are not decoration — they are what pins the solution down, and forgetting them is the most common failure. ## Solving the recursion Rearrange: `P(k+1) - P(k) = P(k) - P(k-1)`. The successive differences are all equal, so `P` is an **arithmetic sequence** — a straight line in `k`. Write `P(k) = a + b*k`. The boundary `P(0) = 0` forces `a = 0`; the boundary `P(N) = 1` forces `b = 1/N`. Hence ``` P(k) = k / N ``` So a player starting with 30 units aiming for 100 has probability 0.30 of getting there before going broke, and 0.70 of ruin. Doubling your money — target `N = 2k` — is exactly a 50/50 proposition, which is the one case where fairness of the game translates directly into fairness of the outcome. ## The martingale reading There is a one-line argument that is worth having ready. In a fair game the expected fortune never changes, so the expected fortune at the moment play stops equals the starting fortune. At stopping, the fortune is either `N` or `0`, so by the law of total expectation `N * P(k) + 0 * (1 - P(k)) = k`, giving `P(k) = k/N` immediately. This is the same conditioning idea applied to the *value* rather than to the probability. ## Expected duration Let `D(k)` be the expected number of bets before absorption. Condition on the first bet again, remembering to charge one bet for the step taken: ``` D(k) = 1 + 0.5 * D(k+1) + 0.5 * D(k-1), D(0) = D(N) = 0 ``` The solution is `D(k) = k * (N - k)`. Verify by substitution: `0.5*(k-1)(N-k+1) + 0.5*(k+1)(N-k-1) + 1` simplifies to `kN - k^2 = k(N-k)`. From 30 against a target of 100 that is `30 * 70 = 2100` bets on average — a fair game with a distant target takes a very long time to resolve, and the mean duration is maximised in the middle at `k = N/2`. ## The unfair game With win probability `p` per bet, `q = 1 - p` and ratio `r = q/p`, the same conditioning gives `P(k) = p*P(k+1) + q*P(k-1)`, whose solution for `p != 1/2` is ``` P(k) = (1 - r^k) / (1 - r^N) ``` The geometric form is brutal. A tiny edge against the player compounds over the many bets required to travel a long distance, so the chance of reaching a distant target collapses far below `k/N`. If instead `p > 1/2` and the target is removed entirely (`N -> infinity`), the gambler avoids ruin forever with probability `1 - r^k`, which is strictly positive — an edge plus a bankroll buys genuine survival. Against an infinitely rich opponent in a fair game, `k/N -> 0` as `N -> infinity`: ruin is certain. Fairness per bet does not protect a finite bankroll against an unbounded one. ## Bet sizing The state space is measured in units of the bet. Betting 2 units instead of 1 rescales both `k` and `N` by a half, so in a fair game the ruin probability is unchanged while the expected number of bets drops by a factor of 4. In an *unfavourable* game, larger bets improve the chance of reaching a target, because they reduce the number of bets over which the edge can grind you down — a genuinely counterintuitive consequence of the geometric solution. ## What interviewers are checking 1. That you condition on one step instead of trying to enumerate paths. 2. That you state and use the boundary conditions. 3. That you can read the result: `k/N` is a statement about the *ratio* of bankroll to target, not about either alone. 4. That you know a small edge and a long walk do not combine linearly. ## Sanity checks - `P(0) = 0` and `P(N) = 1` must come straight out of your formula. - `P` must increase in `k` and decrease in `N`. - `D(k)` must be zero at both boundaries and symmetric about `N/2`.