Dear Uncle Colin,

How big a group of people do you need so that the probability of two of them being married is more than 50%?

- Counting Out Unmarried People Leveraging Exponential Sums

Hi, COUPLES, and thanks for your message!

Im going to model this as a graph theory problem, rather than a sociopolitical one about who’s allowed to marry whom. ((For the record, I think any consenting adults who want to be married should be allowed to be married.))

Our graph consists of the whole population under consideration. Let’s say there are $N$ people, each corresponding to a node, and $c$ marriages, each corresponding to an edge.

If we pick $n < N$ people at random from the graph, that subgraph contains $\frac{1}{2}n(n-1)$ edges. What’s the probability that none of them coincide with the $c$ married edges in the population graph?

Each edge of the subgraph has a $\left(1-\frac{1}{c}\right)$ probability of not being a marriage. Taking the subgraph as a whole, and assuming independence (which seems reasonable enough), that means $P(\text{no marriages})\approx \left(1-\frac{1}{c} \right)^{n(n-1)/2}$.

We want $P(\text{no marriages})<0.5$, so let’s take logs: $\ln\left(0.5\right) > \frac{1}{2}n(n-1) \ln\left(1-\frac{1}{c}\right)$, and we want to solve this for $n$.

Let’s assume $c$ is large, so $\ln\left(1 -\frac{1}{c}\right) \approx -\frac{1}{c}$.

This gives $\ln(0.5) > -\frac{n(n-1)}{2c}$, or $n(n-1) > 2c \ln(2)$.

We’ve assumed $c$ is large, so we can approximate $n(n-1)$ as $n^2$ (we could solve the quadratic if the Mathematical Ninja held a sword to our throat, of course) - but a decent approximation would be $n > \sqrt{2c\ln2}$, or $\sqrt{1.4c}$.

In the UK, there are approximately 16 million married couples, so about 4,500 to 5,000 people randomly picked from the population would likely contain a married couple.

Hope that helps!

- Uncle Colin