7
$\begingroup$

Given a waiting room, filled with $N / 2$ couples ($N$ an even number: the total number of people present in the waiting room), a doctor calls $n$ individuals from the waiting room at random.

What is the probability of $K (0 \le K \le min(N/2,n/2))$ couples being among the group called? Inversely, what is the probability of $I (0 \le I \le min(N/2,n))$ individuals being among the group called?

What I've Tried So Far

My intuition was to first think of how many ways there are to pick K couples: $P_{N/2}^K$.

Then, how many ways are there to pick remaining individuals that will fill in the gaps among $n$, i.e. after the couples are picked: $[N - 2K]\cdot[N-2K-2]\cdot[\ldots]\cdot[N-2K-2(n-2K-1)]$.

I reformulated the above into a piece of notation I just learned about (the double factorial):

$\frac{(N-2K)!!}{[N-2K-2(n-2K)]!!}$

Rewritten:

$\frac{[2(\frac{N}{2}-K)]!!}{[2(\frac{N}{2}-K-(n-2K))]!!}$

Because the above numerator and denominator are even, the double factorial can be replaced with a form I have more information about:

$\frac{2^{\frac{N}{2}-K}(\frac{N}{2}-K)!}{2^{\frac{N}{2}-K-(n-2K)}[\frac{N}{2}-K-(n-2K)]!}$

Reformulated:

$\frac{2^{n-2K}(\frac{N}{2}-K)!}{[\frac{N}{2}-K-(n-2K)]!}$

Reformulated again:

$2^{n-2K}\left(P_{\frac{N}{2}-K}^{n-2K}\right)$

Then, almost there, I multiple the two probabilities (i.e. couples picked first, then individuals picked in order to fill the remaining slots), and divide it by the number of ways there are to re-organise the lineup:

$\frac{2^{n-2K} \left(P_{\frac{N}{2}-K}^{n-2K}\right)\left(P^K_{N/2}\right)}{n!}$

Reformulated:

$\frac{2^n\left(P_{\frac{N}{2}-K}^{n-2K}\right)\left(P^K_{N/2}\right)}{2^{2K} n!}$

The above, I believe, is the number of $n$-selections where K couples are included and the remaining $n-2K$ selections are individuals without their partner.

Assuming I haven't made a mistake, I would assume that dividing this sum by the total number of possible selections, ${N\choose{n}}$, would give the probability I'm interested in, i.e.

$p = \frac{2^n\left(P_{\frac{N}{2}-K}^{n-2K}\right)\left(P^K_{N/2}\right)}{2^{2K} n!{N\choose{n}}}$

Reformulated:

$p = \frac{2^n\left(P_{\frac{N}{2}-K}^{n-2K}\right)\left(P^K_{N/2}\right)}{2^{2K} \left(P_N^n\right)}$

However, There appears to be a mistake above…

I tested the above in Python:

