Expected number of draws with replacement until a repeat draw

Question

An urn contains $n$ balls numbered. We draw one ball, examine its number, and replace it in the urn. We repeat this until we draw any ball for the second time. Let $X$ the number of draws for this to happen (the two draws of the same ball do not have to be consecutive). Determine the distribution of X

For example, if we draw the ball $i$, and replace it in the urn, then $X$ is the number of repetitions needed to draw the same ball $i$ for the second time. I need determine a distribution for $X$, where $X$ takes on values $\{1,2,3\cdots,k\}$ (i.e., on the $k$th draw we select the same ball for the second time). Then $P(X\geq k)$ is the probability we do not draw the same ball in $\{1,2,\cdots,k-1\}$. But this means $n\choose k-1$ ways; I'm not sure this is true, any help? It's my first post here!

Answer 1

Both your quoted problem and your own text are difficult to understand. It sounds like you are drawing balls with replacement and asking the probability distribution of the number of draws until some ball is drawn for a second time. Clearly the chance of a duplicate on the first draw is zero. What is the chance the first two draws are the same? For the first duplicate to be on the third draw you need to have drawn two different balls on the first two draws, then match one of the two on the third draw. Then for the first match to be on the fourth draw, the first three must be different, then the fourth must match one of the three. Can you formalize this?

Answer 2

On the first draw the probability is zero, on the second it is $\frac{1}{n},$ on the third $\frac{2}{n}$ and so on until the $n+1$st ball where the probability is $1.$

However for a stage to be reached all previous stages must fail to repeat a ball, so the probability of stage k is:

$\frac{k-1}{n} \prod_{j=1}^{k-1} \left(1-\frac{j-1}{n}\right)$

I am sure this can be simplified.

Answer 3

We obviously draw the first time with probability $1$. We draw the second time with probability $\frac{n}{n} = 1$ also.

But we continue on to the third draw only if the second ball did not match the first ball, which it does with probability $\frac{1}{n}$. Thus we continue to the third draw with probability $\frac{n-1}{n}$.

We then continue on to the fourth draw only if the third ball did not match either of the first two balls, which it does with probability $\frac{2}{n}$. We therefore continue on to the fourth draw with probability $\frac{n-2}{n}$.

In general, we continue from the $k$th draw to the $k+1$th draw only if the $k$th ball did not match any of the first $k-1$ balls, which it does with probability $\frac{k-1}{n}$. We therefore continue with probability $\frac{n-k+1}{n}$.

The greatest number of draws we can have is $n+1$ (by the pigeonhole principle), after which we continue with probability $\frac{0}{n} = 0$. Our expectation for the total number of draws is therefore

\begin{align} EX & = 1+\frac{n}{n}\left(1+\frac{n-1}{n}\left(1+\frac{n-2}{n}\left(1+\cdots\left(1+\frac{1}{n}\right)\right)\right)\right) \\ & = 2+\frac{n-1}{n}+\frac{n-1}{n}\cdot\frac{n-2}{n}+\frac{n-1}{n}\cdot\frac{n-2}{n}\cdot\frac{n-3}{n}+\cdots+\frac{n-1}{n}\cdot\frac{n-2}{n}\cdot\cdots\cdot\frac{1}{n} \end{align}

which is the desired expression.

Answer 4

Inasmuch as $\frac{\binom nkk!}{n^k}$ is the probability of no repetition in the first $k$ draws (so that the $k+1^{\text{st}}$ draw takes place), the expected number of draws is

$$\sum_{k=0}^n\frac{\binom nkk!}{n^k}=\sum_{k=0}^n\frac{n!}{n^k(n-k)!}.$$