Originally Posted by Khelil

Dear Members I am very bad at probability, so please I hope I can find help here. My problem is that I can't see how to use n and m in this problem

Suppose a coin-flipping game between two players, A and B. The probability that the coin lands heads up is p (0<p<1). In case a head appears, player A gets one point and player B loses one point. In case a tail appears, player B gets one point and player A loses one point. When either one of the players lose all their points, the game ends and the player having points becomes the winner. When the initial points of A and B are m and n respectively, calculate the probability that player A wins. Note that m and n are positive integers.

This is not an easy problem, and it does not have a simple solution. Start by noticing that whenever A wins a point, B loses a point; and vice versa, whenever A loses a point, B wins a point. So the total number of points of A and B combined is always $m+n$. Thus A will lose if his number of points ever goes down to $0$, and he will win if his number of points ever goes up to $m+n$.

Denote by $w_k$ the probability that A will win if he starts with $k$ points, and let $q=1-p$. If A wins the first flip (with probability $p$) then he will have $k+1$ points, and his probability of winning becomes $w_{k+1}.$ If he loses the first flip (with probability $q$) then he will have $k-1$ points, and his probability of winning becomes $w_{k-1}.$ Therefore $$w_k = pw_{k+1} + qw_{k-1}.\qquad(*)$$ Also, $w_0=0$ (corresponding to A losing the game), and $w_{m+n} = 1$ (corresponding to A winning the game).

Put $k=1$ in (*) to see that $w_1 = pw_2$, so $w_2 = \dfrac1pw_1$. Now put $k=2$ in (*): $w_2 = pw_3 + qw_1 = pw_3 + pqw_2$, from which $w_3 = \dfrac{(1-pq)}pw_2 = \dfrac{(1-pq)}{p^2}w_1.$ Continue in this way. The next step will be to put $k=3$ in (*), giving $w_4 = \dfrac{1-2pq}{p(1-pq)}w_3 = \dfrac{1-2pq}{p^2}w_1.$ If you go further, you will find that $w_5 = \dfrac{1-3pq + p^2q^2}{p^4}w_1$ and $w_6 = \dfrac{1-4pq + 3p^2q^2}{p^5}w_1$. Eventually, you get to a formula for $w_{m+n}$ as a multiple of $w_1$. And since you know that $w_{m+n}=1$ you then have an expression for $w_1$ in terms of $p$ and $q$.

Suppose for example that $m+n=6$. Putting $w_6=1$ you find that $$w_1 = \frac{p^5}{1-4pq + 3p^2q^2},$$ $$w_2 = \frac{p^4}{1-4pq + 3p^2q^2},$$ $$w_3 = \frac{(1-pq)p^3}{1-4pq + 3p^2q^2},$$ $$w_4 = \frac{(1-2pq)p^2}{1-4pq + 3p^2q^2},$$ $$w_5 = \frac{(1-3pq + p^2q^2)p}{1-4pq + 3p^2q^2}.$$ That gives A's probabilities of winning a game in which $m+n=6$, in the cases where he starts with 1,2,3,4 or 5 points.

You can see that for larger values of $m$ and $n$ the algebra gets rapidly more complicated. If you know something about solving recurrence relations, you could get a formula for the polynomials in $pq$ that occur in the general solution, but it would not look pretty.

In the case of a fair coin, where $p=q=1/2$, the calculations become very much simpler, and $w_k$ increases linearly from $0$ to $1$ as $k$ goes from $0$ to $m+n$. So when $m+n=6$ you would then find that $w_1 = 1/6$, $w_2 = 1/3$, $w_3 = 1/2$, $w_4 = 2/3$ and $w_5 = 5/6$.

Just for the record, here is a brief sketch of how to derive the general formula for $w_m$ (the probability of A winning, given that A started with $m$ points and B started with $n$ points).

The polynomials $\Delta_1 = \Delta_2 = 1$, $\Delta_3 = 1-pq$, $\Delta_4 = 1-2pq$, $\Delta_5 = 1-3pq + p^2q^2$, $\Delta_6 = 1-4pq + 3p^2q^2$, $\ldots$, satisfy the recurrence relation $\Delta_k = \Delta_{k-1} -pq\Delta_{k-2}\;(k\geqslant3)$, as you can check from the equation (*) in the previous comment. The auxiliary equation for this recurrence relation is $\lambda^2 - \lambda + pq = 0$, with solutions $\lambda = \frac12\bigl(1 \pm \sqrt{1-4pq}\bigr)$. This leads to the formula $$\Delta_k = \frac{\bigl( \frac12\bigl(1 + \sqrt{1-4pq}\bigr)\bigr)^k - \bigl( \frac12\bigl(1 - \sqrt{1-4pq}\bigr)\bigr)^k }{\sqrt{1-4pq}}.$$ Then $\boxed{w_m = \dfrac{p^n\Delta_m}{\Delta_{m+n}}}$. That looks very neat, but of course it disguises the complications in the definition of $\Delta_k$.

Originally Posted by Opalg

Just for the record, here is a brief sketch of how to derive the general formula for $w_m$ (the probability of A winning, given that A started with $m$ points and B started with $n$ points).

The polynomials $\Delta_1 = \Delta_2 = 1$, $\Delta_3 = 1-pq$, $\Delta_4 = 1-2pq$, $\Delta_5 = 1-3pq + p^2q^2$, $\Delta_6 = 1-4pq + 3p^2q^2$, $\ldots$, satisfy the recurrence relation $\Delta_k = \Delta_{k-1} -pq\Delta_{k-2}\;(k\geqslant3)$, as you can check from the equation (*) in the previous comment. The auxiliary equation for this recurrence relation is $\lambda^2 - \lambda + pq = 0$, with solutions $\lambda = \frac12\bigl(1 \pm \sqrt{1-4pq}\bigr)$. This leads to the formula $$\Delta_k = \frac{\bigl( \frac12\bigl(1 + \sqrt{1-4pq}\bigr)\bigr)^k - \bigl( \frac12\bigl(1 - \sqrt{1-4pq}\bigr)\bigr)^k }{\sqrt{1-4pq}}.$$ Then $\boxed{w_m = \dfrac{p^n\Delta_m}{\Delta_{m+n}}}$. That looks very neat, but of course it disguises the complications in the definition of $\Delta_k$.

I keep coming back to this problem, and I now realise that the solution is not nearly as elaborate as I first thought. In fact, the expression $\sqrt{1-4pq}$ can be much simplified, because $q=1-p$ and therefore $1-4pq = 1-4p(1-p) = 1-4p+4p^2 = (1-2p)^2.$ Consequently, the roots of the recurrence relation are $\lambda = p$ and $\lambda = 1-p = q$; and the formula for $\Delta_k$ becomes $$\Delta_k = \left|\frac{p^k - q^k}{p-q}\right|.$$ Thus $\boxed{w_m = \left|\dfrac{p^n(p^m - q^m)}{p^{m+n} - q^{m+n}}\right|}$.