2019-06-25-cherapanamjeri19a.md

abstract	section	title	layout	series	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	publisher	container-title	volume	genre	issued	pdf	extras
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.	contributed	Testing Symmetric Markov Chains Without Hitting	inproceedings	Proceedings of Machine Learning Research	cherapanamjeri19a	0	Testing Symmetric Markov Chains Without Hitting	758	785	758-785	758	false	Cherapanamjeri, Yeshwanth and Bartlett, Peter L.	given family Yeshwanth Cherapanamjeri given family Peter L. Bartlett	2019-06-25		PMLR	Proceedings of the Thirty-Second Conference on Learning Theory	99	inproceedings	date-parts 2019 6 25	http://proceedings.mlr.press/v99/cherapanamjeri19a/cherapanamjeri19a.pdf