Sequential Necessary and Sufficient Conditions for Capacity Achieving Distributions of Channels with Memory and Feedback

We derive sequential necessary and sufficient conditions for any channel input conditional distribution ${\cal P}{0,n}\triangleq{P{X_t|X^{t-1},Y^{t-1}}:~t=0,\ldots,n}$ to maximize the finite-time horizon directed information defined by $$C_{X^n\to Y^n}^{FB}\triangleq \underset{{\mathcal{P}}_{0,n}}{\sup }I(X^n\to Y^n),I(X^n\to Y^n)=\sum _{t=0}^{n}I(X^t;Y_t\mathrm{\mid }{Y}^{t-1})$$ for channel distributions $\{P_{Y_t\mathrm{\mid }{Y}^{t-1},X_t}:t=0,\dots ,n\}$ and $\{P_{Y_t\mathrm{\mid }{Y}_{t-M}^{t-1},X_t}:t=0,\dots ,n\}$, where $Y^t\triangleq \{Y_0,\dots ,Y_t\}$ and $X^t\triangleq \{X_0,\dots ,X_t\}$ are the channel input and output random processes, and $M$ is a finite nonnegative integer. \noi We apply the necessary and sufficient conditions to application examples of time-varying channels with memory and we derive recursive closed form expressions of the optimal distributions, which maximize the finite-time horizon directed information. Further, we derive the feedback capacity from the asymptotic properties of the optimal distributions by investigating the limit $$C_{X^{\mathrm{\infty }}\to Y^{\mathrm{\infty }}}^{FB}\triangleq \underset{n⟶\mathrm{\infty }}{\lim }\frac{1}{n+1}{C}_{X^n\to Y^n}^{FB}$$ without any 'a priori assumptions, such as, stationarity, ergodicity or irreducibility of the channel distribution. The necessary and sufficient conditions can be easily extended to a variety of channels with memory, beyond the ones considered in this paper.