The Spacey Random Walk: A Stochastic Process for Higher-Order Data
The Spacey Random Walk: A Stochastic Process for Higher-Order Data
复制标题
DOI：
10.1137/16m1074023
复制
发表时间：
2017-01-01
期刊：
影响因子：
10.2
通讯作者：
Lim, Lek-Heng
中科院分区：
文献类型：
--
作者：
Benson, Austin R.;Gleich, David F.;Lim, Lek-Heng
随机游动是应用数学中的一个基本模型，也是马尔可夫链的一个常见例子。马尔可夫链的极限平稳分布表示在随机过程中每个状态所花费的时间的分数。对于有限状态集上的随机游走，计算这种分布的标准方法是计算相关转移矩阵的Perron向量。在高阶马尔可夫链的转移概率张量方面，有这个Perron向量的代数类似物。这些向量是非负的，具有与状态空间的维数相等的维数，并且总和为1，并且通过在高阶马尔可夫链的联合平稳分布的方程中进行代数替换而导出。在这里，我们提出了空间随机游动，一个非马尔可夫随机过程的平稳分布是由张量特征向量。该过程本身是一个顶点强化的随机游动，其离散动力学与连续动力系统有关。我们分析了这些动态的收敛性，并讨论了计算平稳分布的数值方法。最后，我们提供了几个应用程序的空间随机游走模型在人口遗传学，排名和聚类数据，我们使用的过程来分析出租车轨迹数据在纽约。这个例子显示了确定的非马尔可夫结构。
Random walks are a fundamental model in applied mathematics and are a common example of a Markov chain. The limiting stationary distribution of the Markov chain represents the fraction of the time spent in each state during the stochastic process. A standard way to compute this distribution for a random walk on a finite set of states is to compute the Perron vector of the associated transition matrix. There are algebraic analogues of this Perron vector in terms of transition probability tensors of higher-order Markov chains. These vectors are nonnegative, have dimension equal to the dimension of the state space, and sum to one and are derived by making an algebraic substitution in the equation for the joint-stationary distribution of a higher-order Markov chains. Here, we present the spacey random walk, a non-Markovian stochastic process whose stationary distribution is given by the tensor eigenvector. The process itself is a vertex-reinforced random walk, and its discrete dynamics are related to a continuous dynamical system. We analyze the convergence properties of these dynamics and discuss numerical methods for computing the stationary distribution. Finally, we provide several applications of the spacey random walk model in population genetics, ranking, and clustering data, and we use the process to analyze taxi trajectory data in New York. This example shows definite non-Markovian structure.