# Mixing time for random walk on graph with $k$ loops on each vertex

I try to find an upper bound for the mixing time of a random walk $$S$$ on a connected graph $$L=(V,E)$$ which has $$k<\min_{v\in V}d(v)$$ loops at every vertex. The transition probabilities of this random walk are given by $$p_{v,w}=\dfrac{1}{d(v)+k};\qquad p_{v,v}=\dfrac{k}{d(v)+k}$$ where $$d(v)$$ is the degree of the vertex $$v$$. I can easily calculate the stationary distribution $$\pi(v) = \dfrac{d(v)+k}{\sum_{v}d(v)+k|V|}$$ but now I am interested in the mixing time of $$S$$, $$t_{mix}:=\inf\{t\geq 0|\inf_{\mu}||\mu P^t -\pi||_{TV}\leq 4^{-1}\}$$ (see Markov Chains and Mixing Times; David A. Levin, Yuval Peres, Elizabeth L. Wilmer). For a random walk on a simple graph, without loops, I know that the mixing time is bounded from above by $$C\log\left(\min_{v\in V}\dfrac{1}{\pi(v)}\right)\Phi(L)^{-1}$$ where $$C$$ is some constant and $$\Phi(L)$$ is the cheeger constant of $$L$$. In all approaches I have found, which use spectral graph theory, the fact that $$\mathrm{trace}(A)=0$$ is explicitly used for the adjacency matrix $$A$$ of $$L$$. But how does it work for graphs with loops?

The inequality you are citing should have a power 2 on the Cheeger constant (a.k.a the bottleneck ratio), so the inequality should read: $$t_{\rm mix} \le C\log\left(\min_{v\in V}\dfrac{1}{\pi(v)}\right)\Phi(L)^{-2} \,.$$
• In my case I am missing $\mathrm{deg}(v)-k$ loops at each vertex $v$ to obtain a lazy RW or I have $k$ too many loops for a simple random walk with transition matrix $P$ to obtain a lazy simple random walk (LSRW) by $2^{-1}(\mathrm{Id}+P)$. Can I say that my random walk with $k$ loops has a smaller mixing time than the LSRW because I have less loops (using a coupling argument)? Aug 5, 2021 at 8:52
• The answer in general is no. Suppose your graph is the complete bipartite graph $K(n,n)$ with $n$ nodes on each side. The mixing time for lazy SRW on this graph is $O(1)$, indeed $t_{\rm mix}$ is at most 4. But when you add a single loop at each node and consider simple RW, the mixing time is at least $n/2$ (and is indeed of order $n$.) Aug 5, 2021 at 16:50