Center for Applied Mathematics Colloquium

Austin BensonCornell University
Spacey random walks

Friday, October 27, 2017 - 3:30pm
Rhodes 655

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. In this talk, I will 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.