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

<p>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|)$).</p>

<p>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. </p>

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

<p>The question seems important and preliminary but I can not find anything about it. </p>

CC BY-SA 3.0
2018-03-27T08:45:14.317Z
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).
tranisstor
CC BY-SA 3.0
2018-03-27T12:13:02.770Z
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.
shahrzad haddadan
CC BY-SA 3.0
2018-03-28T01:26:42.920Z
this seems relevant https://arxiv.org/abs/1501.01528
Sasho Nikolov
CC BY-SA 3.0
2018-03-31T17:45:43.080Z
On a complete graph, the random walk mixes after it visits exactly one vertex.
Peter Shor 
<random-walks>
How many distinct vertices does a random walk visit until it mixes?
shahrzad haddadan
# How many distinct vertices does a random walk visit until it mixes?

(Asked by: username_0 on 2018-03-26)

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.

**Tags:** random-walks

> **Comments:**
> **username_1**: 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).  
> **username_0**: 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.  
> **username_2**: this seems relevant https://arxiv.org/abs/1501.01528  
> **username_3**: On a complete graph, the random walk mixes after it visits exactly one vertex.  

---

## 0 answers

