Learning the causal graph of Markov time series

This paper considers a natural and widely prevalent setting where a collection of one dimensional time series evolve in a causal manner, and one is interested in inferring the graph governing the causality between these processes in a high dimensional setting. We consider this problem in the special case where variables are discrete and updates are Markov. We develop a new algorithm to learn causal graph structure based on the notion of directed information, and analytically and empirically demonstrate its performance. Our algorithm is an adaptation of a greedy heuristic for learning undirected graphical models, with modifications to leverage causality. Analytically, the challenge lies in determining sample complexity, given the dependencies between samples.