# Assessing significance in a Markov chain without mixing

1. aDepartment of Computational and Systems Biology, University of Pittsburgh, Pittsburgh, PA 15213;
2. bDepartment of Mathematical Sciences, Carnegie Mellon University, Pittsburgh, PA 15213
1. Edited by Kenneth W. Wachter, University of California, Berkeley, CA, and approved January 24, 2017 (received for review October 21, 2016)

## Significance

Markov chains are simple mathematical objects that can be used to generate random samples from a probability space by taking a random walk on elements of the space. Unfortunately, in applications, it is often unknown how long a chain must be run to generate good samples, and in practice, the time required is often simply too long. This difficulty can preclude the possibility of using Markov chains to make rigorous statistical claims in many cases. We develop a rigorous statistical test for Markov chains which can avoid this problem, and apply it to the problem of detecting bias in Congressional districting.

## 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 <mml:math><mml:mi>p</mml:mi></mml:math>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 <mml:math><mml:mrow><mml:mn>0.1</mml:mn><mml:mo>%</mml:mo></mml:mrow></mml:math>0.1% outlier compared with the sampled ranks (its rank is in the bottom <mml:math><mml:mrow><mml:mn>0.1</mml:mn><mml:mo>%</mml:mo></mml:mrow></mml:math>0.1% of sampled ranks), then this observation should correspond to a <mml:math><mml:mi>p</mml:mi></mml:math>p value of <mml:math><mml:mn>0.001</mml:mn></mml:math>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 <mml:math><mml:mi>ε</mml:mi></mml:math>ε-outlier on the walk is significant at <mml:math><mml:mrow><mml:mpadded width="+1.7pt"><mml:mi>p</mml:mi></mml:mpadded><mml:mo>=</mml:mo><mml:msqrt><mml:mrow><mml:mn>2</mml:mn><mml:mi>ε</mml:mi></mml:mrow></mml:msqrt></mml:mrow></mml:math>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 <mml:math><mml:mrow><mml:mpadded width="+1.7pt"><mml:mi>p</mml:mi></mml:mpadded><mml:mo>≈</mml:mo><mml:msqrt><mml:mi>ε</mml:mi></mml:msqrt></mml:mrow></mml:math>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.

## Footnotes

• ?1To whom correspondence should be addressed. Email: wes{at}math.cmu.edu.

#### Online Impact

• 595505886 2018-01-24
• 26570885 2018-01-24
• 724358884 2018-01-24
• 649756883 2018-01-24
• 550841882 2018-01-24
• 436793881 2018-01-24
• 99132880 2018-01-23
• 802899879 2018-01-23
• 295573878 2018-01-23
• 352668877 2018-01-23
• 984633876 2018-01-23
• 545928875 2018-01-23
• 976569874 2018-01-23
• 871324873 2018-01-23
• 263462872 2018-01-23
• 577161871 2018-01-23
• 255603870 2018-01-23
• 117346869 2018-01-23
• 90982868 2018-01-23
• 663415867 2018-01-23