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

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

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.