Given a set $M$ with $m$ elements in it, we sample repeatedly from $M$ with replacement and each element in $M$ is equally likely to be selected. Let $X_{T}$ denote the sequence containing $T$ samples, where $T$ is any positive integer.

We define a function $F$ which takes a sequence of elements and returns the number of unique elements in this sequence. e.g. $F((1,2,3,3,4)) = 4$ since we only count $3$ once.

What is the range of $T$ such that the following statement holds:

$F(X_{T}) = \alpha m$ is true with a probability higher than $p$, where $0 \lt \alpha, p \lt 1$. ($\alpha m$ is an integer)

  • $\begingroup$ $i$ seems to be irrelevant here $\endgroup$ – Henry Jul 5 '17 at 22:31

The probability $n$ unique elements are selected in $t$ draws with replacement from $m$ equally likely possibilities is $$\dfrac{S_2(t,n) \, m!}{ m^t\,(m-n)!}$$ where $S_2(t,n)$ is a Stirling number of the second kind sometimes written $\left\{{t\atop n}\right\} $

You seem to want this probability to be equal to $p$: that will only be possible for some specific values of $p$. You also want $n=\alpha m $ to be an integer

For example, with $m=4$ and $\alpha=\frac12$ you would get these values for $p$ and $t$

t   p 
0   0
1   0
2   0.75
3   0.5625
4   0.328125
5   0.17578125
6   0.0908203125
7   0.046142578125
  • $\begingroup$ Can you please describe how such a formula is derived? $\endgroup$ – s9527 Jul 6 '17 at 14:44
  • $\begingroup$ @ChengxinMa It is a counting calculation. The Stirling numbers of the second kind count the number of ways to partition a set of $t$ labelled objects into $n$ nonempty unlabelled subsets. Multiplication by $\frac{m!}{(m-n)!}$ uses $n$ from $m$ labels. Then to turn this into a probability, divide by $m^t$, the total number of possible sample results ignoring the constraints. $\endgroup$ – Henry Jul 6 '17 at 15:00

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.