Perfect Privacy and Strong Stationary Times for Markovian Sources
This work addresses privacy protection for data generated by Markov chains, offering an incremental improvement in utility for applications like secure data sharing.
The paper tackles the problem of sharing correlated data under perfect privacy constraints using redaction mechanisms, showing that both window-based and sequential redaction schemes achieve optimal distortion while redacting only a constant average number of data points, independent of data length N.
We consider the problem of sharing correlated data under a perfect information-theoretic privacy constraint. We focus on redaction (erasure) mechanisms, in which data are either withheld or released unchanged, and measure utility by the average cardinality of the released set, equivalently, the expected Hamming distortion. Assuming the data are generated by a finite time-homogeneous Markov chain, we study the protection of the initial state while maximizing the amount of shared data. We establish a connection between perfect privacy and window-based redaction schemes, showing that erasing data up to a strong stationary time preserves privacy under suitable conditions. We further study an optimal sequential redaction mechanism and prove that it admits an equivalent window interpretation. Interestingly, we show that both mechanisms achieve the optimal distortion while redacting only a constant average number of data points, independent of the data length~$N$.