Can You Ace the Technical Interview?

Start with a segment of length $1$. Split it at a uniformly random point into two pieces and record the product of the two lengths. Then split each piece the same way, recording each product, and continue forever, splitting every piece that appears. On average, what does the running sum of all these products approach?

The Fiddler, Zach Wissner-Gross, May 31, 2024(original post)

Solution

Let $f(L)$ be the expected sum of all products generated from a segment of length $L$. Splitting $L$ at a uniform point contributes one product $x(L-x)$ and then leaves two independent sub-problems, so $$f(L)=\mathbb{E}\bigl[x(L-x)\bigr]+\mathbb{E}\bigl[f(x)\bigr]+\mathbb{E}\bigl[f(L-x)\bigr].$$ Everything scales as area, so write $f(L)=cL^2$. The first term is $\int_0^L\frac{x(L-x)}{L}\,\mathrm dx=\frac{L^2}{6}$, and each of the other two is $\mathbb{E}[c\,x^2]=c\,\frac{L^2}{3}$. Hence $$cL^2=\frac{L^2}{6}+\frac{2c}{3}L^2\;\Longrightarrow\;\frac{c}{3}=\frac16\;\Longrightarrow\;c=\frac12 .$$ At $L=1$ the expected total is $$\boxed{\tfrac12}.$$

The computation

Run the actual process: keep splitting every piece at a uniform point, accumulating products, until the pieces are negligibly small, and average over many realisations. It lands on $\tfrac12$.

import numpy as np
def total(eps=1e-3):                               # one realisation, split until pieces < eps
    stack, s = [1.0], 0.0
    while stack:
        L = stack.pop()
        if L < eps: continue
        x = np.random.random() * L
        s += x * (L - x); stack += [x, L - x]
    return s
np.random.seed(1)
print(np.mean([total() for _ in range(8000)]))     # ~0.500

Extra Credit

Now split into three pieces $a,b,c$ (uniform on $a+b+c=L$) and score by the recursion $$g(L)=abc+g(a{+}b)+g(a{+}c)+g(b{+}c)-g(a)-g(b)-g(c).$$ On average, what does $g(1)$ approach?

Solution

Now $abc$ scales as a volume, so write $g(L)=kL^3$. A uniform split of $L$ into three is a Dirichlet$(1,1,1)$ distribution scaled by $L$, whose moments are $\mathbb{E}[abc]=\tfrac{L^3}{60}$, $\mathbb{E}[(a{+}b)^3]=\mathbb{E}[(L-c)^3]=\tfrac{2}{5}L^3$, and $\mathbb{E}[a^3]=\tfrac{1}{10}L^3$. Taking expectations of the recursion and using the symmetry of $a,b,c$, $$k=\frac{1}{60}+3k\cdot\frac{2}{5}-3k\cdot\frac{1}{10}=\frac{1}{60}+\frac{9k}{10}\;\Longrightarrow\;\frac{k}{10}=\frac{1}{60}\;\Longrightarrow\;k=\frac16 .$$ So $$g(1)\to\boxed{\tfrac16}.$$

The computation

A direct simulation of $g$ branches six ways and explodes, so instead measure the three moments the recursion actually depends on by sampling the uniform three-way split, then solve the self-consistency $k=\mathbb{E}[abc]+3k\,\mathbb{E}[(a{+}b)^3]-3k\,\mathbb{E}[a^3]$. The sampled moments give $k\approx\tfrac16$.

import numpy as np
rng = np.random.default_rng(0); N = 5_000_000
a, b, c = rng.dirichlet([1, 1, 1], N).T              # uniform split of 1 into three
E_abc = (a * b * c).mean()                           # ~ 1/60
E_pair = ((a + b) ** 3).mean()                       # ~ 2/5
E_single = (a ** 3).mean()                           # ~ 1/10
print(round(E_abc / (1 - 3*E_pair + 3*E_single), 4)) # ~0.1667 = 1/6