Biased Patterns

Solution

Let \[ p=P(H)=0.7,\qquad q=P(T)=0.3. \] We want the expected number of flips until the pattern \[ \text{HTTH} \] appears for the first time. The clean way to do this is to track how much of the target pattern we have matched so far. Define these states: \[ S_0:\ \text{no useful match yet} \] \[ S_1:\ \text{the current ending is } H \] \[ S_2:\ \text{the current ending is } HT \] \[ S_3:\ \text{the current ending is } HTT \] Once we reach the full pattern \(HTTH\), we are done. Let \[ E_0,E_1,E_2,E_3 \] be the expected number of additional flips needed starting from states \(S_0,S_1,S_2,S_3\) respectively. Our goal is to find \[ E_0. \]\ From \(S_0\): If the next flip is \(H\), we move to \(S_1\). If the next flip is \(T\), we are still in \(S_0\), because \(T\) does not start the pattern \(HTTH\). So \[ E_0=1+pE_1+qE_0. \] From \(S_1\): We have already matched \(H\). If the next flip is \(H\), the current ending is still just \(H\), so we stay in \(S_1\). If the next flip is \(T\), we now have \(HT\), so we move to \(S_2\). Thus \[ E_1=1+pE_1+qE_2. \] From \(S_2\): We have matched \(HT\). If the next flip is \(T\), we move to \(S_3\), since we now have \(HTT\). If the next flip is \(H\), the string becomes \(HTH\). The longest suffix of \(HTH\) that is also a prefix of \(HTTH\) is just \(H\), so we fall back to \(S_1\). Hence \[ E_2=1+pE_1+qE_3. \] From \(S_3\): We have matched \(HTT\). If the next flip is \(H\), we complete the pattern \(HTTH\), so we are done. If the next flip is \(T\), the string becomes \(HTTT\). No nonempty suffix of this is a prefix of \(HTTH\), so we fall all the way back to \(S_0\). Therefore \[ E_3=1+p\cdot 0+qE_0. \] So \[ E_3=1+qE_0. \] Now substitute \(p=0.7\) and \(q=0.3\). The system is \[ E_0=1+0.7E_1+0.3E_0 \] \[ E_1=1+0.7E_1+0.3E_2 \] \[ E_2=1+0.7E_1+0.3E_3 \] \[ E_3=1+0.3E_0. \] Rearranging the first two: \[ 0.7E_0=1+0.7E_1 \] so \[ E_0=\frac{10}{7}+E_1. \] Also, \[ 0.3E_1=1+0.3E_2 \] so \[ E_1=\frac{10}{3}+E_2. \] Now use \[ E_3=1+0.3E_0. \] Then \[ E_2=1+0.7E_1+0.3E_3 \] becomes \[ E_2=1+0.7E_1+0.3(1+0.3E_0). \] So \[ E_2=1.3+0.7E_1+0.09E_0. \] Substitute this into \[ E_1=\frac{10}{3}+E_2: \] \[ E_1=\frac{10}{3}+1.3+0.7E_1+0.09E_0. \] Since \[ \frac{10}{3}+1.3=\frac{139}{30}, \] we get \[ E_1=\frac{139}{30}+0.7E_1+0.09E_0. \] So \[ 0.3E_1=\frac{139}{30}+0.09E_0, \] and therefore \[ E_1=\frac{139}{9}+0.3E_0. \] Now plug this into \[ E_0=\frac{10}{7}+E_1: \] \[ E_0=\frac{10}{7}+\frac{139}{9}+0.3E_0. \] Thus \[ 0.7E_0=\frac{10}{7}+\frac{139}{9}. \] Combine the fractions: \[ \frac{10}{7}+\frac{139}{9} = \frac{90+973}{63} = \frac{1063}{63}. \] So \[ 0.7E_0=\frac{1063}{63}. \] Since \(0.7=\frac{7}{10}\), \[ \frac{7}{10}E_0=\frac{1063}{63}. \] Hence \[ E_0=\frac{10}{7}\cdot\frac{1063}{63} =\frac{10630}{441}. \] Numerically, \[ E_0\approx 24.10. \] So the expected number of flips needed to see the pattern \(HTTH\) is 24.1.