Condition on the first thing that happens

a repository of mathematical know-how

Condition on the first thing that happens

Title: *

Area of mathematics: *

A comma-separated list of areas of mathematics to which this article applies. Use ">" to tag in a subcategory. Example: Analysis > Harmonic analysis, Combinatorics

Keywords:

A comma-separated list of keywords associated with this article. Example: free group

Used in:

A comma-separated list of examples of where this technique is used. Example: Cauchy-Schwarz inequality

Parent articles:		Order

Body:

[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]
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]

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.$ [cut] 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. [/cut]

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 [add] 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]].}}[/add] 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.

This is a stub

A stub is an article that is not sufficiently complete to be interesting.

Notifications

File attachments

Changes made to the attachments are not permanent until you save this post. The first "listed" file will be included in RSS feeds.

Attach new file:

Images are larger than 640x480 will be resized. The maximum upload size is 1 MB. Only files with the following extensions may be uploaded: jpg jpeg gif png svg.

Revision information

Log message:

An explanation of the additions or updates being made to help other authors understand your motivations.

Condition on the first thing that happens

Recent articles

Active forum topics

Recent comments