Optimal Chernoff and Hoeffding Bounds for Finite State Markov Chains

Vrettos Moulos, Venkat Anantharam

This paper develops an optimal Chernoff type bound for the probabilities of large deviations of sums ${\sum }_{k=1}^{n}f(X_k)$ where $f$ is a real-valued function and $(X_k)_{k \in \m…