Past exam of the mathematics course of the University of Cambridge / 2010 / iii / Paper 12 / 3

Take the sampled points to be independent with the uniform distribution on $T=\{(x,y):0\le y\le x\le 1\}$. Its area is $1/2$, so its probability density is two. With probability one there are no coincidences, equal relevant coordinates or collinear triples. We give an exact first moment method argument; no tangent construction is needed.

First count the probability that $k$ labelled points, together with the endpoints, form a convex chain. In their order along the lower boundary, write their coordinates as $(x_i,y_i)$, $1\le i\le k$, and put $(x_0,y_0)=(0,0)$, $(x_{k+1},y_{k+1})=(1,1)$. They necessarily satisfyIndeed the lower boundary of the convex polygon is the graph of a convex piecewise linear function. Its segment slopes strictly increase; the first is positive because the first point lies above the $x$ axis, making all later slopes positive too.

Set $u_i=x_i-x_{i-1}$ and $v_i=y_i-y_{i-1}$ for $1\le i\le k+1$. Both spacing vectors lie in the open probability simplex, with ${\sum }_i{u}_i={\sum }_i{v}_i=1$. The coordinate-monotone region has volume $1/(k!{)}^2$. The change to the first $k$ spacings in each vector has Jacobian one, and each simplex has uniform volume measure. Simultaneous permutation of all $k+1$ pairs $(u_i,v_i)$ preserves this product volume measure. Except on a null set of ties, the ratios $v_i/u_i$ therefore have all $(k+1)!$ possible orders with equal volume.

Strict increase of these ratios is exactly the convex chain condition. It also puts the intermediate points below the diagonal: the weighted mean of all slopes is ${\sum }_i{u}_i(v_i/u_i)=1$, and each proper initial weighted mean is strictly smaller than one, so $y_j<x_j$ for $j\le k$. Thus it suffices to impose the slope order on the whole coordinate-monotone region; no additional triangle restriction is needed.

The volume for one specified label order is consequently $1/((k!{)}^2(k+1)!)$. There are $k!$ disjoint orders of the labels, and the joint uniform-triangle density is $2^k$. Hence the convex-chain probability in a triangle isFor example $p_1=1$ and $p_2=1/3$.

Let $C_k$ count the $k$-element subsets of the $n$ sampled points that are convex chains. By linearity of expectation, $\mathbb{E}{C}_k=\left(\genfrac{}{}{0ex}{}{n}{k}\right)p_k$. If $L_n\ge k$, an optimal chain contains a $k$-vertex subchain, since removing vertices from a convex polygon preserves convex position of the remaining vertices. Therefore, by the first moment method,We used $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le n^k/k!$, $(k+1)!\ge k!$, and $k!\ge (k/e{)}^k$, the last following from ${\sum }_{j=1}^k\log j\ge {\int }_1^k\log xdx$.

Take $k=\lceil 4e{n}^{1/3}\rceil$. If $k\le n$, the last bound is at most $32^{-k}<1/2$; if $k>n$, the event is empty. Every integer median $m_n$ must then satisfy $m_n<k$, and thereforeThe hint's curve $y=x^2$ is a parabola, not a hyperbola. The exact counting argument above proves the upper bound directly. The same chain probability is recorded in Ambrus and Bárány's analysis of longest convex chains.

We use the directed set version of the Talagrand convex distance:Here a coordinate is an entire sampled point, so $x_i\ne y_i$ means the two planar points differ. This is the distance from the upper event $A$ to the lower event $B$; its order is relevant because the convex distance need not be symmetric.

Fix $x\in A$ and choose exactly $a$ indices $I$ whose points form a convex chain with the endpoints. Such a choice exists even if $L_n(x)>a$, by taking a subchain. It is a certificate of the certifiable function $L_n$. For any $y\in B$, let $J=\{i\in I:x_i\ne y_i\}$. The $a-|J|$ unchanged selected points remain a convex chain in configuration $y$, soChoose the nonnegative weights ${\alpha }_i=a^{-1/2}$ for $i\in I$ and zero otherwise. They have squared sum one, and for every $y\in B$,Taking the infimum over $y$, then the supremum over weights, and finally the infimum over $x\in A$ provesThis proof also works for $b=0$ if zero-length chains are admitted, and gives the usual infinite separation when one of the events is empty. For the uniform sampling model, $L_n\ge 1$ almost surely when $n\ge 1$.

The precise external concentration result we use is Talagrand's convex distance inequality: for a finite product of independent standard probability spaces, a measurable event $B$ of positive probability, and $u\ge 0$,Our coordinates are the independent uniformly sampled points of the triangle, so the hypothesis holds. Part (ii) therefore gives, for integers $a>b\ge 0$,Indeed every configuration in the first event has at least the distance from part (ii) to the second event. If one event is empty, the displayed product bound is automatic. This is the only use of the product-space theorem; the geometric separation was proved directly in part (ii). A precise source for that theorem is Section 4.1 of Talagrand's original product-space concentration paper.

Choose an integer median $m=m_n$, so $\mathbb{P}(L_n\le m)\ge 1/2$ and $\mathbb{P}(L_n\ge m)\ge 1/2$. First set $a=m+t$, $b=m$ in the product bound, and then set $a=m$, $b=m-t$. For positive integers $t$ this yields the convex-chain median concentration estimatesThe lower event is empty if $m-t<1$ in our sampling model; the upper event is empty if $m+t>n$. Thus the stated bounds remain valid for all positive integers $t$. Also $m\ge 1$ for $n\ge 1$.

By part (i), $m\le C{n}^{1/3}$ with $C=4e$. Let $h_n=\omega (n)n^{1/6}/2$, take $t_n=\lfloor h_n\rfloor +1$, and use the deterministic interval $I_n=[m-h_n,m+h_n]$. Its length is exactly $\omega (n)n^{1/6}$. As $L_n$ and $m$ are integers, falling outside this interval implies one of the two tail events with $t=t_n$. ThereforeFor positive $m,t$,Since $t_n\ge h_n$ and $m\le C{n}^{1/3}$, this exponent is at leastConsequentlyThus $L_n$ lies with high probability in the required interval. This proof works for every $\omega (n)\to \infty$, including growth faster than $n^{1/6}$; no extra restriction on $\omega$ is needed. The scale comes from the square root of the $O(n^{1/3})$ certificate size at the median.