期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：2017
卷号：114
期号：11
页码：2860-2864
DOI：10.1073/pnas.1617540114
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：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 p 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 p 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 ε -outlier on the walk is significant at p = 2 ε 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 p ≈ ε 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.
关键词：Markov chain ; mixing time ; gerrymandering ; outlier ; p value
