Finite State Automata

1. Find the expected number of flips of a biased coin to see r (r ≥ 3) consecutive head by deriving a corresponding enumerator.

   Solution: The enumerator can be obtained similarly to the outlined procedure in Example~\ref{M922.1} to obtain \[ G(z) = \frac{p^r z^r}{1-qz \sum_{i=0}^{r-1} (pz)^i} =\frac{p^r z^r (1-pz)}{1- z +qp^r z^{r+1}} . \] Setting $z=1$ in the derivative \[ G' (z) = \frac{rp^r z^{r-1} - (r+1)p^{r+1} z^r}{1- z +qp^r z^{r+1}} + \frac{p^r z^r (1-pz) (1- (1+r) qp^r z^r )}{(1- z +qp^r z^{r+1})^2} , \] we confirm the formula~\eqref{E92expect}.

2. Let M = { V, Σ, δ, v₀, F } be a DFA, where V = { v₀, v₁, v₂, v₃ }, Σ = { 0, 1 }, F = { v₃ }, and the transition function is given by the following table:\\

   State 0 1 v₀ v₀ v₁ v₁ v₁ v₂ v₂ v₁ v₃ v₃ v₃ v₁

   Which of the following strings are in L(M)? (a)     ε (b)     001101, (c)     1110, (d)     11011.

   Solution: You only need to act like this automaton … it will lead you to the answer.>/p> (a) The ε does not move M from v_0$ to $v_3$.\\ {\bf(b)\ \ } Since $\delta^{\ast}(v_0,001101)=v_2$, this string is not accepted.\\ {\bf(c)\ \ } Since $\delta^{\ast}(v_0,1110)=v_3$, this string is accepted.\\ {\bf(d)\ \ } Since $\delta^{\ast}(v_0,11011)=v_3$, this string is accepted.\\

3. Find the mean waiting time and verify stopping probabilities for each pair of the eight triplets when flipping a fair coin in the table. \begin{tabular}[h]{|c|c|c|c|c|c|c|c|c|} \cline{2-9} \multicolumn{1}{c|}{} &\textsf{H}\textsf{H}\textsf{H} &\textsf{H}\textsf{H}\textsf{T} &\textsf{H}\textsf{T}\textsf{T} &\textsf{H}\textsf{T}\textsf{H} &\textsf{T}\textsf{H}\textsf{T}&\textsf{T}\textsf{H}\textsf{H} &\textsf{T}\textsf{T}\textsf{H} &\textsf{T}\textsf{T\textsf{T} \\[0.2ex] \hline \textsf{H}\textsf{H}\textsf{H} &---\!-&\frct12 &\frct25 &\frct25 &\frct5{12} &\frct1{8} &\frct3{10} &\frct12 \\ \hline \textsf{H}\textsf{H}\textsf{T} &\frct12 &---\!-&\frct23 &\frct23 &\frct58 &\frct14 &\frct12 &\frct7{10} \\ \hline \textsf{H}\textsf{T}\textsf{T} &\frct35 &\frct13 &---\!- &\frct12 &\frct12 &\frct12 &\frct34 &\frct78 \\ \hline \textsf{H}\textsf{T}\textsf{H} &\frct35 &\frct13 &\frct12 &---\!- &\frct12 &\frct12 &\frct38 &\frct7{12} \\ \hline \textsf{T}\textsf{H}\textsf{T} &\frct7{12} &\frct38 &\frct12 &\frct12 &---\!- &\frct12 &\frct13 &\frct35 \\ \hline \textsf{T}\textsf{H}\textsf{H} &\frct78 &\frct34 &\frct12 &\frct12 &\frct12 &---\!- &\frct13 &\frct35 \\ \hline \textsf{T}\textsf{T}\textsf{H} &\frct7{10} &\frct12 &\frct14 &\frct58 &\frct23 &\frct23 &---\!-&\frct12 \\ \hline \textsf{T}\textsf{T}\textsf{T} &\frct12 &\frct3{10} &\frct18 &\frct5{12} &\frct25 &\frct25 &\frct12&---\!- \\ \hline \end{tabular}

   Solution:     First, we calculate the leading coefficients:

   \begin{tabular}[h]{|c|c|c|c|c|c|c|c|c|} \cline{2-9} \multicolumn{1}{c|}{} %\hline \setlength{\unitlength}{0.002in}% %\begin{picture}(120,80)(0,20) %\put(-40,-15){$B$} \put(90,30){$A$} \drawline(-58,101.7)(181,-24.8) %\end{picture} &\textsf{H}\textsf{H}\textsf{H} &\textsf{H}\textsf{H}\textsf{T} &\textsf{H}\textsf{T}\textsf{T} &\textsf{H}\textsf{T}\textsf{H} &\textsf{T}\textsf{H}\textsf{T}&\textsf{T}\textsf{H}\textsf{H} &\textsf{T}\textsf{T}\textsf{H} &\textsf{T}\textsf{T\textsf{T}} \\[0.2ex] \hline \textsf{H}\textsf{H}\textsf{H} &---\!-&\frct12 &\frct25 &\frct25 &\frct5{12} &\frct1{8} &\frct3{10} &\frct12 \\ \hline \textsf{H}\textsf{H}\textsf{T} &\frct12 &---\!-&\frct23 &\frct23 &\frct58 &\frct14 &\frct12 &\frct7{10} \\ \hline \textsf{H}\textsf{T}\textsf{T} &\frct35 &\frct13 &---\!- &\frct12 &\frct12 &\frct12 &\frct34 &\frct78 \\ \hline \textsf{H}\textsf{T}\textsf{H} &\frct35 &\frct13 &\frct12 &---\!- &\frct12 &\frct12 &\frct38 &\frct7{12} \\ \hline \textsf{T}\textsf{H}\textsf{T} &\frct7{12} &\frct38 &\frct12 &\frct12 &---\!- &½ &\frct13 &\frct35 \\ \hline \textsf{T}\textsf{H}\textsf{H} &\frct78 &\frct34 &\frct12 &\frct12 &\frct12 &---\!- &\frct13 &\frct35 \\ \hline \textsf{T}\textsf{T}\textsf{H} &\frct7{10} &\frct12 &\frct14 &\frct58 &\frct23 &\frct23 &---\!-&\frct12 \\ \hline \textsf{T}\textsf{T}\textsf{T} &\frct12 &\frct3{10} &\frct18 &\frct5{12} &&frct25; &\frct25 &\frct12&---\!- \\ \hline \end{tabular} Similarly, for average waiting time, we get \begin{tabular}[h]{|c|c|c|c|c|c|c|c|c|} \cline{2-9} \multicolumn{1}{c|}{} &\textsf{H}\textsf{H}\textsf{H} &\textsf{H}\textsf{H}\textsf{T} &\textsf{H}\textsf{T}\textsf{T} &\textsf{H}\textsf{T}\textsf{H} &\textsf{T}\textsf{H}\textsf{T}&\textsf{T}\textsf{H}\textsf{H} &\textsf{T}\textsf{T}\textsf{H} &\textsf{T}\textsf{T\textsf{T}} \\[0.2ex] \hline \textsf{H}\textsf{H}\textsf{H} &$\frac{1}{p} + \frac{1}{p^2} + \frac{1}{p^3}$ &\frct12 &\frct25 &\frct25 &\frct5{12} &\frct1{8} &\frct3{10} &\frct12 \\ \hline \textsf{H}\textsf{H}\textsf{T} &\frct12 &---\!-&\frct23 &\frct23 &\frct58 &\frct14 &\frct12 &\frct7{10} \\ \hline \textsf{H}\textsf{T}\textsf{T} &\frct35 &\frct13 &---\!- &\frct12 &\frct12 &\frct12 &\frct34 &\frct78 \\ \hline \textsf{H}\textsf{T}\textsf{H} &\frct35 &\frct13 &\frct12 &---\!- &\frct12 &\frct12 &\frct38 &\frct7{12} \\ \hline \textsf{T}\textsf{H}\textsf{T} &\frct7{12} &\frct38 &\frct12 &\frct12 &---\!- &\frct12 &\frct13 &\frct35 \\ \hline \textsf{T}\textsf{H}\textsf{H} &\frct78 &\frct34 &\frct12 &\frct12 &\frct12 &---\!- &\frct13 &\frct35 \\ \hline \textsf{T}\textsf{T}\textsf{H} &\frct7{10} &\frct12 &\frct14 &\frct58 &\frct23 &\frct23 &---\!-&\frct12 \\ \hline \textsf{T}\textsf{T}\textsf{T} &\frct12 &\frct3{10} &\frct18 &\frct5{12} &\frct25 &\frct25 &\frct12&---\!- \\ \hline \end{tabular}
4. A coin is tossed successively until either two consecutive head occur in a row or four tail occur in a row. What is the probability that the sequence ends with two consecutive head? What is expected number of tosses for this event?

   Solution:     For fair coin, the probability to see m consecutive head or $n$ consecutive tail is \( \displaystyle \quad p(m,n) = \frac{2^m -1}{2^m + 2^n -2} . \quad \) In particular, p(2,4) = ⅚. The expected number of flips is \fbox{14}. This is a particular case of the following Exercise.

5. A coin is tossed successively until one of the following patterns is observed: either a run of H's of length m or a run of T's of length n. We know from Example~\ref{M582.3} that the expected waiting time of the run of H's is 2^m+1 - 2, while for the run of T's it is 2ⁿ⁺¹ - 2. Find the expected number of tosses until either of these two runs happens for the first time and show that for a fair coin this number is \[ \left( \frac{1}{2^{m+1} -2} +\frac{1}{2^{n+1} -2} \right)^{-1} = \frac{2^{n+m} - 2^{n} - 2^{m} +1}{2^{n-1} + 2^{m-1} -1} \,. \]
   Solution: For a fair coin, the probability to see m consecutive head or n consecutive tail is \( \displaystyle \quad p(m,n) = \frac{2^m -1}{2^m + 2^n -2} . \ \) The expected number of flips until either of these two runs happens for the first time is given by the following nice formula: \[ \frac{p^m \,q^n - p^m -q^n +1}{pq^n + qp^m - p^m \,q^n} \, . \] Consider the DFA shown in Figure\;\ref{FF922.1}.
   RJB

   

   A run on this DFA that reaches the state 𝑎_m corresponds to a run ending in m head without any occurrence of a tail. Similarly, a run that reaches b_n represents a sequence of consequent n tail. We denote by p the probability to flip a head and by q = 1 - p to get a tail.

   To find the probability to get the state 𝑎_m or b_n, we denote by 𝑎_i and b_j states of seeing i consequent head (correspondingly j consequent tail; also, we use the same letters to denote probabilities of getting i head (or j tail) in a row.

   To the state b₁ we can arrive either from the starting state (with probability q) or from any 𝑎_i state, i = 1, 2, … , m-1, so we have \[ b_1 = q + qa_1 + qa_2 + \cdots + qa_{m-1} = q \left( 1+\sum_{i=1}^{m-1} a_i \right) . \] the state b₂ can be reached only from the state b₁ with probability q; hence, b₂ = q b₁. The same is true for any state b_j including the last (accepting) state; and we have \( \displaystyle \quad b_j = qb_{j-1} = q^{j-1} \,b_1, \qquad j=2,\ldots , n. \quad \) On the other hand, the state 𝑎₁ can be reached either from the start state with probability p or from each state b_j except the last one: \[ a_1 = p + pb_1 + p b_2 + \cdots + pb_{n-1} = p \left( 1+\sum_{j=1}^{n-1} b_j \right) . \] State 𝑎₂, as well as any other state, can be reached only from its predecessor: 𝑎₂ = p 𝑎₁, … , 𝑎_i = p 𝑎_i-1 = p^i-1𝑎₁, i = 2, … , m. Substituting these values into expressions for 𝑎₁ and b₁, we obtain \[ a_1 = p \left( 1+\sum_{j=1}^{n-1} b_j \right) = p \left( 1+\sum_{j=1}^{n-1} q^{j-1} \,b_1 \right) = p + B\,b_1 , \] \[ b_1 = q \left( 1+\sum_{i=1}^{m-1} a_i \right) = q \left( 1+\sum_{i=1}^{m-1} p^{i-1} \,a_1 \right) = q + A\,a_1 , \] where \( \displaystyle \quad A= q\,\sum_{i=1}^{m-1} p^{i-1} = q\,\frac{1-p^{m-1}}{1-p} = 1-p^{m-1}\quad \) and \( \displaystyle \quad B = p\,\sum_{j=1}^{n-1} q^{j-1} =p\, \frac{1-q^{n-1}}{1-q} = 1-q^{n-1} . \quad \) Thus, we get two equations with two unknowns: \[ a_1 = p + B\,b_1 , \qquad b_1 = q+Aa_1 \, . \] Solving them, we obtain \[ a_1 = \frac{p+qB}{1-AB} = \frac{1-q^n}{p^{m-1} + q^{n-1} - p^{m-1}\,q^{n-1}} , \qquad b_1 = \frac{q+pA}{1-AB} = \frac{1-p^m}{p^{m-1} + q^{n-1} - p^{m-1}\,q^{n-1}} \, \] The probability to get the final state, $a_m$, is \( \displaystyle \quad pa_{m-1} = p^{m-1} \,a_1 ; \) similarly $b_n = q^{n-1} \,b_1$; and finally we obtain \begin{align*} a_m &= \Pr [m \;\mbox{head}] = p^{m-1} \,\frac{p+qB}{1-AB} = \frac{q^{-n} -1}{q^{-n} + p^{1-m}\,q^{-1} -q^{-1}} , \\ b_n &=\Pr [n \;\mbox{tail}] = q^{n-1} \,\frac{q+pA}{1-AB} = \frac{p^{-m} -1}{p^{-1} \,q^{1-n} + p^{-m} -p^{-1}} \,. \end{align*}

   For a fair coin, we have p = q = ½ and hence the probability to get the final state is \[ \Pr [m \;\mbox{head}] = \frac{2^{n} -1}{2^m + 2^n -2}, \qquad \Pr [n \;\mbox{tail}] = \frac{2^{m} -1}{2^m + 2^n -2} . \] In particular, the probability to get 2 head before 4 tail is \fbox{⅚} and the probability to get 4 tail before 2 \head is \fbox{⅙}.

   Now we calculate expected values to see m head or n tail in a row. Let s be the required expected value, A_i, i = 1, 2, … , m, be the expected value to reach the excepting state from the state 𝑎_i and B_j, j = 1, 2, … , n, be the expected value to reach the excepting state from the state b_j. Note that A_m = B_n = 0 because we are already at our final state. From figure 1 we get the following equation: \( \displaystyle \quad s=1 + pA_1 + qB_1 , \ \) hence \begin{align*} A_1 &= 1+ pA_2 + q B_1 , \quad A_2 &= 1+ pA_3 + q B_1 , \quad A_i &=1+ pA_{i+1} +q B_1 ; \\ B_1 &=1+ pA_1 + qB_2 , \quad B_2 &=1+ pA_1 + qB_3 , \quad B_j &=1+ pA_1 + qB_{j+1} . \end{align*} The solution to this system of algebraic equations is \begin{align*} A_{m-i} &= (1+q\,B_1 ) \,\frac{1-p^i}{1-p} , \quad i=1,2,\ldots , m-1, \qquad &A_1 = (1+q\,B_1 ) \,\frac{1-p^{m-1}}{1-p} , \\ B_{n-j} &= (1+p\,A_1 ) \,\frac{1-q^j}{1-q} , \quad j=1,2,\ldots , n-1,\qquad &B_1 = (1+p\,A_1 ) \,\frac{1-q^{mn1}}{1-q} . \end{align*} Solving for A₁ and B₁, we get \[ A_1 = \frac{(1-p^{m-1} )(1-q^{n})}{D(p,q)} , \qquad B_1 = \frac{(1-q^{n-1} )(1-p^{m})}{D(p,q)} , \] where \( \displaystyle \quad D(p,q) = (1-q)(1-p) -pq (1-q^{n-1})(1-p^{m-1}) = pq^n + qp^m - p^m \,q^n .\quad \) Substituting these values into s = 1 + p A₁ + q B₁, we obtain the expected values to get m head or n tail: \[ E[m\;\mbox{head or $n$ tail}] = \frac{p^m \,q^n - p^m -q^n +1}{pq^n + qp^m - p^m \,q^n} \, . \] Setting p = q = ½, we get the expected value to see m head or n tail by tossing a fair coin to be the expression announced at the beginning formula.

6. Suppose you flip a fair coin without stopping, what is the average waiting time until the first occurrence of the pattern occurs? Write the enumerator for each event.

   (a)     HHHHH,
   (b)     HTHTH,
   (c)     HHHTH,
   (d)     HHHHT .

   Solution: We denote by p the probability to flip a head and by q = 1 − p to flip a tail.

   (a)     Let d_i, i = 0, 1, 2, 3, 4, 5 be the expected waiting time (= number of flips) to reach HHHHH from the state i. Then we have the following equations \[ d_0 = 1+pd_1 + qd_0 , \quad d_1 = 1 +pd_2 + qd_0 , \quad d_2 = 1+pd_3 + qd_0 , \] \[ d_3 = 1 + pd_4 + qd_0 , \quad d_4 = 1 + pd_5 + qd_0 , \quad d_5 =0 . \] Solving these equation, we obtain the required expected waiting time to be \[ d_0 = \frac{1+p+p^2 + p^3 +p^4}{1-q(1+p+p^2 + p^3 +p^4 )} = \frac{1-p^5}{q\,p^5} = 62\quad\mbox{when } p=q=1/2\, . \]

         RJB

   

   To derive the enumerator, we write symbolically the equations for each state: \[ v_0 = 1 v_0 + Tv_0 + Tv_1 +Tv_2 +Tv_3 +Tv_4 , \quad v_1 = Hv_0 , \quad v_i = Hv_{i-1} , \quad i=1,2,\ldots , 5 \, . \] So the final state can be written as \( \displaystyle \quad v_5 = \frac{HHHHH}{1-T-HT -HHT -HHHT -HHHHT}\, v_0 \quad \) and the enumerator is \[ G(z) = \frac{p^5 \,z^5}{1-qz-pqz^2 -p^2 qz^3 -p^3 qz^4 -p^4 qz^5} \, . \] So in general, the expected number of flips to see m head in a row is \[ E[m\;\mbox{head} ] = G' (1) = \frac{1-p^m}{q\,p^m} = q^{-1} \left[ p^{-m} -1 \right] \, . \]

   (b)     Let d_i, i = 0, 1, 2, 3, 4, 5, be the expected waiting time (= number of flips) to reach HTHTH from the state i. Then we have the following equations \[ d_0 = 1+pd_1 + qd_0 , \quad d_1 = 1 +pd_1 + qd_2 , \quad d_2 = 1+pd_3 + qd_0 , \] \[ d_3 = 1 + pd_1 + qd_4 , \quad d_4 = 1 + pd_5 + qd_0 , \quad d_5 =0 , \] where d₅ is the accepting state for HTHTH (so d₅ = 0). Solving these equation, we obtain the required expected waiting time to be \[ d_0 = \frac{2+p+pq^2}{1-pq} = 42\quad\mbox{when } p=q=1/2\, . \]

         RJB

   

   The enumerator is \[ G(z) = \frac{p^3 q^2 \,z^5}{(1-pz)(1-qz) -pqz^2 -p^2 q^3 \,z^5} \, . \]

   (c)    Let d_i, i = 0, 1, 2, 3, 4, 5, be the expected waiting time (= number of flips) to reach HHHTH from the state i. Then we have the following equations \[ d_0 = 1+pd_1 + qd_0 , \quad d_1 = 1 +pd_2 + qd_0 , \quad d_2 = 1+pd_3 + qd_0 , \] \[ d_3 = 1 + pd_3 + qd_4 , \quad d_4 = 1 + pd_5 + qd_0 , \quad d_5 =0 , \] where d₅ is the accepting state for HHHTH. Solving these equation, we obtain the required expected waiting time to be \[ d_0 = \frac{p^3 + 1/q}{1-q-pq-p^2 q -p^3 q} =34 \quad\mbox{when } p=q=1/2\, . \] The enumerator becomes \[ G(z) = \frac{p^4 q \,z^5}{(1-pz)(1-qz -pqz^2 -p^2 qz^3 ) -p^3 q^2 \,z^5} \, . \]

         RJB

   

   (d)    Let d_i, i = 0, 1, 2, 3, 4, 5, be the expected waiting time to reach HHHHT from the state i. Then we have the following equations \[ d_0 = 1+pd_1 + qd_0 , \quad d_1 = 1 +pd_2 + qd_0 , \quad d_2 = 1+pd_3 + qd_0 , \] \[ d_3 = 1 + pd_4 + qd_0 , \quad d_4 = 1 + pd_4 + qd_5 , \quad d_5 =0 , \] where d₅ is the accepting state for HHHHT. Solving these equation, we obtain the required expected waiting time to be \[ d_0 = \frac{1}{qp^4} =32 \quad\mbox{when } p=q=1/2\, . \] The enumerator becomes \[ G(z) = \frac{p^4 q \,z^5}{(1-pz)(1-qz -pqz^2 -p^2 qz^3 -p^3 qz^4 )}\, .\]

         RJB

   

7. What is the probability that in a stochastic sequence of head (H) and tail (T) the pattern HHHHT appears earlier than HHHTH? Assume that tail lands with probability q. \begin{full}

   Solution: The dfa was found in Exercise~\ref{X923.3}:

         RJB

   

   The state v_ε describes a ``no progress'' situation. It is the initial state and whenever the sequence so far cannot terminate with a prefix of a stopping string, such as TT or HHT. The stopping states can only be reached from the states v_t and v_h, respectively. The odd coil on the left stands for the sequence of state transitions needed to proceed from v_ε to v_H³, a sequence that is either an initial HHH or has the suffix THHH. The number of the required transitions has the probability generating function (assuming we flip head with probability p) \( \displaystyle \quad T(u) = u^3p^3/(1-uq-u^2pq-u^3pq^2) , \ \) which has the expected value of \( \displaystyle \quad p(1-p^3)/[q(p-q^2)], \ \) which amounts to 14 when p = ½.

   To find the probability 𝑎 that v_𝑎 is reached before state v_b we only need to follow events from the state v_{H³, and this gives rise to the relation \( \displaystyle \quad a = \mbox{Pr}(TH) + \mbox{Pr}(TT)a =(1+a)/4, \ \) so that 𝑎 = ⅓. This calculation elides many details that need be considered when we want the time till absorption. Slightly more generally, if the probability of flipping head is p, and we let q = 1 − p, then we find \( \displaystyle \quad a = q(p+qa) \quad \Longringarrow \quad a=\frac{q}{1+q}. \)}

8. (a)    On average, how many times do you need to choose digits from the alphabet Σ = { 0, 1, … , 9 } (taken randomly with replacement) to see 4-long sequence (i, i, i, i), i ∈ Σ?
   (b)    A pseudo-random generator produces r-tuples of integers (i₁, i₂, … , i_r ) from the alphabet Σ = { 0, 1, … , 9 }. What is expected waiting time (measured in the number of calls of the random generator) for the sequence (i, i, … , i)?

   Solution: (a)    First we draw the DFA:

         RJB

   

   Of course, we cannot draw all moves, but only some of them. The accepting states are in the top row, with last indices 4. Let p = 0.1 be the probability to see a particular number, and let q = 1 − p = 0.9. Each state in the row j is denoted by v_ij, i = 0, 1, … , 9; correspondingly, we denote by d_ij the expected number of calls for random number generator to reach from state v_ij to an accepting state (v_{_i4}, i = 0, 1, … , 9). By d₀ we denote the (required) expected value of numbers needed to reach from the start state to an accepting state. Then we have the following system of equations:

   \( \displaystyle \quad d_0 = 1 + p \sum_{i=0}^9 d_{i1}; \)
   \( \displaystyle \quad d_{i1} = 1 + p d_{i2} + p \sum_{j\ne i} d_{j1}, \quad i=0,1,\ldots , 9; \)
   \( \displaystyle \quad d_{i2} = 1 + p d_{i3} + p \sum_{j\ne i} d_{j1}, \quad i=0,1,\ldots , 9; \)
   \( \displaystyle \quad d_{i3} = 1 + p d_{i4} + p \sum_{j\ne i} d_{j1}, \quad i=0,1,\ldots , 9$; \)
   \( \displaystyle \quad d_{i4} =0, \quad $i=0,1,\ldots , 9. \)

   The last 3 sets of equations can be eliminated, which reduces the problem to the following system of equations: \[ d_0 = 1 + p \sum_{i=0}^9 d_{i1} , \quad d_{i1} = 1+p+p^2 + p(1+p+p^2 )\,\sum_{j\ne i} d_{j1}, \quad i=0,1,\ldots , 9. \] Since the equations for d_i1 are symmetrical, we get for i = 0, 1, 2, … , 9 that \[ d_{i1} =\frac{(1+p+p^2 ) (1+p+p^2 +p^3 )}{1-8p(1+p+p^2 ) -9p^2 (1+p+p^2 )^2} = \frac{(1+p+p^2 ) (1+p+p^2 +p^3 )}{(1+p)(1+p^2 )(1-9p-9p^2 -9p^3 )} . \] Substituting these values into the latter equation for d₀, we obtain the expected value to be \[ d_0 = \frac{(1+p)(1+p^2 )}{1-9p-9p^2 -9p^3} = 1111, \quad\mbox{when } p=0.1. \]

   (b)    Actually we don't need to do any calculations. Any digit to show up has the same probability, $p=0.1$. So we use the formula \eqref{E92expect} to obtain the expected number of calls to see a sequence of $r$ consecutive zeroes (for instance), which is $(1-p^r )/qp^r$. Dividing this number by 10, we obtain the expected value to be \[ \frac{1-p^r}{10q p^r} = \frac{10^r -1}{9} . \]

9. The goal of this exercise is to show that some waiting time problems may have counterintuitive solutions. Given two sequences of patterns, HTHT and THTT, a coin is flipped repeatedly until one of the patterns appears as a run; what pattern win? Find the expected number of tosses needed to see a winner; also, determine the expected running time (=number of flips) for each of the patterns. As a check on your answers for a fair coin: the odds are 9 to 5 in favor of getting HTHT first, though its expected number of tosses till first arrival is 20, whereas the pattern THTT needs only 18 flips on the average.

   Solution: To solve this problem, we draw first a transition diagram for a finite state machine that simulates this Bernoulli process.

         RJB

   

   two final states, we get the following system of equations: \begin{align*} d_H &= 1+p d_H +q d_{HT} , \quad d_{HT} &= 1 +p d_{HTH} +qd_T , \quad d_{HTH} &= 1 +pd_H , \\ d_T &= 1+q d_T +p d_{TH} , \quad d_{TH} &= 1+q d_{THT} +p d_H ,\quad d_{THT} &= 1+pd_{HTH} , \end{align*} where d = 1 +pd_H +qd_T is the expected value to reach either of stopping states. Solving for d, we obtain \[ d= \frac{1+2pq -2p^3 +3p^4 -p^5}{pq^2 (1-p^2 +p^3 )} . \] For p = q = ½ we have $d=\frac{90}{7} \approx 12.85714286$. To find the expected number of tosses needed to obtain either of patterns, HTHT or THTT, we draw the diagrams for the corresponding DFAs:

         RJB

   

   Let d be the expected number of flips needed to see a run of HTHT. Then we have the following system of algebraic equations: \begin{align*} d&=1+q\,d +p\,d(H), \quad &d(H) &= 1+p\,d(H) +q\,d(HT), \\ d(HT) &=1+p\,d(HTH) +q\,d, \quad &d(HTH) &=1+p\,d(H) , \end{align*} where d(H) is the expected number of flips to reach the final state, HTHT, d(HT)$ is the average number of tosses to reach HTHT, and d(HTH) is the expected waiting time for the state HTH. Solving for d, we obtain \[ d= \frac{1+p-p^2}{p^2 \,q^2} \quad\mbox{which for a fair coin gives}\quad d=20. \] For the pattern THTT we have

         RJB

   

   Solving the corresponding system of equations \begin{align*} d&=1+q\,d +p\,d(H), \quad &d(H) &= 1+p\,d(H) +q\,d(HT), \\ d(HT) &=1+p\,d(HTH) +q\,d, \quad &d(HTH) &=1+p\,d(H) , \end{align*} we obtain the expected number of flips to see a run of THTT: \[ d=\frac{1+p-2p^2 +p^3}{pq^3} ,\quad\mbox{which for a fair coin gives}\quad d=18. \] Finally, we calculate the probabilities to reach either of the stopping states. We can arrive to start state only from itself with probability 1, so v₀ = 1. To state v_H we can some only from the start state with probability p, or from itself with probability p, or from states TH and HTH with probability p. Hence, \[ v_H = p\,v_0 + p\,v_{H} + p\,v_{TH} + p\,v_{HTH} = p+p\,v_{H} + p\,v_{TH} + p\,v_{HTH} . \] Similarly \begin{align*} v_{HT} &= q\,v_H , \quad &v_{HTH} = p\,v_{HT} + p\,v_{THT} , \\ v_{TH} &= p\,v_T , \quad &v_{THT} = q\, v_{TH} , \quad v_T = q + q\,v_T+q\,v_{HT} . \end{align*} Solving for v_HTH and v_THT, we obtain \[ v_{HTH} = \frac{p(1+p-2p^2 +p^3 )}{q(1-p^2 +p^3} , \quad v_{THT} = \frac{1-2p^2 +p^3}{1 -p^2 +p^3} . \] The final states can be reached from the states v_HTH and v_THT with probability q. Hence, the odds of the stopping states are
   v_HTHT, :
   v_THTT = p(1+p-2p² + p³ ) \, : q(1-2p² + p³ ).

   Therefore the probability to reach the final states are \[ \Pr [HTHT] = \frac{p(1+p-2p^2 +p^3 )}{1-p^2 +p^3} , \qquad \Pr [THTT] = \frac{q(1-2p^2 +p^3 )}{1-p^2 +p^3} . \] For fair coin when p = q = ½, we get their probabilities to be 9/14 and 5/14, respectively.

10. Suppose, for instance, that A flips a coin until she observes either HHHTH or HTHTH, while B flips another coin until he observes either HHHHT or HHHTH. Here H stands for head and T---for tail. It is assumed that both coins have the same probability p of head on each trial. For what p the average waiting times for A and for B will be the same?

    Solution: The dfa of player A is

          RJB

    

    For the patterns HHHTH or HTHTH, from the corresponding DFA, we get the system of equations (with q = 1 − p and d = d₀): \begin{align*} d_0 &= 1+pd_1+qd_0, & d_1 &= 1+pd_2+qd_0, & d_2 &= 1+pd_3+qd_0\\ d_3 &= 1+pd_4+qd_5, & d_4 &= 1+pd_4, & d_5 &= 1+qd_0. \end{align*} Solving for d, the expected value to arrive to either HHHTH or HTHTH, we get \( \displaystyle \quad d=d_0 = \frac{1-q^2p^3}{p^4q(1+q)} . \)

    The dfa of player B is

          RJB

    

    The equations here are \begin{align*} d_0 &= 1+pd_1+qd_0, & d_1 &= 1+pd_2+qd_0, & d_2 &= 1+pd_3+qd_0\\ d_3 &= 1+pd_4+qd_5, & d_4 &= 1+pd_4, & d_5 &= 1+qd_0. \end{align*} Solving for d₀ = d, the expected value to arrive to either HHHHT or HHHTH, we get
    \( \displaystyle \quad \\ d= d_0 = \frac{1-q^2p^3}{p^4q(1+q)} \)

    Equating these two expected values, we obtain the fifth order algebraic equation in $p$ with the single positive solution at p = ½.