Directed information

The essence of directed information is causal conditioning. The probability of ${\displaystyle y^{n}}$ causally conditioned on ${\displaystyle x^{n}}$ is defined as[5]

${\displaystyle P(x^{n}||y^{n})\triangleq \prod _{i=1}^{n}P(x_{i}|x^{i-1},y^{i})}$.

This is similar to the chain rule for conventional conditioning ${\displaystyle P(x^{n}|y^{n})=\prod _{i=1}^{n}P(x_{i}|x^{i-1},y^{n})}$ except one conditions on "past" and "present" symbols ${\displaystyle y^{i}}$ rather than all symbols ${\displaystyle y^{n}}$. To include "past" symbols only, one can introduce a delay by prepending a constant symbol:

${\displaystyle P(x^{n}||(0,y^{n-1}))\triangleq \prod _{i=1}^{n}P(x_{i}|x^{i-1},y^{i-1})}$.

It is common to abuse notation by writing ${\displaystyle P(x^{n}||y^{n-1})}$ for this expression, although formally all strings should have the same number of symbols.

One may also condition on multiple strings: ${\displaystyle P(x^{n}||y^{n},z^{n})\triangleq \prod _{i=1}^{n}P(x_{i}|x^{i-1},y^{i},z^{i})}$.

A decomposition rule for causal conditioning[1] is

${\displaystyle P(x^{n},y^{n})=P(x^{n}||y^{n-1})P(y^{n}||x^{n})}$.

This rule shows that any product of ${\displaystyle P(x^{n}||y^{n-1}),P(y^{n}||x^{n})}$ gives a joint distribution ${\displaystyle P(x^{n},y^{n})}$.

The causal conditioning probability${\displaystyle P(y^{n}||x^{n})=\prod _{i=1}^{n}P(y_{i}|y^{i-1},x^{i})}$ is a probability vector, i.e.,

${\displaystyle P(y^{n}||x^{n})\geq 0\quad {\text{and}}\quad \sum _{y^{n}}P(y^{n}||x^{n})=1\quad {\text{for all }}(x^{n},y^{n})}$.

Directed Information can be written in terms of causal conditioning:[2]

${\displaystyle I(X^{N}\rightarrow Y^{N})=\mathbf {E} \left[\log {\frac {P(Y^{N}||X^{N})}{P(Y^{N})}}\right]=H(Y^{n})-H(Y^{n}||X^{n})}$.

The relation generalizes to three strings: the directed information flowing from ${\displaystyle X^{n}}$ to ${\displaystyle Y^{n}}$ causally conditioned on ${\displaystyle Z^{n}}$ is

${\displaystyle I(X^{n}\to Y^{n}||Z^{n})=H(Y^{n}||Z^{n})-H(Y^{n}||X^{n},Z^{n})}$.

Estimating and optimizing the directed information is challenging because it has ${\displaystyle n}$ terms where ${\displaystyle n}$ may be large. In many cases, one is interested in optimizing the limiting average, that is, when ${\displaystyle n}$ grows to infinity termed as a multi-letter expression.

Massey's directed information was motivated by Marko's early work (1966) on developing a theory of bidirectional communication.[25][26] Marko's definition of directed transinformation differs slightly from Massey's in that, at time ${\displaystyle n}$, one conditions on past symbols ${\displaystyle X^{n-1},Y^{n-1}}$ only and one takes limits:

${\displaystyle T_{12}=\lim _{n\to \infty }\mathbf {E} \left[-\log {\frac {P(X_{n}|X^{n-1})}{P(X_{n}|X^{n-1},Y^{n-1})}}\right]\quad {\text{and}}\quad T_{21}=\lim _{n\to \infty }\mathbf {E} \left[-\log {\frac {P(Y_{n}|Y^{n-1})}{P(Y_{n}|Y^{n-1},X^{n-1})}}\right].}$

Marko defined several other quantities, including:

• Total information: ${\displaystyle H_{1}=\lim _{n\to \infty }\mathbf {E} \left[-\log P(X_{n}|X^{n-1})\right]}$ and ${\displaystyle H_{2}=\lim _{n\to \infty }\mathbf {E} \left[-\log P(Y_{n}|Y^{n-1})\right]}$
• Free information: ${\displaystyle F_{1}=\lim _{n\to \infty }\mathbf {E} \left[-\log P(X_{n}|X^{n-1},Y^{n-1})\right]}$ and ${\displaystyle F_{2}=\lim _{n\to \infty }\mathbf {E} \left[-\log P(Y_{n}|Y^{n-1},X^{n-1})\right]}$
• Coincidence: ${\displaystyle K=\lim _{n\to \infty }\mathbf {E} \left[-\log {\frac {P(X_{n}|X^{n-1})P(Y_{n}|Y^{n-1})}{P(X_{n},Y_{n}|X^{n-1},Y^{n-1})}}\right].}$

The total information is usually called an entropy rate. Marko showed the following relations for the problems he was interested in:

• ${\displaystyle K=T_{12}+T_{21}}$
• ${\displaystyle H_{1}=T_{12}+F_{1}}$ and ${\displaystyle H_{2}=T_{21}+F_{2}}$

He also defined quantities he called residual entropies:

• ${\displaystyle R_{1}=H_{1}-K=F_{1}-T_{21}}$
• ${\displaystyle R_{2}=H_{2}-K=F_{2}-T_{12}}$

and developed the conservation law ${\displaystyle F_{1}+F_{2}=R_{1}+R_{2}+K=H_{1}+H_{2}-K}$ and several bounds.

Directed information is related to transfer entropy, which is a truncated version of Marko's directed transinformation ${\displaystyle T_{21}}$.

The transfer entropy at time ${\displaystyle i}$ and with memory ${\displaystyle d}$ is

${\displaystyle T_{X\to Y}=I(X_{i-1},\dots ,X_{i-d};Y_{i}|Y_{i-1},\dots ,Y_{i-d}).}$

where one does not include the present symbol ${\displaystyle X_{i}}$ or the past symbols ${\displaystyle X^{i-d-1},Y^{i-d-1}}$ before time ${\displaystyle i-d}$.

Transfer entropy usually assumes stationarity, i.e., ${\displaystyle T_{X\to Y}}$ does not depend on the time ${\displaystyle i}$.