0
$\begingroup$

Consider the set $N=\{1,\ldots, n\}$. Let $p_n(m,k)$ denote the probability that we have $m$ unique elements from $N$ after $x$ draws (with replacement). As per this post, we explicitly have $$p_n(m,x)=\frac{S_2(x,m) \; n!}{n^x \; (n-m)!},$$ where $S_2(x,m)$ is a Stirling number of the second kind. I have been asked to express $p_n(m,x)$ recursively in terms of $p_n(m,x-1)$ and $p_n(m-1,x-1)$. I have tried playing around with the equation above but I have not gotten any results. Maybe I need to simply condition on something? If that is the case, then I am not seeing it. Thanks in advance for the help.

$\endgroup$
0
$\begingroup$

Suppose after $x$ draws we have $m$ unique elements.

This implies that after the first $x-1$ draws, we either had $m-1$ unique elements or $m$ unique elements. Can you use these two cases (combined with the appropriate deduction of what the $x$th draw must be in each case) to get an expression for $p(m,x)$?

$\endgroup$
  • $\begingroup$ I see. After $x-1$ draws if we have $m-1$ unique elements then the chance of drawing a new element is $(n-m+1)/n$. On the other hand, if we already had $m$ unique elements then with $m/n$ probability we still have $m$ elements after a new draw. So $p_n(m,x)=(n-m+1)p_n(m-1,x-1)/n + mp_n(m,x-1)/n$. $\endgroup$ – strawberryBeef Dec 1 '16 at 4:13

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.