Directed information

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

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

where ${\displaystyle I(X_{i:1};Y_{i}|Y_{i-1:1})}$ is the conditional mutual information ${\displaystyle 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,[1][2] capacity of discrete memoryless networks with feedback,[3] gambling with causal side information,[4] compression with causal side information,[5] and in real-time control communication settings [6] [7], statistical physics [8].

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 ${\displaystyle n}$ terms and as ${\displaystyle n}$ grows its more and more challenging. There exists algorithms for optimizing the directed information based on Blahut-Arimoto algorithm such as [9] 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 [10] and on empirical parametric distributions [11].

References

1. Massey, James (1990). "Causality, Feedback And Directed Information" (ISITA). CiteSeerX 10.1.1.36.5688. Cite journal requires |journal= (help)
2. Permuter, Haim Henry; Weissman, Tsachy; Goldsmith, Andrea J. (February 2009). "Finite State Channels With Time-Invariant Deterministic Feedback". IEEE Transactions on Information Theory. 55 (2): 644–662. arXiv:cs/0608070. doi:10.1109/TIT.2008.2009849.
3. Kramer, G. (January 2003). "Capacity results for the discrete memoryless network". IEEE Transactions on Information Theory. 49 (1): 4–21. doi:10.1109/TIT.2002.806135.
4. Permuter, Haim H.; Kim, Young-Han; Weissman, Tsachy (June 2011). "Interpretations of Directed Information in Portfolio Theory, Data Compression, and Hypothesis Testing". IEEE Transactions on Information Theory. 57 (6): 3248–3259. arXiv:0912.4872. doi:10.1109/TIT.2011.2136270.
5. Simeone, Osvaldo; Permuter, Haim Henri (June 2013). "Source Coding When the Side Information May Be Delayed". IEEE Transactions on Information Theory. 59 (6): 3607–3618. arXiv:1109.1293. doi:10.1109/TIT.2013.2248192.
6. Charalambous, Charalambos D.; Stavrou, Photios A. (August 2016). "Directed Information on Abstract Spaces: Properties and Variational Equalities". IEEE Transactions on Information Theory. 62 (11): 6019–6052. arXiv:1302.3971. doi:10.1109/TIT.2016.2604846.
7. Tanaka, Takashi; Esfahani, Peyman Mohajerin; Mitter, Sanjoy K. (January 2018). "LQG Control With Minimum Directed Information: Semidefinite Programming Approach". IEEE Transactions on Automatic Control. 63 (1): 37–52. doi:10.1109/TAC.2017.2709618.
8. Vinkler, Dror A; Permuter, Haim H; Merhav, Neri (20 April 2016). "Analogy between gambling and measurement-based work extraction". Journal of Statistical Mechanics: Theory and Experiment. 2016 (4): 043403. arXiv:1404.6788. doi:10.1088/1742-5468/2016/04/043403.
9. Naiss, Iddo; Permuter, Haim H. (January 2013). "Extension of the Blahut–Arimoto Algorithm for Maximizing Directed Information". IEEE Transactions on Information Theory. 59 (1): 204–222. doi:10.1109/TIT.2012.2214202.
10. Jiao, Jiantao; Permuter, Haim H.; Zhao, Lei; Kim, Young-Han; Weissman, Tsachy (October 2013). "Universal Estimation of Directed Information". IEEE Transactions on Information Theory. 59 (10): 6220–6242. arXiv:1201.2334. doi:10.1109/TIT.2013.2267934.
11. Quinn, Christopher J.; Kiyavash, Negar; Coleman, Todd P. (December 2015). "Directed Information Graphs". IEEE Transactions on Information Theory. 61 (12): 6887–6909. arXiv:1204.2003. doi:10.1109/TIT.2015.2478440.