# expected value of getting a head or a tail right after each other when flipping a fair coin

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

i relate this problem to the famous coin changeover problem. i got stuck right from the beginning. thanks for any help.

-
For any given two consecutive flips, the a priori probability of all four of these combinations is 0.25: HH, HT, TH, TT. So the probability that one flip is the opposite of the preceding flip is, ... wait for it, ... 0.25 + 0.25 = 0.50. Amazing! Every flip has an identical chance of being either heads or ails, and continues to be independent of the preceding flip, just as we assumed when we stated that the coin is fair. –  Pieter Geerkens Apr 30 '13 at 6:41

A start: Define random variables $X_1,X_2,\dots, X_{N-1}$ by $X_i=1$ if at $i$ we get a tail and at $i+1$ we get a head. So $X_1+X_2+\cdots+X_{N-1}$ is the number of tail to head transitions. By the linearity of expectation, $E(X_1+\cdots+X_{N-1})=E(X_1)+\cdots+E(X_{N-1})$.

But $\Pr(X_i=1)=\frac{1}{4}$, so the expected number of tail to head transitions is $\frac{N-1}{4}$.

For the variance, we would like to find first $E((X_1+\cdots+X_{N-1})^2$, and subtract the square of the expectation of $X_1+\cdots+X_{N-1}$. The calculation is similar to the previous one, but quite a bit more complicated. Expand $(X_1+\cdots+X_{N-1})^2$. Again, use the linearity of expectation.

Added: When we expand $(X_1+\cdots+X_{N-1})^2$, we get $\sum X_i^2$ plus "mixed" terms. The expectation of $\sum X_i^2$ has already been calculated, sine $X_i^2=X_i$. The mixed terms $X_iX_j$ can be divided into two types. The numbers $i$ and $j$ could be consecutive. For such $i,j$ we have $X_iX_j=0$. Or they could be non-consecutive. There are $\binom{N-1}{2}$ unordered pairs, of which $N-2$ are consecutive, leaving $\frac{(N-2)(N-3)}{2}$ non-consecutive pairs. For such a pair $\{i,j\}$, we have $\Pr(X_iX_j=1)=\frac{1}{2^4}$. But for each pair $\{i,j\}$ we have the term $2X_iX_j$. So the expectation of the mixed terms is $\frac{N-2)(N-3)}{2^4}$.

-
@ Andre Nicolas: thanks for your response. honestly i'm not as smart as you so i don't get why E[X] = (N-1)/4. could you also find the expected number of head to tail transition? is it also (N-1)/4? –  Sean Jones Apr 30 '13 at 6:59
For head to tail, sure, it is the same. For $E(X_i)$, by the usal way to calculate expectation this is $1\cdot \Pr(X_i=1)+0\cdot \Pr(X_i=0)$, or more simply just $\Pr(X_i)=1$. But $X_i=1$ if tail on $i$ and head on $i+1$, so the probability is $\frac{1}{2^2}$. Now add up, $i=1$ to $N-1$. Note that the $X_i$ are not independent, but linearity of expectation holds always. And it is not a question of smart, I have taught this sort of stuff many times. –  André Nicolas Apr 30 '13 at 7:10
i also get the expected number of head to tail transition is (N-1)/4? Is that correct? i tried to calculate the var(X) but get stuck when expanding E[(X1 + X2 + ...Xn)^2] –  Sean Jones Apr 30 '13 at 7:20
When you expand, you get $X_i^3$ terms, easy since $X_i^2=X_i$. You also get $XiX_j$ terms, with $i\ne j$. Write down the condition for $X_iX_j$ to be $1$. Impossible if $j=i+1$. But if separated by at least $2$, probability is $\frac{1}{16}$. Now need to count. –  André Nicolas Apr 30 '13 at 7:29
@ Andre Nicolas: thanks for being with me. what you described is exactly where I got stuck. E[(X1 + X2 + ... Xn)^2] = E[X1^2 + ... Xn^2 + 2(X1X2 + ...Xn-1Xn)]. i don't know how to deal with the later part. could you please be more specific? thanks –  Sean Jones Apr 30 '13 at 7:56