A simple variance inequality for U-statistics of a Markov chain with applications

We establish a simple variance inequality for U-statistics whose underlying sequence of random variables is an ergodic Markov Chain. The constants in this inequality are explicit and depend on computable bounds on the mixing rate of the Markov Chain. We apply this result to derive the strong law of large numbers for U-statistics of a Markov Chain under conditions which are close to being optimal.