0
$\begingroup$

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)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – Jens Fischer
    Commented Aug 5, 2021 at 8:52
  • $\begingroup$ 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$.) $\endgroup$
    – Yuval Peres
    Commented Aug 5, 2021 at 16:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .