Directed information

Directed information (DI) is an information measure that attempts to capture directionality in the flow of information from one random process to another. The definition of DI, in its present form, is due to Massey (1990), but the origins can be traced back to the work of Marko in the 1960s. It is closely related to other causal influence measures, such as transfer entropy and Granger causality. This monograph provides an overview of DI and its main application in information theory, namely, characterizing the capacity of channels with feedback and memory. The authors begin by reviewing the definitions and basic properties of DI, particularly its relation to mutual information, the classic information measure introduced by Shannon. The authors then explain how DI is related to transfer entropy, Granger causality and Pearl’s causality. DI is often used to identify causal relationships in natural processes, such as neural spike trains. Several methods have been developed in the literature to estimate the DI between two processes from time series data. The authors provide a survey, ranging from classic plug-in estimators to modern neural-network-based estimators. Considering the information-theoretic application of channel capacity estimation, the authors describe how such estimators numerically optimize DI rate over a class of joint distributions on input and output processes. A significant part of the monograph is devoted to techniques to compute the feedback capacity of finite-state channels (FSCs). The feedback capacity of a strongly connected FSC is given by a multi-letter expression involving the maximization of the DI rate from the channel input process to the output process, the maximization being performed over the class of causal conditioned probability distributions on the input process. When the FSC is also unifilar, i.e., the next state is given by a time-invariant function of the current state and the new input-output symbol pair, the feedback capacity is the optimal average reward of an appropriately formulated Markov decision process (MDP). This MDP formulation has been exploited to develop several methods to compute exactly, or at least estimate closely, the feedback capacity of a unifilar FSC. This monograph describes these methods, starting from the classic value iteration algorithm, moving on to Q-graph methods, and ending with reinforcement learning algorithms that can handle channels with large input and output alphabets.