5
$\begingroup$

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 .

$\endgroup$
4
  • 6
    $\begingroup$ arxiv.org/pdf/math.PR/0001057 is a great introduction to this subject. $\endgroup$ Nov 28, 2009 at 2:30
  • 5
    $\begingroup$ 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. $\endgroup$ Nov 28, 2009 at 10:13
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 28, 2009 at 11:40
  • 4
    $\begingroup$ 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. $\endgroup$ Nov 28, 2009 at 20:08

4 Answers 4

7
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ The general solution is harmonic, only with respect to a different operator. $\endgroup$ Nov 28, 2009 at 6:39
23
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ ...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". $\endgroup$ Nov 28, 2009 at 6:28
7
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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