Universal estimation of directed information
Jiantao Jiao, Haim H. Permuter, Lei Zhao, Young-Han Kim, and Tsachy Weissman
IEEE Transactions on Information Theory, vol. 59, no. 10, pp. 6220–6242, October 2013.
Preliminary results appeared in Proceedings of the IEEE International Symposium on Information Theory, pp. 1433–1437, Austin, Texas, June 2010 and Proceedings of the IEEE International Symposium on Information Theory, pp. 523–527, Cambridge, Massachusetts, July 2012.
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
Verdu in 2005 and Cai in 2006 for estimation of other information
measures. We show the almost sure and 
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 
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.