Condition on the first thing that happens

Quick description

Many probabilities associated with random walks can be solved with the help of the slogan, "Condition on the first thing that happens." Typically, the result of doing this is a recurrence formula or an equation, and solving the recurrence or the equation gives the probability in question.

Prerequisites

Basic definitions of probability.

Example 1

Suppose that two players, A and B, take turns tossing a fair coin, and the first person to get heads wins. What is the probability that the first player wins?

The brute-force solution to this problem is as follows. Let A be the first player. Then the probability that A wins on A's $k$ th turn is $2^{-(2k-1)}$ since for this event to happen there must be a run of $2(k-1)$ tails followed by a head. Therefore, A's probability of winning is $\frac 12+\frac 18+\frac 1{32}+\dots=\frac 23.$

Here is a nicer solution. Let A be the first player and let $p$ be the probability that $A$ wins. The law of total probability tells us that the probability that A wins is half the probability that A wins after getting heads on the first go plus half the probability that A wins after getting tails on the first go. The probability that A wins after getting tails on the first go is the probability that B gets tails and A is then the first person to get heads. But if B gets tails, then they are back to the starting situation, so the probability that A wins after getting tails on the first go is $p/2.$

From this we deduce the equation $p=\frac 12+\frac p4,$ which implies that $p=\frac 23.$

The second proof may look longer than the first, but that is just because we explained it in more detail. Here is a briefer way of presenting the argument. A wins if and only if A gets heads on the first go or A and B get tails on the first go and A goes on to win. Therefore, $p=\frac 12+\frac p4.$

General discussion

In order to derive the above equation we conditioned on the outcome of A's first toss of the coin. That is the general technique to be discussed in this article.

Example 2

A gambler goes into a casino with 100 pounds and aims to leave with 200 pounds. In order to achieve this, he keeps placing bets of 1 pound on red in roulette. The probability of red would be $\frac 12$ , were it not for the fact that there is a $1/37$ chance that the roulette ball lands in the green slot and the casino takes all the money that has been bet that round. So in fact the probability of red is $18/37.$ If the gambler runs out of money then he is thrown out of the casino. What is the probability that his plan will succeed?

To answer this question, we define $p_k$ to be the probability that the gambler reaches 200 pounds before running out of money if he has $k$ pounds left, and we try to find a recurrence relation for $p_k$ . Once again, we condition on the first thing that happens, which tells us that $p_k=\frac{18}{37}p_{k+1}+\frac{19}{37}p_{k-1}.$ We also know that $p_0=0$ and $p_{200}=1.$ The recurrence relation is of a standard kind, so it is not hard to work out the general solution, and the boundary conditions are enough to determine which particular solution we have and therefore to calculate $p_{100},$ which turns out to be about $1/250.$ The calculation is straightforward. ( Rearranging the recurrence, we find that $p_{k+1}-\frac{37}{18}p_k+\frac{19}{18}p_{k-1}=0.$ We therefore need to solve the quadratic $x^2-\frac{37}{18}x+\frac{19}{18}=0.$ The left-hand side factorizes as $(x-1)(x-\frac{19}{18}),$ which tells us that the general solution is $p_k=A+(19/18)^kB.$ Setting $k=0$ we deduce that $0=A+B,$ and using this and setting $k=200$ we deduce that $1=A(1-(19/18)^{200}).$ Therefore, the general solution is $p_k=((19/18)^k-1)/((19/18)^{200}-1).$ In particular, $p_{100}=((19/18)^{100}-1)/((19/18)^{200}-1).$ This is a pretty small number: if we approximate $(19/18)^{100}$ by $e^{100/18},$ we find that the probability of success for the gambler is around $1/250,$ as claimed. )

Why is the probability so small, when replacing the probability $18/37$ by $18/36$ would give the gambler a fifty-fifty chance of success? The explanation lies in the fact that the gambler takes small steps. A much better strategy would be to place one bet of 100 pounds, in which case the probability of success would of course be $18/37.$ To understand why taking small steps makes such a big difference, one can think of the process as follows: on each turn the gambler has a $1/37$ chance of losing a pound, and otherwise loses or gains a pound with equal probability. So what the gambler is doing can be thought of as a random walk with probability 1/2 of going up or down, combined with a "drift" downwards at a rate of $1/37.$ Now the number of steps before a random walk has travelled a distance of $n$ from the starting point is typically proportional to $n^2$ . To see this, let $X_i=1$ if the walk goes up at step $i$ and $-1$ if it goes down. Then the distance travelled after $m$ steps is $X_1+\dots+X_m.$ Each $X_i$ has variance 1, and the $X_i$ are independent, so we use the fact that variances of independent random variables add together to conclude that the variance of $X_1+\dots+X_m$ is $m,$ and therefore its standard deviation is $\sqrt{m}.$ For more precise arguments that show that a random walk has very little chance of going much further than $\sqrt{m}$ after $m$ steps, see Example 3 of the article on bounding probabilities by expectations. Therefore, for the pure random walk to travel a distance of 100 we would expect to need something of the order of 10000 steps, during which time the average drift downwards is 10000/37, which is about 300. So even a rather small drift becomes very important.