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

Quentin Berthet, Varun Kanade

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. We derive instance-dependent minimax rates for the sample complexity of this problem, and show how its dependence in time is related to the spectral properties of the Markov chain. We show that there exists a wide statistical window, in terms of sample complexity for hypothesis testing between different pairs of initial distributions. We illustrate these results in several concrete examples.

Introduction

A fundamental challenge in statistical inference is recovering information about the initial state of a system that has been corrupted by noise over time. Examples range from tracing the origin of a rumor in a social network to understanding the evolution of DNA sequences. Formally, this can be modeled as a hypothesis testing problem: given $n$ independent samples at time $t$, did the process originate from distribution $\mu$ or distribution $\mu'$?

Traditionally, the "mixing time" of a Markov chain is used to define the point at which initial information is effectively lost. However, mixing time is often a coarse metric. Information does not vanish uniformly; specific features of the initial distribution may persist much longer than others. This paper provides a precise characterization of the sample complexity—the number of observations required to distinguish $\mu$ from $\mu'$—as a function of time $t$ and the spectral properties of the transition matrix $P$.

Evolution of two initial distributions $\mu$ and $\mu'$ under the transition matrix $P^t$.

Methodology

The authors utilize spectral analysis of reversible Markov chains to decompose the initial distributions into components aligned with the eigenvectors of the transition matrix $P$. The study focuses on the optimal Likelihood Ratio Test (LRT) to distinguish between the two hypotheses.

The probability of error is linked to the Total Variation (TV) distance between the distributions of the samples at time $t$. By bounding this distance using Hellinger distance and Kullback-Leibler (KL) divergence, the authors derive instance-dependent minimax rates. These rates are "instance-dependent" because they depend explicitly on the specific pair of candidate distributions $(\mu, \mu')$ and the geometry of the state space defined by $P$.

Key Results and the Statistical Window

The central contribution is the characterization of the sample complexity $n^*$: $$n^*_{\mu,\mu',t} \asymp \frac{1}{\sum_{i=2}^d \lambda_i^{2t} (\alpha_i - \alpha'_i)^2}$$ where $\lambda_i$ are the eigenvalues of $P$, and $\alpha_i, \alpha'_i$ are the coordinates of $\mu$ and $\mu'$ in the eigenvector basis.

Beyond the Spectral Gap

While the spectral gap (the difference between the two largest eigenvalues) typically dictates mixing time, this research demonstrates that the entire spectrum is relevant. If the difference between $\mu$ and $\mu'$ is concentrated in eigenvectors associated with small eigenvalues, the information is lost rapidly. Conversely, differences aligned with eigenvalues near 1 (or -1 in periodic cases) persist.

The Statistical Window Phenomenon

The "statistical window" is defined as the ratio between the sample complexities of the easiest and hardest pairs of distributions to distinguish. The authors prove this window can be exponentially wide, scaling as $(\lambda_{[2]} / \lambda_{[d]})^{2t}$. In certain cases, such as bipartite graphs where parity is preserved, some information never decays, leading to an infinite statistical window.

Discussion and Limitations

This work provides a rigorous framework for understanding information decay in Markovian systems. However, several avenues for future research remain:

  • Known Parameters: The current model assumes the transition matrix $P$ and time $t$ are known, which is often not the case in practical inverse problems.
  • Observation Model: The analysis assumes $n$ independent samples at a fixed time $t$. Real-world data often consists of a single trajectory observed over time.
  • Reversibility: The reliance on reversibility allows for clean spectral decomposition; extending these results to non-reversible chains presents a significant mathematical hurdle.

The findings underscore that "mixing" is not a binary event but a multi-scale process where different types of information are lost at different rates.

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. We derive instance-dependent minimax rates for the sample complexity of this problem, and show how its dependence in time is related to the spectral properties of the Markov chain. We show that there exists a wide statistical window, in terms of sample complexity for hypothesis testing between different pairs of initial distributions. We illustrate these results in several concrete examples.
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},
}

Loading related content...

Figure