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.
Basic definitions of probability.
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 th turn is since for this event to happen there must be a run of tails followed by a head. Therefore, A's probability of winning is
Here is a nicer solution. Let A be the first player and let be the probability that 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
From this we deduce the equation which implies that
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,
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.
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 , were it not for the fact that there is a 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 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 to be the probability that the gambler reaches 200 pounds before running out of money if he has pounds left, and we try to find a recurrence relation for . Once again, we condition on the first thing that happens, which tells us that We also know that and 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 which turns out to be about The calculation is straightforward. ( Rearranging the recurrence, we find that We therefore need to solve the quadratic The left-hand side factorizes as which tells us that the general solution is Setting we deduce that and using this and setting we deduce that Therefore, the general solution is In particular, This is a pretty small number: if we approximate by we find that the probability of success for the gambler is around as claimed. )
Why is the probability so small, when replacing the probability by 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 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 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 Now the number of steps before a random walk has travelled a distance of from the starting point is typically proportional to . To see this, let if the walk goes up at step and if it goes down. Then the distance travelled after steps is Each has variance 1, and the are independent, so we use the fact that variances of independent random variables add together to conclude that the variance of is and therefore its standard deviation is For more precise arguments that show that a random walk has very little chance of going much further than after 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.