Testing Symmetric Markov Chains Without Hitting

Yeshwanth Cherapanamjeri, Peter L. Bartlett
Proceedings of the Thirty-Second Conference on Learning Theory, PMLR 99:758-785, 2019.

Abstract

We study the problem of identity testing of symmetric markov chains. In this setting, we are given access to a single trajectory from a markov chain with unknown transition matrix $\bm{Q}$ and the goal is to determine whether $\bm{Q} = \bm{P}$ for some known matrix $\bm{P}$ or $\text{Dist}(\bm{P}, \bm{Q}) \geq \epsilon$ where $\text{Dist}$ is suitably defined. In recent work by Daskalakis et al, 2018, it was shown that it is possible to distinguish between the two cases provided the length of the observed trajectory is at least super-linear in the hitting time of $\bm{P}$ which may be arbitrarily large. In this paper, we propose an algorithm that avoids this dependence on hitting time thus enabling efficient testing of markov chains even in cases where it is infeasible to observe every state in the chain. Our algorithm is based on combining classical ideas from approximation algorithms with techniques for the spectral analysis of markov chains.

Cite this Paper

BibTeX
@InProceedings{pmlr-v99-cherapanamjeri19a, title = {Testing Symmetric Markov Chains Without Hitting}, author = {Cherapanamjeri, Yeshwanth and Bartlett, Peter L.}, booktitle = {Proceedings of the Thirty-Second Conference on Learning Theory}, pages = {758--785}, year = {2019}, editor = {Beygelzimer, Alina and Hsu, Daniel}, volume = {99}, series = {Proceedings of Machine Learning Research}, month = {25--28 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v99/cherapanamjeri19a/cherapanamjeri19a.pdf}, url = {https://proceedings.mlr.press/v99/cherapanamjeri19a.html}, abstract = {We study the problem of identity testing of symmetric markov chains. In this setting, we are given access to a single trajectory from a markov chain with unknown transition matrix $\bm{Q}$ and the goal is to determine whether $\bm{Q} = \bm{P}$ for some known matrix $\bm{P}$ or $\text{Dist}(\bm{P}, \bm{Q}) \geq \epsilon$ where $\text{Dist}$ is suitably defined. In recent work by Daskalakis et al, 2018, it was shown that it is possible to distinguish between the two cases provided the length of the observed trajectory is at least super-linear in the hitting time of $\bm{P}$ which may be arbitrarily large. In this paper, we propose an algorithm that avoids this dependence on hitting time thus enabling efficient testing of markov chains even in cases where it is infeasible to observe every state in the chain. Our algorithm is based on combining classical ideas from approximation algorithms with techniques for the spectral analysis of markov chains.} }
Endnote
%0 Conference Paper %T Testing Symmetric Markov Chains Without Hitting %A Yeshwanth Cherapanamjeri %A Peter L. Bartlett %B Proceedings of the Thirty-Second Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Alina Beygelzimer %E Daniel Hsu %F pmlr-v99-cherapanamjeri19a %I PMLR %P 758--785 %U https://proceedings.mlr.press/v99/cherapanamjeri19a.html %V 99 %X We study the problem of identity testing of symmetric markov chains. In this setting, we are given access to a single trajectory from a markov chain with unknown transition matrix $\bm{Q}$ and the goal is to determine whether $\bm{Q} = \bm{P}$ for some known matrix $\bm{P}$ or $\text{Dist}(\bm{P}, \bm{Q}) \geq \epsilon$ where $\text{Dist}$ is suitably defined. In recent work by Daskalakis et al, 2018, it was shown that it is possible to distinguish between the two cases provided the length of the observed trajectory is at least super-linear in the hitting time of $\bm{P}$ which may be arbitrarily large. In this paper, we propose an algorithm that avoids this dependence on hitting time thus enabling efficient testing of markov chains even in cases where it is infeasible to observe every state in the chain. Our algorithm is based on combining classical ideas from approximation algorithms with techniques for the spectral analysis of markov chains.
APA
Cherapanamjeri, Y. & Bartlett, P.L.. (2019). Testing Symmetric Markov Chains Without Hitting. Proceedings of the Thirty-Second Conference on Learning Theory, in Proceedings of Machine Learning Research 99:758-785 Available from https://proceedings.mlr.press/v99/cherapanamjeri19a.html.

Related Material