MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have \$3. I flip a coin. If I get heads, I get \$1. If I get tails, I lose \$1. The game stops when I have \$0 or \$7. What is the probability I get \$7?

I solved this by creating a system of linear equations, where $P_0 = 0$, $P_7 = 1$, and $P_x = 0.5 \cdot P_{x-1} + 0.5 \cdot P_{x+1}$. Solving them, I got $P_3 = 3/7$. Moreover, $P_x = x/7$. Why does it work out to such a simple fraction?

More generally, it seems that $P_{x,y} = x/y$, which is the probability that, starting from x dollars, I end up with y dollars. I haven't proven this, but why is this the case?

Finally, what is $P_{x,y,p}$, where I gain 1 dollar with probability $p$ instead of probability 0.5 .

share|cite|improve this question
6 is a great introduction to this subject. – Qiaochu Yuan Nov 28 '09 at 2:30
Why does a basic UG question like this get +4 and three answers, whereas much harder UG quetsions in pure get -4 and closed? I'm thinking for example of the standard question about orders with no countable dense subset. Even the "0.99999...=1?" question is in some sense about as elementary as this, and that was hammered. – Kevin Buzzard Nov 28 '09 at 10:13
Probably because these questions don't come up in everyone's UG curriculum. I enjoyed and answered a very elementary question (the two-bucket puzzle) which was obvious with care, but hadn't come up. Either that or it's a matter of writing style. – Elizabeth S. Q. Goodman Nov 28 '09 at 11:40
For me it's because the OP showed work and is asking a conceptual question rather than for the answer to the (easy version of the) problem. – Qiaochu Yuan Nov 28 '09 at 20:08
up vote 7 down vote accepted

I really like Vigleik's answer, but I'll throw in yet another way to look at your original problem. Px = (Px-1+Px+1)/2 is an example of a (discrete) harmonic function; i.e., a function whose value is the average of the adjacent values. In this case, Px is a harmonic function on a chain graph. For purposes of intuition, we can move from a discrete to a continuous line and think about the criterion for a function of one (real) variable to be harmonic: it is harmonic if and only if its second derivative vanishes; i.e., it's linear. This provides some intuition why your solution just linearly interpolates between 0 and 1.

Your general problem of Px,y,p is no longer harmonic, so it will not have as easy a solution, as you may be discovering. For notational simplicity, I'll write Pn for Pn,y,p (preferring n as the index of a sequence to x). If you write down your new recurrence, you will get equations

Pn = (1-p)Pn-1+pPn+1

subject to P0 = 0, Py = 1. We can work with this, or we can use a trick. Let k = (1-p)/p (so p = 1/(1+k)). Then you can verify that

Pn = kPn-1 + 1

satisfies the original equation (with the additional freedom to scale all Pn by a constant factor - we've broken the homogeneity of our original recurrence). [It actually takes some doing to verify this: consider using this new recurrence to write down Pn-Pn+1. When you solve that out for Pn, you retrieve the original recurrence.]

This is much easier to handle, with solution

$P_n = \frac{k^n-1}{k-1}$.

This gives P0 = 0 as desired, but you'll need to scale down all solutions so that Py = 1.

share|cite|improve this answer
The general solution is harmonic, only with respect to a different operator. – Ori Gurel-Gurevich Nov 28 '09 at 6:39

You don't need much math at all to answer this question. Your expected value at the end of the game is $3, because the expected earnings at each turn is 0.

Your expected value at the end of the game is 7P7=3, so there you have it.

share|cite|improve this answer
...assuming that the game ends (which of course it does with prob 1). Similar games may not end, though. Look up "Doob's optional stopping theorem" a good way to think about this in more general "games". – Kevin O'Bryant Nov 28 '09 at 6:28

An amusing observation in connection with the first proof is that if you start with m dollars and can choose at each stage what the amount is that you will win/lose if the coin is heads/tails (the two amounts being equal of course), subject to the condition that you are not allowed to bet an amount that would take you over n or below zero, then your probability of getting to n before you get to 0 is still m/n, as long as you bet a positive integer number each time. In other words, if you try to do better by developing a strategy that involves betting different amounts at each stage, you won't. (But at least you won't do worse either.)

On the other hand, if you are playing roulette and your probability of winning goes very slightly down because of the 37, then your best hope is to bet the maximal amount every time, so as to minimize the chance that a 37 ever occurs during the process. (That's not a proof, but the conclusion is sound: if you take very small steps then the slight bias towards the bank means you will almost certainly lose.)

share|cite|improve this answer

If your equation $P_{x,y} = \frac{P_{x-1,y}+P_{x+1,y}}{2}$ is intuitive then the result should be intuitive. If the probability starting with $x$ dollars is the arithmetic mean of the probabilities starting with $x-1$ and $x+1$, then $P_{0,y},P_{1,y},\ldots,P_{y,y}$ is an arithmetic sequence. The simple form then follows immediately from the equal spacing and the facts that $P_{0,y}=0$ and $P_{y,y}=1$. I don't know how to make intuition precise, but because you are equally likely to go up or down at any given time, it makes sense that the probability of reaching y is proportional to the distance from 0.

share|cite|improve this answer

Ori Gurel-Gurervich's comment suggests a very simple way to use a martingale (an example of a Wald martingale) to evaluate the final question in which the probability of gaining a dollar is $p \ne \frac12$.

If $m(t)$ is how much money you have at time $t$, then $m(t)$ is not a martingale for $p \ne \frac12$. However, for the right base $C$, $C^{m(t)}$ is a martingale: $E (C^{m(t+1)}) = E(C^{m(t)})$. That means we can use the same argument that the starting value of a martingale is the average of the stopping values to compute the probabilities of ending at $0$ or $y$, or even of escaping to $\infty$ (with a bit more technical work).

The right value of $C$ is $(1-p)/p$. You start at $C^x$ and end at $C^y$ or $C^0 = 1$, so if you finish with probability 1 (easy to prove with another martingale) you end up at $C^y$ with probability $(1-C^x)/(1-C^y)$, and you end up at $C^0$ with the complementary probability $(C^x-C^y)/(1-C^y)$.

When $p \sim \frac12$, $C^x \sim 1- x \epsilon$ and $C^y \sim 1-y\epsilon$, which is continuous with the case $p=\frac12$.

If you don't stop at $y$, the probability that you escape to $\infty$ is $0$ if $p \le 1/2$ and $1-C^x$ if $p \gt 1/2$, which makes the probability of ruin $C^x$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.