Head-Tail Coin Tosses

Let $I_i$ , $i = 1$ to $8$ be the indicator variable that the $i^{th}$ coin is $H$ and the ${i+1}^{th}$ coin is $T$ . Specifically, $I_i=1$ when the $i^{th}$ coin is $H$ and the ${i+1}^{th}$ coin is $T$ , and $I_i=0$ otherwise. Then, $X = I_1 + I_2 + \ldots + I_{8}$ .

We can calculate that $E(I_i) = \frac {1}{4} \cdot 1 + \frac {3}{4} \cdot 0 = \frac {1}{4}$ and $\mbox{Var}(I_i) = \frac {1}{4} (1-\frac {1}{4})^2 + \frac {3}{4}(0-\frac {1}{4})^2 = \frac {3}{16}$ . For $j > i+1$ , the coins flips of the $i^{th}, {i+1}^{th}, j^{th}$ and ${j+1}^{th}$ coins are independent, so $\mbox{Cov}(I_i, I_j)=0$ . If $j=i+1$ , then $I_i I_j = 0$ , so $\mbox{Cov}(I_i,I_j) = E[I_i I_j]-E[I_i]E[I_j] = 0 - \frac {1}{4} \cdot \frac {1}{4} =-\frac {1}{16}$ . We then calculate

$\begin{aligned} \mbox{Var}(X) & = \mbox{Var}(I_1 + I_2 + \ldots + I_{8} )\\ & = \sum_i \mbox{Var}(I_i) + \sum_{j=i+1} 2\mbox{Cov}(I_i, I_j) +\sum_{j > i+1} 2 \mbox{Cov}(I_i, I_j) \\ & = 8 \cdot \frac {3}{16} + 7 \cdot 2 \cdot (- \frac {1}{16} ) + 0 \\ & = \frac {5}{8}\\ \end{aligned}$

Thus, $a+b=5+8=13$ .

Note that X can be only integers from 0 to 4 (obviously), and that the total number of different sequences that 9 coin tosses can produce is $2^9 = 512$ . Now we consider for each $X$ from 0 to 4, how many possible sequences can arise.

For $X = 0$ , the sequence has to be: $TT...THH...H$ . The number of T's can range from 0 to 9, and the number of H's will change accordingly, hence there are 10 sequences in this case.

For $X = 1$ , the sequence has to be: $TT...THH...HTT...THH...H$ . For simplicity we shall rewrite this as $THTH$ , where each $T$ and $H$ represent a string of Ts or Hs, respectively. Note that the 'inner' 2 strings of $H$ and $T$ must represent at least 1 coin toss, in order for there to be "consecutive coin tosses that yields a Head and then a Tail". On the other hand, the T-string in front and the H-string at the back can represent 0 coin tosses or more. Hence, the number of such sequences is simply the number of ways to solve $a+b+c+d=9$ , where $b,c≥1$ and $a,d≥0$ . We may further simplify this problem to $a+p+q+d=7$ , by using the substitution $p=b-1, q=c-1$ , so that now a bijection can be made to arranging 7 'items' and 3 'dividers', to produce such a sequence of $(a,p,q,c)$ , so there are ${10 \choose 7} = 120$ such sequences.

For $X = 2$ , we adopt a similar approach. Using a 'skeleton' of THTHTH, and knowing that the middle 4 strings need to represent at least 1 coin toss each, we have that the number of sequences is equivalent to the number of ways of putting the remaining 5 coin tosses into 6 strings, i.e. ${10 \choose 5} = 252$ .

For $X=3$ , by a similar approach, there are ${10 \choose 3} = 120$ sequences

For $X=4$ , by a similar approach, there are ${10 \choose 1} = 10$ sequences for X=4.

[A quick check, summing 10+120+252+120+10 yields 512, which is the total number of sequences.]

Now, the mean value of X, by symmetry, has to be 2. To calculate variance, we get $\frac {10}{512}(0-2)^2 + \frac {120}{512}(1-2)^2 + \frac {252}{512}(2-2)^2 + \frac {120}{512}(3-2)^2 + \frac {10}{512}(4-2)^2 = \frac {5}{8}$ . Hence the answer is 13.

Let $Y$ be the random variable of the number of HT pairs out of the 9 coin tosses. Furthermore, let $X_{i}$ be the random variable that the $i^{th}$ coin comes up heads and the $(i+1)^{th}$ coin comes up tails. That is, $X_{i} = 1$ if the $i^{th}$ coin is heads and the $(i+1)^{th}$ coin is tails, and is 0 otherwise. All this implies,

