A sharp deviation inequality for the stochastic traveling salesman problem (Q1824393)

For n independent and uniformly distributed points in the unit square the length \(T_ n\) of a shortest hamiltonian cycle is a random variable known to be remarkably concentrated around its mean \(E(T_ n)\). Here, the existence of some number K, independent of n, is proven such that \[ P(| T_ n-E(T_ n)| >t)\leq K\quad \exp (-t^ 2/K) \] for all \(t\geq 0\). The proof is based on martingale difference sequence methods.