{{context|date=September 2016}} '''Directed information''' is an information theory measure that quantifies the information flow from the random string <math>X^n = (X_1,X_2,\dots,X_n)</math> to the random string <math>Y^n = (Y_1,Y_2,\dots,Y_n)</math>. The term ''directed information'' was coined by James Massey and is defined as<ref name="Massey 1990">{{cite conference |last1=Massey |first1=James |title=Causality, Feedback And Directed Information |book-title=Proceedings 1990 International Symposium on Information Theory and its Applications, Waikiki, Hawaii, Nov. 27-30, 1990 |date=1990}}</ref> :<math>I(X^n\to Y^n) \triangleq \sum_{i=1}^n I(X^i;Y_i|Y^{i-1})</math> where <math>I(X^{i};Y_i|Y^{i-1})</math> is the conditional mutual information <math>I(X_1,X_2,...,X_{i};Y_i|Y_1,Y_2,...,Y_{i-1})</math>.
Directed information has applications to problems where causality plays an important role such as the capacity of channels with feedback,<ref name="Massey 1990"/><ref name="Kramer 1998">{{cite thesis |type=Doctoral |last=Kramer |first=Gerhard |date=1998 |title=Directed information for channels with feedback |doi=10.3929/ethz-a-001988524 |publisher=ETH Zurich |hdl=20.500.11850/143796 |language=en}}</ref><ref>{{cite thesis |type=Doctoral |last=Tatikonda |first=Sekhar Chandra |date=2000 |title=Control under communication constraints |url=https://dspace.mit.edu/handle/1721.1/16755 |publisher=Massachusetts Institute of Technology|hdl=1721.1/16755 }}</ref><ref name="2008.2009849">{{cite journal |last1=Permuter |first1=Haim Henry|last2=Weissman|first2=Tsachy|last3=Goldsmith |first3=Andrea J.|title=Finite State Channels With Time-Invariant Deterministic Feedback|journal=IEEE Transactions on Information Theory |date=February 2009 |volume=55|issue=2 |pages=644–662 |doi=10.1109/TIT.2008.2009849|arxiv=cs/0608070|bibcode=2009ITIT...55..644P |s2cid=13178}}</ref> capacity of discrete memoryless networks,<ref name="Kramer 2003">{{cite journal |last1=Kramer |first1=G. |title=Capacity results for the discrete memoryless network|journal=IEEE Transactions on Information Theory|date=January 2003|volume=49|issue=1 |pages=4–21|doi=10.1109/TIT.2002.806135 |bibcode=2003ITIT...49....4K }}</ref> capacity of networks with in-block memory,<ref>{{cite journal |last1=Kramer |first1=Gerhard |title=Information Networks With In-Block Memory |journal=IEEE Transactions on Information Theory |date=April 2014 |volume=60 |issue=4 |pages=2105–2120 |doi=10.1109/TIT.2014.2303120|arxiv=1206.5389 |bibcode=2014ITIT...60.2105K |s2cid=16382644 }}</ref> gambling with causal side information,<ref>{{cite journal|last1=Permuter|first1=Haim H.|last2=Kim |first2=Young-Han|last3=Weissman |first3=Tsachy|title=Interpretations of Directed Information in Portfolio Theory, Data Compression, and Hypothesis Testing|journal=IEEE Transactions on Information Theory|date=June 2011|volume=57|issue=6 |pages=3248–3259|doi=10.1109/TIT.2011.2136270|arxiv=0912.4872 |bibcode=2011ITIT...57.3248P |s2cid=11722596}}</ref> compression with causal side information,<ref>{{cite journal|last1=Simeone|first1=Osvaldo |last2=Permuter|first2=Haim Henri|title=Source Coding When the Side Information May Be Delayed |journal=IEEE Transactions on Information Theory|date=June 2013 |volume=59|issue=6|pages=3607–3618 |doi=10.1109/TIT.2013.2248192|arxiv=1109.1293|bibcode=2013ITIT...59.3607S |s2cid=3211485}}</ref> real-time control communication settings,<ref>{{Cite journal |last1=Sabag |first1=Oron |last2=Tian |first2=Peida |last3=Kostina |first3=Victoria |last4=Hassibi |first4=Babak |date=September 2023 |title=Reducing the LQG Cost With Minimal Communication |journal=IEEE Transactions on Automatic Control |volume=68 |issue=9 |pages=5258–5270 |doi=10.1109/TAC.2022.3220511 |issn=0018-9286|arxiv=2109.12246 |bibcode=2023ITAC...68.5258S }}</ref><ref>{{cite journal |last1=Charalambous|first1=Charalambos D. |last2=Stavrou |first2=Photios A.|title=Directed Information on Abstract Spaces: Properties and Variational Equalities |journal=IEEE Transactions on Information Theory|date=August 2016|volume=62|issue=11|pages=6019–6052 |doi=10.1109/TIT.2016.2604846 |arxiv=1302.3971|bibcode=2016ITIT...62.6019C |s2cid=8107565}}</ref><ref>{{cite journal |last1=Tanaka |first1=Takashi |last2=Esfahani |first2=Peyman Mohajerin |last3=Mitter |first3=Sanjoy K. |title=LQG Control With Minimum Directed Information: Semidefinite Programming Approach |journal=IEEE Transactions on Automatic Control |date=January 2018 |volume=63 |issue=1 |pages=37–52 |doi=10.1109/TAC.2017.2709618 |s2cid=1401958 |arxiv=1510.04214 |bibcode=2018ITAC...63...37T |url=http://resolver.tudelft.nl/uuid:d9db1c11-fbfd-4c0c-b66f-f341b49fa61a}}</ref> and statistical physics.<ref>{{cite journal |last1=Vinkler |first1=Dror A |last2=Permuter |first2=Haim H |last3=Merhav |first3=Neri |title=Analogy between gambling and measurement-based work extraction |journal=Journal of Statistical Mechanics: Theory and Experiment |date=20 April 2016 |volume=2016 |issue=4 |article-number=043403 |doi=10.1088/1742-5468/2016/04/043403 |arxiv=1404.6788 |bibcode=2016JSMTE..04.3403V |s2cid=124719237}}</ref>
== Causal conditioning== The essence of directed information is '''causal conditioning'''. The probability of <math>x^n</math> causally conditioned on <math>y^n</math> is defined as<ref name="Kramer 2003"/> :<math>P(x^n||y^n) \triangleq \prod_{i=1}^n P(x_i|x^{i-1},y^{i})</math>. This is similar to the chain rule for conventional conditioning <math>P(x^n|y^n) = \prod_{i=1}^n P(x_i|x^{i-1},y^{n})</math> except one conditions on "past" and "present" symbols <math>y^{i}</math> rather than all symbols <math>y^{n}</math>. To include "past" symbols only, one can introduce a delay by prepending a constant symbol: :<math>P(x^n||(0,y^{n-1})) \triangleq \prod_{i=1}^n P(x_i|x^{i-1},y^{i-1})</math>. It is common to abuse notation by writing <math>P(x^n||y^{n-1})</math> for this expression, although formally all strings should have the same number of symbols.
One may also condition on multiple strings: <math>P(x^n||y^n,z^n) \triangleq \prod_{i=1}^n P(x_i|x^{i-1},y^{i},z^{i})</math>.
===Causally conditioned entropy=== The '''causally conditioned entropy''' is defined as:<ref name="Kramer 1998"/> :<math>H(X^n || Y^n)=\mathbf E\left[ -\log {P(X^n||Y^n)} \right]=\sum_{i=1}^n H(X_{i}|X^{i-1},Y^{i})</math> Similarly, one may causally condition on multiple strings and write <math>H(X^n || Y^n,Z^n)=\mathbf E\left[ -\log {P(X^n||Y^n,Z^n)} \right]</math>.
==Properties== A decomposition rule for causal conditioning<ref name="Massey 1990"/> is :<math>P(x^n, y^n) = P(x^n||y^{n-1}) P(y^n||x^n)</math>. This rule shows that any product of <math>P(x^n||y^{n-1}), P(y^n||x^n)</math> gives a joint distribution <math>P(x^n, y^n)</math>.
The causal conditioning probability<math>P(y^n||x^n) = \prod_{i=1}^n P(y_i|y^{i-1},x^{i})</math> is a probability vector, i.e., :<math>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)</math>.
Directed Information can be written in terms of causal conditioning:<ref name="Kramer 1998"/> :<math>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)</math>.
The relation generalizes to three strings: the directed information flowing from <math>X^n</math> to <math>Y^n</math> causally conditioned on <math>Z^n</math> is :<math>I(X^n\to Y^n || Z^n) = H(Y^n || Z^n)- H(Y^n || X^n, Z^n)</math>.
===Conservation law of information=== This law, established by James Massey and his son Peter Massey,<ref>{{cite book |last1=Massey |first1=J.L. |last2=Massey |first2=P.C. |title=Proceedings. International Symposium on Information Theory, 2005. ISIT 2005 |chapter=Conservation of mutual and directed information |date=September 2005 |pages=157–158 |doi=10.1109/ISIT.2005.1523313|isbn=0-7803-9151-9 |s2cid=38053218 }}</ref> gives intuition by relating directed information and mutual information. The law states that for any <math>X^n, Y^n </math>, the following equality holds: :<math>I(X^n;Y^n)= I(X^n \to Y^n)+I(Y^{n-1} \to X^n).</math>
Two alternative forms of this law are<ref name="Kramer 1998"/><ref>{{cite journal |last1=Amblard |first1=Pierre-Olivier |last2=Michel |first2=Olivier |title=The Relation between Granger Causality and Directed Information Theory: A Review |journal=Entropy |date=28 December 2012 |volume=15 |issue=1 |pages=113–143 |doi=10.3390/e15010113 |arxiv=1211.3169 |bibcode=2012Entrp..15..113A |doi-access=free }}</ref> :<math>I(X^n;Y^n) = I(X^n \to Y^n) + I(Y^n \to X^n) - I(X^n \leftrightarrow Y^n)</math> :<math>I(X^n;Y^n) = I(X^{n-1} \to Y^n) + I(Y^{n-1} \to X^n) + I(X^n \leftrightarrow Y^n)</math> where <math>I(X^n \leftrightarrow Y^n) = \sum_{i=1}^n I(X_i ; Y_i | X^{i-1}, Y^{i-1})</math>.
== Estimation and optimization == Estimating and optimizing the directed information is challenging because it has <math>n</math> terms where <math>n</math> may be large. In many cases, one is interested in optimizing the limiting average, that is, when <math>n</math> grows to infinity termed as a multi-letter expression.
===Estimation=== Estimating directed information from samples is a hard problem since the directed information expression does not depend on samples but on the joint distribution <math>\{P(x_i,y_i|x^{i-1},y^{i-1})_{i=1}^n\}</math> which may be unknown. There are several algorithms based on context tree weighting<ref>{{cite journal |last1=Jiao |first1=Jiantao |last2=Permuter |first2=Haim H. |last3=Zhao |first3=Lei |last4=Kim |first4=Young-Han |last5=Weissman |first5=Tsachy |title=Universal Estimation of Directed Information |journal= IEEE Transactions on Information Theory|date=October 2013 |volume=59 |issue=10 |pages=6220–6242 |doi=10.1109/TIT.2013.2267934 |arxiv=1201.2334 |bibcode=2013ITIT...59.6220J |s2cid=10855063 }}</ref> and empirical parametric distributions<ref>{{cite journal |last1=Quinn |first1=Christopher J. |last2=Kiyavash |first2=Negar |last3=Coleman |first3=Todd P. |title=Directed Information Graphs |journal= IEEE Transactions on Information Theory|date=December 2015 |volume=61 |issue=12 |pages=6887–6909 |doi=10.1109/TIT.2015.2478440|arxiv=1204.2003 |bibcode=2015ITIT...61.6887Q |s2cid=3121664}}</ref> and using long short-term memory.<ref name="2003.04179"/>
===Optimization=== Maximizing directed information is a fundamental problem in information theory. For example, given the channel distributions <math>\{P(y_i|x^{i},y^{i-1}\}_{i=1}^n)</math>, the objective might be to optimize <math> I(X^n\to Y^n)</math> over the channel input distributions <math>\{P(x_i|x^{i-1},y^{i-1}\}_{i=1}^n)</math>.
There are algorithms to optimize the directed information based on the Blahut-Arimoto,<ref name="1012.5071">{{cite journal |last1=Naiss |first1=Iddo |last2=Permuter |first2=Haim H. |title=Extension of the Blahut–Arimoto Algorithm for Maximizing Directed Information |journal= IEEE Transactions on Information Theory|date=January 2013 |volume=59 |issue=1 |pages=204–222 |doi=10.1109/TIT.2012.2214202 |s2cid=3115749 |arxiv=1012.5071 |bibcode=2013ITIT...59..204N }}</ref> Markov decision process,<ref name="2008.924681">{{cite journal |last1=Permuter |first1=Haim |last2=Cuff |first2=Paul |last3=Van Roy |first3=Benjamin |last4=Weissman |first4=Tsachy |title=Capacity of the Trapdoor Channel With Feedback |journal= IEEE Transactions on Information Theory|date=July 2008 |volume=54 |issue=7 |pages=3150–3165 |doi=10.1109/TIT.2008.924681|arxiv=cs/0610047 |bibcode=2008ITIT...54.3150P |s2cid=1265}}</ref><ref name="1205.4674">{{cite journal |last1=Elishco |first1=Ohad |last2=Permuter |first2=Haim |title=Capacity and Coding for the Ising Channel With Feedback |journal= IEEE Transactions on Information Theory|date=September 2014 |volume=60 |issue=9 |pages=5138–5149 |doi=10.1109/TIT.2014.2331951 |arxiv=1205.4674 |bibcode=2014ITIT...60.5138E |s2cid=9761759}}</ref><ref name="2015.2495239">{{cite journal |last1=Sabag |first1=Oron |last2=Permuter |first2=Haim H. |last3=Kashyap |first3=Navin |title=The Feedback Capacity of the Binary Erasure Channel With a No-Consecutive-Ones Input Constraint |journal= IEEE Transactions on Information Theory|date=January 2016 |volume=62 |issue=1 |pages=8–22 |doi=10.1109/TIT.2015.2495239 |bibcode=2016ITIT...62....8S |s2cid=476381}}</ref><ref name="1712.02690">{{cite journal |last1=Peled |first1=Ori |last2=Sabag |first2=Oron |last3=Permuter |first3=Haim H. |title=Feedback Capacity and Coding for the $(0,k)$ -RLL Input-Constrained BEC |journal= IEEE Transactions on Information Theory|date=July 2019 |volume=65 |issue=7 |pages=4097–4114 |doi=10.1109/TIT.2019.2903252 |arxiv=1712.02690 |s2cid=86582654}}</ref><ref name="Shemuel_fsc_enc_2024">{{cite journal |last1=Shemuel |first1=Eli |last2=Sabag |first2=Oron |last3=Permuter |first3=Haim H. |title=Finite-State Channels With Feedback and State Known at the Encoder |journal=IEEE Transactions on Information Theory |date=March 2024 |volume=70 |issue=3 |pages=1610–1628 |doi=10.1109/TIT.2023.3336939|arxiv=2212.12886 |bibcode=2024ITIT...70.1610S }}</ref> Recurrent neural network,<ref name="2003.04179">{{cite book |last1=Aharoni |first1=Ziv |last2=Tsur |first2=Dor |last3=Goldfeld |first3=Ziv |last4=Permuter |first4=Haim Henry |title=2020 IEEE International Symposium on Information Theory (ISIT) |chapter=Capacity of Continuous Channels with Memory via Directed Information Neural Estimator |arxiv=2003.04179 |date=June 2020 |pages=2014–2019 |doi=10.1109/ISIT44484.2020.9174109 |isbn=978-1-7281-6432-8 |s2cid=212634151}}</ref> Reinforcement learning.<ref name="2008.07983">{{cite arXiv |last1=Aharoni |first1=Ziv |last2=Sabag |first2=Oron |last3=Permuter |first3=Haim Henri |title=Reinforcement Learning Evaluation and Solution for the Feedback Capacity of the Ising Channel with Large Alphabet |date=18 August 2020 |class=cs.IT |eprint=2008.07983}}</ref> and Graphical methods (the Q-graphs).<ref>{{cite journal |last1=Sabag |first1=Oron |last2=Permuter |first2=Haim Henry |last3=Pfister |first3=Henry |title=A Single-Letter Upper Bound on the Feedback Capacity of Unifilar Finite-State Channels |journal= IEEE Transactions on Information Theory|date= March 2017 |volume=63 |issue=3 |pages=1392–1409|doi=10.1109/TIT.2016.2636851 |arxiv=1604.01878 |bibcode=2017ITIT...63.1392S |s2cid=3259603 }}</ref><ref>{{cite journal |last1=Sabag |first1=Oron |last2= Huleihel |first2= Bashar |last3=Permuter |first3=Haim Henry |title= Graph-Based Encoders and their Performance for Finite-State Channels with Feedback |journal= IEEE Transactions on Communications|date= 2020 |volume= 68 |issue=4 |pages=2106–2117 |doi=10.1109/TCOMM.2020.2965454 |arxiv=1907.08063 |bibcode=2020ITCom..68.2106S |s2cid=197544824}}</ref><ref name="Shemuel_fsc_enc_2024" /> For the Blahut-Arimoto algorithm,<ref name="1012.5071"/> the main idea is to start with the last mutual information of the directed information expression and go backward. For the Markov decision process,<ref name="2008.924681"/><ref name="1205.4674"/><ref name="2015.2495239"/><ref name="1712.02690"/> the main ideas is to transform the optimization into an infinite horizon average reward Markov decision process. For a Recurrent neural network,<ref name="2003.04179"/> the main idea is to model the input distribution using a Recurrent neural network and optimize the parameters using Gradient descent. For Reinforcement learning,<ref name="2008.07983"/> 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.
== Marko's theory of bidirectional communication == Massey's directed information was motivated by Marko's early work (1966) on developing a theory of bidirectional communication.<ref>{{cite journal |last1=Marko |first1=Hans |title=Die Theorie der bidirektionalen Kommunikation und ihre Anwendung auf die Nachrichtenübermittlung zwischen Menschen (Subjektive Information) |journal=Kybernetik |date=1 September 1966 |volume=3 |issue=3 |pages=128–136 |doi=10.1007/BF00288922 |pmid=5920460 |s2cid=33275199 |url=https://link.springer.com/article/10.1007/BF00288922 |language=de |issn=1432-0770|url-access=subscription }}</ref><ref>{{cite journal |last1=Marko |first1=H. |title=The Bidirectional Communication Theory--A Generalization of Information Theory |journal=IEEE Transactions on Communications |date=December 1973 |volume=21 |issue=12 |pages=1345–1351 |doi=10.1109/TCOM.1973.1091610|bibcode=1973ITCom..21.1345M |s2cid=51664185 }}</ref> Marko's definition of '''directed transinformation''' differs slightly from Massey's in that, at time <math>n</math>, one conditions on past symbols <math>X^{n-1},Y^{n-1}</math> only and one takes limits: :<math>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].</math> Marko defined several other quantities, including: * Total information: <math>H_{1} = \lim_{n \to \infty} \mathbf E\left[ -\log P(X_{n}|X^{n-1}) \right]</math> and <math>H_{2} = \lim_{n \to \infty} \mathbf E\left[ -\log P(Y_{n}|Y^{n-1}) \right]</math> * Free information: <math>F_{1} = \lim_{n \to \infty} \mathbf E\left[ -\log P(X_{n}|X^{n-1},Y^{n-1}) \right]</math> and <math>F_{2} = \lim_{n \to \infty} \mathbf E\left[ -\log P(Y_{n}|Y^{n-1},X^{n-1}) \right]</math> * Coincidence: <math>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].</math> The total information is usually called an entropy rate. Marko showed the following relations for the problems he was interested in: * <math>K = T_{12}+T_{21}</math> * <math>H_{1} = T_{12}+F_{1}</math> and <math>H_{2} = T_{21}+F_{2}</math> He also defined quantities he called ''residual entropies'': * <math>R_{1} = H_{1}-K = F_{1}-T_{21}</math> * <math>R_{2} = H_{2}-K = F_{2}-T_{12}</math> and developed the conservation law <math>F_{1}+F_{2} = R_{1}+R_{2}+K = H_{1}+H_{2}-K</math> and several bounds.
==Relation to transfer entropy== Directed information is related to transfer entropy, which is a truncated version of Marko's directed transinformation <math>T_{21}</math>.
The transfer entropy at time <math>i</math> and with memory <math>d</math> is :<math> T_{X \to Y} = I(X_{i-d},\dots,X_{i-1} ; Y_i | Y_{i-d},\dots,Y_{i-1}). </math> where one does not include the present symbol <math>X_i</math> or the past symbols <math>X^{i-d-1},Y^{i-d-1}</math> before time <math>i-d</math>.
Transfer entropy usually assumes stationarity, i.e., <math>T_{X \to Y}</math> does not depend on the time <math>i</math>.
== Information matrix (InfoMat) == thumb|Visualizing temporal dependencies in the InfoMat. The visualization capabilities are demonstrated through a simple Gaussian process pair. Left figure presents representative process samples, while the right presents the corresponding InfoMat. The '''information matrix''' (InfoMat) is a matrix-valued representation introduced as a visualization and analysis tool for information transfer in sequential systems. For two sequences <math>X^n</math> and <math>Y^n</math>, the InfoMat arranges the conditional mutual information terms <math>I(X_i;Y_j \mid X^{i-1},Y^{j-1})</math> into an <math>n \times n</math> matrix, capturing the full mutual information decomposition across time. Within this representation, the directed information <math>I(X^n \to Y^n)</math> corresponds to the sum of a triangular sub-matrix, providing a direct visual interpretation of causal information flow. The InfoMat framework unifies directed information, transfer entropy, and related information conservation laws, and enables their interpretation through matrix structure and heatmap visualizations.<ref>{{cite journal |last1=Tsur |first1=Dor |last2=Permuter |first2=Haim H. |title=InfoMat: Leveraging Information Theory to Visualize and Understand Sequential Data |journal=Entropy |date=2025 |volume=27 |issue=4 |page=357 |doi=10.3390/e27040357 |doi-access=free |pmid=40282592 |pmc=12026351 |bibcode=2025Entrp..27..357T }}</ref>
==References== {{Reflist}}
Category:Information theory