# Probability of nth draw being same value

Disclaimer at the beginning: this does relate to a homework problem, but is not the actual homework problem itself.

Consider a series of numbers, $$1, 2,...,n$$. We select one value at a time at random from this sequence (with replacement) until we select a value that has already been selected before. Let $$D_n$$ be the draw on which we select a value that has been selected before. $$D_n$$ clearly only takes on values from $$2$$ to $$n+1$$.

Now, the homework problem asks us to show that (but this is not what I'm asking about): $$\lim_{n \to \infty}P\{\frac{D_n}{\sqrt{n}}>x\}=e^{\frac{-x^2}{2}}$$

However, what I'm curious to know about is the probability $$P\{D_n=t\}$$. In my calculation, there are $$n^{n+1}$$ possible ways of making $$n+1$$ draws of n values. And, there are $$n(n-1)(n-2)...(n-t+1)\binom{n-1}{1}(n^{n-t+1})=\frac{n!(n-1)(n^{n-t+1})}{(n-t+1)!}$$ ways of having exactly two values in t draws be equal. So, then the $$P\{D_n=t\}$$:

$$P\{D_n=t\}=\frac{n!(n-1)(n^{n-t+1})}{(n-t+1)!}*\frac{1}{n^{n+1}}$$ $$=\frac{n!(n-1)(n^{-t})}{(n-t+1)!}$$

However, I know this must be wrong because as $$n \to \infty$$, this is (according to Mathematica), unbounded. Where am I going wrong?

The probability that the $$\ t^\mathrm{th}\$$ draw repeats any of the preceding $$\ t-1\$$ draws is $$\ \frac{t-1}{n}\$$, and the probability that it doesn't is $$\ \frac{n+1-t}{n}\$$. Thus, since the draws are independent, the probability that there are no repeats in the first $$\ t-1\$$ draws is $$\ \left(\frac{n-1}{n}\right)\left(\frac{n-2}{n}\right)\dots\left(\frac{n+2-t}{n}\right)=\frac{n!}{n^{t-1}\left(n+1-t\right)!}\$$, and therefore $$\ P\{D_n=t\}=\frac{n!}{n^{t-1}\left(n+1-t\right)!}\left( \frac{t-1}{n}\right)=\frac{n!\left(t-1\right) }{n^t\left(n+1-t\right)!}\ .$$
This pinpoints the source of the error in your calculation as the factor $$\ {n-1\choose 1}\$$ in your formula for the number of "ways of having exactly two values in $$\ t\$$ draws be equal". This needs to be the number of ways in which the first repeat occurs in the $$\ t^\mathrm{th}\$$ place, and that is $$n(n-1)(n-2)...(n-t+1)(t-1)n^{n-t+1}\ .$$
• Why do you have a factor of $n^{n - t + 1}$ in your final expression? If you are counting the number of ways in which the first repeat occurs in the $t^{\text{th}}$ place, then there are $n$ ways if $t = 2$. – N. F. Taussig May 21 at 9:18
• The factor of $n^{n-t+1}$ is the number of ways in which the remaining $n-t+1$ draws can occur after the first repeat occurs. I assumed the OP wanted to count the total number of $n+1$ drawings in which the first match occurs in the $t^{th}$ position (which is indeed what he needs to do if he wants the get the required probability by dividing by the total number of $n+1$ drawings). In the case $t=2$, the first two terms, $n(t-1)$, produce your $n$ ways of getting the match, and the remaining factor of $n^{n-1}$ is the number of ways the remaining $n-1$ drawings can occur. – lonza leggiera May 21 at 10:53
You made a mistake. The probability that a repeated item is drawn in $$t$$-th attempt is the product of probability that all $$t-1$$ previously drawn items are distinct: $$\frac nn\frac{n-1}n\cdots\frac{n-t+2}n=\frac{n!}{n^{t-1}(n-t+1)!}$$ and the probability that the $$t-th$$ drawn item coincides with a previous one: $$\frac{t-1}n.$$
Thus the correct result is: $$P\{D_n=t\}=\frac{n!(\color{red}t-1)}{n^t(n-t+1)!}.$$