Consider an arbitrary undirected simple connected graph having vertex set $V$ and edge set $E$, and a lazy simple random walk on it.

How many distinct vertices does the random walk visit until it mixes? (We define the mixing time to be the time the random walk needs to get close to stationarity ($\forall v\in V, \pi(v)=deg(v)/|E|)$).

When a random walk traverses the vertices of a graph it may occur that goes back to already visited vertices. This gets more likely when the walk is trapped in a subset of $V$ with low conductance.

It seems to me that the number of distinct vertices visited by a random walk should be related to the graph's conductance.

The question seems important and preliminary but I can not find anything about it.

  • 3
    $\begingroup$ You have to be more precise. Is the graph directed or undirected? Is it acyclic and irreducible? How do you define when a graph is mixed? There are several works about this question. See, e.g., "Pseudorandom Walks on Regular Digraphs and the RL vs. L Problem" by Reingold, Trevisan and Vadhan for many references (also for the undirected case). $\endgroup$ – tranisstor Mar 27 '18 at 8:45
  • $\begingroup$ Thanks for the comment, I just edited it. Usually when talking about a random walk we assume connectivity and self loops so it is acyclic and irreducible, thus it converges to some stationarity. Mixing time is the time it takes a walk to get close to stationarity. Now the question is about the number of distinct vertices. $\endgroup$ – shahrzad haddadan Mar 27 '18 at 12:13
  • 1
    $\begingroup$ this seems relevant arxiv.org/abs/1501.01528 $\endgroup$ – Sasho Nikolov Mar 28 '18 at 1:26
  • $\begingroup$ On a complete graph, the random walk mixes after it visits exactly one vertex. $\endgroup$ – Peter Shor Mar 31 '18 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.