Directed information

Directed information, $I(X^{n}\to Y^{n})$, is a measure of information theory that measures the amount of information that flows from the process $X^{n}$ to $Y^{n}$, where $X^{n}$ denotes the vector $X_{1},X_{2},...,X_{n}$ and $Y^{n}$ denotes $Y_{1},Y_{2},...,Y_{n}$. The term directed information was coined by James Massey and is defined as

$I(X^{n}\to Y^{n})=\sum _{i=1}^{n}I(X_{i:1};Y_{i}|Y_{i-1:1})$,

where $I(X_{i:1};Y_{i}|Y_{i-1:1})$ is the conditional mutual information $I(X_{1},X_{2},...,X_{i};Y_{i}|Y_{1},Y_{2},...,Y_{i-1})$.

The Directed information has many applications in problems where causality plays an important role such as capacity of channel with feedback, capacity of discrete memoryless networks with feedback, gambling with causal side information, compression with causal side information, and in real-time control communication settings , statistical physics .

Estimation and Optimization of Directed Information

Estimating and optimizing the directed information is challenging because it is an expression of multi-letter, namely, it contains $n$ terms and as $n$ grows its more and more challenging. There exists algorithms for optimizing the directed information based on Blahut-Arimoto algorithm such as where the main idea is to start with the last element of the directed information and go backward. For estimation there exists an algorithm based on context tree weight and on empirical parametric distributions .