# Expected Number of Trials for First Success when Probability Changes Every Trial

Let's say you have a box containing exactly 1 blue ball and 1 red ball.

At every trial, one ball is randomly picked from the box. After picking one, one blue ball is added to the box. (NOTE: After picking, the ball is returned back to the box)

What is the average/mean expected number of trial needed to pick a red ball? (first success?) Is it possible to calculate this? If so, calculate the Variance as well.

MY ATTEMPT:

If I'm not wrong, the formula for calculating the number of trials needed to flip the first head of a coin is 1/p (which I suspected was very similar to this). The thing that got me stuck is that the probability changes after every trial. Maybe some special kind of distribution is needed to calculate this or some limit theorem (idk?) but I'm very lost about that. Any pointers?

EDIT 1: Please tell me if I made a mistake somewhere: the probability of red ball first got picked at nth trial is the product of all probabilities of red ball not getting picked before the nth trial and probability of red ball getting picked at the nth trial so:

the probability that a red ball only got picked at 1st trial is 1/2

the probability that a red ball only got picked at 2nd trial is 1/2 * 1/3 = 1/6

the probability that a red ball only got picked at 3rd trial is 1/2 * 2/3 * 1/4 = 1/12

the probability that a red ball only got picked at 4th trial is 1/2 * 2/3 * 3/4 * 1/5 = 1/20

the probability that a red ball only got picked at 5th trial is 1/2 * 2/3 * 3/4 * 4/5 * 1/6 = 1/30

I'm seeing a pattern, but I'm still at lost on how to count the expected number of trials

EDIT 2: The ball that got picked is returned to the box afterwards. Sorry for not being clear.

EDIT 3 : Because I am after the number of trials for first success, the formula would be 1/p correct?

Therefore the expected trials needed at can be calculated as a function of n : f(n) = n(n+1) (where n is the trial number in which the red ball got picked)

However I'm still very stumped on how to calculate the mean expected trials with n still in the way...

• What have you tried? Can you compute the probability that it takes one trial? Two trials? After working a few of these small cases, perhaps some pattern will emerge.
– lulu
Aug 11 '20 at 16:03
• After you pick the ball, is the ball returned? In other words are you sampling with or without replacement? Aug 11 '20 at 16:14
• Post edit: Good work. You should see (numerically) that the probability of success on trial $n$ is $\frac 1{n(n+1)}$. Now, try to prove that by induction.
– lulu
Aug 11 '20 at 16:15
• @RawrDamn Should have said: Suppose (even if you haven't proven it yet) that the probability that the first success comes on trial $n$ is indeed $\frac 1{n(n+1)}$. What would that imply for the expected value?
– lulu
Aug 11 '20 at 16:17
• If $\Pr(X=k) = \frac{1}{k(k+1)}$ is the probability that you pick the red ball at $k$-th trial, then the expected value is undefined: $$\mathbb{E}[X] = \sum_{k=1}^{\infty} k \cdot \Pr(X=k) = \sum_{k=1}^{\infty} k \cdot \frac{1}{k(k+1)} = \sum_{k=1}^{\infty} \frac{1}{k+1} \to \infty$$ Aug 11 '20 at 16:51

## 1 Answer

Let $$X$$ be the random variable that counts the number of trials until the red ball is taken out of the box. Note that $$X$$ is an unbounded random variable with realizations in $$[1, \infty)$$.

As you observed, following @lulu's advice, we have: $$\Pr(X = k) = \prod_{i=2}^k \left(1 - \frac1i\right) \cdot \frac{1}{k+1} = \frac{1}{k\cdot(k+1)}$$

where: $$\prod_{i=2}^k \left(1 - \frac1i\right) = \prod_{i=2}^k \left(\frac{i-1}{i}\right) = \frac12\cdot\frac23\cdot\frac34\cdot \dots \cdot \frac{k-1}{k} = \frac1k$$

Now, the expected value is: $$\mathbb{E}[X] = \sum_{k=1}^{\infty} k \cdot \Pr(X=k) = \sum_{k=1}^{\infty} \frac{k}{k\cdot(k+1)} = \sum_{k=1}^{\infty} \frac{1}{k+1}$$

The sum is the harmonic series $$- 1$$, which is divergent, so $$\mathbb{E}[X] \to \infty$$, and thus, $$\mathrm{Var}[X]$$ is also undefined.

Regarding your comment:

does that mean that the expected number of trials cannot be calculated in this case?

That is the final calculation, $$X$$ has infinite expectation.

It also makes sense intuitively, since if you don't pick up the red ball at some trial $$k$$, then you make it even harder (i.e. less probable, by adding a new blue ball) to do so at some later trial - you're increasing the probability of failure.