3
$\begingroup$

Imagine I have a bag of n labeled marbles. I would like to pick a single random marble out of the bag x number of times. Every time I pick a marble, I place it back in the bag.

How do I calculate the probability that I will only pick p distinct marbles?

In my case, I have 90 labeled marbles, 550 selections and I want to know what the probability is that I will only select 60 distinct marbles.

$\endgroup$
  • $\begingroup$ I want to inform you that the answer you accepted earlier had a mistake in its reasoning, which I explain in my latest edit. I updated my answer with what I now believe is correct. At the end, I give a brief explanation for why my previous, accepted answer, was wrong. $\endgroup$ – Bridgeburners Jan 31 '18 at 4:12
3
$\begingroup$

We can start by asking the following combinatorics question:

Given a set of $m$ categories and $l$ items, such that each item and each category is unique, how many possible ways can we distribute the $l$ items among the $m$ categories?

For example, suppose we went fishing and I told you I caught 5 fish. In the lake there are three types of fish: tuna, salmon, and carp. How many ways are there to distribute the 5 catches among the 3 fish types, where the order of the catches matter?

If both item and category are unique, then the label of the catch number matters. So, for example, it's not enough to say "we caught 3 tuna and 2 carp", because we want to distinguishing between the scenario "TTTCC" and "TCTCT". (In both cases there were 3 tuna and 2 carp, but the order was different.)

Another way of asking this question is as follows:

How many functions are there from the set $\{1, 2, \dots, l\}$ to $\{1, 2, \dots, m \}$?

The answer is $m^l.$

Now we can ask the following, more restricted combinatorics question:

Given a set of $m$ categories and $l$ items, such that each item and each category is unique, how many possible ways can we distribute the $l$ items among the $m$ categories such that each category is represented at least once? (i.e. none of the categories have been selected zero times).

An equivalent form of this question is,

How many functions are there from $\{1, \dots, l \}$ to $\{1, \dots, m \}$ that is a surjection?

A "surjection" is a mapping from set $S_1$ to $S_2$ such that each element in $S_2$ has been mapped to at least once.

Without going into too much detail about how to solve this, this can be done using the inclusion-exclusion principle, which states that the size of the union of a finite number of sets is equal to the sum of the size of each set, minus the sum of the sizes of each intersection of pairs of sets, plus the sum of the sizes of each intersection of set triplets, etc. A good intuitive explanation of why this is can be found here.

In general, the number of surjections from $\{1, \dots, l \}$ to $\{1, \dots, m \}$ is given by $m! {l \brace m},$ where $l \brace m$ is a Stirling Number of the Second Kind, defined as, $$ {l \brace m} = \frac{1}{m!} \sum_{j=0}^m (-1)^{m-j} {m \choose j} j^l. $$ This is an example of a set of combinatorics problems called the "twelvefold way", specifically this one.

Now to bring this to the above problem. Because each marble can be selected any number of times, we can treat each marble as a category, and each selection as an item. For $n$ marbles, of which we only select a specific set of size $p$ out of $k$ draws, but for which we select all of those $p$ marbles, the number of possible selections is $p! {k \brace p}.$

Now, there can be $n \choose p$ possible groups of $p$ marbles out of $n$. Because the above result is for a specific choice of $p$ marbles out of $n,$ the total number of ways to select exactly a set of $p$ marbles out of $n$ given $k$ selections is, $$ N_p = {n \choose p} p! {k \brace p}. $$

The total number of ways of distributing the $k$ selections out of $n$ marbles with replacement, with no regard to how many unique marbles were selected, is $$ n^k. $$

The probability of selecting exactly $p$ out of $n$ marbles given $k$ selections is just $N_p/N.$ That is,

$$ P_p = \frac{ {n \choose p} p! {k \brace p} }{ {n^k} } = \frac{n! {k \brace p}} {(n-p)! n^k}. $$

Keep in mind that this is not a closed-form solution, because the Stirling number of the second kind is not an analytic function, but rather, the result of a sum. Therefore each computation of this probability must be done numerically, by evaluating the Stirling number.

Using the numbers in your example is tricky, because the numbers are large enough that operations like exponents and factorials can't be stored in most systems. We could try and apply approximation methods to get accurate results. But we could also be lazy and use the "gmp" library in R, which uses the class "bigz" to store huge integers, and "bigq" to store rational fractions of huge integers, then convert back to numeric after the calculations. As well as its built-in functions "chooseZ", "factorialZ", and "Stirling2" that automatically does these operations on bigZ objects. Here is a code snippet:

library('gmp')
P <- function(p, n, k) chooseZ(n,p) * factorialZ(p) * Stirling2(k,p) / ( as.bigz(n) ^ as.bigz(k) )

n <- 90
k <- 550

Pp <- lapply(1:n, function(p) P(p,n,k))
Pvec <- sapply(Pp, asNumeric)

Pvec[60]
#[1] 9.449035e-74
#As a sanity check, see if Pvec is a valid probability distribution
sum(Pvec)
#[1] 1

The probability of only selecting 60 unique marbles from 550 selections, when there are 90 total marbles, is roughly a negligible $10^{-73}.$


NOTE This is an update to a previous solution that I submitted, which was incorrect but accepted nonetheless. This edit was made on January 30, 2018, so if you want to see the old (incorrect) accepted submission you can look at an edit from before then.

To summarize, the old solution was, $$ P_p = \frac{ {n \choose p} {k-1 \choose k-p} } {n+k-1 \choose k}. $$ I used the "stars-and-bars" combinatorics problem that answers the question of surjective functions from $\{1, \dots, l \}$ to $\{1, \dots, m \}$ up to a permutation of the first set, given by this twelvefold way. Essentially, it's asking how many enumerations of marble choices there are, where order of the choice doesn't matter. Even though the above is a valid probability distribution (which you can verify), it is still wrong.

The reason it is wrong is because it doesn't identify each choice. For example, suppose we only choose marbles A and B out of 5 selections. Consider the two scenarios:

1) Marble A gets chosen 4 times and marble B gets chosen 1 time

2) Marble A gets chosen 3 times and marble B gets chosen 2 times

There are 5 different possibilities for the first scenario, and 10 possibilities for the second scenario. Yet the above solution treats those scenarios equally, because it doesn't consider the order in which the choices are taken.

$\endgroup$
  • $\begingroup$ Thanks for that incredible explanation. Now, if I plug all my numbers in, I get P(60) = 2.98525×10^17 for k = 550, n = 90. That number makes no sense to me. How can I have a probability of 2.98525×10^17? Here is the wolfram alpha link $\endgroup$ – terrigenus Dec 20 '17 at 13:53
  • $\begingroup$ You accidentally did $k-1 \choose k-n$. Here's the corrected link. wolframalpha.com/input/… $\endgroup$ – Bridgeburners Dec 20 '17 at 14:03

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.