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)
Best Answer
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