<p>Your question is essentially covered by Cor 9.5 in [1]
which implies that as long as the ratio of self-loops to the original degree is bounded above and below, the mixing time of this modified walk is equivalent (up to constants) to the mixing time of the lazy walk on <span class="math-container">$G_1$</span>.</p>
<p>[1]
Peres, Yuval, and Perla Sousi. &quot;Mixing times are hitting times of large sets.&quot; Journal of Theoretical Probability 28, no. 2 (2015): 488-519.
<a href="https://www.dpmms.cam.ac.uk/%7Eps422/mix-hit.pdf" rel="nofollow noreferrer">https://www.dpmms.cam.ac.uk/~ps422/mix-hit.pdf</a></p>

CC BY-SA 4.0
2021-02-13T08:18:20.813Z
Thanks a lot for the answer. This helps. Just to confirm, it means that in case no such bound is specified for the ratio of self-loops to the original degree, the trivial bound can be used, i.e., in worst case (n-1)+1 self-loops are added and in degree 1 nodes and 0+1 self loop is added to nodes with degree (n-1), implying that in the lazier random walk would be n times slower. However, when it's known that the graph is mostly regular and only few self loops need to be added, then the bound is tighter (only constant difference).
SSS
CC BY-SA 4.0
2021-02-19T17:45:33.450Z
If this answer is helpful, there is a standard way to accept answers....
Yuval Peres
CC BY-SA 4.0
2021-02-12T23:59:23.277Z
2021-02-12T23:59:23.277Z
Yuval Peres
<p>Consider 2 graphs G1 and G2.</p>
<p>G1: Any non-regular graph.</p>
<p>G2: Same graph but with added self-loops such that degree of each node is the same (either some <span class="math-container">$\Delta$</span>, or maximum '<span class="math-container">$n$</span>', where <span class="math-container">$n$</span> is the number of nodes in the graph).</p>
<p>We run a lazy random walk on G1, such that the random walk at a node <span class="math-container">$v$</span> either stays at <span class="math-container">$v$</span>  with probability <span class="math-container">$1/2$</span> or moves out to a neighbor with probability <span class="math-container">$1/2d_{v}$</span>, where <span class="math-container">$d_{v}$</span> is the degree of the node <span class="math-container">$v$</span>. Consider, <span class="math-container">$t_{mix}$</span> as the mixing time of this random walk. Additionally, we maintain a queue where the starting node of the random walk is added to a queue, and thereafter each time the random walk jumps to a neighbor, the node it jumps to is added to the queue. Let the queue contain <span class="math-container">$k$</span> nodes when the random walk has mixed <span class="math-container">$(k&lt;= t_{mix})$</span>. Note that since the graph is non-regular the stationary distribution that it converges to is non-uniform.</p>
<p>Now, consider another random walk on G2, which chooses each edge with probability <span class="math-container">$1/d_{v}$</span>, where <span class="math-container">$d_v$</span> is the degree of node <span class="math-container">$v$</span> including the self-loops. Assume that this random walk exactly follows the previous random walk (on G1) in the sense that each time there is a jump to the neighbor, it jumps to the same neighbor as the previous walk, i.e., it will push the exact same nodes to its maintained queue. When we consider time, of course, this would be slower as, in low-degree nodes, the random walk would have to undertake many self-loops before being able to jump to a neighbor.  What I want to show that, is when the queue contains <span class="math-container">$k$</span> nodes or (<span class="math-container">$O(k)$</span> nodes), then this random walk has also mixed. Note that, as opposed to before, the stationary distribution here with respect to which we want the mixing is uniform (due to the added self-loops).</p>
<p>Is there any existing work that shows this? Or if not, what can be a good coupling argument to prove this? Any reference or help would be greatly appreciated.</p>
<p>(Observe that, the random walk on G2, can also be considered as another (biased) random walk on G1 where the random walk stays at the current node <span class="math-container">$v$</span> with probability <span class="math-container">$1-(deg(v)/n)$</span> and, with probability <span class="math-container">$1/n$</span>, moves to a uniformly at random chosen neighbor.)</p>

