Finite-length Analysis on Tail probability for Markov Chain and Application to Simple Hypothesis Testing

Abstract

Using terminologies of information geometry, we derive upper and lower bounds of the tail probability of the sample mean. Employing these bounds, we obtain upper and lower bounds of the minimum error probability of the 2nd kind of error under the exponential constraint for the error probability of the 1st kind of 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. As a byproduct, we obtain another simple proof of central limit theorem for Markov chain.

References in corpus (6)

• Uniform Random Number Generation from Markov Chains: Non-Asymptotic and Asymptotic Analyses
• Information Geometry Approach to Parameter Estimation in Markov Chains
• Two approaches to obtain the strong converse exponent of quantum hypothesis testing for general sequences of quantum states
• A uniform Berry--Esseen theorem on $M$-estimators for geometrically ergodic Markov chains
• Finite-Block-Length Analysis in Classical and Quantum Information Theory
• The exponential family of Markov chains and its information geometry

Cited by in corpus (16)

• Coherence and entanglement measures based on Rényi relative entropies
• Uniform Random Number Generation from Markov Chains: Non-Asymptotic and Asymptotic Analyses
• Non-Asymptotic Classical Data Compression with Quantum Side Information
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory
• Second-order asymptotics for quantum hypothesis testing in settings beyond i.i.d. - quantum lattice systems and more
• Information Geometry of Reversible Markov Chains
• Moderate deviation expansion for fully quantum tasks
• Parallelization of Adaptive Quantum Channel Discrimination in the Non-Asymptotic Regime
• Universal channel coding for general output alphabet
• Asymptotic Properties for Markovian Dynamics in Quantum Theory and General Probabilistic Theories
• Information Geometry Approach to Parameter Estimation in Hidden Markov Models
• Moderate Deviation Analysis for Classical-Quantum Channels and Quantum Hypothesis Testing
• Second Order Analysis for Joint Source-Channel Coding with Markovian Source
• Asymptotic and Non-Asymptotic Analysis for Hidden Markovian Process with Quantum Hidden System
• Local Equivalence Problem in Hidden Markov Model
• Optimal Chernoff and Hoeffding Bounds for Finite State Markov Chains