Motivated by multiple applications in social networks, nervous systems, and
financial risk analysis, we consider the problem of learning the underlying
(directed) influence graph or causal graph of a high-dimensional multivariate
discrete-time Markov process with memory. At any discrete time instant, each
observed variable of the multivariate process is a binary string of random
length, which is parameterized by an unobservable or hidden [0,1]-valued
scalar. The hidden scalars corresponding to the variables evolve according to
discrete-time linear stochastic dynamics dictated by the underlying influence
graph whose nodes are the variables. We extend an existing algorithm for
learning i.i.d. graphical models to this Markovian setting with memory and
prove that it can learn the influence graph based on the binary observations
using logarithmic (in number of variables or nodes) samples when the degree of
the influence graph is bounded. The crucial analytical contribution of this
work is the derivation of the sample complexity result by upper and lower
bounding the rate of convergence of the observed Markov process with memory to
its stationary distribution in terms of the parameters of the influence graph.

基于对多个应用程序在社交网络、神经系统和金融风险分析中的动机，我们研究了学习具有内存的高维多元离散时间马尔可夫过程的底层（有向）影响图或因果图的问题。我们将一个已有的算法扩展到这种带有内存的马尔可夫设定中，并证明了在影响图的度受限制的条件下，它可以基于二进制观测量学习影响图，在样本复杂度上具有对数（相对于变量或节点数量）的要求。本工作的重要分析贡献是通过上界和下界约束观测到的带有内存的马尔可夫过程相对于影响图参数的收敛速率来导出样本复杂度结果。