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 .



Intuitive explanation to Probability question
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.


