Directed information

This article provides insufficient context for those unfamiliar with the subject. Please help improve the article by providing more context for the reader. (September 2016) (Learn how and when to remove this template message)

|

Directed information is an information theory measure that quantifies the information flow from the random string Xn=(X1,X2,…,Xn) to the random string Yn=(Y1,Y2,…,Yn). The term directed information was coined by James Massey and is defined as[1]

I(Xn->Yn)≜∑i=1nI(Xi;Yi|Yi−1)

where I(Xi;Yi|Yi−1) is the conditional mutual information I(X1,X2,...,Xi;Yi|Y1,Y2,...,Yi−1).

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][11] and statistical physics.[12]

## Contents

* 1 Causal conditioning
* 1.1 Causally conditioned entropy
* 2 Properties
* 2.1 Conservation law of information
* 3 Estimation and optimization
* 3.1 Estimation
* 3.2 Optimization
* 4 Marko's theory of bidirectional communication
* 5 Relation to transfer entropy
* 6 Information matrix (InfoMat)
* 7 References

## Causal conditioning

The essence of directed information is causal conditioning. The probability of xn causally conditioned on yn is defined as[5]

P(xn||yn)≜∏i=1nP(xi|xi−1,yi).

This is similar to the chain rule for conventional conditioning P(xn|yn)=∏i=1nP(xi|xi−1,yn) except one conditions on "past" and "present" symbols yi rather than all symbols yn. To include "past" symbols only, one can introduce a delay by prepending a constant symbol:

P(xn||(0,yn−1))≜∏i=1nP(xi|xi−1,yi−1).

It is common to abuse notation by writing P(xn||yn−1) for this expression, although formally all strings should have the same number of symbols.

One may also condition on multiple strings: P(xn||yn,zn)≜∏i=1nP(xi|xi−1,yi,zi).

### Causally conditioned entropy

The causally conditioned entropy is defined as:[2]

H(Xn||Yn)=𝐄[−log⁡P(Xn||Yn)]=∑i=1nH(Xi|Xi−1,Yi)

Similarly, one may causally condition on multiple strings and write H(Xn||Yn,Zn)=𝐄[−log⁡P(Xn||Yn,Zn)].

## Properties

A decomposition rule for causal conditioning[1] is

P(xn,yn)=P(xn||yn−1)P(yn||xn).

This rule shows that any product of P(xn||yn−1),P(yn||xn) gives a joint distribution P(xn,yn).

The causal conditioning probabilityP(yn||xn)=∏i=1nP(yi|yi−1,xi) is a probability vector, i.e.,

P(yn||xn)≥0and∑ynP(yn||xn)=1for all (xn,yn).

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

I(XN->YN)=𝐄[log⁡P(YN||XN)P(YN)]=H(Yn)−H(Yn||Xn).

The relation generalizes to three strings: the directed information flowing from Xn to Yn causally conditioned on Zn is

I(Xn->Yn||Zn)=H(Yn||Zn)−H(Yn||Xn,Zn).

### Conservation law of information

This law, established by James Massey and his son Peter Massey,[13] gives intuition by relating directed information and mutual information. The law states that for any Xn,Yn, the following equality holds:

I(Xn;Yn)=I(Xn->Yn)+I(Yn−1->Xn).

Two alternative forms of this law are[2][14]

I(Xn;Yn)=I(Xn->Yn)+I(Yn->Xn)−I(Xn↔Yn)
I(Xn;Yn)=I(Xn−1->Yn)+I(Yn−1->Xn)+I(Xn↔Yn)

where I(Xn↔Yn)=∑i=1nI(Xi;Yi|Xi−1,Yi−1).

## Estimation and optimization

Estimating and optimizing the directed information is challenging because it has n terms where n may be large. In many cases, one is interested in optimizing the limiting average, that is, when n 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 {P(xi,yi|xi−1,yi−1)i=1n} which may be unknown. There are several algorithms based on context tree weighting[15] and empirical parametric distributions[16] and using long short-term memory.[17]

### Optimization

Maximizing directed information is a fundamental problem in information theory. For example, given the channel distributions {P(yi|xi,yi−1}i=1n), the objective might be to optimize I(Xn->Yn) over the channel input distributions {P(xi|xi−1,yi−1}i=1n).

There are algorithms to optimize the directed information based on the Blahut-Arimoto,[18] Markov decision process,[19][20][21][22][23] Recurrent neural network,[17] Reinforcement learning.[24] and Graphical methods (the Q-graphs).[25][26][23] For the Blahut-Arimoto algorithm,[18] the main idea is to start with the last mutual information of the directed information expression and go backward. For the Markov decision process,[19][20][21][22] the main ideas is to transform the optimization into an infinite horizon average reward Markov decision process. For a Recurrent neural network,[17] the main idea is to model the input distribution using a Recurrent neural network and optimize the parameters using Gradient descent. For Reinforcement learning,[24] 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.[27][28] Marko's definition of directed transinformation differs slightly from Massey's in that, at time n, one conditions on past symbols Xn−1,Yn−1 only and one takes limits:

