  A random walk is a basic stochastic process on graphs and a key primitive in
the design of distributed algorithms. One of the most important features of
random walks is that, under mild conditions, they converge to a stationary
distribution in time that is at most polynomial in the size of the graph. This
fundamental property, however, only holds if the graph does not change over
time, while on the other hand many distributed networks are inherently dynamic,
and their topology is subjected to potentially drastic changes.
  In this work we study the mixing (i.e., converging) properties of random
walks on graphs subjected to random changes over time. Specifically, we
consider the edge-Markovian random graph model: for each edge slot, there is a
two-state Markov chain with transition probabilities $p$ (add a non-existing
edge) and $q$ (remove an existing edge). We derive several positive and
negative results that depend on both the density of the graph and the speed by
which the graph changes. We show that if $p$ is very small (i.e., below the
connectivity threshold of Erd\H{o}s-R\'{e}nyi random graphs), random walks do
not mix (fast). When $p$ is larger, instead, we observe the following behavior:
if the graph changes slowly over time (i.e., $q$ is small), random walks enjoy
strong mixing properties that are comparable to the ones possessed by random
walks on static graphs; however, if the graph changes too fast (i.e., $q$ is
large), only coarse mixing properties are preserved.
