A GENERAL METHOD FOR LOWER BOUNDS ON FLUCTUATIONS OF RANDOM VARIABLES

• 成果类型: Article
• 署名作者: Chatterjee, Sourav
• 署名单位: Stanford University
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/18-AOP1304
• 发表日期: 2019
• 页码: 2140-2171
• 关键词: 1st passage percolation; limit; shape; approximation; CONVERGENCE; determinant; divergence; symmetry; absence

摘要

There are many ways of establishing upper bounds on fluctuations of random variables, but there is no systematic approach for lower bounds. As a result, lower bounds are unknown in many important problems. This paper introduces a general method for lower bounds on fluctuations. The method is used to obtain new results for the stochastic traveling salesman problem, the stochastic minimal matching problem, the random assignment problem, the Sherrington-Kirkpatrick model of spin glasses, first-passage percolation and random matrices. A long list of open problems is provided at the end.