Past exam of the mathematics course of the University of Cambridge / 2016 / iii / Paper 112 / 3 / iii / Solution

Write $f(x)=\mathrm{TS}\{x_1,\dots ,x_n\}$. Besides Talagrand's convex distance inequality, we use the precise squared edge bound for tours in the unit square stated above and the triangle inequality, which permits shortcutting a closed walk without increasing its length. We first prove the geometric comparison that connects these results.

For each fixed $x$, choose a cyclic tour $C$ with edge lengths ${\ell }_i$ satisfying ${\sum }_i{\ell }_i^2\le 4$. At vertex $x_i$, let $a_i(x)$ be the sum of the lengths of its two incident edges in $C$. The Cauchy-Schwarz inequality givesWe claim the weighted mismatch bound for Euclidean tours:To prove it, keep the vertices whose coordinates agree. In the cyclic ordering $C$, the deleted vertices split into consecutive runs between kept vertices. For one run, let $a,b$ denote its two boundary edge lengths and $S$ the sum of its internal edge lengths. Starting at the left kept endpoint, visit the run and return along the same path, at cost $2(a+S)$; starting at the right endpoint costs $2(b+S)$. Choose the cheaper detour. Its cost is at mostwhich is exactly the sum of $a_i(x)$ over that run. Attach these detours to a shortest tour through $y$, which already visits every kept point. The resulting closed walk visits all points of $x$; shortcut it using the triangle inequality. Summing the detour costs proves the claimed weighted mismatch bound for Euclidean tours. If there is just one kept vertex, the same argument uses that vertex as both endpoints of the unique run. If there are no kept vertices, $f(x)\le {\sum }_i{\ell }_i\le {\sum }_i{a}_i(x)$ proves the comparison directly. Repeated point locations cause no difficulty, since their connecting edges may have length zero.

Let $M$ be any median of $f(X)$ and set $A=\{y:f(y)\le M\}$. For $f(x)\ge M+t$, the weighted mismatch bound for Euclidean tours impliesThe weights have squared sum at most one, so $d_T(x,A)\ge t/4$. Since $\mathbb{P}(A)\ge 1/2$, Talagrand's convex distance inequality yieldsFor the lower tail, put $B=\{x:f(x)\le M-t\}$. If $\mathbb{P}(B)=0$ there is nothing to prove. For every $y$ with $f(y)\ge M$, apply the same weighted mismatch bound for Euclidean tours with its weights $a_i(y)$ and all $x\in B$. It gives $d_T(y,B)\ge t/4$. The set of such $y$ has probability at least $1/2$, so Talagrand's convex distance inequality instead givesCombining both tails,The bound has a constant fluctuation scale, independent of $n$. Only independence of the point coordinates and their support in the square are needed here; their uniform distribution was needed for the earlier lower bound on the expected value.