T12=limn->∞𝐄[−log⁡P(Xn|Xn−1)P(Xn|Xn−1,Yn−1)]andT21=limn->∞𝐄[−log⁡P(Yn|Yn−1)P(Yn|Yn−1,Xn−1)].

Marko defined several other quantities, including:

* Total information: H1=limn->∞𝐄[−log⁡P(Xn|Xn−1)] and H2=limn->∞𝐄[−log⁡P(Yn|Yn−1)]
* Free information: F1=limn->∞𝐄[−log⁡P(Xn|Xn−1,Yn−1)] and F2=limn->∞𝐄[−log⁡P(Yn|Yn−1,Xn−1)]
* Coincidence: K=limn->∞𝐄[−log⁡P(Xn|Xn−1)P(Yn|Yn−1)P(Xn,Yn|Xn−1,Yn−1)].

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

* K=T12+T21
* H1=T12+F1 and H2=T21+F2

He also defined quantities he called residual entropies:

* R1=H1−K=F1−T21
* R2=H2−K=F2−T12

and developed the conservation law F1+F2=R1+R2+K=H1+H2−K and several bounds.

## Relation to transfer entropy

Directed information is related to transfer entropy, which is a truncated version of Marko's directed transinformation T21.

The transfer entropy at time i and with memory d is

TX->Y=I(Xi−d,…,Xi−1;Yi|Yi−d,…,Yi−1).

where one does not include the present symbol Xi or the past symbols Xi−d−1,Yi−d−1 before time i−d.

Transfer entropy usually assumes stationarity, i.e., TX->Y does not depend on the time i.

## Information matrix (InfoMat)

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 Xn and Yn, the InfoMat arranges the conditional mutual information terms I(Xi;Yj∣Xi−1,Yj−1) into an n×n matrix, capturing the full mutual information decomposition across time. Within this representation, the directed information I(Xn->Yn) 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.[29]

## References

