# $m$ people choosing $l$ elements out of $n$ independently, what is the probability of each element being chosen at least $k$ times?

We have $$m$$ people and a set of $$n$$ elements. Each person chooses $$l$$ elements out of $$n$$, independently from each other. What is the probability that each element is chosen at least $$k$$ times?

Let $$X_1, \dots X_n$$ be the random variables counting how many times each element is chosen. I want to determine the density $$\mathbb{P}(X_1=k_1, \dots X_n=k_n)$$, then I can sum over all values greater than $$k$$ to determine the probability.

I am having a hard time trying to compute the combinations. The denominator of the probability is easy, because it's all possible combinations of $$l$$ elements out of $$n$$, repeated $$m$$ times, due to independence: $$\binom{n}{l}^m$$

But how can I determine only those combinations, such that the elements are chosen exactly $$k_1, \dots k_n$$ times? I don't know if a simple formula exists for this.

Example: Let's say we have $$m=10$$ people voting for $$n=5$$ parties. Each person is expressing $$l=2$$ votes (more precisely, they randomly choose $$2$$ different parties). What is the probability that each party gets at least $$k=1$$ vote?

Addendum: I am not sure if it helps, but I also thought of formalizing this problem in a different way. Basically it's a random $$m \times n$$ binary matrix, with each row summing to $$l$$ and each column summing to a number $$\geq k$$. I need to count all the possible matrices.

• The example should be doable using brute force (case-by-case), and using a few tricks here and there to cut down on computation, although even then it's still very long and tedious. I don't see another way. Commented Feb 12 at 11:26

ۤFor $$\color{blue}{l=1}$$, the problem is equivalent to count the ways that $$m$$ distinct things can be distributed in $$n$$ distinct urns such that each urn has at least $$k$$ elements. It is given by

$$n!S_k(m,n)$$

where $$S_k$$ denotes the $$k$$-associated Stirling number of the second kind; for $$k=1$$ it is the Stirling number of the second kind (see Variants section in the link).

The probability is then given by

$$\frac{n!S_k(m,n)}{(m)^n}$$

The same idea can be used to find an upper bound for the number as follows:

$$n!S_k(m \times l,n)$$

in which each of the $$n$$ items can be selected multiple times (each person can give more than one vote to each party). Hence, the probability is less than

$$\frac{n!S_k(m \times l,n)}{\binom{n}{l}^m}.$$

The above results show that the problem for arbitrary $$\color{blue}{l \ge 1}$$ should be very difficult. I checked different recurrences, but could not find low-dimensional recurrences. Finally I reached to the following one, which seems to be more reasonable when $$n$$ is not a large number (other similar ones can be developed, but they seem to be less useful).

Let $$A_{m,l}(k_1,...,k_n)$$ denote the number of ways that $$m$$ persons can select $$l$$ items from $$n$$ distinct items such that each item $$i$$ is selected at least $$k_i$$ times by different persons. Then, we have the recurrence

$$A_{\color{blue}{m},l}(k_1,...,k_n)=\sum_{i_1+ \cdots +i_n=l}A_{\color{blue}{m-1},l}([k_1-i_1]^+,...,[k_n-i_n]^+)$$

where $$[x]^+=\max(x,0)$$, and

$$A_{m,l}(0,...,0)=\binom{n}{l}^m.$$ The recurrence is obtained by assuming that person 1 first selects his/her $$l$$ items, and the other persons select their items next.

The solution to the OP is $$A_{m,l}(k,...,k)$$, which can be obtained from the above recurrence.

To see how much the solution can be complex, the explicit formulas for two simple cases $$k_2=0,k_3=0,\cdots, k_n=0$$ and $$k_3=0,k_4=0,\cdots, k_n=0$$ are given below:

$$A_{m,l}(k_1,0,...,0)=\sum_{i=k_1}^{n} \binom{n}{i} \binom{n}{l-1}^i\binom{n}{l}^{n-i}, n\ge \, k_1$$ $$A_{m,l}(k_1,k_2,0,...,0)=\\ \sum_{i=k_1}^{n}\sum_{j=k_2}^{n} \sum_{j_1} \binom{n}{i}\binom{i}{j_1}\binom{n-i}{j-j_1} \binom{n}{l-2}^{j_1}\binom{n}{l-1}^{i-j_1+j-j_1}\binom{n}{l}^{n-(i+j-j_1)}, \, n\ge k_1+k_2.$$