2019/03/04 by Thomas Sauerwald, Sauerwald, Thomas, Luca Zanetti +1 · 3 citations
Mathematics · Physics and Astronomy · #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #Complex Network Analysis Techniques
paper · pdf · doi:10.48550/arxiv.1903.01342
We establish and generalise several bounds for various random walk quantities\nincluding the mixing time and the maximum hitting time. Unlike previous\nanalyses, our derivations are based on rather intuitive notions of local\nexpansion properties which allows us to capture the progress the random walk\nmakes through t-step probabilities.\n We apply our framework to dynamically changing graphs, where the set of\nvertices is fixed while the set of edges changes in each round. For random\nwalks on dynamic connected graphs for which the stationary distribution does\nnot change over time, we show that their behaviour is in a certain sense\nsimilar to static graphs. For example, we show that the mixing and hitting\ntimes of any sequence of d-regular connected graphs is O(n2), generalising\na well-known result for static graphs. We also provide refined bounds depending\non the isoperimetric dimension of the graph, matching again known results for\nstatic graphs. Finally, we investigate properties of random walks on dynamic\ngraphs that are not always connected: we relate their convergence to\nstationarity to the spectral properties of an average of transition matrices\nand provide some examples that demonstrate strong discrepancies between static\nand dynamic graphs.\n