Probability Applied to Problems in Algorithmic Statistics, Statistical Physics and the Combinatorics of Permutations

概率应用于算法统计、统计物理和排列组合问题

• 批准号: 1261010
• 负责人: Naya Banerjee
• 金额: $ 14万
• 依托单位: University of Delaware
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-08-01 至 2017-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1261010&HistoricalAwards=false
• 关键词: Probability; Applied; Problems; Algorithmic; Statistics

The theme of this project is the application of probabilistic, algorithmic and combinatorial ideas to the following three areas:(1) Rigorous analysis of heuristics for statistical problems such as fast random generation and simulation of posterior distributions, and classification of the difficulty of these problems. Of particular interest are heuristics based on Markov Chain Monte Carlo. The emphasis will be on understanding the models for which such heuristics are provably efficient as well as cases where they are not. The investigator expects this to lead to a better understanding of how to design algorithms for these problems.(2) The proposal aims to explore the connection between phase transitions in Gibbs measures for spin systems on sparse random graphs and algorithmic phase transitions in constraint satisfaction problems. For example, one long-term goal is to rigorously show a connection between decay of correlations in the Gibbs measure and phase transitions in the connectivity of the solution space.(3) The investigator proposes to study properties of permutations under non-uniform measures, especially the asymptotics, large deviations and fluctuations of statistics such as the longest increasing subsequence. These questions give rise to interesting refinements of the theory of limiting shapes of random Young diagrams, point processes and interacting particle processes. One question we aim to shed more light on is the relationship between the number of inversions in a permutation and the longest increasing subsequence.This project envisages using probabilistic techniques to solve problems from areas such as statistics, statistical physics, computer science and combinatorics. Problems involving large amounts of data and algorithms for fast simulation of large systems are of interest to researchers in industry and experimentalists in the physical sciences. The proposal aims to rigorously address the question of efficient simulation. The study of Gibbs measures is a classical topic in probability and statistical mechanics. The questions proposed here are of value in establishing connections between the theory of Gibbs measures and theoretical computer science which attempts to understand efficiency of algorithms, including those which make use of randomness. Permutations are well studied objects in combinatorics and probability. The investigator hopes that their study under distributions that are not uniformly random will contribute newmethods of analysis and results to this classical subject. The areas described are a good source of problems of practical and theoretical importance which students at both graduate and undergraduate levels could find a stimulating point at which to start their scientific inquiries.

该项目的主题是将概率论、算法和组合思想应用到以下三个领域：（1）对快速随机生成和后验分布模拟等统计问题进行严格的启发式分析，并对这些问题的难度进行分类。特别令人感兴趣的是基于马尔可夫链蒙特卡罗的启发法。重点是理解此类启发式方法被证明有效的模型以及无效的情况。研究人员希望这能够更好地理解如何为这些问题设计算法。(2) 该提案旨在探索稀疏随机图上自旋系统的吉布斯度量中的相变与约束满足问题中的算法相变之间的联系。例如，一个长期目标是严格显示吉布斯测度中的相关性衰减与解空间连通性中的相变之间的联系。（3）研究者建议研究非均匀测度下的排列特性，特别是最长递增子序列等统计量的渐近、大偏差和波动。这些问题引起了对随机杨氏图、点过程和相互作用粒子过程的限制形状理论的有趣改进。我们旨在进一步阐明的一个问题是排列中的反转次数与最长递增子序列之间的关系。该项目设想使用概率技术来解决统计学、统计物理、计算机科学和组合学等领域的问题。涉及大型系统快速模拟的大量数据和算法的问题引起了工业研究人员和物理科学实验人员的兴趣。该提案旨在严格解决高效模拟的问题。吉布斯测度的研究是概率和统计力学中的一个经典课题。这里提出的问题对于在吉布斯测度理论和理论计算机科学之间建立联系很有价值，理论计算机科学试图理解算法的效率，包括那些利用随机性的算法。排列是组合学和概率学中深入研究的对象。研究人员希望他们在非均匀随机分布下的研究将为这个经典课题提供新的分析方法和结果。所描述的领域是具有实际和理论重要性的问题的良好来源，研究生和本科生都可以找到开始他们的科学探究的刺激点。