  In this paper, we derive upper bounds on generalization errors for deep
neural networks with Markov datasets. These bounds are developed based on
Koltchinskii and Panchenko's approach for bounding the generalization error of
combined classifiers with i.i.d. datasets. The development of new
symmetrization inequalities in high-dimensional probability for Markov chains
is a key element in our extension, where the spectral gap of the infinitesimal
generator of the Markov chain plays a key parameter in these inequalities. We
also propose a simple method to convert these bounds and other similar ones in
traditional deep learning and machine learning to Bayesian counterparts for
both i.i.d. and Markov datasets. Extensions to $m$-order homogeneous Markov
chains such as AR and ARMA models and mixtures of several Markov data services
are given.
