title: Assessing significance in a Markov chain without mixing.
abstract: 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 [Formula: see text] 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 [Formula: see text] outlier compared with the sampled ranks (its rank is in the bottom [Formula: see text] of sampled ranks), then this observation should correspond to a [Formula: see text] value of [Formula: see text] 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 [Formula: see text]-outlier on the walk is significant at [Formula: see text] 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 [Formula: see text] 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.
authors.affiliation: Department of Computational and Systems Biology, University of Pittsburgh, Pittsburgh, PA 15213.
authors.forename: Maria
authors.initials: M
authors.lastname: Chikina
authors.affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213.
authors.forename: Alan
authors.initials: A
authors.lastname: Frieze
authors.affiliation: Department of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213 wes@math.cmu.edu.
authors.forename: Wesley
authors.initials: W
authors.lastname: Pegden
mesh_terms: D015982:Bias; D006801:Humans; D008390:Markov Chains; D008962:Models, Theoretical; D011057:Politics
keywords: Markov chain; gerrymandering; mixing time; outlier; p value