FINITE-LENGTH ANALYSIS ON TAIL PROBABILITY FOR MARKOV CHAIN AND APPLICATION TO SIMPLE HYPOTHESIS TESTING

• 成果类型: Article
• 署名作者: Watanabe, Shun; Hayashi, Masahito
• 署名单位: Tokyo University of Agriculture & Technology; Nagoya University; National University of Singapore
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/16-AAP1216
• 发表日期: 2017
• 页码: 811-845
• 关键词: CENTRAL-LIMIT-THEOREM; exponential-families; additive-functionals; estimators

摘要

Using terminologies of information geometry, we derive upper and lower bounds of the tail probability of the sample mean for the Markov chain with finite state space. Employing these bounds, we obtain upper and lower bounds of the minimum error probability of the type-2 error under the exponential constraint for the error probability of the type-1 error in a simple hypothesis testing for a finite-length Markov chain, which yields the Hoeffding-type bound. For these derivations, we derive upper and lower bounds of cumulant generating function for Markov chain with finite state space. As a byproduct, we obtain another simple proof of central limit theorem for Markov chain with finite state space.