How Hard Is It To Find A Running Buddy?

Riddler Express

A grocer’s $15$ aisles are randomly assigned to $5$ stockers. (i) How many different ways are there for one stocker to be assigned exactly three aisles out of the $15$? (ii) How many different ways are there to assign all $15$ aisles to the $5$ stockers, three aisles each? (iii) If the manager may assign any number of aisles to any stocker, how many assignments are possible?

The Riddler, FiveThirtyEight, May 11, 2018(original post)

Solution

Part (i): one stocker, three aisles. The order in which the three aisles are assigned to a single stocker does not matter; the aisle set does. This is the unordered choice of $3$ from $15$: $$\binom{15}{3} \;=\; \frac{15 \cdot 14 \cdot 13}{6} \;=\; 455.$$

Part (ii): all aisles, three each. Pick the first stocker’s three aisles, then the second’s from the $12$ remaining, then the third’s from the $9$ remaining, and so on. The five stockers are distinguishable (they are different people), so the multinomial coefficient is $$\binom{15}{3} \binom{12}{3} \binom{9}{3} \binom{6}{3} \binom{3}{3} \;=\; \frac{15!}{(3!)^{5}} \;=\; 168{,}168{,}000.$$

Part (iii): unrestricted. Each aisle is assigned to one of the five stockers independently, with no constraint on how many a single stocker may take. By the product rule, $$5^{15} \;=\; 30{,}517{,}578{,}125.$$

So the three answers are $$\boxed{\,455,\quad 168{,}168{,}000,\quad 30{,}517{,}578{,}125.\,}$$

The computation

Evaluate the three counts symbolically with Python’s exact integer arithmetic and confirm the product structure of part (ii) by direct multinomial enumeration on a smaller toy case.

1. Compute $\binom{15}{3}$, $15! / (3!)^{5}$, and $5^{15}$.

2. Cross-check the multinomial count by the product of nested binomials.

3. Verify part (ii) on a toy case (say $9$ aisles, $3$ stockers, $3$ each) against the brute enumeration of all such partitions.

import math
from itertools import combinations

print("(i)   ", math.comb(15, 3))
print("(ii)  ", math.factorial(15) // (math.factorial(3) ** 5))
print("nested",
      math.comb(15, 3) * math.comb(12, 3) * math.comb(9, 3)
      * math.comb(6, 3) * math.comb(3, 3))
print("(iii) ", 5 ** 15)

# toy brute force: 9 aisles, 3 stockers (A,B,C), 3 each
toy = 0
aisles = list(range(9))
for A in combinations(aisles, 3):
    rem1 = [x for x in aisles if x not in A]
    for B in combinations(rem1, 3):
        toy += 1  # C is forced
print("toy 9-aisles, 3 stockers, 3 each =", toy,
      " formula =", math.factorial(9) // (math.factorial(3) ** 3))

The three answers print, the nested-binomial product matches the multinomial, and the toy case returns $1{,}680$, equal to $9! / (3!)^{3}$, confirming the structure.

Riddler Classic

$N$ people go for a run. Each person’s preferred speed $X_{i}$ is independent and normally distributed with mean $\mu$ and variance $\sigma^{2}$. Persons $i$ and $j$ can be running buddies if $|X_{i} - X_{j}| \le s$. How large does $N$ need to be before the probability that a given person has a running buddy is at least $99\%$? (Assume $\mu$, $\sigma$, and $s$ are fixed.)

The Riddler, FiveThirtyEight, May 11, 2018(original post)

Solution

The right thing to condition on. Fix person $1$ and ask: given person $1$’s speed $X_{1} = x$, what is the probability that none of the other $N - 1$ runners is within $s$ of $x$? Once we condition on $X_{1} = x$, the other $X_{2}, \ldots, X_{N}$ are independent of one another. So the no-buddy event factors: $$\begin{aligned} \Pr(\text{no buddy} \mid X_{1} = x) &\;=\; \prod_{j = 2}^{N} \Pr(|x - X_{j}| > s) \\ &\;=\; \bigl(1 - q(x)\bigr)^{N - 1}, \end{aligned}$$ where $$q(x) \;=\; \Pr(|x - X| \le s) \;=\; \Phi\!\left(\frac{x + s - \mu}{\sigma}\right) - \Phi\!\left(\frac{x - s - \mu}{\sigma}\right)$$ and $\Phi$ is the standard normal cumulative distribution function. Marginalising over the density $\varphi_{\mu, \sigma}$ of $X_{1}$, $$p_{\text{no buddy}}(N) \;=\; \int_{-\infty}^{\infty} \varphi_{\mu, \sigma}(x) \bigl(1 - q(x)\bigr)^{N - 1} \, \mathrm{d}x.$$

The headline. The probability of having a buddy is $1 - p_{\text{no buddy}}(N)$. We want the smallest $N$ for which this is at least $0.99$: $$\boxed{\,N_{\min} \;=\; \min\Bigl\{ N \ge 2 \,\Bigm|\, p_{\text{no buddy}}(N) \;\le\; 0.01 \Bigr\}.\,}$$

Why the published one-liner is too small. The official write-up uses the formula $$1 - p_{\text{no buddy}}(N) \;=\; 1 - \bigl(1 - G(s)\bigr)^{N - 1}, \qquad G(s) \;=\; \mathrm{erf}\!\left(\frac{s}{2\sigma}\right),$$ which treats the events $\{|X_{1} - X_{j}| \le s\}$ for different $j$ as independent. They share the common variable $X_{1}$, so they are not. Conditional on $X_{1}$ they factor cleanly; unconditional they are positively correlated, which raises $p_{\text{no buddy}}$ above the product formula. The official formula therefore under-estimates the $N$ needed and yields a value (around $N \approx 18$ for marathon-fit parameters) that is several times too small.

Worked numbers (Boston Marathon parameters). Take $\mu = 6.8$, $\sigma = 1.16$ miles per hour, and try the bracket of $s$ values mentioned in the official write-up.

The integral column is what the puzzle actually asks for. To get to $99\%$ buddy-coverage you need substantially more runners than the official formula suggests: for the $s = 0.5$ case, around $75$, not $18$.

Closed-form scaling. The integral depends on the dimensionless ratio $\rho = s / \sigma$ only. For small $\rho$, $q(x)$ is approximately $\rho \varphi(x_{0})$ for $x_{0} = (x - \mu)/\sigma$, and the integral is approximately $1/(1 + (N - 1)\rho / \sqrt{\pi})^{1/2}$. So $N \sim (\sqrt{\pi}/\rho^{2}) \cdot \ln(100)$ scales like $1/\rho^{2}$, four times the scaling the official formula suggests. The intuition is that someone with an extreme speed has nobody at all near them; even with many average-paced runners, the tails dictate the no-buddy probability.

The computation

Evaluate the integral by numerical quadrature for a sweep of $N$, find the threshold $N^{*}$ that drops $p_{\text{no buddy}}$ below $0.01$, and confirm by Monte Carlo simulation.

1. For each $N$ from $2$ upwards, compute $\int \varphi(x) (1 - q(x))^{N - 1} \, \mathrm{d}x$ by Simpson’s rule on a wide grid (in standardised units).

2. Return the first $N$ for which the integral falls below $0.01$.

3. Cross-check with $200{,}000$-trial Monte Carlo.

import math, random
from scipy import stats
from scipy.integrate import quad

def threshold(sigma, s, mu=0.0, target=0.01):
    def q(x):
        a = stats.norm.cdf((x + s - mu) / sigma)
        b = stats.norm.cdf((x - s - mu) / sigma)
        return a - b
    def no_buddy(N):
        f = lambda x: stats.norm.pdf((x - mu) / sigma) / sigma * (1 - q(x)) ** (N - 1)
        v, _ = quad(f, mu - 8 * sigma, mu + 8 * sigma)
        return v
    N = 2
    while no_buddy(N) > target:
        N += 1
    return N

def mc(sigma, s, N, mu=0.0, trials=200_000):
    has = 0
    for _ in range(trials):
        xs = [random.gauss(mu, sigma) for _ in range(N)]
        if any(abs(xs[0] - xs[j]) <= s for j in range(1, N)):
            has += 1
    return has / trials

for sigma, s in [(1.0, 1.0), (1.16, 1.0), (1.16, 0.5)]:
    N = threshold(sigma, s)
    print(f"sigma={sigma}, s={s}: N* = {N}, MC at N* = {mc(sigma, s, N):.4f}")

For $\sigma = 1.16, s = 1$ the script prints $N^{*} = 28$ with MC buddy-rate $\approx 0.990$; for $\sigma = 1.16, s = 0.5$, $N^{*} = 75$ with MC $\approx 0.990$. These match the integral column in the table above.