The term directed information was coined by James Massey and is defined as[1] where
is the conditional mutual information
Directed information has applications to problems where causality plays an important role such as the capacity of channels with feedback,[1][2][3][4] capacity of discrete memoryless networks,[5] capacity of networks with in-block memory,[6] gambling with causal side information,[7] compression with causal side information,[8] real-time control communication settings,[9][10] and statistical physics.
[11] The essence of directed information is causal conditioning.
is defined as[5] This is similar to the chain rule for conventional conditioning
except one conditions on "past" and "present" symbols
To include "past" symbols only, one can introduce a delay by prepending a constant symbol: It is common to abuse notation by writing
for this expression, although formally all strings should have the same number of symbols.
The causally conditioned entropy is defined as:[2] Similarly, one may causally condition on multiple strings and write
The causal conditioning probability
is a probability vector, i.e., Directed Information can be written in terms of causal conditioning:[2] The relation generalizes to three strings: the directed information flowing from
is This law, established by James Massey and his son Peter Massey,[12] gives intuition by relating directed information and mutual information.
, the following equality holds: Two alternative forms of this law are[2][13] where
Estimating and optimizing the directed information is challenging because it has
In many cases, one is interested in optimizing the limiting average, that is, when
grows to infinity termed as a multi-letter expression.
Estimating directed information from samples is a hard problem since the directed information expression does not depend on samples but on the joint distribution
There are several algorithms based on context tree weighting[14] and empirical parametric distributions[15] and using long short-term memory.
There are algorithms to optimize the directed information based on the Blahut-Arimoto,[17] Markov decision process,[18][19][20][21][22] Recurrent neural network,[16] Reinforcement learning.
[24][25][22] For the Blahut-Arimoto algorithm,[17] the main idea is to start with the last mutual information of the directed information expression and go backward.
For the Markov decision process,[18][19][20][21] the main ideas is to transform the optimization into an infinite horizon average reward Markov decision process.
For a Recurrent neural network,[16] the main idea is to model the input distribution using a Recurrent neural network and optimize the parameters using Gradient descent.
For Reinforcement learning,[23] the main idea is to solve the Markov decision process formulation of the capacity using Reinforcement learning tools, which lets one deal with large or even continuous alphabets.
Massey's directed information was motivated by Marko's early work (1966) on developing a theory of bidirectional communication.
[26][27] Marko's definition of directed transinformation differs slightly from Massey's in that, at time
, one conditions on past symbols
only and one takes limits: Marko defined several other quantities, including: The total information is usually called an entropy rate.
Marko showed the following relations for the problems he was interested in: He also defined quantities he called residual entropies: and developed the conservation law
Directed information is related to transfer entropy, which is a truncated version of Marko's directed transinformation
Transfer entropy usually assumes stationarity, i.e.,