Abstract

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)
JournalIEEE Transactions on Network Science and Engineering
DOIs
StateAccepted/In press - Apr 21 2018

    Fingerprint

Keywords

  • Autoregressive process
  • Autoregressive processes
  • Bars
  • Biological system modeling
  • Complexity theory
  • Heuristic algorithms
  • Markov processes
  • Time series analysis
  • mixing times of Markov chains
  • networked processes
  • structural learning

ASJC Scopus subject areas

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

Cite this