  The random order graph streaming model has received significant attention
recently, with problems such as matching size estimation, component counting,
and the evaluation of bounded degree constant query testable properties shown
to admit surprisingly space efficient algorithms.
  The main result of this paper is a space efficient single pass random order
streaming algorithm for simulating nearly independent random walks that start
at uniformly random vertices. We show that the distribution of $k$-step walks
from $b$ vertices chosen uniformly at random can be approximated up to error
$\varepsilon$ per walk using $(1/\varepsilon)^{O(k)} 2^{O(k^2)}\cdot b$ words
of space with a single pass over a randomly ordered stream of edges, solving an
open problem of Peng and Sohler [SODA `18]. Applications of our result include
the estimation of the average return probability of the $k$-step walk (the
trace of the $k^\text{th}$ power of the random walk matrix) as well as the
estimation of PageRank. We complement our algorithm with a strong impossibility
result for directed graphs.
