The big-O Problem for Labelled Markov Chains

Given two labelled Markov chains, consider the problem of whether one is big-O of the other. More concretely, the problem asks whether the probability of every finite word in the first chain is smaller than some constant multiple of the probability in the second. We show that the problem is, in general, undecidable. Even when it is known one is big-O of the other, the problem of finding or approximating the constant in the big-O is also undecidable. Our main result shows the big-O problem is coNP-complete for unlabelled Markov chains (i.e. when the alphabet consists of a single character). The problem can be restated as a ratio total variation distance, which instead of finding the maximum difference between the probabilities of any two events, finds the maximum ratio between the probabilities of any two events. The problem has application to ε-differential privacy, for which the constant of the big-O notation is exactly exp(ε). Joint work with Dmitry Chistikov, Stefan Kiefer and Andrzej Murawski.

Authors

• David Purser.

Keywords

No keywords are indexed for this paper.