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
    
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

2 Answers 2

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

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

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.