Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain

Quentin Berthet, Varun Kanade

Introduction

In many stochastic processes, we are interested in recovering the initial state of a system after it has evolved over time. Imagine observing a rumor spreading through a social network or examining a deck of cards after several shuffles. The fundamental question is: can we determine if the process started at Point A or Point B? In statistical terms, this is a hypothesis testing problem where we aim to identify the initial distribution $\mu$ based on samples taken after $t$ steps of a Markov chain.

Standard Markov chain theory often focuses on the mixing time—the duration required for a chain to reach a stationary state where all information about the starting point is effectively lost. However, this paper argues that mixing time is a coarse metric. For specific pairs of starting distributions, the ability to distinguish them may vanish much earlier or persist much later than the mixing time would suggest. The authors introduce the concept of a "statistical window" to characterize this nuanced rate of information loss.

The Statistical Window

The "statistical window" is the paper's central contribution. It describes the period during which the required sample size to distinguish two distributions varies drastically depending on how those distributions align with the chain's internal structure. The authors prove that the ratio of sample complexities between the "easiest" and "hardest" pairs of distributions to distinguish grows exponentially as $(\lambda_{[2]} / \lambda_{[d]})^{2t}$.

Decay of the distance between distributions over time, illustrating how different components reach the distinguishability threshold at different times.

As shown in the figure above, the distance between distributions (and thus the ease of testing) decays at different rates. This implies that even if two distributions are far from the stationary state, they might already be indistinguishable from each other if their differences align with rapidly decaying components of the chain.

Spectral Analysis and Sample Complexity

The authors employ spectral decomposition to derive instance-dependent minimax rates. For reversible Markov chains, the transition matrix $P$ has real eigenvalues $\lambda_i$ and orthonormal eigenvectors $u_i$. The difference between two candidate distributions can be decomposed along these eigenvectors.

The key result is that the number of samples $n^*$ required to distinguish $\mu$ from $\mu'$ with high probability is approximately: $$n^* \approx \frac{1}{\sum_{i=2}^d \lambda_i^{2t} \langle u_i, \mu - \mu' \rangle_\pi^2}$$

This formula reveals that eigenvalues act as the "clocks" of information loss. If the difference between distributions aligns with small eigenvalues (near 0), information is lost almost instantly. Conversely, alignment with eigenvalues near 1 or -1 allows information to persist for much longer.

The Pachinko Model

To illustrate these theoretical findings, the authors introduce the Pachinko Random Walk, a model based on a dyadic tree structure. This model serves as a benchmark for hierarchical information loss.

The Pachinko Random Walk on a dyadic tree, where transitions move up to a peak and then down, losing information at different levels of the hierarchy.

In the Pachinko model, information at different "heights" of the tree is lost at different exponential rates. This demonstrates how structural properties of the state space directly influence the statistical window, creating a hierarchy of features that vanish at predictable intervals.

Conclusion

This research moves beyond global properties like mixing time to provide a localized, instance-dependent view of information loss in Markov chains. By establishing tight upper and lower bounds using the Likelihood Ratio Test, the authors show that the geometry of the initial distributions relative to the chain's eigenvectors determines the feasibility of recovery. Future work may extend these results to non-reversible chains or scenarios where the transition matrix itself must be estimated from data.

Summary updated

Abstract

We study the problem of hypothesis testing between two discrete distributions, where we only have access to samples after the action of a known reversible Markov chain, playing the role of noise. W...
BibTeX
@inproceedings{berthet2019statistical,
  author = {Quentin Berthet and Varun Kanade},
  title = {{Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=MK1lfvRBNue},
}
Figure