>>> from math import perm
>>> def f(N,n,K):
...     n,d = 2**n*perm(N//2,K)*perm(N//2-K,n-2*K),2**(2*K)*perm(N,n)
...     return n, d, n/d
...
>>> for i in range(3):
...     print(i, f(10,5,i))
... 
0 (3840, 30240, 0.12698412698412698)
1 (3840, 120960, 0.031746031746031744)
2 (1920, 483840, 0.003968253968253968)

I must have made a mistake in my assumptions somewhere along the way, because the probabilities above appear off. E.g. the calculation states that the probability of selecting 2 couples, while choosing 5 from a group of 10, is lower than the probability of choosing 0 couples. This is clearly false.

Using simulation, the expected probabilities for 0, 1 and 2 couples in the set of 5 are as follows: {1: 0.634806, 2: 0.2380557, 0: 0.1271383}

N = sorted(list(range(5)) * 2)
for _ in range(10000000):
         shuffle(N)
         couples = 5-len(set(N[:5]))
         results[couples] = results.get(couples,0)+1
print({k:v/sum(results.values()) for k, v in results.items()})

Any insights would be greatly appreciated.

$\endgroup$
5
  • 4
    $\begingroup$ What have you tried Seán? $\endgroup$
    – Galen
    Dec 1, 2023 at 17:42
  • 1
    $\begingroup$ This looks like a homework problem, so it would be useful to know what you have tried. $\endgroup$
    – dherrera
    Dec 1, 2023 at 18:27
  • 3
    $\begingroup$ I've updated the question with what I've tried so far. $\endgroup$ Dec 1, 2023 at 20:17
  • $\begingroup$ "Inversely, what is the probability of 𝐼(0≤𝐼≤𝑚𝑖𝑛(𝑁/2,𝑛)) individuals being among the group called?" << By "individuals", do you mean "people whose spouses are not in the group"? $\endgroup$
    – Stef
    Dec 2, 2023 at 14:55
  • $\begingroup$ @Stef, yes, I do. $\endgroup$ Dec 2, 2023 at 15:17

2 Answers 2

9
$\begingroup$

There are three kinds of couples after the selection: those from whom one individual was picked, those where both were picked, and those where neither were picked.

When $k$ is the number of individuals selected and $X$ the (random) number of couples with one individual picked, there will be $X$ of the first kind of couple, $(k-X)/2$ of the second kind, and (writing $N=2n$) the remaining $n - k - (k-X)/2$ couples will be of the third kind.

The number of such combinations is the multinomial coefficient

$$\binom{n}{X;\ \frac{k-X}{2};\ n-X-\frac{k-X}{2}} = \frac{n!}{X!\left(\frac{k-X}{2}\right)!\left(n-X-\frac{k-X}{2}\right)!}.$$

That is because this part of the problem is no different than counting the number of ways in which three distinct kinds of objects can be selected.

However, when only one individual in a couple is selected, there are two ways to select them and such selections are independent from one couple to the next. Therefore the previous count must be multiplied by $2^X$ to find all the possible ways.

To find the probability, divide this count by all possible ways to select $k$ out of $2n$ individuals, equal to $\binom{2n}{k}.$

This R code does the calculation in a way that avoids floating point overflow as much as possible.

f <- function(x, k, n, probability = TRUE) {
  j <- (k - x)/2
  q <- lfactorial(n) - lfactorial(x) - lfactorial(j) - lfactorial(n - x - j) + 
       x * log(2) 
  if (isTRUE(probability)) q <- q - lchoose(2 * n, k)
  ifelse (j != floor(j) | j < 0, 0, exp(q))
}

Optionally this code returns the count of combinations -- but this will overflow even for values of $n$ in the hundreds.

Here is an illustrative plot of probabilities for a selection of 13,749 individuals out of 10,000 couples.

enter image description here

Although simulation is an attractive check, it's better to perform an exhaustive search when $n$ is small:

n <- 5 # Number of couples
k <- 5 # Number of people to select
#
# Create a population of couples
#
pop <- rep(seq_len(n), each = 2)
#
# Take all possible samples of size `X` and count the types of couples.
#
X <- apply(apply(apply(combn(2*n, k), 1, \(i) pop[i]), 
           1, tabulate, nbins = n) + 1, 
           2, tabulate, nbins = 3)
rownames(X) <- c("None", "Individuals", "Couples")
#
# Report on the first type of couple, for instance.
#
counts <- table(X["Individuals", ])
x <- seq(k%%2, n, by = 2)
p <- setNames(f(x, k, n, probability = TRUE), x)
rbind(Exhaustive = counts / sum(counts), Formula = p)

The output in this instance is

                   1         3         5
Exhaustive 0.2380952 0.6349206 0.1269841
Formula    0.2380952 0.6349206 0.1269841
$\endgroup$
5
  • $\begingroup$ Thanks, @whuber, I was also wondering if you had any information on the general case of this, e.g. in a waiting room of triples, probability of individuals, doubles and actual triples making it through the selection process. $\endgroup$ Dec 2, 2023 at 7:55
  • 1
    $\begingroup$ I believe this approach generalizes ;-). $\endgroup$
    – whuber
    Dec 3, 2023 at 0:11
  • $\begingroup$ With large enough group sizes, say 10, would this approach not become infeasible? We would need to try out all possible ways in which the subgroup sizes may represent beyond the waiting room? With couples, using a variable X works well, but with group sizes of 10, you would need 9 variables, and the ways in which these variables could be populated appears to explode (it's the number of ways to partition the sampling size $k$ if I'm not mistaken?) $\endgroup$ Dec 3, 2023 at 0:19
  • $\begingroup$ I don't think so. It's simple enough to count the number of ways of selecting $0\le j\le g$ objects out of each group. $\endgroup$
    – whuber
    Dec 3, 2023 at 0:21
  • $\begingroup$ Yes, but after you select those j objects for inclusion among the total k selected, the choices of how the remainder of the k gets populated will be much more complicated. It could be populed by subgroups of size 1, or 2 or lots of other sizes. I've set up another question to address this problem if you're interested :-) stats.stackexchange.com/questions/632863/… $\endgroup$ Dec 3, 2023 at 1:12
1
$\begingroup$

In this solution $N$ is the number of couples, and $N=2h$, where $h$ is the half-number. The number $k$ represents how many matching pairs we want, and $n$ is the number of people called.

It would be helpful to label you problem.

Every couple has a "position", and in each "position" there is a male/female. When labeled it looks as follows: $$ M_1, F_1, M_2, F_2, ..., M_h, F_h $$

For instance, $F_4$ represents couple in "position" 4, and it is the female in that couple.

You want to choose $n$ of them and have exactly $k$ matching pairs. We first pick the $k$ matching "positions", there is ${h\choose k}$ ways to do that. That leaves us with $h-k$ remaining "positions".

Up to this point we picked $2k$ people, and we need to pick $n$ in total. So we have $n - 2k$ more people to pick, but they cannot match.

From the remaining "positions" we pick $n - 2k$ "positions", but for each "positions" we can assign male/female. Thus, there are $2^{n-2k}$ gender assignments.

Thus, the total number of ways to do this is equal to, $$ 2^{n - 2k} {h\choose k} {{h - k}\choose {n - 2k}}$$

$\endgroup$
3
  • $\begingroup$ Hi, thanks for your reply! Question: is there a mistake there in your h-2k as the final exponent of 2? Should it not be n-2k? $\endgroup$ Dec 3, 2023 at 19:37
  • 1
    $\begingroup$ Yes, you are correct. It should be $n-2k$ in the exponent. By the way, this method will generalize to triples as you asked in your other question. Assuming your question is, "a family of size 3". Do you see how to do it? $\endgroup$ Dec 3, 2023 at 20:50
  • $\begingroup$ I've started to notice this, yes, currently looking at all the bells and whistles in order to generalise it :-) Thank you for your answer! $\endgroup$ Dec 3, 2023 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.