Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
Abstract
Sequential data such as documents, conversations, and trajectories are naturally partitioned across users, motivating privacy guarantees that protect each user's entire trajectory. We initiate the study of privately estimating the transition matrix of a discrete ergodic Markov chain from N independent trajectories of length T, with arbitrary initial distributions, under maximum row-wise ell 1 error. Besides N, T, and the number of states, our bounds depend on the minimum stationary probability and the pseudo-spectral gap, which govern state coverage and mixing. Under item-level privacy, we give upper and lower bounds that separate the costs of sampling, state occupancy and mixing, and privacy. Under user-level privacy, we reduce the problem for sufficiently long trajectories to private product distribution estimation. Along the way, we establish optimal user-level private bounds for estimating products of discrete distributions, which may be of independent interest. In the user level setting, our bounds are nearly tight in the large T regime, whereas in the item-level setting, our bounds as tight up-to a non-private term.
Related
- Optimal quantum locally differentially private mechanisms in the high-privacy regime
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
- When to spend privacy: optimal allocation in private learning
- Differentially Private Distributed Optimization via the Intrinsic Randomness of Zeroth-Order Estimators: Sampling Geometry, Convergence, and Privacy Guarantees
- Personalized and differentially private federated learning for mobility data mining via the TrajectoryGuard framework
BibTeX
@misc{gupta2026differentially,
title = {{Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy}},
author = {Devansh Gupta and Cristóbal Guzman and Enayat Ullah},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19335},
eprint = {2610.19335},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19335},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
AU - Devansh Gupta
AU - Cristóbal Guzman
AU - Enayat Ullah
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2610.19335
UR - https://arxiv.org/abs/2610.19335
AB - Sequential data such as documents, conversations, and trajectories are naturally partitioned across users, motivating privacy guarantees that protect each user's entire trajectory. We initiate the study of privately estimating the transition matrix of a discrete ergodic Markov chain from N independent trajectories of length T, with arbitrary initial distributions, under maximum row-wise ell 1 error. Besides N, T, and the number of states, our bounds depend on the minimum stationary probability and the pseudo-spectral gap, which govern state coverage and mixing. Under item-level privacy, we give upper and lower bounds that separate the costs of sampling, state occupancy and mixing, and privacy. Under user-level privacy, we reduce the problem for sufficiently long trajectories to private product distribution estimation. Along the way, we establish optimal user-level private bounds for estimating products of discrete distributions, which may be of independent interest. In the user level setting, our bounds are nearly tight in the large T regime, whereas in the item-level setting, our bounds as tight up-to a non-private term.
ER -