Expected length of runs in a binary string

Question

Question

This is a math of the Introduction to Probability Models (11th edition) written by Sheldon M Ross.

Runs of 0s or 1s follow a geometric distribution. The solution I found in the solution manual:

Answer

Here conditioning has been applied on the first bit. So E[L1|X = 0] should be (1/p) - 1 , as the expected value of a geometric random variable is 1/p (where p is the probability of success). Here the expected length of first run given that first bit is zero is 1/p "including the first 1 after the run of zeroes". So I have written (1/p) - 1 , excluding the first 1 after the run of zeroes. But in the solution manual, it is (1/p). Am I missing something?

If I think somewhat different (not conditioning on the first bit), the first run can contain either all os or all 1s. If it contains all 0s, the expected length should be (1/p) - 1 or (1-p)/p , and if it contains all 1s, the expected length should be 1/(1-p) - 1 or p/(1-p) . In the first case, the success of a geometric random variable is characterized by the presence of a 1 after the first run ends. Same type of logic applies for the run of 1s. Then my solution matches with the solution of the picture.

Can anyone please point out what I am missing?

Answer 1

The solution manual is correct in stating that-

E(L₁|X=0) = 1 + ($\frac{1}{p}$ - 1)

In this expression, the first 1 accounts for the "0" symbol at the very start of the sequence. The second term accounts for the number of zeroes until the first one is encountered. You are right, $\frac{1}{p}$ includes the final symbol "1" that we see in the sequence and we thus need to subtract one from $\frac{1}{p}$. However, you forgot to account for the first "0" symbol encountered at the very beginning.

Answer 2

I note that the formulas given in the answer key are correct only if the length of the sequence is infinite, so I'll assume that the use of a finite sequence as an example of "the outcome sequence" was not intended to indicate that the sequence is finite.

---

Regarding your formulas, suppose $p = \frac23.$ Then $\frac1p - 1 = \frac32 - 1 = \frac12.$ So you are saying that when a sequence with $p = \frac23$ starts with a $0,$ the expected length of the first run is $\frac12.$

Since the length of a run is always at least $1,$ it is impossible for the expected length of a run to be less than $1.$ Therefore your formula for this case cannot be correct.

One way to look at this is that indeed $\frac1p$ is the expected number of elements in an initial string that consists of zero or more $0$s followed by exactly one $1.$ (Every It is also the expected number of elements in a string $S$ of zero or more $0$s followed by exactly one $1$ that starts at the second element of the sequence. The expected length of the initial run, given that the first element of the sequence is $0,$ is the length of the string $S,$ minus $1$ because the final $1$ in $S$ is not part of the run of $0$s, plus $1$ because the initial $0$ in the sequence is not part of $S$ but is part of the first run.

If that's too confusing, go back to basics. Given that the initial digit is $0,$ then $P(L_1 = 1) = p$ (the probability that the second digit is $1$), $P(L_1 = 2) = (1 - p)p$ (the probability that the second digit is $0$ and the third digit is $1$), $P(L_1 = 3) = (1 - p)^2p,$ $P(L_1 = 4) = (1 - p)^3p,$ and so forth. Then $$ E[L_1] = \sum_{k=1}^\infty k(1-p)^{k-1}p = \frac1p. $$

---

I don't quite follow your reasoning in the paragraph that begins, "If I think somewhat different (not conditioning on the first bit)". You proceed to write, "If it contains all $0$s, the expected length should be ... ," so you are conditioning on whether the first run is a run of $0$s or a run of $1$s. But the initial run is a run of $0$s if and only if the initial bit is $0,$ so conditioning on all $0$s is the same as conditioning on the first bit being $0.$ It should not change the answer.