$Y = X_{1} + X_{2} + \cdots + X_{8}$

It is tempting to express the variance of $Y$ as a linear combination of the variances of each of the $X_{i}$ 's. However, we cannot do this because $X_{i}$ and $X_{i+1}$ are not independent. In this case we must use the more general formula for the variance of a linear combination:

${\it Var} \left( \sum _{i=i}^{N}X_{{i}} \right) =\sum _{i=1}^{N}{\it Var} \left( X_{{i}} \right) +2\sum{E \left( \left( X_{{i}}-\mu_{{i}} \right) \left( X_{{j}}-\mu_{{j}} \right) \right)}$

where the last sum is over all pairs of $(i, j)$ such that $1 \leq i < j \leq N$ . Also, $E$ denotes the expectation value of the quantity in the parentheses.

$E \left( \left( X_{{i}}-\mu_{{i}} \right) \left( X_{{j}}-\mu_{{j}} \right) \right)$ is just the covariance of $X_{i}$ and $X_{j}$ , and in our case is 0, unless $j = i + 1$ . This is because when two random variables are independent, their covariance is 0. The HT pairs are independent unless they are adjacent to each other, in which case $j = i + 1$ . So we only need to sum over $E \left( \left( X_{{i}}-\mu_{{i}} \right) \left( X_{{i+1}}-\mu_{{i+1}} \right) \right)$ from $i = 1$ to $i = 7$

The above quantities can be calculated by hand. We first have:

$\mu_{i} = 1*(\frac{1}{4}) + 0*(\frac{3}{4}) = \frac{1}{4}$

And,

${\it Var} \left( X_{{i}} \right) = (1-\frac{1}{4})^{2} * \frac{1}{4} + (0 - \frac{1}{4})^{2}*\frac{3}{4} = \frac{3}{16}$

And,

$E \left( \left( X_{i}-\mu_{i} \right) \left( X_{i+1}-\mu_{i+1} \right) \right) = (1-\frac{1}{4})*(0-\frac{1}{4})*\frac{1}{4} \\ + (0-\frac{1}{4})*(1-\frac{1}{4})*\frac{1}{4} +(0-\frac{1}{4})*(0-\frac{1}{4})*\frac{1}{2} \\ = -\frac{1}{16}$

Putting it all together, we have:

$Var(Y) = {\it Var} \left( \sum _{i=i}^{8}X_{{i}} \right) \\ \hspace{18 mm} = \sum _{i=1}^{8}{\it Var} \left( X_{{i}} \right) +2\sum{E \left( \left( X_{{i}}-\mu_{{1}}\right) \left( X_{{j}}-\mu_{{2}} \right) \right)} \\ \hspace{18 mm} = \frac{3}{16}*8 + 2*(-\frac{1}{16})*7 \\ \hspace{18mm} = \frac{5}{8}$ .

Our answer is $5 + 8 = 13$ .

We analyze the distribution of $X$ first and then calculate its variance.

Let $n\geq 1$ be an integer. Suppose that $x_1, \cdots, x_n$ is a possible outcome of the $n$ tossed fair coins. Whenever $x_j \neq x_{j+1}$ , we say that there is a flip . The number of cases when there are $m$ flips is $\binom{n-1}{k}$ .

In the cases when $x_1=H$ , $X=k$ is equivalent to exactly $2k-1$ or $2k$ flips; when $x_1=T$ , $X=k$ is equivalent to $2k$ or $2k+1$ flips. Therefore

$P[X=k] = \frac{\binom{n-1}{2k-1}+\binom{n-1}{2k}+\binom{n-1}{2k}+\binom{n-1}{2k+1}}{2^n}$ $= \frac{\binom{n}{2k}+\binom{n}{2k+1}}{2^n} = \frac{1}{2^n}\binom{n+1}{2k+1}$

In the calculation of the variance of $X$ , we will need to calculate a few summations related to binomial coefficients. We summarize and prove them here:

(1) $\sum_{k\geq 0} \binom{n}{2k+1} = 2^{n-1}$

(2) $\sum_{k\geq 0} \binom{n}{2k+1}(2k+1) = n 2^{n-2}$

(3) $\sum_{k\geq 1} \binom{n}{2k+1}(2k+1)(2k) = n (n-1) 2^{n-3}$

