Expected Value of the number of 0's and 1's until a certain pattern occur

Question

I'm facing the following problem:

Let $X, X_1, X_2..$ be IID random variables with $P(X=0) = P(X=1) = 1/2$.

• Let $N_1$ be the number of 0's and 1's until the first appearance of the pattern 10. Find $E[N_1]$

I am trying to use the following property:

$$E[X] = \sum_{i=1}^{\infty}P(X\geq i)$$

thus:

$E[N_1] = \sum_{i=1}^{\infty}(1 - P(N_1 < i))$

My tentative is the following:

$P(N_1<1) = P(N_1=0) = \dfrac{1}{2}\times\dfrac{1}{2} = \dfrac{1}{4} $ (i.e the probability of obtaining 1 in the first try and 0 in the second, so:

$P(N_1<2) = P(N_1=0) + P(N_1=1) = \dfrac{1}{4} + \dfrac{1}{2}\times\dfrac{1}{2}\times\dfrac{1}{2}$

$P(N_1<3) = P(N_1=0) + P(N_1=1)+P(N_1=2) = \dfrac{1}{4} + \dfrac{1}{8} + (\dfrac{1}{2})^{4}$

$$\vdots$$

$P(N_1<n) = P(N_1=0) + P(N_1=1) \dots +P(N_1=n-1) = \sum_{i=1}^{n}\Bigg(\dfrac{1}{2} \times \dfrac{1}{2^i}\Bigg)$

Thus: $E[N_1] = \sum_{i=1}^{\infty} \Bigg(1- \sum_{j=1}^{i}\dfrac{1}{2^{i+1}}\Bigg)$

And I don't know how to continue and I think that I'm doing something terribly wrong. Anyone can hep-me? Sorry if a made a huge mistake, I'm a beginner in probability.

Answer 1

What you are doing is needed if you are trying to find the distribution of 0s and 1s until you get 10, but for expected value, you can take a much simpler approach.

• Let's say the first trial is a 1. Let $X_1$ denote the expected number of trials until you get to 10.

w.p. ${1 \over 2}$, you will get 0 in the next trial and you are done in just one more trial.

w.p. ${1 \over 2}$, you will get 1 in the next trial and you are back to where you started (since the trials are independent, the past doesn't matter). This means that you "wasted" a trial and now you need another $X_1$ expected trials to get to 10 (by definition of $X_1$)

So you have $X_1 = {1 \over 2}(1) + {1 \over 2}(X_1+1)$

Solve to get $X_1 = 2$.

• Now let's say the first trial was a 0. Let $X_0$ denote the expected number of trials needed to get to 10.

w.p. ${1 \over 2}$, you get a 0 and you are back to where you started

w.p ${1 \over 2}$, you get a 1 and now you need another $X_1$ expected trials to get to 10 (remember we defined $X_1$ above

This gives $X_0 = {1 \over 2}(1 + X_0) + {1 \over 2}(1 + X_1)$

Since we know $X_1 = 2$, you can solve the above to get $X_0 = 4$

• Putting it all together, your first trial could have been a 0 or a 1 w.p. ${1 \over 2}$. So the total number of expected trials is:

${1 \over 2}X_0 + {1 \over 2}X_1 + 1 = 4$ (the +1 at the end is because you need to count the very first trial as well)

This is a good problem to learn the idea of a "state". The experiment may wander over different states and once it comes back to the state where it started, the history is forgotten! You will learn a lot more about this when you study Markov chains.

Answer 2

Intuition: we expect it to take two trials to see the first $1$, then we expect another $2$ trials to get the next $0$, so the answer is $4$.

Fleshing that out a bit:

The key point is that once you see the first $1$, the game ends with the next $0$.To write that out, we work with states:

Let $S_1$ denote the state in which the last trial gave a $1$. Let $S_0$ denote the state in which the last trial gave a $0$ (we'll include the start in this state). Let $E_i$ be the expected number of tosses it takes to finish from state $S_i$. Thus the answer you want is $E_0$.

Considering the possible outcomes of the next trial we see that $$E_0=1+\frac 12\times E_0+\frac 12\times E_1\quad \&\quad E_1=1+\frac 12\times E_1$$

which indeed yields $E_0=4$.