Htykuut

For a somwehat simple version of the problem, imagine a group of ten people ($n=10$), for which we observe two binary attributes ($d= 2$). One of the attributes tells us if any given person wears glasses ($d_1$) the other if any given person wears a hat ($d_2$). We know that in total $5$ people wear hats and $6$ people wear glasses, but we don't know who wears what (random binary array). What is the probability of finding a subset of size $4$ ($k= 4$) such that at least three people in the subset wear a hat ($s_1 = 3$) AND at least four people wear glasses ($s_2 = 4$)? It's somewhat clear that there are realisations where wearing a hat and wearing glasses are mutually exclusive, such that those who have a hat don't have glasses, and realisations where having glasses and having a hat go together. Thus, for any realisation of the random binary array there might or might not be a subset of size $k$ with the above properties. I can't figure, though, how to calculate the probabilities.

The more general definition of the problem is this:

What is the probability of finding a $k$-subset in a $d$-dimensional random binary array of length $n$, such that this subset has at least $s_1$ ones in dimension $1$, $s_2$ ones in dimension  $2$, ..., $s_d$ ones in dimension $d$. The total number of ones per dimension ($ts_1$ to $ts_d$) are fixed.

Is there a name to this problem?  I tried to google, but I really did not know what to look for, since the problem definition is quite unwieldy to begin with.

Is the problem tractable analytically?  If yes does the solution scale to larger $d$, $k$ and $n$ when solved algorithmically?

Your help is highly appreciated! Thanks a lot in advance!

$newcommand{prob}[1]{text{Pr}mathopen{}left[#1right]}$
$newcommand{ksubsets}{binom{[N]}{k}}$

I am a colleague of @derpetermann and wanted to share a attempt to solving this, in the hope that it clarifies things and from there on it may be easier for others to solve it. So this is the way I approached the problem...

Among a population of $N$ individuals, every individual $n in [N]$ (I use the short notation [N] for ${1,2,..,N}$) is described by absence or presence of $D$ features:

$$ X_{n,d} :=
begin{cases}
1 & text{Feature $d$ present in individual $n$} \
0 & text{o/w}
end{cases}
$$

We know the total number of occurrences of each feature, given by

$$C_d := sum_{n in [N]} X_{n,d}$$

Otherwise, for a fixed $d$, the $X_{n,d}$ are equally distributed. Now we want to know: What is the probability of finding a subset $S$ of $k$ individuals, such that every feature $d$ is present in at least $c_d$ individuals in $S$ (for given $c_d in [k]$). I.e. how can we compute (or) estimate the following probability?

$$prob{bigcup_{S in binom{[N]}{k}} bigcap_{d in [D]} Big( sum_{n in S} X_{n,d} geq c_d Big) }$$

Note: While the $X_{cdot,d}$ for different features are independent, the union is not over independent (nor disjoint) events. And that is where we got stuck. We can rewrite the inner part (the probability that a fixed $k$-subset $S$ satisfies our condition):

$$Y_S := bigcap_{d in [D]} Big( sum_{n in S} X_{n,d} geq c_d Big)$$
$$prob{Y_S} = prod_{d in [D]} frac{sum_{c=c_d}^{min(k, C_d)} binom{k}{c} binom{N-k}{C_d - c}}{binom{N}{C_d}}$$

but have no idea of how to compute the union $prob{bigcup_{S in binom{[N]}{k}} Y_S}$. Even a useful bound upper bound on this probability would be highly appreciated.