A general method for lower bounds on fluctuations of random variables (Q2327942)

In this paper, the author presents a simple, yet powerful, general method for obtaining lower bounds on the order of fluctuations of a sequence of random variables \((X_n)\); that is, the construction of a sequence \((\delta_n)\) such that there does not exist a sequence of intervals \((I_n)\) where \(I_n\) has length of order \(\delta_n\) and \(\mathbb{P}(X_n\in I_n)\to1\) as \(n\to\infty\). This construction is based on the observation that for any random variables \(X\) and \(Y\) constructed on the same probability space, and for any \(a\leq b\), \[ \mathbb{P}(a\leq X\leq b)\leq\frac{1}{2}\left[1+\mathbb{P}(|X-Y|\leq b-a)+d_{TV}(X,Y)\right]\,, \] where \(d_{TV}\) is the total variation distance. Despite its relative simplicity, this observation is powerful enough for the author to use it to derive lower bounds on the order of fluctuations in applications to the stochastic travelling salesman problem, the stochastic minimal matching problem, the random assignment problem, free energy in the Sherrington-Kirkpatrick model, first passage percolation and determinants of random matrices. The paper concludes with a list of 13 open problems related to the work presented.