Probability of nth draw being same value

Question

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?

Answer 1

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}\ . $$

Answer 2

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)!}.$$