1
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ 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: mathoverflow.net/questions/330064/… $\endgroup$ – Aryeh Feb 11 at 18:01
  • $\begingroup$ 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. $\endgroup$ – SSS Feb 13 at 8:30
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$ – SSS Feb 13 at 8:18
  • $\begingroup$ If this answer is helpful, there is a standard way to accept answers.... $\endgroup$ – Yuval Peres Feb 19 at 17:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.