Consider finding the expected time until a given string appears in a IID binary sequence with Pr{Xn = 1} = p1, Pr{Xn = 0} = p0 = 1 - p1.

(a) Following the procedure in Example 4.5.1, draw the three-state Markov chain for the string (0,1). Find the expected number of trials until the first occurrence of the string.

(b) For (b) and (c), let (a1, a2, a3, ... , ak) = (0, 1, 1, ... , 1), i.e., zero followed by k - 1 ones. Draw the corresponding Markov chain for k = 4.

(c) Let vi, 1 ≤ i ≤ k be the expected first-passage time from state i to state k. Note that vk = 0. For each i, 1 ≤ i <>, show that vi = αi + vi+1 and v0 = βi + vi+1, where αi and βi are each expressed as a product of powers of p0 and p1. Hint: Use induction on i taking i = 1 as the base. For the inductive step, first find βi+1 as a function of βi starting with i = 1 and using the equation v0 = 1/p0 + v1.

(d) Let a = (0, 1, 0). Draw the corresponding Markov chain for this string. Evaluate v0, the expected time for (0, 1, 0) to occur.

Text Book: Stochastic Processes: Theory for Applications By Robert G. Gallager.