2
$\begingroup$

I a programmer not a mathematician so please excuse my ignorance and please dumb it down for me.

My research indicates that this is a variation of the Coupon Collector problem but I really don't know how to get the answer.

Assuming $n$ equally likely desired selections (Probability for each=$1/m$) how many selections with replacement must be made to have an $X$ probability of getting at least one of each of the $n$ desired objects?

$\endgroup$
  • 1
    $\begingroup$ Should probability for each be $\frac{1}{n}$ rather than $\frac{1}{m}$? $\endgroup$ – paw88789 Aug 26 '14 at 2:13
  • 2
    $\begingroup$ @paw88789: It may be (and probably is) that the $n$ "equally likely desired selections" are not exhaustive, so that while each has equal probability, say $1/m$, these need not total $1$ but rather something less (indeed, assuming mutually exclusive "selections", they add up to $n/m$ in any one sampling). $\endgroup$ – hardmath Aug 26 '14 at 2:28
  • $\begingroup$ @hardmath: Good point. Thanks. $\endgroup$ – paw88789 Aug 26 '14 at 2:32
1
$\begingroup$

We can formulate this as a ball-and-urns problem: we have $k$ distinct balls (number of extractions) that we can place with equal probability in $m$ urns, of which $n<m$ are marked as "desired". We want to compute the probability of event $E$: the $n$ desired urns are non-empty. Let $j=0 \cdots k$ be the total number of balls that fall in the desired urns.

Then

$$P(E \mid j) = \frac{j! \,S_{n,j}}{n^j}$$ where $S_{n,j}$ is the Stirling number of the second kind. Further, $P(j)={k \choose j} n ^j /m^k$. Then

$$P(E ) =\frac{1}{m^k}\sum_{j=0}^k {k \choose j} j! \,S_{n,j} = \frac{k!}{m^k} \sum_{j=0}^k \frac{1}{(k-j)!}S_{n,j} $$

Perhaps this can be simplified a little, I doubt it. From this you could get your desired $k$ numerically.

An approximation using Poissonization: $P(E) \approx (1 - e^{-k/m})^n$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ $j!S_{n,j}$ should be $n!S_{j,n}$, and $P(j)$ is missing a factor $(m-n)^{k-j}$. About the possibility of simplification, see my answer. $\endgroup$ – joriki May 21 '16 at 11:22
0
$\begingroup$

The probability of having all $n$ desired selections after $r$ "draws" can be computed by matrix multiplication. In fact we will do a little more than this and compute the chance of having $k$ out of $n$ of the desired selections for each "turn".

At the beginning, before any selection is made, the chance of having all $n$ is of course zero. More to the point, the chance of having none of the desired selections is $1$. We will set up a row vector $\vec{p}_r$ that expresses with entries the probability that after $r$ selections, we have $k=0,1,\ldots,n$ of the ones desired:

$$ \vec{p}_r = (p_r^{(0)}, p_r^{(1)}, \ldots, p_r^{(n)} ) $$

where $p_r^{(k)}$ is the chance after $r$ turns that we have $k$ of the desired selections.

In the language of Markov chains we say that having all $n$ desired selections is an absorbing state, because once you have all of them, further selections do not alter that circumstance. You still have at least one of each of the desired items.

The initial state is having none of the desired items with probability $1$:

$$ \vec{p}_0 = (1,0,\ldots,0) $$

We can update the distribution of probabilities by multiplying that row vector on the right by a state transition probability matrix of size $(n+1)\times (n+1)$. In this case the chance of going from having $k$ desired items to having $k+1$ desired items is $\frac{n-k}{m}$, and this probability is the same for each turn at selecting a new item. The only other transition possible is to stay at having exactly $k$ desired items, either because we draw one of the undesired items or because we draw one we already have. The matrix therefore has at most two nonzero entries in each row, with only one nonzero entry in the last row (the "absorbing" state).

The resulting expression after $r$ selections is this:

$$ \vec{p}_r = \vec{p}_0 \begin{pmatrix} 1- \frac{n}{m} & \frac{n}{m} & 0 & \dots & 0 \\ 0 & 1- \frac{n-1}{m} & \frac{n-1}{m} & \dots & 0 \\ \vdots & \; & \ddots & \ddots & \vdots \\ \vdots & \; & \; & 1- \frac{1}{m} & \frac{1}{m} \\ 0 & \dots & \dots & 0 & 1 \end{pmatrix}^r $$

For a problem of modest size $n,m$, you can simply multiply the successive powers of the state transition probability matrix times the initial state until we find $r$ for which the final component $p_r^{(n)}$ exceeds the $X$ prescribed in the Question. For larger sizes we may want to use some linear algebra tricks (binary exponentiation, diagonalization) to speed up the computation.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

This can be solved using inclusion-exclusion. We have $n$ conditions of the $n$ desirable selections being present. The probability for $l$ particular conditions to be violated is $\left(1-\frac lm\right)^k$, and these conditions can be chosen in $\binom nl$ ways. Thus by inclusion-exclusion the probability for none of the conditions to be violated is

$$ \sum_{l=0}^n(-1)^l\binom nl\left(1-\frac lm\right)^k\;. $$

This result can also be reached using leonbloy's approach by substituting the inclusion-exclusion representation of the Stirling numbers,

$$ S_{j,n}=\frac1{n!}\sum_{l=0}^n(-1)^{n-l}\binom nll^j\;, $$

and performing the sum over $j$. Since the probability is non-zero only for $k\gt n$ and Stirling numbers are more costly to compute, the sum up to $n$ will usually be more efficient in practice.

| cite | improve this answer | |
$\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.