  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.