To prove these, notice that if $f(x)=(1+x)^n=\sum_{k\geq 0}\binom{n}{k}x^k$ then $g(x):=\frac{f(x)-f(-x)}{2} = \sum_{k\geq 0}\binom{n}{2k+1}x^{2k+1}.$

Formula (1) can be found by evaluating $g(1)$ . To prove (2), we calculate $g'(1)$ :

$\sum_{k\geq 0}\binom{n}{2k+1}(2k+1)=\frac{f'(1)+f'(-1)}{2}=n 2^{n-2}$

To prove (3), calculate $g''(1)$ :

$\sum_{k\geq 1}\binom{n}{2k+1}(2k+1)(2k)=\frac{f''(1)-f''(-1)}{2}=n(n-1) 2^{n-3}$

The mean of $X$ is: $E[X] = \frac{1}{2^n}\sum_{k\geq 0} \binom{n+1}{2k+1} k = \frac{1}{2^n} \sum_{k\geq 0} \binom{n+1}{2k+1} \frac{(2k+1)-1}{2}$ $= \frac{1}{2^n} \frac{ (n+1) 2^{n-1} - 2^n}{2} = \frac{n-1}{4}.$

The mean of $X^2$ is: $E[X^2] = \frac{1}{2^n}\sum_{k\geq 0} \binom{n+1}{2k+1} k^2$ $= \frac{1}{2^n}\sum_{k\geq 0} \binom{n+1}{2k+1} \frac{(2k+1)(2k) - (2k + 1) + 1}{4}$ $= \frac{1}{2^n} \frac{(n+1)n 2^{n-2} - (n+1) 2^{n-1} + 2^n}{4}$ $= \frac{(n+1)n - 2(n+1) + 4}{16} = \frac{n^2-n+2}{16}$

Therefore the variance of $X$ is equal to: $E[X^2]-E[X]^2 = \frac{n^2-n+2}{16} - \frac{n^2-2n+1}{16} = \frac{n+1}{16}$

When $n=9$ , this is equal to $\frac{5}{8}$ .

In order to find the variance, we must find the expected value. Since there are 8 pairs of consecutive flips when we flip 9 coins, and each one has a 1/4 chance of being successful, we have an expected value of $8/4=2$ .

Now to find the distribution of possibilities, consider 9 “stars”, denoted with O’s.

O O O O O O O O O

We want to use stars and bars, so let’s create a correspondence between coins flips and our stars and bars. We will look at every sequence of flips as a chain of T’s, followed by a chain of H’s, followed by a chain of T’s, ... ended with a chain of H’s. All of these chains will have a positive number of elements, except for possibly the ends. For example, the sequence TTHHHTTTH corresponds to

O O | O O O | O O O | O

and the sequence HHHHHHTTT corresponds to

| O O O O O O | O O O |

Note that since our sequence will have an even number of chains of T’s and H’s, so it has an odd number of bars.

Now we have to count up our possibilities. Consider all sequences with 0 HT combinations. These sequences must be in the form TH, where T and H represent blocks of T’s and H’s, repectively. Keeping in mind that we can have 0 of an endpoint (e.g. just H), our stars and bars correspondence says that there are $\binom{10}{1}$ sequences of this form.

Consider sequences with 1 HT combination. These sequences are in the form THTH, where endpoints can be 0. Stars and bars gives us $\binom{10}{3}$ of these. Similarly, there are $\binom{10}{5}$ sequences with 2 HT’s, $\binom{10}{7}$ with 3, and $\binom{10}{9}$ with 4. Calculating the variance from here is simple by following the formula.

$\text{variance}=\frac{1}{512}(\binom{10}{1}(0-2)^2+\binom{10}{3}(1-2)^2+\binom{10}{5}(2-2)^2+\binom{10}{7}(3-2)^2+\binom{10}{9}(4-2)^2)$

$=\frac{1}{512}(40+120+0+120+40)=\frac{320}{512}=\frac{5}{8}$ .

Finally, we have $a+b=5+8=\boxed{13}$

Throwing 9 fair coins will result in $2^9 = 512$ different cases. In each case, we can have 0, 1, 2, 3 or 4 "Head-Tail" pairs (HT-pairs), since 5 HT-pairs will require at least 5 heads and 5 tails, but we have only 9 coins.

