# Conformal Predictions under Markovian Data

arXiv: https://arxiv.org/abs/2407.15277 · HTML: https://mlsanity.com/paper/2407.15277/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 34 references that are in the map.
- First posted on arXiv 21 Jul 2024.

## Builds on (most cited first, 12 of 12)

- [Distribution-Free Predictive Inference For Regression](https://mlsanity.com/paper/1604.04173/) (2016)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [Adaptive Conformal Inference Under Distribution Shift](https://mlsanity.com/paper/2106.00170/) (2021)
- [Conformal prediction beyond exchangeability](https://mlsanity.com/paper/2202.13415/) (2022)
- [Adaptive Conformal Predictions for Time Series](https://mlsanity.com/paper/2202.07282/) (2022)
- [Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms](https://mlsanity.com/paper/2006.08916/) (2020)
- [Adaptive Conformal Prediction for Motion Planning among Dynamic Agents](https://mlsanity.com/paper/2212.00278/) (2022)
- [Mixing time estimation in reversible Markov chains from a single sample path](https://mlsanity.com/paper/1708.07367/) (2017)
- [Estimating the Mixing Time of Ergodic Markov Chains](https://mlsanity.com/paper/1902.01224/) (2019)
- [Concentration bounds for empirical conditional value-at-risk: The unbounded case](https://mlsanity.com/paper/1808.01739/) (2018)
- [Conformal Off-Policy Evaluation in Markov Decision Processes](https://mlsanity.com/paper/2304.02574/) (2023)
- [Computationally Efficient Estimation of the Spectral Gap of a Markov Chain](https://mlsanity.com/paper/1806.06047/) (2018)

## Built on by (most cited first, 4 of 4)

- [Leave a Window Out: Modifying the Jackknife for Predictive Inference in Time Series](https://mlsanity.com/paper/2605.30292/) (2026)
- [Conformal Prediction Beyond the Horizon: Distribution-Free Inference for Policy Evaluation](https://mlsanity.com/paper/2510.26026/) (2025)
- [Conflict Forecasting via Conformal Prediction for Markov Processes](https://mlsanity.com/paper/2604.25139/) (2026)
- [Valid and Efficient Split Conformal Regression for Time Series](https://mlsanity.com/paper/2609.33866/) (2026)

## Abstract (arXiv)

We study the split Conformal Prediction method when applied to Markovian data. We quantify the gap in terms of coverage induced by the correlations in the data (compared to exchangeable data). This gap strongly depends on the mixing properties of the underlying Markov chain, and we prove that it typically scales as √tmixln(n)/n (where tmix is the mixing time of the chain). We also derive upper bounds on the impact of the correlations on the size of the prediction set. Finally we present K-split CP, a method that consists in thinning the calibration dataset and that adapts to the mixing properties of the chain. Its coverage gap is reduced to tmix/(nln(n)) without really affecting the size of the prediction set. We finally test our algorithms on synthetic and real-world datasets.