Intuitive/Visual solution for: There are $k$ balls in a bowl. How many draws does it on average take, to get one specific ball?

Question

I have the following problem:

There are $k$ balls in a bowl. So $k$ different possibilities of the same probability $\frac{1}{k}$ to be drawn from the bowl. Any drawn ball is immediately replaced into the bowl again. How many draws does it on average take, to get one specific ball?

With $k=2$ it would be like a coin toss. With $k=6$ like rolling a dice.

So, you see, it's not really an advanced problem. However, I'm looking for the most intuitive/visual solution.

Answer 1

A most intuitive is perhaps referring to the law of large numbers.

Denote by $X$ the geometric variable in question, i.e. the number of draws before we draw the specific ball B. Now let us draw the balls indefinitely and count how may times we take B. The number $N_n$ of draws before we take it $n$ times is the sum of independent copies of $X$. Therefore, by the law of large numbers, $$ \frac{N_n}{n}\to \mathbb{E}[X], n\to\infty. $$ On the other hand, $\frac{n}{N_n}$ is the ratio of draws of B to the total draws. Again, by the law of large numbers, $$ \frac{n}{N_n}\to \frac1k, n\to\infty. $$ Hence we get $\mathbb{E}[X] = k$.

Answer 2

You are looking for the expected number of draws, if assuming you only draw repeatedly until you get the right ball.

This is given by: $$ E[\#\text{draws}]=\sum_{i=0}^\infty i P(i) $$

With $P(i)$ the probability of taking $i$ draws. Computing for some cases:

$$ P(1) = 1/k $$ $$ P(2) = ((k-1)/k)(1/k) $$

$$ P(3) = ((k-1)/k)^2(1/k) $$ ...

$$ P(i) = ((k-1)/k)^{(i-1)}(1/k) $$

Thus:

$$ E[\#\text{draws}]=\sum_{i=1}^\infty i ((k-1)/k)^{(i-1)}(1/k)=(1/k)\sum_{i=1}^\infty i ((k-1)/k)^{(i-1)} $$

Which is an Arithmetic-Geometric sum. The partial sum of such sequence is given by:

$$ S_n =\frac{a-[a+(n-1)d]r^n}{1-r}+\frac{dr(1-r^{n-1})}{(1-r)^2} $$

Then for a ratio $r$ such that $|r|<1$, the series converges to:

$$ S =\frac{a}{1-r}+\frac{dr}{(1-r)^2} $$

In the current case:

• $r= (k-1)/k$ so $(1-r)=1/k$

• $a=1$

• $d=1$

So the arithmetic geometric sum is given by: $$ S =\frac{1}{(1/k)}+\frac{(k-1)/(k)}{(1/k)^2}=k+k(k-1)=k^2 $$

Going back to our previous summation: $$ E[\#\text{draws}]=(1/k)\sum_{i=1}^\infty i ((k-1)/k)^{(i-1)}=(1/k)\left(k^2 \right)=k $$

Answer 3

Let $E$ denote the result.

Consider the first trial. You win with probability $\frac 1k$. With probability $\frac {k-1}k$ you start over. It follows that $$E=\frac 1k\times 1 +\frac {k-1}k\times \left(E+1\right)\implies E=k$$