Intuitive explanation to Probability question - MathOverflow

Intuitive explanation to Probability question

2009-11-28T00:52:11Z

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 .

Answer by Jonas Meyer for Intuitive explanation to Probability question

2009-11-28T01:26:29Z

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.

Answer by Vigleik Angeltveit for Intuitive explanation to Probability question

2009-11-28T02:26:38Z

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 7P₇=3, so there you have it.

Answer by Kevin Carde for Intuitive explanation to Probability question

2009-11-28T02:35:11Z

I really like Vigleik's answer, but I'll throw in yet another way to look at your original problem. P_x = (P_x-1+P_x+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, P_x 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 P_x,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 P_n for P_n,y,p (preferring n as the index of a sequence to x). If you write down your new recurrence, you will get equations

P_n = (1-p)P_n-1+pP_n+1

subject to P₀ = 0, P_y = 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

P_n = kP_n-1 + 1

satisfies the original equation (with the additional freedom to scale all P_n 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 P_n-P_n+1. When you solve that out for P_n, you retrieve the original recurrence.]

This is much easier to handle, with solution

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

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

Answer by gowers for Intuitive explanation to Probability question

2009-11-28T10:38:45Z

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

Answer by Douglas Zare for Intuitive explanation to Probability question

2010-01-13T13:42:50Z

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