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.

[this is a classic problem appeared on a mathematical journal. i see someone already asked it here but i still don't get it. i think it's interesting to get through it with some thoughtful ideas] we flip a fair coin N times. the probability getting a head or a tail is of course 0.5. after N tossings, we record a sequence of heads and tails. let A be the total number of times that we get a head right after we get a tail. let B be the total number of times that we get a tail right after we get a head. for example, if we flip the coin 7 times and record a result as HHTTHTH, then A=2 and B=2. find E(A) and E(B).

share|improve this question

marked as duplicate by Jonas Meyer, RecklessReckoner, Jack D'Aurizio, Joel Reyes Noche, FlintLockwood Feb 15 at 0:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

    
So why not wait until the same question gets answered. Posting it twice doesn't add to it's importance. –  jay-sun Apr 30 '13 at 17:30
    
hi. i'm just curious about this problem. i want to get a new way of getting it resolved. i don't intend to cause any confusion. i'm sorry. –  Linda Lee Apr 30 '13 at 17:38
    
"someone already asked it here"---no link? –  Jonas Meyer Feb 14 at 21:56

2 Answers 2

Instead of throwing a head-tails-coin $N$ times and counting changes, we can throw a change-nochange-coin and will obtain $A+B$, which is thus a $B(N-1,\frac12)$ distributed variable with $E(A+B)=\frac{N-1}2$ and $V(A+B)=\frac{N-1}4$. By symmetry, $E(A)=E(B)=\frac12 E(A+B)=\frac{N-1}4$ and $V(A)=V(B)$. However, we can't do completely as simple as that for the variance. More specifically, we have $|A-B|\le1$ and therefore $$\tag1 P(A=B=k) = {N-1\choose2k}2^{1-N}$$ and (using symmetry again) $$\tag2 P(A-1=B=k)=P(B-1=A=k) = {N-1\choose2k+1}2^{-N},$$ hence $$\tag3P(A=k)={N-1\choose2k}2^{1-N}+{N-1\choose2k+1}2^{-N}+{N-1\choose2k-1}2^{-N}={N+1\choose 2k+1}2^{-N}.$$ Thus $$\tag4\begin{align} E(A^2)&=2^{-N}\sum_{k=0}^{\lfloor\frac{N+1}2\rfloor} k^2{N+1\choose 2k+1}\\ &=2^{-N-2}\sum_{0\le r\le N+1\atop r\text{ odd}}(r-1)^2{N+1\choose r}\end{align}$$ Consider $$\tag5f(x)=\frac{(1+x)^{N+1}-(1-x)^{N+1}}2=\sum_{0\le r\le N+1\atop r\text{ odd}}{N+1\choose r}x^r$$ and note that $$\tag6\begin{align}f'(x) &= \frac{N+1}2\left((1+x)^N+(1-x)^N\right)\\f''(x)&=\frac{N(N+1)}{2}\left((1+x)^{N-1}-(1-x)^{N-1}\right) \end{align}$$ Then $$\tag7xf'(x) = \sum_{0\le r\le N+1\atop r\text{ odd}}r{N+1\choose r}x^r $$ and the derivative of this is
$$\tag8 f'(x)+xf''(x)=\sum_{0\le r\le N+1\atop r\text{ odd}}r^2{N+1\choose r}x^{r-1}.$$ We thus find, as $(r-1)^2=r^2-2r+1$, $$\tag9\begin{align}2^{N+2}E(A^2) &= \left[f'(1)+f''(1)\right] -2\left[f'(1)\right] + f(1)\\&=f(1)-f'(1)+f''(1)\\&=2^N-(N+1)2^{N-1}+N(N+1)2^{N-2}\\&=2^{N-2}(N^2-N+2)\end{align}$$ and finally $$\tag{10}V(A)=E(A^2)-E(A)^2 = \frac{N^2-N+2}{16} -\frac{(N-1)^2}{16}=\frac{N+1}{16}.$$


To calculate the covariance, we need $E(AB)$ which (using $(1)$ and $(2)$) is just $$\begin{align}E(AB)&= \sum k^2{N-1\choose 2k}2^{1-N}+\sum_kk(k+1){N-1\choose 2k+1}2^{1-N}\\ &=2^{1-N}\left(\sum_{r\text{ even}}\frac{r^2}4{N-1\choose r}+\sum_{r\text{ odd}}\frac{r^2-1}4{N-1\choose r}\right)\\ &=2^{-N-1}\left(\sum_{r=0}^{N-1}r^2{N-1\choose r}-\sum_{r\text{ odd}}{N-1\choose r}\right)\end{align}$$ This expression can be treated similar to above and we find $$ E(AB)=2^{-N-1}\left((N-1)2^{N-2}+(N-1)(N-2)2^{N-3} +2^{N-2}\right)=\frac{N^2-N+1}{16}$$ and hence $$\operatorname{cov}(A,B)=E(AB)-E(A)E(B)=\frac{N^2-N+1}{16}-\frac{(N-1)^2}{16} =\frac N{16}.$$

share|improve this answer
    
@ Hagen von Eitzen: thanks for your reply. i don't really understand your reasoning. could you stick to normal of of calculating var(A) = E[A^2] - (E[A])^2? the way i calculate E[A] is that set Ai = 1 if if at i we get a tail and at i+1 we get a head and Ai = 0 otherwise. so E[A] = (sum of)1*P(Ai=1) = (N-1)/4. but I don't know how to calculate E[A^2]. could you help me please? thanks –  Linda Lee May 1 '13 at 0:38
    
@ Hagen von Eitzen: your second last equation doesn't seem to be correct. shouldn't it be E(AB) = (N^2 - N + 2)/16? –  Linda Lee May 1 '13 at 8:16

The calculation of the variance can also be done using generating functions. Let $p_n$ be the probability generating function in $u, v$ of coin toss sequences that end in heads with $u$ marking the count of heads obtained after tails and $v$ the number of tails obtained after heads. Similarly for $q_n$ marking sequences ending in tails. This gives $$p_1 = \frac{1}{2} z \quad \text{and} \quad q_1 = \frac{1}{2} z.$$ Furthermore, $$p_n = \frac{1}{2} p_{n-1} + \frac{1}{2} u q_{n-1} \\ q_n = \frac{1}{2} v p_{n-1} + \frac{1}{2} q_{n-1}.$$ Translating to generating functions we introduce $$ P(z, u, v) = \sum_{n\ge 1} p_n z^n \quad \text{and} \quad Q(z, u, v) = \sum_{n\ge 1} q_n z^n $$ and find that $$ P - \frac{1}{2} z = \frac{1}{2} z P + \frac{1}{2} u z Q \quad \text{and} \quad Q - \frac{1}{2} z = \frac{1}{2} v z P + \frac{1}{2} z Q .$$ The solution to this system of equations is $$ P = -{\frac { \left( -z+uz+2 \right) z}{-4+4\,z-{z}^{2}+v{z}^{2}u}} \quad \text{and} \quad Q = -{\frac {z \left( 2-z+vz \right) }{-4+4\,z-{z}^{2}+v{z}^{2}u}}.$$ Now the expected value $E[A]$ of $A$ is $$[z^n]\left.\frac{\partial}{\partial u} (P+Q)\right|_{u=1, v=1} = [z^n]\frac{1}{4} \frac{z^2}{(1-z)^2} = \frac{1}{4} (n-1).$$ The expected value of $B$ is equal by symmetry, but we may check just the same. $$[z^n]\left.\frac{\partial}{\partial v} (P+Q)\right|_{u=1, v=1} = [z^n]\frac{1}{4} \frac{z^2}{(1-z)^2} = \frac{1}{4} (n-1).$$ For the variance we need $E[A(A-1)]$, so we use $$[z^n]\left.\left(\frac{\partial}{\partial u}\right)^2 (P+Q)\right|_{u=1, v=1} = [z^n]\frac{1}{8} \frac{z^4}{(1-z)^3} = \frac{1}{8} \frac{1}{2} (n-2)(n-3) = \frac{1}{16} (n-2)(n-3).$$ We thus have $$V[A] = E[A(A-1)]+E[A]-E[A]^2 = \frac{1}{16} (n-2)(n-3) + \frac{1}{4} (n-1) - \frac{1}{16} (n-1)^2 = \frac{1}{16} (n+1).$$ Finally, to get the covariance, we compute $E[AB],$ getting $$[z^n]\left.\frac{\partial}{\partial u} \frac{\partial}{\partial v}(P+Q)\right|_{u=1, v=1} = [z^n] \frac{1}{8} \frac{(2-z)z^3}{(1-z)^3} = \frac{1}{8} [z^n] \frac{2z^3}{(1-z)^3} - \frac{1}{8} [z^n] \frac{z^4}{(1-z)^3} = \frac{1}{8} (n-1)(n-2) - \frac{1}{8} \frac{1}{2} (n-2)(n-3) = \frac{1}{16} (n+1)(n-2).$$ This finally yields $$Cov(A,B) = \frac{1}{16} (n+1)(n-2) - \frac{1}{16} (n-1)^2 =\frac{1}{16}(n-3).$$

share|improve this answer
    
@ Marko Riedel: thanks for your response. could you check the result of cov(A,B)? Hagel got it equal N/16 and I once got that too. could you stick to normal of of calculating var(A) = E[A^2] - (E[A])^2? the way i calculate E[A] is that set Ai = 1 if if at i we get a tail and at i+1 we get a head and Ai = 0 otherwise. so E[A] = (sum of)1*P(Ai=1) = (N-1)/4. but I don't know how to calculate E[A^2]. could you help me please? thanks –  Linda Lee May 1 '13 at 1:03

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