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?


Thank you for your help!


(This question is a copy from [here](https://math.stackexchange.com/questions/4214270/mixing-time-for-random-walk-on-graph-with-k-loops-on-each-vertex))



Mixing time for random walk on graph with $k$ loops on each vertex
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} \,.$$


This need not hold on a simple graph without loops; e.g. it fails if the graph is bipartite, where the mixing time is infinite. The inequality holds for lazy simple random walk, where the number of loops added at each vertex equals its degree. In the most general case you need to also bound the most negative eigenvalue of the chain. For the simplest case of the inequality combine inequality (12.10) and Theorem 13.10 (Due to Jerrum-Sinclair and Lawler-Sokal) in [1].


[1] Markov Chains and Mixing Times; 2nd edition, <https://pages.uoregon.edu/dlevin/MARKOV/mcmt2e.pdf>


