# gambling probability problem

We are given a fair coin. We start out with 5 dollars. We keep tossing the coin. If the outcome is different than the previous one, we are awarded another 5 dollars. However, we do not get anything if the outcome is the same as the previous one. Let's say we toss the coin X times in the long run. How much do we expect to have in the end?

-
Note that for a fair coin this is the essentially the same as ignoring the first toss and winning with heads / losing with tails. –  Hagen von Eitzen Jan 18 '13 at 16:52
And if it is a biased coin that comes up heads with some probability x then what bias would we really seek in this case?! –  user58749 Jan 18 '13 at 16:56
Well, the case of biased coin would be very different. –  Hagen von Eitzen Jan 18 '13 at 17:22

Given the current state: time $n\geq 0$ and the amount of money $5x$ dollars, the probability that we have $5(x+1)$ at the next step is the same as the probability that we stay with $5x$, and of course both are $\frac12$. So as Hagen has mentioned, your expected profit is $$5+\mathsf E\sum_{i=0}^X \xi_i = 5\left(1+\frac X2\right).$$ since $\xi_0 = 0$ and $\xi_i$ takes values $\{0,5\}$ equiprobable.
This problem may be solved using generating functions which is admittedly more powerful than strictly necessary in this case, but it does illustrate the method, which is worth knowing. Let $p_A(n)$ be a polynomial in $u$ such that $[u^k] p_A(n)$ is the probability of having a capital of $k$ dollars and the last coin came up heads and similarly $p_B(n)$ for tails. Then we have the following system of equations $$p_A(n) = \frac{1}{2} p_A(n-1) + \frac{1}{2} u^5 p_B(n-1) \\ p_B(n) = \frac{1}{2} u^5 p_A(n-1) + \frac{1}{2} p_B(n-1)$$ with initial conditions $$p_A(0) = \frac{1}{2} u^5 \quad \text{and} \quad p_B(0) = \frac{1}{2} u^5.$$ Now introduce the generating functions $$P_A(z) = \sum_{n\ge 0} p_A(n) z^n \quad \text{and} \quad P_B(z) = \sum_{n\ge 0} p_B(n) z^n.$$ Multiply the recurrences by $z^n:$ $$p_A(n) z^n = z \frac{1}{2} z^{n-1} p_A(n-1) + z \frac{1}{2} u^5 z^{n-1} p_B(n-1) \\ p_B(n) z^n = z \frac{1}{2} u^5 z^{n-1} p_A(n-1) + z \frac{1}{2} z^{n-1} p_B(n-1)$$ Sum over $n$ to obtain the following system of equations $$P_A(z) - \frac{1}{2} u^5 = \frac{1}{2}z P_A(z) + \frac{1}{2}u^5 z P_B(z) \\ P_B(z) - \frac{1}{2} u^5 = \frac{1}{2}u^5 z P_A(z) + \frac{1}{2}z P_B(z).$$ The solution to this system is $$P_A(z)=-{\frac {{u}^{5}}{{u}^{5}z-2+z}}\\ P_B(z) =-{\frac {{u}^{5}}{{u}^{5}z-2+z}}.$$ The generating function for the expected capital after $n$ steps is then given by $$f(z) = \left( \frac{d}{du} (P_A(z) + P_B(z)) \right)_{u=1} = -10\, \left( 2\,z-2 \right) ^{-1}+10\,{\frac {z}{ \left( 2\,z-2 \right) ^{2}}}.$$ Now we have $$[z^n] f(z) = 5+5/2\,n,$$ which is precisely what was obtained above. We can also compute the variance, which is where the generating functions start to shine. First compute the expected factorial moment $Q(Q-1)$ where $Q$ is the capital. This has generating function $$g(z) = \left( \frac{d}{du} \frac{d}{du} (P_A(z) + P_B(z)) \right)_{u=1} = -40\, \left( 2\,z-2 \right) ^{-1}+140\,{\frac {z}{ \left( 2\,z-2 \right) ^{2}}}-100\,{\frac {{z}^{2}}{\left( 2\,z-2 \right) ^{3}}} .$$ This gives $$[z^n] g(z) = 20+{\frac {115}{4}}\,n+{\frac {25}{4}}\,{n}^{2}.$$ The variance can now be obtained from $$Var[Q] = E[Q^2] - E[Q]^2 = E[Q(Q-1)] + E[Q] - E[Q]^2,$$ which gives $$Var[Q] = {\frac {25}{4}}\,n.$$ We could in fact compute all factorial moments if desired.