Friday, October 27, 2017 at 3:30pm
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.
Austin Benson is currently a postdoctoral associate in the department of Computer Science at Cornell. He will join the faculty of Computer Science at Cornell in July 2018. Before coming to Cornell, he received his PhD in 2017 from the Institute for Computational and Mathematical Engineering at Stanford University. Before that, he received undergraduate degrees in computer science and applied mathematics from UC-Berkeley. Outside of the university, he has also spent time as an intern at Google Research, Sandia National Laboratories, and HP Labs.