Assessing significance in a Markov chain without mixing
Assessing significance in a Markov chain without mixing
复制标题
DOI：
10.1073/pnas.1617540114
复制
发表时间：
2017-03-14
影响因子：
11.1
通讯作者：
Pegden, Wesley
中科院分区：
文献类型：
--
作者：
Chikina, Maria;Frieze, Alan;Pegden, Wesley
我们提出了一项统计检验，以检测到可逆的马尔可夫链的呈现状态不是从固定分布中选择的。特别是，给定对马尔可夫链状态的价值函数，我们要严格地表明，通过在零假设下建立一个RHO值，即从固定的假设中选择它是对值的异常值链的分布。实践中使用的一个简单的启发式方法是从马尔可夫链上的长随机轨迹中样本等级，并将其与提出状态的等级进行比较。如果与采样等级相比，呈现的状态为0：1％的离群（其等级为底部的0：1％的采样等级），则此观察值应对应于0：001的RHO值。但是，这种意义并不严格，在马尔可夫链的混合时间上没有良好的界限。我们的测试如下：鉴于马尔可夫链中的呈现状态，以任何数量的步骤从呈现的状态中随机步行。我们证明，观察到的状态在步行中是epsilon淘汰者，在rho = root 2 epsilon下，在零假设下是从固定分布中选择该状态的。我们对马尔可夫链的可逆性一无所知，并表明在Rho上的意义近似于根部Epsilon是最好的。我们说明了我们的测试的使用，并潜在地应用了国会地区的严格检测。
We present a statistical test to detect that a presented state of a reversible Markov chain was not chosen from a stationary distribution. In particular, given a value function for the states of the Markov chain, we would like to show rigorously that the presented state is an outlier with respect to the values, by establishing a Rho value under the null hypothesis that it was chosen from a stationary distribution of the chain. A simple heuristic used in practice is to sample ranks of states from long random trajectories on the Markov chain and compare these with the rank of the presented state; if the presented state is a 0 : 1% outlier compared with the sampled ranks (its rank is in the bottom 0 : 1% of sampled ranks), then this observation should correspond to a Rho value of 0:001. This significance is not rigorous, however, without good bounds on the mixing time of the Markov chain. Our test is the following: Given the presented state in the Markov chain, take a random walk from the presented state for any number of steps. We prove that observing that the presented state is an epsilon-outlier on the walk is significant at Rho = root 2 epsilon under the null hypothesis that the state was chosen from a stationary distribution. We assume nothing about the Markov chain beyond reversibility and show that significance at Rho approximate to root epsilon is best possible in general. We illustrate the use of our test with a potential application to the rigorous detection of gerrymandering in Congressional districting.