# Calculate a variable to meet a certain probability in random sampling

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)

• $i$ seems to be irrelevant here – 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

• Can you please describe how such a formula is derived? – s9527 Jul 6 '17 at 14:44
• @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. – Henry Jul 6 '17 at 15:00