International Mathematics Competition
for University Students
2024

IMC2024: Day 1, Problem 5

Problem 5. Let \(\displaystyle n>d\) be positive integers. Choose \(\displaystyle n\) independent, uniformly distributed random points \(\displaystyle x_1,\ldots,x_n\) in the unit ball \(\displaystyle B\subset \mathbb{R}^d\) centered at the origin. For a point \(\displaystyle p\in B\) denote by \(\displaystyle f(p)\) the probability that the convex hull of \(\displaystyle x_1,\ldots,x_n\) contains \(\displaystyle p\). Prove that if \(\displaystyle p,q\in B\) and the distance of \(\displaystyle p\) from the origin is smaller than the distance of \(\displaystyle q\) from the origin, then \(\displaystyle f(p)\geq f(q)\).

Fedor Petrov, St Petersburg State University

Solution. By radial symmetry of the distribution, \(\displaystyle f(p)\) depends only on \(\displaystyle |op|\) (the distance between \(\displaystyle o\) and \(\displaystyle p\)), so, we may assume that \(\displaystyle p\) lies on the segment between \(\displaystyle o\) and \(\displaystyle q\). For points \(\displaystyle x_1,\ldots,x_n\) and \(\displaystyle x\in B\) denote by \(\displaystyle f_x(x_1,\ldots,x_n)\) the indicator function of the event ``\(\displaystyle x\) is in the convex hull of \(\displaystyle x_1,\ldots,x_n\)''. The claim follows from the following deterministic inequality

where \(\displaystyle x_1,\ldots,x_n\in B\) are arbitrary points in general position and the summations are over all \(\displaystyle 2^n\) choices of signs (here \(\displaystyle o\) is identified with the origin, that is, \(\displaystyle x\) and \(\displaystyle -x\) are symmetric with respect to \(\displaystyle o\)). Indeed, taking the expectation in (1) over independent random uniform \(\displaystyle x_1,\ldots,x_n\), we get \(\displaystyle 2^nf(p)\geqslant 2^n f(q)\). (To be specific, here ``general position'' means that for any point set \(\displaystyle A\subset \{\pm x_1,\ldots,\pm x_n,p,q\}\), which does not contain simultaneosuly \(\displaystyle x_i\) and \(\displaystyle -x_i\), is not contained in an (affine) \(\displaystyle (|A|-2)\)-dimensional plane. This holds with probability 1.)

To prove (1), we use the following formula for the characteristic function \(\displaystyle \chi_P\) of the convex polyhedron \(\displaystyle P\subset \mathbb{R}^d\): if \(\displaystyle P_1,\ldots,P_k\) are all facets of \(\displaystyle P\), and \(\displaystyle Q_i\) is the convex hull of \(\displaystyle o\) and \(\displaystyle P_i\), then \(\displaystyle \chi_P=\sum \pm \chi_{Q_i}\), where the sign is plus if \(\displaystyle o\) and \(\displaystyle P\) are on the same side of \(\displaystyle P_i\), and minus otherwise. Indeed, for every point \(\displaystyle p\) in general position look how the ray \(\displaystyle op\) intersects the boundary of \(\displaystyle P\) and realize that for at most two summands the contribution of the RHS at point \(\displaystyle p\) is non-zero, and the total contribution equals 1 when \(\displaystyle p\) is inside \(\displaystyle P\) and 0 (possibly as \(\displaystyle 0=1-1\)) otherwise. Use this formula for every polyhedron \(\displaystyle P\) with \(\displaystyle n\) vertices \(\displaystyle y_1,\ldots,y_n\), where each \(\displaystyle y_i\) is \(\displaystyle \pm x_i\). These polyhedrons are simplicial (all facets are simplices) because of the general position condition. Sum up over all \(\displaystyle 2^n\) such \(\displaystyle P\), we get the expression of \(\displaystyle \sum_P \chi_P\) as a linear combination of \(\displaystyle \chi_S\), where \(\displaystyle S\) are simplices formed by \(\displaystyle o\) and some \(\displaystyle d\) points in \(\displaystyle \{\pm x_1,\ldots,\pm x_n\}\) (not containing \(\displaystyle x_i\) and \(\displaystyle -x_i\) simultaneously).

For proving (1), it suffices to verify that all coefficients of \(\displaystyle \chi_S\) in this linear combination are positive (since two sides of (1) are the values of the sum \(\displaystyle \sum_P \chi_P\) at \(\displaystyle p\) and \(\displaystyle q\)). Let's find a coefficient of \(\displaystyle \chi_S\), where, say, \(\displaystyle S\) is a simplex with vertices \(\displaystyle o,x_1,\ldots,x_d\). The plane \(\displaystyle \alpha\) through \(\displaystyle x_1,\ldots,x_d\) partitions \(\displaystyle \mathbb{R}^d\) onto two parts \(\displaystyle H^+\) (containing \(\displaystyle o\)) and \(\displaystyle H^{-}\) (not containing \(\displaystyle o\)). For every pair \(\displaystyle \{x_i,-x_i\}\) with \(\displaystyle i>d\), either both points belong to \(\displaystyle H^+\), or one belongs to \(\displaystyle H^{-}\) and another to \(\displaystyle H^+\). \(\displaystyle \chi_S\) goes with the plus sign for \(\displaystyle P\) with vertices \(\displaystyle x_1,\ldots,x_d\) and other vertices from \(\displaystyle H^+\), and with the minus sign for \(\displaystyle P\) with vertices \(\displaystyle x_1,\ldots,x_d\) and other vertices from \(\displaystyle H^-\). It is immediate that there are at least as many pluses as minuses.