Xpectation Mania #3

For $0 \le j \le n$ , let $T_j$ be the expected number of additional tosses required to obtain a sequence of HT $n$ times in a row, given that the last $2j$ tosses have resulted in HT $j$ times in a row. Note that $T_n = 0$ , and $T_0 = g(n)$ . Also, for $0 \le j \le n-1$ , let $H_n$ be the expected number additional tosses required to obtain a sequence of HT $n$ times in a row, given that the last $2j+1$ tosses have resulted in HT $j$ times in a row, followed by a H. Conditional probability considerations tell us that $T_j \; = \; \tfrac12(1 + H_j) + \tfrac12(1 + T_0) \hspace{2cm} H_j \; = \; \tfrac12(1 + T_{j+1}) + \tfrac12(1 + H_0) \hspace{2cm} 0 \le j \le n-1$ In particular we deduce that $H_0 = T_0 - 2$ , and we have the equations $2T_j \; = \; H_j + T_ 0 + 2 \hspace{1cm} 2H_j \; = \; T_{j+1} + T_0 \hspace{2cm} 0 \le j \le n-1$ Thus $\begin{aligned} 4T_j & = \; 2H_j + 2T_0 + 4 \; = \; T_{j+1} + 3T_0 + 4 \\ \frac{T_j}{4^j} & = \; \frac{T_{j+1}}{4^{j+1}} + \frac{3T_0 + 4}{4^{j+1}} \\ T_0 - \frac{T_j}{4^j} & = \; \sum_{k=0}^{j-1}\frac{3T_0 + 4}{4^{k+1}} \; = \; \tfrac13(3T_0 + 4)(1 - 4^{-j}) \end{aligned}$ and hence $T_j \; = \; T_0 - \tfrac43(4^j - 1) \hspace{2cm} 0 \le j \le n$ Since $T_n=0$ we deduce that $g(n) \; = \; T_0 \; = \; \tfrac43(4^n - 1)$ and hence $g(7) = \boxed{21844}$ .