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

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

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.