Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

2 Answers

up vote 2 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
Another application of this method to a somewhat more complicated scenario may be found here. –  Marko Riedel Jan 19 '13 at 0:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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