# A Probability Question of Infinite situation

Consider this situation:

The computer will randomly output 1 or 0, the probability of each one is 1/2.

The computer will continuously output until the number of 1 reaches 100.

Now,the number of 0 will be 1 or 2 or 3 or ...

My question is the expected number of 0s.

(

There is another explanation:

Let N be the number of zeros before there are a hundred ones

I just want to know the expected value of N )

Maybe it does not meet the definition, I just want to say----which number of 0 is the most possible?

I do this question with the binormial distribution,I think it's may be

$$\displaystyle\sum_{n=0}^{\infty} C_{100+n}^{n}\displaystyle\frac{n}{2^{100+n}}$$

However,I don't know how to deal with it.

On the other hand, I'm not sure , I think my method is strange...

• @Semiclassical so you mean I should make a litte change my question? What should I do? Feb 24 '21 at 14:29
• You should probably edit your question. What I would do if I were you is give a name to what you are searching. "Let $N$ be the number of zeroes before there are a hundred ones", and then say you are looking for the expected value of $N$ Feb 24 '21 at 14:31
• @Semiclassical OK,thanks! Feb 24 '21 at 14:32
• For more practical advice, you may want to look up the negative binomial distribution. Per Wikipedia, the negative binomial distribution "models the number of successes in a sequence of independent and identically distributed Bernoulli trials before a specified (non-random) number of failures (denoted r) occurs." That seems awfully close to what you want. Feb 24 '21 at 14:40
• Hint: what is the answer for $1$ instead of $100$? That should tell you the general result, which is then easily proven by recursion..
– lulu
Feb 24 '21 at 14:51

So basically, let’s formalize and generalize the problem.

Let $$(X_i)$$ be the bits the computer outputs. $$(X_i) \sim B(1/2)$$ iid.

We can modify the problem a bit and say (equivalently) $$(X_i)$$ is infinite, and we are looking for the number $$N$$ of zeroes before we see a hundred 1s

Actually let us generalize the problem a bit and consider the number

$$N_n$$ of zeroes before we reach n ones. We are looking for $$N_{100}$$

let us use a recursive strategy on $$N_n$$ :

• $$N_1$$ is pretty easy : it is the number of zeroes before the first 1, it follows a geometric law $$\mathcal{G}(1/2)$$

• let us now look at $$N_{k + 1}$$ knowing $$N_{k}$$ : fun thing is that $$N_{k + 1} - N_{k} | N_{k}$$ also follows a geometric law (it is the number of zeroes between the kth one and the (k+1)th one

afterward $$\mathbb{E}(N_{k+1}) = \mathbb{E}(\mathbb{E}(N_{k+1} | N_{k})) \\ = \mathbb{E}(\mathbb{E}(N_{k+1} - N_k + N_k | N_{k}))\\ = \mathbb{E}(\mathbb{E}(N_{k+1} - N_k | N_{k}) + N_k) \\ = \mathbb{E}(N_k) + \mathbb{E}(\mathcal{G}(1/2))$$

From this, I think you can infer the end of the induction

• Good Answere,Thank you very much! Feb 24 '21 at 23:19

Let $$X_i \in \{0,1\}$$, $$i=1, 2 \cdots M$$, with $$\sum_{i=1}^{M-1} X_i=99$$, $$X_{M}=1$$

Then $$N=M-100$$ and $$E[N \mid M] = M - 100$$ and

$$E[N]= E [E[N \mid M]] = E[M] - 100$$

To compute $$M$$, partition the sequence in subsequences consisting on $$k$$ (perhaps zero) $$0$$'s followed by one $$1$$. Let $$Y_j$$ be the length of these subsquences, hence $$Y_j = 1,2 \cdots$$ with $$M=\sum_{j=1}^{100} Y_j$$

Now each $$Y_j$$ follows a geometric distribution (number of tries till first success) with $$E[Y_j] = 2$$

Hence $$E[N]= 100 E[Y_j] - 100 = 100$$

Put in another way, for each $$1$$ we expect before a run of $$0$$'s which have average length one. Hence, in average, we expect the same number of zeroes and ones.

• For your last sentence, I have thought about it too, I guess the answer is 100 but I think it's not rigorous... Thanks for your clear answer. It's very easy to understand. Feb 24 '21 at 23:21