656 IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. IT-33, NO. 5, SEPTEMBER 1987 Ergodicity of Markov Channels ROBERT M. GRAY, FELLOW, IEEE, MAR1 0. DUNHAM, MEMBER, IEEE, AND R. I. GOBBI Abstract -A Markov channel is a discrete information channel that includes as special cases the finite state channels and finite state codes of information theory. Kieffer and Rahe proved that one-sided and two-sided Markov channels have the following property: If the input source to a Markov channel is asymptotically mean stationary (AMS), then so is the resulting input-output process and hence the ergodic theorem and the Shannon-McMillan-Breiman theorem hold for the input-output process. Kieffer and Rahe also provided a sufficient condition for any AMS ergodic source to yield an AMS ergodic input-output process. New conditions for a Markov channel to have this ergodicity property are presented and discussed here. Several relations are developed among various classes of channels, including weakly ergodic, indecomposable, and strongly mixing channels. Some connections between Markov channels and the theory of nonhomogeneous Markov chains are also discussed. G IVEN AN INFORMATION SOURCE (a discrete- time random process) and a noisy channel (essentially a regular conditional probability measure describing a probability measure on output sequences given an input sequence), information about the source can be communi- cated to a receiver by first encoding the source sequence into a channel input sequence and decoding the channel output sequence into a reproduction sequence observed by the receiver. Assume that we have some measure of the quality of the reproduction sequence, that is, how well it approximates the original source sequence. The coding theorems of information theory quantify the theoretically optimum performance that can be achieved using the given source and given channel with any encoder and decoder within some constrained class, where “optimum” means that the system has the minimum possible average distor- tion. The design algorithms of information theory are methods for actually designing codes that work well, ideally not too badly in comparison with the theoretical optimum. The proofs of coding theorems rest primarily on the ergodic theorem and on the Shannon-McMillan- Breiman theorem. They also generally require that the appropriate sample averages converge to constants and Manuscript received April 17, 1986; revised December 8, 1986. This paper was presented in part at the IEEE International Symposium on Information Theory, Brighton, England, June 23-28, 1985. This research was partially supported by the National Science Foundation under Grant ECS83-17981. R. M. Gray is with the Information Systems Laboratory, Stanford University, Stanford, CA 94305, USA. M. 0. Dunham is with the Department of Computer Science and Electrical Engineering, Boston University, Boston, MA 02215, USA. R. L. Gobbi is with Lockheed Missiles and Space Co., Sunnyvale, CA 94806, USA. IEEE Log Number 8613567. hence that the underlying system be ergodic. (The proofs for nonergodic systems generally combine the ergodic proof with the ergodic decomposition). In addition, proofs of the convergence of some code design algorithms based on long training sequences of actual data also rest on the ergodic theorem. Hence it is of interest to know when communica- tion system models satisfy the conditions for an ergodic theorem and the Shannon-McMillan-Breiman theorem. Stationarity and block stationarity (stationarity of successive blocks of fixed size) have long been known to be a sufficient condition for these results, but the finite state channels and the finite state codes introduced by Shannon [14] do not generally meet these conditions. For example, if the process begins at time 0 in a particular state, then the channel or code may exhibit initial transients and hence not be stationary. Partially as a result, coding theo- rems for finite state channels have proved difficult, relying on the special properties of Markov chains, and the stationarity and ergodicity properties of finite state codes have been little developed. Gray and Kieffer [6] showed that a necessary and sufficient condition for a process to have an ergodic theorem is that it be asymptotically mean stationary (AMS) and that an AMS process satisfies the Shannon-McMillan-Breiman theorem. A channel is said to be AMS if connecting an AMS source or input process to the channel results in an AMS input-output process. Kieffer and Rahe [9] introduced a generalization of both finite state channels and finite state codes called a Markov channel and showed that such channels are AMS. An AMS channel is said to be ergodic if connecting any AMS ergodic source to the channel yields an AMS ergodic input-output process. Kieffer and Rahe showed that a sufficient condition for a Markov channel to be ergodic is that it be indecomposable in a sense similar to that of Blackwell, Breiman, and Thomasian [2]. Unfortunately, however, this condition is too strong for some applications. For example, in design studies of finite state codes many examples have been found that are not indecomposable, yet they appear to yield ergodic processes. In this paper we develop and compare several sufficient conditions for Markov channels to be ergodic. The prin- cipal result focuses on channels whose output forms a weakly ergodic nonhomogeneous Markov chain as in Hajnal [7]. A superficially similar result was recently ob- tained for a very different application-proving exponen- tial convergence of adaptive algorithms-by Shi and Kozin [15] using results of Furstenberg and Kesten [4] on prod- ucts of random sequences of matrices. Additional results focus on the relations among weakly ergodic channels and OOlS-9448/87/0900-0656$01.00 01987 IEEEGRAY et d: ERGODICITY OF MARKOV CHANNELS various types of indecomposable channels. Most notably, we show that weakly ergodic Markov channels in the sense of Hajnal are equivalent to strongly mixing channels in the sense of Adler [l]. The results developed here