2
$\begingroup$

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...

$\endgroup$
9
  • $\begingroup$ @Semiclassical so you mean I should make a litte change my question? What should I do? $\endgroup$
    – Hovard
    Feb 24 at 14:29
  • $\begingroup$ 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$ $\endgroup$
    – Nephanth
    Feb 24 at 14:31
  • $\begingroup$ @Semiclassical OK,thanks! $\endgroup$
    – Hovard
    Feb 24 at 14:32
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 24 at 14:40
  • 1
    $\begingroup$ Hint: what is the answer for $1$ instead of $100$? That should tell you the general result, which is then easily proven by recursion.. $\endgroup$
    – lulu
    Feb 24 at 14:51
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Good Answere,Thank you very much! $\endgroup$
    – Hovard
    Feb 24 at 23:19
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Hovard
    Feb 24 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.