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 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,
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 , 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.