  We study finite-length bounds for source coding with side information for
Markov sources and channel coding for channels with conditional Markovian
additive noise. For this purpose, we propose two criteria for finite-length
bounds. One is the asymptotic optimality and the other is the efficient
computability of the bound. Then, we derive finite-length upper and lower
bounds for coding length in both settings so that their computational
complexity is efficient. To discuss the first criterion, we derive the large
deviation bounds, the moderate deviation bounds, and second order bounds for
these two topics, and show that these finite-length bounds achieves the
asymptotic optimality in these senses. For this discussion, we introduce
several kinds of information measure for transition matrices.
