CIF:Small:Collaborative Research:Statistics of slow mixing Markov processes: theory and applications to community detection

历史上，统计学领域是围绕着对现象的多重独立观察而发展起来的。然而，从生物学到社会网络的现代应用的进步越来越需要对依赖的观察有更深的理解。依赖观察会引入独立抽样中看不到的偏差。如果解释不当，它们往往会导致误导性的结论。本研究开发了一个统计框架来解释由依赖观察产生的样本。然后，问题被反过来开发算法来检测数据中有意义的依赖关系。例如，这种算法被用于识别协同工作的基因，或发现社交网络在某些问题上的两极分化程度。这项研究不仅被转化为课程、示范和推广项目，而且夏威夷的地理位置也被利用来接触科学和工程领域代表性不足的社区，特别是女性和太平洋岛民社区。无论样本量多大，有限的样本都不能很好地反映马尔可夫过程的平稳性质。这种偏差通常被形式化为混合，在独立采样中是看不见的。本研究分析了马尔可夫样本，甚至在样本反映渐近平稳性质之前，并开发了一个用于推断，分析和模拟缓慢混合马尔可夫过程的框架。然后，基于过去的耦合开发了算法原语，用于广泛研究的图中的社区检测任务，其中顶点被划分为簇，以便簇内顶点比不同簇中的顶点连接得更紧密。由于机器学习中的一些重采样过程（如交叉验证和自举）以独立采样为前提，并且在马尔可夫设置中没有很好的类似物，因此本研究为潜在的缓慢混合马尔可夫过程开发了新的重采样方法。

Historically, the field of statistics developed around multiple independent observations of phenomena. Yet progress in modern applications from biology to social networks increasingly requires deeper understanding of observations that are dependent. Dependent observations introduce biases unseen in independent sampling. If not interpreted properly, they often lead to misleading conclusions. This research develops a statistical framework to interpret samples generated by dependent observations. The problem is then turned around to develop algorithms that detect meaningful dependencies in data. Such algorithms are used, for example, to identify genes working together, or find the extent to which social networks are polarized on certain issues. Not only is this research translated to classes, demonstrations and outreach programs, but also the location in Hawaii is leveraged to reach out to underrepresented communities in science and engineering, in particular, women and the Pacific Islander community.Stationary properties of Markov processes may not be very well reflected by finite samples, no matter how large the sample size. This bias is often formalized as mixing, and is unseen in independent sampling. This research analyzes Markov samples even before the samples reflect the asymptotic stationary properties, and develops a framework for inference, analysis and simulation of slow mixing Markov processes. Then, algorithmic primitives based on coupling from the past are developed for the widely studied task of community detection in a graph, where vertices are partitioned into clusters so that intra-cluster vertices are connected tighter than those in disparate clusters. As several resampling procedures in machine learning such as cross validation and bootstrap are premised on independent sampling and have no good analogs in the Markov setting, this research develops new resampling approaches for potentially slow mixing Markov processes.