CC BY-SA 4.0
2021-02-11T18:01:37.443Z
The lazy walk on a connected graph is always ergodic, while the non-lazy walk on this graph might not be. See closely related question here: https://mathoverflow.net/questions/330064/comparing-mixing-time-of-lazy-and-non-lazy-markov-chains
Aryeh
CC BY-SA 4.0
2021-02-13T08:30:31.357Z
Thanks for the link. That, however, gives the link for a very specific coupling where the laziness depends on a Bernoulli random variable. I am not sure, if it directly applies for arbitrary non-regular graphs, as in whether such a coupling can always be shown to exist. Also, notice that both random walks are lazy (but with different number of self-loops per node), so both are connected and ergodic.
SSS
<graph-theory><pr.probability><markov-chains><random-walks>
Effect of self loops on mixing time?
SSS
# Effect of self loops on mixing time?

(Asked by: username_0 on 2021-02-11)

Consider 2 graphs G1 and G2.

G1: Any non-regular graph.

G2: Same graph but with added self-loops such that degree of each node is the same (either some $\Delta$, or maximum '$n$', where $n$ is the number of nodes in the graph).

We run a lazy random walk on G1, such that the random walk at a node $v$ either stays at $v$  with probability $1/2$ or moves out to a neighbor with probability $1/2d\_{v}$, where $d\_{v}$ is the degree of the node $v$. Consider, $t\_{mix}$ as the mixing time of this random walk. Additionally, we maintain a queue where the starting node of the random walk is added to a queue, and thereafter each time the random walk jumps to a neighbor, the node it jumps to is added to the queue. Let the queue contain $k$ nodes when the random walk has mixed $(k<= t\_{mix})$. Note that since the graph is non-regular the stationary distribution that it converges to is non-uniform.

Now, consider another random walk on G2, which chooses each edge with probability $1/d\_{v}$, where $d\_v$ is the degree of node $v$ including the self-loops. Assume that this random walk exactly follows the previous random walk (on G1) in the sense that each time there is a jump to the neighbor, it jumps to the same neighbor as the previous walk, i.e., it will push the exact same nodes to its maintained queue. When we consider time, of course, this would be slower as, in low-degree nodes, the random walk would have to undertake many self-loops before being able to jump to a neighbor.  What I want to show that, is when the queue contains $k$ nodes or ($O(k)$ nodes), then this random walk has also mixed. Note that, as opposed to before, the stationary distribution here with respect to which we want the mixing is uniform (due to the added self-loops).

Is there any existing work that shows this? Or if not, what can be a good coupling argument to prove this? Any reference or help would be greatly appreciated.

(Observe that, the random walk on G2, can also be considered as another (biased) random walk on G1 where the random walk stays at the current node $v$ with probability $1-(deg(v)/n)$ and, with probability $1/n$, moves to a uniformly at random chosen neighbor.)

**Tags:** graph-theory, pr.probability, markov-chains, random-walks
> **Comments:**
> **username_1**: The lazy walk on a connected graph is always ergodic, while the non-lazy walk on this graph might not be. See closely related question here: https://mathoverflow.net/questions/330064/comparing-mixing-time-of-lazy-and-non-lazy-markov-chains  
> **username_0**: Thanks for the link. That, however, gives the link for a very specific coupling where the laziness depends on a Bernoulli random variable. I am not sure, if it directly applies for arbitrary non-regular graphs, as in whether such a coupling can always be shown to exist. Also, notice that both random walks are lazy (but with different number of self-loops per node), so both are connected and ergodic.  

---

## 1 answers

### Answer by username_2 on 2021-02-12. Score: 3 | Accepted answer

Your question is essentially covered by Cor 9.5 in [1]
which implies that as long as the ratio of self-loops to the original degree is bounded above and below, the mixing time of this modified walk is equivalent (up to constants) to the mixing time of the lazy walk on $G\_1$.

[1]
Peres, Yuval, and Perla Sousi. "Mixing times are hitting times of large sets." Journal of Theoretical Probability 28, no. 2 (2015): 488-519.
[https://www.dpmms.cam.ac.uk/~ps422/mix-hit.pdf](https://www.dpmms.cam.ac.uk/%7Eps422/mix-hit.pdf)

> **Comments:**
> **username_0**: Thanks a lot for the answer. This helps. Just to confirm, it means that in case no such bound is specified for the ratio of self-loops to the original degree, the trivial bound can be used, i.e., in worst case (n-1)+1 self-loops are added and in degree 1 nodes and 0+1 self loop is added to nodes with degree (n-1), implying that in the lazier random walk would be n times slower. However, when it's known that the graph is mostly regular and only few self loops need to be added, then the bound is tighter (only constant difference).  
> **username_2**: If this answer is helpful, there is a standard way to accept answers....  

---

