The essence of directed information is causal conditioning. The probability of causally conditioned on is defined as
This is similar to the chain rule for conventional conditioning except one conditions on "past" and "present" symbols rather than all symbols . To include "past" symbols only, one can introduce a delay by prepending a constant symbol:
It is common to abuse notation by writing for this expression, although formally all strings should have the same number of symbols.
One may also condition on multiple strings: .
Causally conditioned entropy
The causally conditioned entropy is defined as:
Similarly, one may causally condition on multiple strings and write
A decomposition rule for causal conditioning is
This rule shows that any product of gives a joint distribution .
The casual conditioning probability is a probability vector, i.e.,
Directed Information can be written in terms of causal conditioning:
The relation generalizes to three strings: the directed information flowing from to causally conditioned on is
Conservation law of information
This law, established by James Massey and his son Peter Massey, gives intuition by relating directed information and mutual information. The law states that for any , the following equality holds:
Estimating and optimizing the directed information is challenging because it has terms where may be large. In many cases, one is interested in optimizing the limiting average, that is, when grows to infinity termed as a multi-letter expression.
The estimation of directed information from given samples is a very hard problem since the directed information expression does not depends on samples but on the joint distribution which is unknown. There exist several algorithms based on context tree weight and on empirical parametric distributions and using Long short-term memory.
The maximization of the directed information is a fundamental problem in information theory. For a fixed sequence of channel distributions , the objective is to optimize over the channel input distributions .
Massey's directed information was motivated by Marko's early work (1966) on developing a theory of bidirectional communication. Marko's definition of directed transinformation differs slightly from Massey's in that, at time , one conditions on past symbols only and one takes limits:
Marko defined several other quantities, including:
Total information: and
Free information: and
The total information is usually called an entropy rate. Marko showed the following relations for the problems he was interested in:
He also defined quantities he called residual entropies:
and developed the conservation law and several bounds.
Relation to transfer entropy
Directed information is related to transfer entropy, which is a truncated version of Marko's directed transinformation.
The transfer entropy at time and with memory is
where one does not include the present symbol or the past symbols before time .
Transfer entropy usually assumes stationarity, i.e., does not depend on the time .
^ abcMassey, James (1990). "Causality, Feedback And Directed Information". Proc. 1990 Intl. Symp. on Info. Th. and its Applications, Waikiki, Hawaii, Nov. 27-30, 1990.
^ abKramer, 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.
^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.
^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. S2CID11722596.
^ abSabag, 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. S2CID476381.
^ abAharoni, 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].
^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. arXiv:1604.01878. doi:10.1109/TIT.2016.2636851. S2CID3259603.