4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – N. F. Taussig May 21 at 9:18
  • 2
    $\begingroup$ 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. $\endgroup$ – lonza leggiera May 21 at 10:53
  • $\begingroup$ Thanks for the clarification. $\endgroup$ – N. F. Taussig May 21 at 15:23
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.