Source-linked AI summary
Universal Estimation of Directed Information
Jiantao Jiao, Haim H. Permuter, Lei Zhao, Young-Han Kim, Tsachy Weissman
TL;DR
Estimating directed information matters in applications including causal-influence analysis, but existing universal estimators motivate further development. This paper proposes four estimators based on universal probability assignments and reports consistency, near-optimal rates for two estimators, and experiments on simulated and real data.
Problem
Directed information is used to study causal influence, motivating efficient estimation methods for processes with finite alphabets.
Source: §I · p. 1Method
Four estimators map universal probability assignments to information-theoretic functionals for directed-information rate between jointly stationary ergodic finite-alphabet processes.
Source: §I · p. 2, §III · p. 4Results
All four estimators have weak and strong consistency results, and two have convergence rates optimal to within logarithmic factors.
Source: §VI · p. 10Takeaways & Limitations
Experiments on simulated and real data support the potential of directed-information estimation for detecting and quantifying causality and delay.
Source: §VI · p. 10
Abstract
from arXiv · showhide
Four estimators of the directed information rate between a pair of jointly stationary ergodic finite-alphabet processes are proposed, based on universal probability assignments. The first one is a Shannon--McMillan--Breiman type estimator, similar to those used by Verd\'u (2005) and Cai, Kulkarni, and Verd\'u (2006) for estimation of other information measures. We show the almost sure and $L_1$ convergence properties of the estimator for any underlying universal probability assignment. The other three estimators map universal probability assignments to different functionals, each exhibiting relative merits such as smoothness, nonnegativity, and boundedness. We establish the consistency of these estimators in almost sure and $L_1$ senses, and derive near-optimal rates of convergence in the minimax sense under mild conditions. These estimators carry over directly to estimating other information measures of stationary ergodic finite-alphabet processes, such as entropy rate and mutual information rate, with near-optimal performance and provide alternatives to classical approaches in the existing literature. Guided by these theoretical results, the proposed estimators are implemented using the context-tree weighting algorithm as the universal probability assignment. Experiments on synthetic and real data are presented, demonstrating the potential of the proposed schemes in practice and the utility of directed information estimation in detecting and measuring causal influence and delay.
I. INTRODUCTION
The introduction motivates directed-information estimation through its roles in feedback information theory and causal-influence analysis, then presents a general estimator framework focused on directed-information rate. The preliminaries define the relevant probability and process notation and explain how directed information differs from mutual information.
I. INTRODUCTION
- Directed information supports feedback-channel capacity results and applications including portfolio theory, data compression, hypothesis testing, and biological causal-influence analysis.Prior work used it to study gene-network influence, and feedback-channel capacity,,,,.Source: §I · p. 1
- The paper proposes a general framework using single-letter information-theoretic functionals to estimate information measures, focusing on directed-information rate for jointly stationary ergodic finite-alphabet processes.It builds on universal methods for directed information and reports consistency results, near-optimal convergence rates under mild conditions, and simulated and real-data applications.Source: §I · p. 2
II. PRELIMINARIES
- The preliminaries establish notation for finite-alphabet processes and introduce directed information, causally conditional entropy, universal probability assignments, and context-tree weighting.The context-tree weighting algorithm is used to implement the universal estimators introduced later.Source: §II · p. 2
A. Directed Information
- Unlike mutual information, directed information uses causally conditional entropy and is generally asymmetric between the two process directions.The section also relates directed information to causally conditional entropy rate, allowing estimation through estimates of that rate.Source: A. Directed Information · pp. 2–3
B. Universal Probability Assignment
The section describes probability assignments and distinguishes universal from pointwise universal behavior. It then explains how context-tree weighting constructs a sequential assignment from context-specific counts and weighted probabilities.
B. Universal Probability Assignment
- A probability assignment specifies conditional pmfs whose product gives probabilities for finite sequences.The section defines universal and pointwise universal assignments, while noting that pointwise universality alone need not imply universality because normalized log loss can be unbounded.Source: B. Universal Probability Assignment · p. 3
- Combining a pointwise universal assignment with an i.i.d. uniform assignment can yield both universal and pointwise universal behavior when the mixing weight decays subexponentially.The section gives 1/n as an example of such a decay.Source: B. Universal Probability Assignment · p. 3
C. Context-Tree Weighting
- The CTW algorithm provides sequential probability assignments in linear time in block length and is extended here to alphabets larger than binary.For simulated data, the authors assume tree depth exceeds source memory; another algorithm can alleviate that assumption but is not implemented.Source: C. Context-Tree Weighting · p. 3
- In context-tree weighting, each node represents a preceding-symbol context and stores counts of the symbols emitted after that context.The CTW assignment at the root combines weighted probabilities based on context-specific Krichevsky–Trofimov estimates.Source: C. Context-Tree Weighting · pp. 3–4
- The CTW assignment is universal and pointwise universal for stationary irreducible aperiodic finite-alphabet Markov processes.The pointwise universality claim is proved in the appendix.Source: C. Context-Tree Weighting · p. 4
III. FOUR ESTIMATORS
The paper presents four directed-information-rate estimators built from universal probability assignments. They use log-probability, entropy, and relative-entropy functionals, with different convergence guarantees and sample-path properties.
III. FOUR ESTIMATORS
- The first estimator is a difference of two Shannon–McMillan–Breiman-type terms, while three others replace Cesàro-mean terms with functionals of probability assignments.The second uses conditional entropy; the third and fourth use relative entropy.Source: §III · p. 5
- The first estimator is motivated by the asymptotic equipartition property and is shown to converge to the directed-information rate.The cited discussion connects the approach to prior entropy-measure estimators,.Source: §III · p. 5
- The first estimator can be very large on some realizations, whereas the second is bounded in absolute value by log |Y| on every realization.The first averages logarithms of estimated conditional probabilities; the second uses an information-theoretic functional to smooth the estimate.Source: §III · p. 5
- The first two estimators can be negative with insufficient data or violated stationarity assumptions, while the relative-entropy-based third and fourth estimators are always nonnegative.The paper notes that short-term nonstationarity may have caused negative estimates in its stock-market example.Source: §III · p. 5
IV. PERFORMANCE GUARANTEES
The section establishes consistency guarantees for the proposed estimators and near-optimal minimax rates under mild conditions. It also gives a lower bound showing that convergence faster than O(n^-1/2) is unattainable, even for i.i.d. sources.
IV. PERFORMANCE GUARANTEES
- The section targets almost-sure and L1 consistency for the proposed estimators and near-optimal minimax convergence rates under mild conditions.Source: §IV · p. 5
- For any universal probability assignment and jointly stationary ergodic finite-alphabet processes, Theorem 1 establishes almost-sure and L1 convergence.Source: §IV · p. 6
- The first two estimators’ convergence rates are optimal within a logarithmic factor, while rates faster than O(n^-1/2) are unattainable even for i.i.d. sources.The minimax lower bound also applies to universal entropy estimation because entropy rate is a special case of directed information when Y = X.Source: §IV · p. 6
- CTW-based consistency results for the third and fourth estimators are given under joint Markov conditions, including a tree-depth bound and matching-order Markov output process.Source: §IV · p. 6
V. ALGORITHMS AND NUMERICAL EXAMPLES
The experiments implement the estimators with CTW and test them on synthetic and real data. They show convergence toward the true directed information rate and use shifted directed information to estimate channel delay.
V. ALGORITHMS AND NUMERICAL EXAMPLES
- The CTW implementation computes the ˆI2 update from conditional probability assignments for paired symbols and for Y, with the other estimators differing in their update rules.The algorithm updates a context tree for each conditional assignment; CTW provides the probability assignment directly and has linear computational complexity in block length n.Source: §V · p. 7
- The experiments also extend the estimators to mutual information and directed information with delay, and apply them to causal-influence detection in stock-market data.The real-data example examines influence between the Chinese and US stock markets.Source: §V · p. 7
A. Stationary Hidden Markov Processes
- With p = 0.3 and ǫ = 0.2, all four estimates approach the analytical directed information rate as data length grows.The context-tree depth is 3; Fig. 3 presents the estimates, and its straight line is the analytical value.Source: A. Stationary Hidden Markov Processes · p. 7, Figure 3 · p. 7
- The sample paths of ˆI2 and ˆI4 appear smoother than the first estimator, which is sensitive to sample-path idiosyncrasies.The paper relates the smoother paths to applying entropy and relative entropy functionals to the probability-mass-function estimate.Source: A. Stationary Hidden Markov Processes · p. 8
B. Channel Delay Estimation via Shifted Directed Information
- For d < D′ the shifted estimate is near zero, while for d ≥ D′ it is significantly larger, providing a way to estimate the channel delay.The experiment uses D′ = 2.Source: Figure 5 · p. 8, B. Channel Delay Estimation via… · p. 8
C. Causal Influence Measurement
The section uses directed and reverse directed information to quantify influence in each direction, under a timing assumption that X precedes Y. Universal estimators are applied to channel and causal-influence settings beyond the Gauss–Markov assumptions used by Granger causality.
C. Causal Influence Measurement
- Causal interpretation assumes each X_i occurs earlier than its paired Y_i, yielding forward and backward conditional channels.Source: C. Causal Influence Measurement · p. 9, Figure 6 · p. 9
- The forward link exists exactly when I(X^n → Y^n) > 0, and the backward link exists exactly when I(Y^{n−1} → X^n) > 0.Source: C. Causal Influence Measurement · p. 9
- Directed information I(X^n → Y^n) quantifies how much X influences Y, while reverse directed information quantifies how much Y influences X.Source: C. Causal Influence Measurement · p. 9
- For the simulated binary-symmetric channels, the analytic measures agree with the direction-of-influence cases: α < β corresponds to X influencing Y more.Source: C. Causal Influence Measurement · p. 9
- The estimators extend to reverse directed information by shifting the process pair, and normalized mutual information follows by summing the two directed estimates.Source: C. Causal Influence Measurement · p. 9
- With a few hundred samples, directed and reverse directed information begin strongly indicating that X influences Y more when α < β.Source: C. Causal Influence Measurement · pp. 9–10
D. Causal Influence in Stock Markets
Using daily HSI and DJIA data from 1990–2011, the paper estimates directional information measures and finds substantially greater influence from the U.S. market toward the Chinese market. The conclusion summarizes consistency, convergence rates, and practical merits across the four estimators.
D. Causal Influence in Stock Markets
- The analysis uses daily HSI and DJIA changes from 1990–2011, quantized as −1, 0, or 1 according to daily moves around a 0.8% threshold.Source: D. Causal Influence in Stock Markets · p. 10
- Estimators I1 and I2 can produce negative outputs, while I3 and I4 are always nonnegative and are preferred when data are insufficient.Source: D. Causal Influence in Stock Markets · p. 10
- The reverse directed information estimate is much higher than directed information, indicating greater DJIA influence on HSI during 1990–2011; Fig. 10 presents the comparison.Source: Figure 10 · p. 10, D. Causal Influence in Stock Markets · p. 10
VI. CONCLUDING REMARKS
- Across the four estimators, the paper establishes weak and strong consistency; two have convergence rates optimal to within logarithmic factors, while others offer merits such as nonnegativity.Source: §VI · p. 10
- Experiments on simulated and real data support the estimators’ potential for detecting and quantifying causality and delay.Source: §VI · p. 10
APPENDIX A SOME KEY LEMMAS
Appendix A supplies lemmas used in the paper’s proofs, including an L1 extension of the AEP for causally conditional entropy and CTW redundancy bounds. Appendix B then uses these tools in proving estimator convergence.
APPENDIX A SOME KEY LEMMAS
- Appendix C provides proofs of the lemmas listed in Appendix A.Source: Appendix A · p. 11
- The causally conditional entropy-rate AEP holds almost surely and in L1, with convergence rates also shown for jointly stationary irreducible aperiodic Markov processes.Source: Appendix A · p. 11
- For a finite-alphabet Markov process whose order is within the CTW tree depth, the CTW probability assignment has pointwise and expected redundancy bounds.Source: Appendix A · p. 11
APPENDIX B PROOFS OF THEOREMS AND PROPOSITIONS
- Appendix B proves Theorem 1 by showing estimator I1 converges in L1 for a universal probability assignment and almost surely for a pointwise universal assignment.Source: A. Proof of Theorem 1 · p. 12
2) Almost sure convergence:
The proof material establishes convergence claims for estimators and derives a CTW-based almost-sure rate under Markov assumptions. It also outlines the convergence argument for a second estimator using martingale convergence and boundedness.
2) Almost sure convergence:
- Estimator I1 converges almost surely to the directed information rate under pointwise universality, completing the proof’s almost-sure convergence step.Source: 2) Almost sure convergence · p. 13
B. Proof of Proposition 1
- The Proposition 1 proof derives convergence rates by applying the CTW redundancy bound and combining it with the L1 rate for D_n.Source: B. Proof of Proposition 1 · p. 13, 1) L1 convergence · pp. 13–14
2) Almost sure convergence rates:
- The passage gives (X →Y) a P-a.s. rate of o(n^-1/2(log n)^(5/2+ε)); it does not establish that this rate belongs to the CTW estimator.Source: 2) Almost sure convergence rates · p. 14
C. Proof of Theorem 2
- Theorem 2’s proof uses martingale convergence and boundedness of the sequence g_k to establish the required convergence result.Source: C. Proof of Theorem 2 · p. 14
D. Proof of Proposition 2
The proof establishes almost-sure convergence of Ĥ2 and develops L1 bounds; the minimax lower-bound proof uses a two-model construction and a Bernoulli divergence bound.
D. Proof of Proposition 2
- For the L1 bounds, Lemma 2 makes conditional-pmf differences small enough for Lemma 4 to apply.Source: 2) L1 convergence rates · p. 15
1) Almost sure convergence:
- Proposition 2's almost-sure convergence of Ĥ2 is justified by combining bounds (150) and (151).Source: 2) L1 convergence rates · p. 15, 1) Almost sure convergence · p. 15
E. Proof of Proposition 3
- The minimax lower-bound proof uses separated models and the bound D(P∥Q) ≤ 8(p − q)^2 for Bernoulli parameters with |p|, |q| ≤ 1/4.Source: E. Proof of Proposition 3 · pp. 15–16
F. Proof of Theorem 3
Theorem 3's proof reduces convergence to component terms, including CTW probability assignments; related arguments establish L1 convergence of the causally conditional entropy AEP and support Theorem 4.
F. Proof of Theorem 3
- Under Theorem 3's conditions, the second term of (184) converges to H(Y∥X) almost surely and in L1.Source: F. Proof of Theorem 3 · p. 17
1) Almost sure convergence:
- The CTW assignments Q(yi|Xi, Y^{i−1}) and Q(yi|Y^{i−1}) converge almost surely to their true conditional probabilities.Source: 1) Almost sure convergence · p. 17
G. Proof of Theorem 4
- Because Gn has a form similar to Fn, the proof establishes Theorem 4 by analogous steps.Source: G. Proof of Theorem 4 · p. 17
1) General stationary ergodic processes:
- For general stationary ergodic processes, the AEP for causally conditional entropy holds in L1.Source: A. Proof of Lemma 1 · p. 17, 1) General stationary ergodic processes · p. 19
2) Irreducible aperiodic Markov processes:
The Markov-process arguments invoke a Gál–Koksma bound for convergence rates, while the CTW tree proof establishes vanishing internal-node weights under stationary irreducible aperiodic finite-alphabet Markov conditions.
2) Irreducible aperiodic Markov processes:
- For a stationary Markov process, Egi is constant across i.Source: 2) Irreducible aperiodic Markov… · p. 19
- For the rate bound, the proof applies Gál–Koksma with Ψ(n) = n(log n)^2 and p = 2.Source: 2) Irreducible aperiodic Markov… · p. 20
B. Proof of Lemma 2
- For stationary irreducible aperiodic finite-alphabet Markov processes, βs(Xn) tends to zero almost surely at every internal context-tree node.Source: B. Proof of Lemma 2 · p. 20
- In the context-tree argument, ns counts the symbols in Xn observed with context s.Source: B. Proof of Lemma 2 · p. 20
C. Proof of Lemma 3
The auxiliary proofs bound a function's continuity and range, relate entropy differences to distribution distances, and bound mixing under Markov conditions.
C. Proof of Lemma 3
- Lemma 3 uses uniform continuity of f on bounded closed M(X, Y), with f bounded by log |X| + log |Y|.Source: C. Proof of Lemma 3 · p. 21
D. Proof of Lemma 4
- The entropy-difference argument decomposes the change in conditional entropy into differences for the joint and marginal entropies.Source: D. Proof of Lemma 4 · pp. 21–22
E. Proof of Lemma 5
- For stationary irreducible aperiodic Markov processes, α(n) decays exponentially; Lemma 5's bound uses C4 = 1 + 8C7eC8/(eC8 − 1)^2.Source: E. Proof of Lemma 5 · p. 22