Suppose I have a weighted graph $G$, and let $M$ be the Markov chain corresponding to a random walk on $G$. Let $t_{\text{mix}, M}(\epsilon)$ be the $\epsilon$-mixing time of $M$.
Now let $M'$ be the "personalized PageRank" random walk on $G$, which I define below, with restart probability $r$. Let $t_{\text{mix}, M'}(\epsilon)$ be the mixing time on $M'$.
Is there any relation between $t_{\text{mix}, M'}(\epsilon)$ and $t_{\text{mix}, M}(\epsilon)$?
EDIT: I probably should be more clear about what I mean by a personalized PageRank random walk on $G$. Fix a set of vertices $v_1, ..., v_n$ and $r \in (0,1)$. Suppose you are at vertex $w$. Then:
- with probability $1-r$, you move to the next state in $M$, as you usually would
- with probability $r$, you teleport to one of $v_1, ..., v_n$, picked uniformly at random.