Sequential data such as documents, conversations, and trajectories is naturally grouped by user. This paper studies how to learn Markov chains from such data while guaranteeing that each user's entire sequence remains private, a stronger requirement than protecting individual items.
The authors initiate the study of differentially private Markov chain estimation under user-level privacy. They show that the sample complexity needed for private learning is near-optimal, meaning the privacy guarantee does not impose a significant penalty compared to the non-private setting.
This result provides a theoretical foundation for building private models on sequential user data, with potential applications in natural language processing, mobility analysis, and other domains where data arrives as ordered sequences.