Title: Spacey random walks
Authors: Austin Benson - Cornell University (United States) [presenting]
David Gleich - Purdue University (United States)
Lek-Heng Lim - University of Chicago (United States)
Abstract: Random walks are a fundamental model in applied mathematics and are a common example of a Markov chain. A standard way to compute the stationary distribution for a random walk on a finite set of states is to compute the Perron vector of the associated transition probability matrix. There are algebraic analogues of the Perron vector in terms of $z$ eigenvectors of transition probability tensors whose entries come from higher-order Markov chains. These vectors look stochastic, but they are derived from an algebraic substitution in the stationary distribution equation of higher-order Markov chains and do not carry a probabilistic interpretation. We present the spacey random walk, a non-Markovian stochastic process whose stationary distribution is given by a dominant $z$ eigenvector of the transition probability tensor. 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. We also 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.