  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 \mathbb{Z}_{\ge 0}}$ is a finite state Markov chain
with an arbitrary initial distribution and an irreducible transition
probability matrix satisfying a mild assumption on its positivity pattern,
related to the function $f$ being considered. The novelty lies in this being a
non-asymptotic finite sample bound. Further, our bound is optimal in the large
deviations sense, attaining a constant prefactor and an exponential decay with
the optimal large deviations rate. Moreover, through a Pinsker type inequality
and a Hoeffding type lemma, we are able to loosen up our Chernoff type bound to
a Hoeffding type bound and reveal the sub-Gaussian nature of the sums. Finally,
under the same mild assumption on the positivity pattern of the transition
probability matrix, we prove a uniform multiplicative ergodic theorem for the
exponential family of tilted transition probability matrices corresponding to
$f$.
