  We extend Hoeffding's lemma to general-state-space and not necessarily
reversible Markov chains. Let $\{X_i\}_{i \ge 1}$ be a stationary Markov chain
with invariant measure $\pi$ and absolute spectral gap $1-\lambda$, where
$\lambda$ is defined as the operator norm of the transition kernel acting on
mean zero and square-integrable functions with respect to $\pi$. Then, for any
bounded functions $f_i: x \mapsto [a_i,b_i]$, the sum of $f_i(X_i)$ is
sub-Gaussian with variance proxy $\frac{1+\lambda}{1-\lambda} \cdot \sum_i
\frac{(b_i-a_i)^2}{4}$. This result differs from the classical Hoeffding's
lemma by a multiplicative coefficient of $(1+\lambda)/(1-\lambda)$, and
simplifies to the latter when $\lambda = 0$. The counterpart of Hoeffding's
inequality for Markov chains immediately follows. Our results assume none of
countable state space, reversibility and time-homogeneity of Markov chains and
cover time-dependent functions with various ranges. We illustrate the utility
of these results by applying them to six problems in statistics and machine
learning.