Now we count the number of cases that will lead to 0, 1, 2, 3 and 4 HT-pairs. We denote a HT pair by A, and a sequence of non-HT pairs by B (B can be a sequence with no elements). Also observe that a k-sequence of non-HT pairs consists of (k+1) possible combinations, {(TT..T), (T...TH), (T...TH), ... , (HH...H)}, since no tails can occur downstream of the sequence after one head has occurred.

The possible sequences are denoted below:-

0 HT-pair: $B$

B must be of sequence 9. Therefore there is a total of $10$ combinations.

1 HT-pair: $B_1AB_2$

$B_1$ and $B_2$ must add up to be of sequence 7. There are 8 ways of doing so, where $(B_1,B_2) = (0,7), (1,6), ... , (7,0)$ . Multiplying each cases and summing them up, we have $1 \times 8 + 2 \times 7 + ... + 8 \times 1 = 120$ combinations.

3 HT-pairs: $B_1AB_2AB_3AB_4$

$B_1$ , $B_2$ , $B_3$ and $B_4$ must add up to be of sequence 3. We further split into 3 cases, where a) 3 of $B_i$ has sequence 1 (1 with sequence 0), b) 1 of $B_i$ has sequence 2 and another with sequence 1, c) 1 of $B_i$ has sequence 3.

For a), there is a total of 4 possibilities with $2 \times 2 \times 2 \times 1 = 8$ combinations. For b), there is a total of $4 \times 3 = 12$ possibilities with $3 \times 2 \times 1 \times 1 = 6$ combinations. For c), there is a total of 4 possibilities with $4 \times 1 \times 1 \times 1 = 4$ combinations. Summing them, we have $8 \times 4 + 12 \times 6 + 4 \times 4 = 120$ combinations.

4 HT-pairs: $B_1AB_2AB_3AB_4AB_5$

$B_1$ , $B_2$ , $B_3$ , $B_4$ and $B_5$ must add up to be of sequence 1. There are 5 ways of doing so, when one of $B_i$ has sequence 1. Therefore there are $5 \times 2 = 10$ combinations.

2 HT-pairs:

Since there is a total of 512 combinations, there are 512 - (10 + 120 + 120 + 10) = $252$ combinations of 2 HT-pairs.

We can now calculate the variance.

$Var (X) = \displaystyle \sum_{i=1}^5 (p_i (x_i-\mu)^2)$

$\mu = \frac{10 \times 0 + 120 \times 1 + 252 \times 2 + 120 \times 3 + 10 \times 4}{512} = 2$

Therefore, $Var (X) = \frac{10}{512}(0-2)^2 + \frac{120}{512}(1-2)^2$ $+ \frac{252}{512}(2-2)^2 + \frac{120}{512}(3-2)^2 + \frac{10}{512}(4-2)^2 = \frac{5}{8}$

This is probably an invalid solution, but I "flipped a coin" 9 times and then counted the number of HTs using python, 10 million times. I then calculated the variance using the 10 million values. The resulting variance was within .0001 of .625, which is equal to 5/8, and the sum is 13.

the rule is: "when head appear at one tossed, it must be head after the end tossed."

for the first we have to find the frequency for the case below: 1. no head following by tail : using the rule, total possibility is 10 that is no head, one head until nine head.

1. exactly one head immediately following by tail (two place has been taken and there are two place to tossed after and before HT) : with the same idea, we have (1 8+2 7+3 6+4 5+5 4+6 3+7 2+8 1=120)

2. exactly two head immediately following by tail (four place has been taken and there is three place to tossed there are before, between and after the two HT) : with the same idea we have (3 (1 1 6)+6 (1 2 5)+6 (1 3 4)+3 (2 2 4)+3 (2 3*3)=252)

3. exactly three head immediately following by tail: the last case is more easy to counting.

4. exactly four head immediately following by tail (8 place has been taken and there is 5 place to tossed there are before, between and after the two HT) : with the same idea we have (2 1 1 1 1+1 2 1 1 1+1 1 2 1 1+1 1 1 2 1+1 1 1 1 2=10); so the frequency for case four have to : 2^9-10-120-252-10=120

the average of the case : (10 0+120 1+252 2+120 3+10 4)/2^9=2 the varians of the case : (10 (0-2)^2+120 (1-2)^2+252 (2-2)^2+120 (3-2)^2+10 (4-2)^2)/512=5/8 so a+b=13

9 1/2 1/2=9/4 9+4=13