Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain

Quentin Berthet, Varun Kanade
Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, PMLR 89:246-255, 2019.

Abstract

We study the problem of hypothesis testing between two discrete distributions, where we only have access to samples after the action of a known reversible Markov chain, playing the role of noise. We derive instance-dependent minimax rates for the sample complexity of this problem, and show how its dependence in time is related to the spectral properties of the Markov chain. We show that there exists a wide statistical window, in terms of sample complexity for hypothesis testing between different pairs of initial distributions. We illustrate these results in several concrete examples.

Cite this Paper

BibTeX
@InProceedings{pmlr-v89-berthet19a, title = {Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain}, author = {Berthet, Quentin and Kanade, Varun}, booktitle = {Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics}, pages = {246--255}, year = {2019}, editor = {Chaudhuri, Kamalika and Sugiyama, Masashi}, volume = {89}, series = {Proceedings of Machine Learning Research}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v89/berthet19a/berthet19a.pdf}, url = {https://proceedings.mlr.press/v89/berthet19a.html}, abstract = {We study the problem of hypothesis testing between two discrete distributions, where we only have access to samples after the action of a known reversible Markov chain, playing the role of noise. We derive instance-dependent minimax rates for the sample complexity of this problem, and show how its dependence in time is related to the spectral properties of the Markov chain. We show that there exists a wide statistical window, in terms of sample complexity for hypothesis testing between different pairs of initial distributions. We illustrate these results in several concrete examples.} }
Endnote
%0 Conference Paper %T Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain %A Quentin Berthet %A Varun Kanade %B Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Masashi Sugiyama %F pmlr-v89-berthet19a %I PMLR %P 246--255 %U https://proceedings.mlr.press/v89/berthet19a.html %V 89 %X We study the problem of hypothesis testing between two discrete distributions, where we only have access to samples after the action of a known reversible Markov chain, playing the role of noise. We derive instance-dependent minimax rates for the sample complexity of this problem, and show how its dependence in time is related to the spectral properties of the Markov chain. We show that there exists a wide statistical window, in terms of sample complexity for hypothesis testing between different pairs of initial distributions. We illustrate these results in several concrete examples.
APA
Berthet, Q. & Kanade, V.. (2019). Statistical Windows in Testing for the Initial Distribution of a Reversible Markov Chain. Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 89:246-255 Available from https://proceedings.mlr.press/v89/berthet19a.html.

Related Material