Identity Testing of Reversible Markov Chains

Sela Fried, Geoffrey Wolfer
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:798-817, 2022.

Abstract

We consider the problem of identity testing of Markov chain transition matrices based on a single trajectory of observations under the distance notion introduced by Daskalakis et al. (2018a) and further analyzed by Cherapanamjeri and Bartlett (2019). Both works made the restrictive assumption that the Markov chains under consideration are symmetric. In this work we relax the symmetry assumption and show that it is possible to perform identity testing under the much weaker assumption of reversibility, provided that the stationary distributions of the reference and of the unknown Markov chains are close under a distance notion related to the separation distance. Additionally, we provide intuition on the distance notion of Daskalakis et al. (2018a) by showing how it behaves under several natural operations. In particular, we address some of their open questions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-fried22a, title = { Identity Testing of Reversible Markov Chains }, author = {Fried, Sela and Wolfer, Geoffrey}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {798--817}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/fried22a/fried22a.pdf}, url = {https://proceedings.mlr.press/v151/fried22a.html}, abstract = { We consider the problem of identity testing of Markov chain transition matrices based on a single trajectory of observations under the distance notion introduced by Daskalakis et al. (2018a) and further analyzed by Cherapanamjeri and Bartlett (2019). Both works made the restrictive assumption that the Markov chains under consideration are symmetric. In this work we relax the symmetry assumption and show that it is possible to perform identity testing under the much weaker assumption of reversibility, provided that the stationary distributions of the reference and of the unknown Markov chains are close under a distance notion related to the separation distance. Additionally, we provide intuition on the distance notion of Daskalakis et al. (2018a) by showing how it behaves under several natural operations. In particular, we address some of their open questions. } }
Endnote
%0 Conference Paper %T Identity Testing of Reversible Markov Chains %A Sela Fried %A Geoffrey Wolfer %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-fried22a %I PMLR %P 798--817 %U https://proceedings.mlr.press/v151/fried22a.html %V 151 %X We consider the problem of identity testing of Markov chain transition matrices based on a single trajectory of observations under the distance notion introduced by Daskalakis et al. (2018a) and further analyzed by Cherapanamjeri and Bartlett (2019). Both works made the restrictive assumption that the Markov chains under consideration are symmetric. In this work we relax the symmetry assumption and show that it is possible to perform identity testing under the much weaker assumption of reversibility, provided that the stationary distributions of the reference and of the unknown Markov chains are close under a distance notion related to the separation distance. Additionally, we provide intuition on the distance notion of Daskalakis et al. (2018a) by showing how it behaves under several natural operations. In particular, we address some of their open questions.
APA
Fried, S. & Wolfer, G.. (2022). Identity Testing of Reversible Markov Chains . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:798-817 Available from https://proceedings.mlr.press/v151/fried22a.html.

Related Material