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, 2021 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$
    – tbrugere
    Feb 24, 2021 at 14:31
  • $\begingroup$ @Semiclassical OK,thanks! $\endgroup$
    – Hovard
    Feb 24, 2021 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, 2021 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, 2021 at 14:51

2 Answers 2

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, 2021 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, 2021 at 23:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .