Putnam 2021, Problem B-6

Given an ordered list of $3N$ real numbers, we can trim it to form a list of $N$ numbers as follows: We divide the list into $N$ groups of 3 consecutive numbers, and within each group, discard the highest and lowest numbers, keeping only the median.

Consider generating a random number $X$ by the following procedure: Start with a list of $3^{2021}$ numbers, drawn independently and uniformly at random between 0 and 1. Then trim this list as defined above, leaving a list of $3^{2020}$ numbers. Then trim again repeatedly until just one number remains; let $X$ be this number. Let $\mu$ be the expected value of $|X - \frac{1}{2}|$. Show that
\[
\mu \geq \frac{1}{4} \left( \frac{2}{3} \right)^{2021}.
\]


Solution:
**First solution.** (based on a suggestion of Noam Elkies)

Let $f_k(x)$ be the probability distribution of $X_k$, the last number remaining when one repeatedly trims a list of $3^k$ random variables chosen with respect to the uniform distribution on $[0,1]$; note that $f_0(x) = 1$ for $x \in [0,1]$. Let $F_k(x) = \int_0^x f_k(t) dt$ be the cumulative distribution function; by symmetry, $F_k(1/2) = 1/2$. Let $\mu_k$ be the expected value of $X_k - 1/2$; then $\mu_0 = 1/4$, so it will suffice to prove that $\mu_k \geq \frac{2}{3}\mu_{k-1}$ for $k > 0$.

By integration by parts and symmetry, we have
$$\mu_k = 2 \int_0^{1/2} \left(\frac{1}{2} - x\right) f_k(x) dx = 2 \int_0^{1/2} F_k(x) dx;$$
that is, $\mu_k$ computes twice the area under the curve $y = F_k(x)$ for $0 \leq x \leq 1/2$. Since $F_k$ is a monotone function from $[0, 1/2]$ with $F_k(0) = 0$ and $F_k(1/2) = 1/2$, we may transpose the axes to obtain
$$\mu_k = 2 \int_0^{1/2} \left(\frac{1}{2} - F_k^{-1}(y)\right) dy. \tag{1}$$

Since $f_k(x)$ is the probability distribution of the median of three random variables chosen with respect to the distribution $f_{k-1}(x)$,
$$f_k(x) = 6f_{k-1}(x)F_{k-1}(x)(1-F_{k-1}(x)) \tag{2}$$
or equivalently
$$F_k(x) = 3F_{k-1}(x)^2 - 2F_{k-1}(x)^3. \tag{3}$$

By induction, $F_k$ is the $k$-th iterate of $F_1(x) = 3x^2 - 2x^3$, so
$$F_k(x) = F_{k-1}(F_1(x)). \tag{4}$$

Since $f_1(t) = 6t(1-t) \leq \frac{3}{2}$ for $t \in [0, 1/2]$,
$$\frac{1}{2} - F_1(x) = \int_x^{1/2} 6t(1-t) dt \leq \frac{3}{2} \left(\frac{1}{2} - x\right);$$
for $y \in [0, 1/2]$, we may take $x = F_k^{-1}(y)$ to obtain
$$\frac{1}{2} - F_k^{-1}(y) \geq \frac{2}{3} \left(\frac{1}{2} - F_{k-1}^{-1}(y)\right). \tag{5}$$

Using (4) and (5), we obtain
$$\mu_k = 2 \int_0^{1/2} \left(\frac{1}{2} - F_k^{-1}(y)\right) dy$$
$$\geq \frac{4}{3} \int_0^{1/2} \left(\frac{1}{2} - F_{k-1}^{-1}(y)\right) dy = \frac{2}{3}\mu_{k-1}$$
as desired.

**Second solution.** Retain notation as in the first solution. Again $F_k(1/2) = 1/2$, so (2) implies
$$f_k\left(\frac{1}{2}\right) = 6f_{k-1}\left(\frac{1}{2}\right) \times \frac{1}{2} \times \frac{1}{2}.$$

By induction on $k$, we deduce that $f_k(1/2) = (\frac{3}{2})^k$ and $f_k(x)$ is nondecreasing on $[0, 1/2]$. (More precisely, besides (2), the second assertion uses that $F_{k-1}(x)$ increases from 0 to 1/2 and $y \mapsto y - y^2$ is nondecreasing on $[0, 1/2]$.)

The expected value of $|X_k - 1/2|$ equals
$$\mu_k = 2 \int_0^{1/2} \left(\frac{1}{2} - x\right) f_k(x) dx$$
$$= 2 \int_0^{1/2} x f_k\left(\frac{1}{2} - x\right) dx.$$

Define the function
$$g_k(x) = \begin{cases} \left(\frac{3}{2}\right)^k & x \in \left[0, \frac{1}{2} \left(\frac{2}{3}\right)^k\right] \\ 0 & \text{otherwise.} \end{cases}$$

Note that for $x \in [0, 1/2]$ we have
$$\int_0^x (g_k(t) - f_k(1/2-t)) dt \geq 0$$
with equality at $x = 0$ or $x = 1/2$. (On the interval $[0, (1/2)(2/3)^k]$ the integrand is nonnegative, so the function increases from 0; on the interval $[(1/2)(2/3)^k, 1/2]$ the integrand is nonpositive, so the function decreases to 0.) Hence by integration by parts,
$$\mu_k - 2 \int_0^{1/2} x g_k(x) dx$$
$$= \int_0^{1/2} 2x(f_k\left(\frac{1}{2} - x\right) - g_k(x)) dx$$
$$= \int_0^{1/2} x^2 \left(\int_0^x g_k(t) - \int_0^x f_k\left(\frac{1}{2} - t\right) dt dt\right) dx \geq 0.$$

(This can also be interpreted as an instance of the rearrangement inequality.)

We now see that
$$\mu_k \geq 2 \int_0^{1/2} x g_k(x) dx$$
$$\geq 2 \left(\frac{3}{2}\right)^k \int_0^{(1/2)(2/3)^k} x dx$$
$$= 2 \left(\frac{3}{2}\right)^k \frac{1}{2} x^2 \Big|_0^{(1/2)(2/3)^k}$$
$$= 2 \left(\frac{3}{2}\right)^k \frac{1}{8} \left(\frac{2}{3}\right)^{2k} = \frac{1}{4} \left(\frac{2}{3}\right)^k$$

as desired.

**Remark.** For comparison, if we instead take the median of a list of $n$ numbers, the probability distribution is given by
$$P_{2n+1}(x) = \frac{(2n+1)!}{n!n!} x^n(1-x)^n.$$

The expected value of the absolute difference between $1/2$ and the median is
$$2 \int_0^{1/2} (1/2 - x)P_{2n+1}(x)dx = 2^{-2n-2} \binom{2n+1}{n}.$$

For $n = 3^{2021}$, using Stirling's approximation this can be estimated as $1.13(0.577)^{2021} < 0.25(0.667)^{2021}$. This shows that the trimming procedure produces a quantity that is on average further away from $1/2$ than the median.