Minimax Testing of Identity to a Reference Ergodic Markov Chain

Geoffrey Wolfer, Aryeh Kontorovich
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:191-201, 2020.

Abstract

We exhibit an efficient procedure for testing, based on a single long state sequence, whether an unknown Markov chain is identical to or e-far from a given reference chain. We obtain nearly matching (up to logarithmic factors) upper and lower sample complexity bounds for our notion of distance, which is based on total variation. Perhaps surprisingly, we discover that the sample complexity depends solely on the properties of the known reference chain and does not involve the unknown chain at all, which is not even assumed to be ergodic.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-wolfer20a, title = {Minimax Testing of Identity to a Reference Ergodic Markov Chain}, author = {Wolfer, Geoffrey and Kontorovich, Aryeh}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {191--201}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/wolfer20a/wolfer20a.pdf}, url = {https://proceedings.mlr.press/v108/wolfer20a.html}, abstract = {We exhibit an efficient procedure for testing, based on a single long state sequence, whether an unknown Markov chain is identical to or e-far from a given reference chain. We obtain nearly matching (up to logarithmic factors) upper and lower sample complexity bounds for our notion of distance, which is based on total variation. Perhaps surprisingly, we discover that the sample complexity depends solely on the properties of the known reference chain and does not involve the unknown chain at all, which is not even assumed to be ergodic.} }
Endnote
%0 Conference Paper %T Minimax Testing of Identity to a Reference Ergodic Markov Chain %A Geoffrey Wolfer %A Aryeh Kontorovich %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-wolfer20a %I PMLR %P 191--201 %U https://proceedings.mlr.press/v108/wolfer20a.html %V 108 %X We exhibit an efficient procedure for testing, based on a single long state sequence, whether an unknown Markov chain is identical to or e-far from a given reference chain. We obtain nearly matching (up to logarithmic factors) upper and lower sample complexity bounds for our notion of distance, which is based on total variation. Perhaps surprisingly, we discover that the sample complexity depends solely on the properties of the known reference chain and does not involve the unknown chain at all, which is not even assumed to be ergodic.
APA
Wolfer, G. & Kontorovich, A.. (2020). Minimax Testing of Identity to a Reference Ergodic Markov Chain. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:191-201 Available from https://proceedings.mlr.press/v108/wolfer20a.html.

Related Material