We introduce a multivariate random process producing Bernoulli outputs per dimension, that can possibly formalize binary interactions in various graphical structures and can be used to model opinion dynamics, epidemics, financial and biological time series data, etc. We call this a Bernoulli Autoregressive Process (BAR). While many dynamical models of processes on graphs have been studied previously, the main feature of our model is that it provides a parsimonious description of a Markov chain with non-reversible dynamics in general, which may be important in some applications. The goal is to learn the causal connectivity of the underlying graph from time-series data, assuming that the connectivity is sparse. Not surprisingly, the simplicity of the model leads to a simple and natural learning algorithm. However, proving the near-optimal sample complexity of the algorithm is non-trivial. The sample complexity is related to the mixing time of the BAR Markov chain, which is hard to estimate because of the lack of reversibility. A key contribution of the paper is an upper bound on the mixing time based on coupling arguments and a probabilistic inequality which may itself be of independent interest.

Original languageEnglish (US)
Pages (from-to)364-378
Number of pages15
JournalIEEE Transactions on Network Science and Engineering
Issue number3
StatePublished - Jul 1 2018


  • Autoregressive process
  • mixing times of Markov chains
  • networked processes
  • structural learning

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Computer Networks and Communications


Dive into the research topics of 'Mixing Times and Structural Inference for Bernoulli Autoregressive Processes'. Together they form a unique fingerprint.

Cite this