- #1
derpetermann
- 1
- 0
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!
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!