1. ↑ 1.0 1.1 1.2 Massey, James (1990). "Causality, Feedback And Directed Information".
2. ↑ 2.0 2.1 2.2 2.3 Kramer, Gerhard (1998). Directed information for channels with feedback (Doctoral). ETH Zurich. doi:10.3929/ethz-a-001988524. hdl:20.500.11850/143796.
3. ↑ Tatikonda, Sekhar Chandra (2000). Control under communication constraints (Doctoral). Massachusetts Institute of Technology. hdl:1721.1/16755.
4. ↑ 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. doi:10.1109/TIT.2008.2009849. Bibcode: 2009ITIT...55..644P.
5. ↑ 5.0 5.1 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. Bibcode: 2003ITIT...49....4K.
6. ↑ Kramer, Gerhard (April 2014). "Information Networks With In-Block Memory". IEEE Transactions on Information Theory 60 (4): 2105–2120. doi:10.1109/TIT.2014.2303120. Bibcode: 2014ITIT...60.2105K.
7. ↑ 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. doi:10.1109/TIT.2011.2136270. Bibcode: 2011ITIT...57.3248P.
8. ↑ 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. doi:10.1109/TIT.2013.2248192. Bibcode: 2013ITIT...59.3607S.
9. ↑ Sabag, Oron; Tian, Peida; Kostina, Victoria; Hassibi, Babak (September 2023). "Reducing the LQG Cost With Minimal Communication". IEEE Transactions on Automatic Control 68 (9): 5258–5270. doi:10.1109/TAC.2022.3220511. ISSN 0018-9286. Bibcode: 2023ITAC...68.5258S.
10. ↑ 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. doi:10.1109/TIT.2016.2604846. Bibcode: 2016ITIT...62.6019C.
11. ↑ 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. Bibcode: 2018ITAC...63...37T. http://resolver.tudelft.nl/uuid:d9db1c11-fbfd-4c0c-b66f-f341b49fa61a.
12. ↑ 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). doi:10.1088/1742-5468/2016/04/043403. Bibcode: 2016JSMTE..04.3403V.
13. ↑ Massey, J.L.; Massey, P.C. (September 2005). "Conservation of mutual and directed information". Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. pp. 157–158. doi:10.1109/ISIT.2005.1523313. ISBN 0-7803-9151-9.
14. ↑ Amblard, Pierre-Olivier; Michel, Olivier (28 December 2012). "The Relation between Granger Causality and Directed Information Theory: A Review". Entropy 15 (1): 113–143. doi:10.3390/e15010113. Bibcode: 2012Entrp..15..113A.
15. ↑ 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. doi:10.1109/TIT.2013.2267934. Bibcode: 2013ITIT...59.6220J.
16. ↑ Quinn, Christopher J.; Kiyavash, Negar; Coleman, Todd P. (December 2015). "Directed Information Graphs". IEEE Transactions on Information Theory 61 (12): 6887–6909. doi:10.1109/TIT.2015.2478440. Bibcode: 2015ITIT...61.6887Q.
17. ↑ 17.0 17.1 17.2 Aharoni, Ziv; Tsur, Dor; Goldfeld, Ziv; Permuter, Haim Henry (June 2020). "Capacity of Continuous Channels with Memory via Directed Information Neural Estimator". 2020 IEEE International Symposium on Information Theory (ISIT). pp. 2014–2019. doi:10.1109/ISIT44484.2020.9174109. ISBN 978-1-7281-6432-8.
18. ↑ 18.0 18.1 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. Bibcode: 2013ITIT...59..204N.
19. ↑ 19.0 19.1 Permuter, Haim; Cuff, Paul; Van Roy, Benjamin; Weissman, Tsachy (July 2008). "Capacity of the Trapdoor Channel With Feedback". IEEE Transactions on Information Theory 54 (7): 3150–3165. doi:10.1109/TIT.2008.924681. Bibcode: 2008ITIT...54.3150P.
20. ↑ 20.0 20.1 Elishco, Ohad; Permuter, Haim (September 2014). "Capacity and Coding for the Ising Channel With Feedback". IEEE Transactions on Information Theory 60 (9): 5138–5149. doi:10.1109/TIT.2014.2331951. Bibcode: 2014ITIT...60.5138E.
21. ↑ 21.0 21.1 Sabag, Oron; Permuter, Haim H.; Kashyap, Navin (January 2016). "The Feedback Capacity of the Binary Erasure Channel With a No-Consecutive-Ones Input Constraint". IEEE Transactions on Information Theory 62 (1): 8–22. doi:10.1109/TIT.2015.2495239. Bibcode: 2016ITIT...62....8S.
22. ↑ 22.0 22.1 Peled, Ori; Sabag, Oron; Permuter, Haim H. (July 2019). "Feedback Capacity and Coding for the $(0,k)$ -RLL Input-Constrained BEC". IEEE Transactions on Information Theory 65 (7): 4097–4114. doi:10.1109/TIT.2019.2903252.
23. ↑ 23.0 23.1 Shemuel, Eli; Sabag, Oron; Permuter, Haim H. (March 2024). "Finite-State Channels With Feedback and State Known at the Encoder". IEEE Transactions on Information Theory 70 (3): 1610–1628. doi:10.1109/TIT.2023.3336939. Bibcode: 2024ITIT...70.1610S.
24. ↑ 24.0 24.1 Aharoni, Ziv; Sabag, Oron; Permuter, Haim Henri (18 August 2020). "Reinforcement Learning Evaluation and Solution for the Feedback Capacity of the Ising Channel with Large Alphabet". arXiv:2008.07983 [cs.IT].
25. ↑ Sabag, Oron; Permuter, Haim Henry; Pfister, Henry (March 2017). "A Single-Letter Upper Bound on the Feedback Capacity of Unifilar Finite-State Channels". IEEE Transactions on Information Theory 63 (3): 1392–1409. doi:10.1109/TIT.2016.2636851. Bibcode: 2017ITIT...63.1392S.
26. ↑ Sabag, Oron; Huleihel, Bashar; Permuter, Haim Henry (2020). "Graph-Based Encoders and their Performance for Finite-State Channels with Feedback". IEEE Transactions on Communications 68 (4): 2106–2117. doi:10.1109/TCOMM.2020.2965454. Bibcode: 2020ITCom..68.2106S.
27. ↑ Marko, Hans (1 September 1966). "Die Theorie der bidirektionalen Kommunikation und ihre Anwendung auf die Nachrichtenübermittlung zwischen Menschen (Subjektive Information)" (in de). Kybernetik 3 (3): 128–136. doi:10.1007/BF00288922. ISSN 1432-0770. PMID 5920460. https://link.springer.com/article/10.1007/BF00288922.
28. ↑ Marko, H. (December 1973). "The Bidirectional Communication Theory--A Generalization of Information Theory". IEEE Transactions on Communications 21 (12): 1345–1351. doi:10.1109/TCOM.1973.1091610. Bibcode: 1973ITCom..21.1345M.
29. ↑ Tsur, Dor; Permuter, Haim H. (2025). "InfoMat: Leveraging Information Theory to Visualize and Understand Sequential Data". Entropy 27 (4): 357. doi:10.3390/e27040357. PMID 40282592. Bibcode: 2025Entrp..27..357T.

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Directed information. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Directed_information&oldid=4228198"