# Differential Privacy for Symbolic Systems with Application to Markov Chains

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Feb 2022.

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

- [Differential Privacy in Cooperative Multiagent Planning](https://mlsanity.com/paper/2301.08811/) (2023)
- [Deceptive Sequential Decision-Making via Regularized Policy Optimization](https://mlsanity.com/paper/2501.18803/) (2025)
- [Policy Gradient Methods for Information-Theoretic Opacity in Markov Decision Processes](https://mlsanity.com/paper/2511.02704/) (2025)
- [Almost Sure Convergence Analysis of Differentially Private Stochastic Gradient Methods](https://mlsanity.com/paper/2511.16587/) (2025)
- [Goal inference with Rao-Blackwellized Particle Filters](https://mlsanity.com/paper/2512.09269/) (2025)
- [Almost Sure Convergence Analysis of Stochastic Gradient Methods with Clipping and Additive Noise](https://mlsanity.com/paper/2609.12119/) (2026)

## Abstract (arXiv)

Data-driven systems are gathering increasing amounts of data from users, and sensitive user data requires privacy protections. In some cases, the data gathered is non-numerical or symbolic, and conventional approaches to privacy, e.g., adding noise, do not apply, though such systems still require privacy protections. Accordingly, we present a novel differential privacy framework for protecting trajectories generated by symbolic systems. These trajectories can be represented as words or strings over a finite alphabet. We develop new differential privacy mechanisms that approximate a sensitive word using a random word that is likely to be near it. An offline mechanism is implemented efficiently using a Modified Hamming Distance Automaton to generate whole privatized output words over a finite time horizon. Then, an online mechanism is implemented by taking in a sensitive symbol and generating a randomized output symbol at each timestep. This work is extended to Markov chains to generate differentially private state sequences that a given Markov chain could have produced. Statistical accuracy bounds are developed to quantify the accuracy of these mechanisms, and numerical results validate the accuracy of these techniques for strings of English words.