4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Commented Feb 12 at 11:26

1 Answer 1

4
$\begingroup$

ۤ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.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .