8
$\begingroup$

If couples are seated randomly at a round table, what is the chance that no-one is seated opposite their partner?

If there are four people the answer is 2/3.

If there are six it is 8/15, I think.

After that, my step by step method, filling in all the possibilities and ending up with a sum of various expected values, becomes pretty laborious. Intriguingly, an intuitive approach gets the right answer for 6 people in the form of (4/5) x (2/3), but I'm struggling to generalise this. Is there a neat method, leading to a formula for the case of 2n people (n couples)?

$\endgroup$
6
$\begingroup$

Analysis

Let's guess and then systematically improve the guess until it's correct.

Begin by guessing the answer is $1$. Of course that's wrong. To see how wrong, label one partner in each pair "Red" and the other "Blue". From the perspective of any Red individual, there is a $1/(2n-1)$ chance that their (Blue) partner will sit across from them. Because there are $n$ red individuals, let's subtract $n\times 1/(2n-1)$ from that initial guess.

But wait--that's still not quite right, because all pairs of couples have been double-counted. If one couple is seated opposite, there remain $n-1$ couples, $2n-2$ places, and from any Red individual's point of view, the chance that they are part of a second couple is $1/(2n-3)$. Therefore we need to re-add $\binom{n}{2}\times 1/(2n-1)\times 1/(2n-3)$.

But now we have undercounted contributions to the result from triples of couples, which we need to correct. And so it goes, until finally we have accommodated all $n$ couples in the formula. (This, of course, is just the Principle of Inclusion-Exclusion in action.)

The resulting formula is

$$\sum_{i=0}^n (-1)^i \binom{n}{i} \frac{1}{(2n-1)(2n-3)\ldots (2n-2i+1)} = {_1}F_1\left(-n, -n+\frac{1}{2}, -\frac{1}{2}\right).\tag{1}$$

Computation

For positive integers $n$, the Kummer confluent hypergeometric function ${_1}F_1\left(-n, -n+\frac{1}{2}, z\right)$ is a polynomial of degree $n$ in $z$. From the Kummer Transformation

$${_1}F_1\left(-n, -n+\frac{1}{2}, -\frac{1}{2}\right) = e^{-1/2}\ {_1}F_1\left(\frac{1}{2}, -n+\frac{1}{2}, \frac{1}{2}\right)$$

it is straightforward to deduce that the limiting value of the probability as $n$ grows large is $e^{-1/2} \approx 0.6065306597\ldots$. The convergence is slow: you have to multiply $n$ by $10$ to attain an additional decimal digit. Nevertheless, accurate (double-precision) values can quickly be computed for any $n$ by noting that the terms in the left hand sum of $(1)$ grow more slowly than powers of $-1/2$. Thus, by the time $i$ reaches $52$, the new values will be essentially zero compared to $e^{-1/2}$ (and in fact a closer analysis suggests that stopping the summation by $i=45$ will work).

This formula will break down for $n$ greater than 10,000,000 in certain computing environments due to imprecision in the log Gamma function. The problem arises from cancellation in the differences arising when computing terms in the series. An excellent approximation to those differences when $n$ is sufficiently large can be found in terms of $\psi(n-1/4)$, where $\psi$ is the derivative of $\log \Gamma$ (the digamma function). That is implemented in the code below, at a slight cost in computation time.


Implementation

The following R code computes about 20,000 double-precision values per second.

f <- function(n) {
  h <- function(n) {
    ifelse(n < 1e6, lfactorial(n) - lfactorial(n-1/2), digamma(n+3/4)/2)
  }
  m <- min(n, 46)
  k <- 0:m
  x <- exp(h(n) - h(n-k) - lfactorial(k) - k*log(2)) * (-1)^k
  sum(x)
}

As an example, let's track how closely log(f(n)) comes to its limiting value of $-1/2$ for large $n$. As claimed above, each factor of $10$ in $n$ adds one decimal place of limiting accuracy. Let's therefore look at the $n^\text{th}$ decimal place in the logarithm of the ratio of $f(n)$ to $e^{-1/2}$, for whole powers of $10$ from $n=10^1$ through $n=10^{14}$:

> round(sapply(1:14, function(n) 10^n * (log(f(10^n)) + 1/2)), 3)

[1] -0.255 -0.251 -0.250 ... -0.250 -0.249 -0.249 -0.400

(Seven values have been omitted from the middle, all equal to -0.250.) The constant pattern is clear. At the end, with $n=10^{14}$, it starts to break down, indicating loss of precision. Improving on this would likely require high-precision arithmetic.

$\endgroup$
1
  • 1
    $\begingroup$ Now I know what PIE stands for! $\endgroup$ – Matthew Graves Aug 8 '16 at 18:12
3
$\begingroup$

Why would the intuitive method work?

Think of the table as a collection of pairs; that is, instead of the traditional North-West-East-South cross of a bridge table, we look at it like a table with two rows:

North-South

West-East

If we condition on North being the senior partner of one couple, then there's a 1/3rd chance that South will be the junior partner of that couple, which then forces West and East to be a couple, and a 2/3rd chance that South will be a member of the other couple, and then the the last set is also definitely not a couple.

When we extend from $n=2$ to $n=3$, we just add a row to the table:

Northwest-Southeast

North-South

West-East

If we set Northwest as always being the senior partner of the first couple, then there's clearly a $\frac{1}{5}$ chance that there's a paired couple and we can stop, and a $\frac{4}{5}$ chance that there isn't, and we can continue, with a smaller problem.

Note that the smaller problem is a different one, though, which is 'coincidentally' the same. Instead of having four people and two couples going into the problem, we must have one couple and two singles, and the chance that the couple is paired up is $\frac{1}{3}$ (for the same reasons as before).


This gives us a recursive approach; we can talk about a problem with two parameters, $(n,c)$, where $n$ refers to the number of people and $c$ refers to the number of couples. So $(8,4)$ gives us $\frac{6}{7}(6,2)$ (that is to say, four couples with 8 people gives us a $\frac{1}{7}$ chance of failure when assigning the first pair, and then the chance of failure for 2 couples and 6 people in the case where we survive), and then for $(6,2)$ we need to expand out four cases:

  1. Both of the next couple are single: $\frac{2*1}{6*5}(4,2)$

  2. One was single, the other was in a couple: $\frac{4*2*2}{6*5}(4,1)$

  3. Both were in different couples: $\frac{4*2}{6*5}(4,0)$ (Note that $(4,0)=1$, for obvious reasons.)

  4. Both were in the same couple: $\frac{4*1}{6*5}$ (This is a loss condition)

If you go through and do all the math, I think you end up with $\frac{20}{35}$ for the 8 person case, which is not $\frac{6}{7}\frac{8}{15}$. (It's higher because of the chance that we totally break up the couples early on.)


I'm not aware of an immediate trick that allows you to just use a combinatoric formula to get an answer in closed form, but it seems likely that there could be one. [edit: See whuber's answer for the solution.]

$\endgroup$
5
  • $\begingroup$ (+1) You can get an immediate formula using PIE. $\endgroup$ – whuber Aug 5 '16 at 19:03
  • $\begingroup$ Thanks Matthew. I was working along similar lines (thinking in terms of available diagonals at each stage), but also couldn't turn it into a combinatoric formula (though I see whuber says it can be done). $\endgroup$ – John Aug 5 '16 at 19:56
  • $\begingroup$ Matthew: if you're right about 20/35, this means that (6,2) is 2/3. My intuition was that it is always 2/3 after the first step. Following the logic of the dumb mathematician in the old joke: farmdale.com/emp-jokes.shtml I'm tempted to leap to the claim that the general answer is (2/3) x (2n-2)/(2n-1) for n couples.... but having said that, my own working for the 8 person case is giving me 8/9 for what you have labelled (6,2) rather than your answer of 2/3 $\endgroup$ – John Aug 6 '16 at 22:43
  • $\begingroup$ @John Oh, that's not the sequence I had in mind. It looks to me like 8,3 is above .7, though, so I think it's another 'coincidence' that 6,2 is 2/3. For 6,2, 8/9ths is too high a survival chance; assume the first person you pick is part of a pair. Then there's a 1/5th chance that you pick their partner and lose. (If they're part of a singleton, it should be obvious that all possible picks lead to 4,2 or 4,1, in which case the lose chance is 1/3.) $\endgroup$ – Matthew Graves Aug 7 '16 at 6:58
  • 1
    $\begingroup$ Ah yes, you're right about (6,2). I've been approaching it slightly differently, filling places one at a time rather than filling diagonals, but I hadn't accounted for the fact that in the transition from (6,2) to (5,1) to (4,1) some of the arrangements are failures (i.e. a couple sat opposite each other). Similarly with (4,1) to (3,0) to (2,0). I'd been too focused on the end points of the process, (2,0) as compared with (2,1). I'll keep at it. $\endgroup$ – John Aug 7 '16 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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