Given a directed graph $G=(V,E)$, with no self-loops, with a vertex that has a maximal out-degree $\le d\in O(\log |V|)$, and with a diameter $\text{diam}(G)\in O(\text{poly }d)$, consider converting the adjacency matrix of $G$ into a lazyish, doubly-stochastic transition matrix, with the following transition probabilities:

- $\forall x\in V,\:p(x,x)=1-\frac{\text{deg} (x)}{d}$
- $\forall (x,y)\in E,\:p(x,y)= \frac{1}{d}$

where $\text{deg} (x)$ is the out-degree of vertex $x$.

We thus have

- $\forall x\in V,\sum p(x,y_i)=1$

We also require

- $\forall y\in V,\sum p(x_i,y)=1$

We are also given that the transition matrix is not periodic.

Can we say that it is always the case that the mixing time $T_{mix}(G)$ of a random walk on $G$ is also polynomial in $d$?

Much as a random walk on a Cayley graph of a group is doubly-stochastic, I'm picturing a Markov chain acting on a rather big, discrete graph that's not *a-priori* given by a regular graph. However, by adding enough laziness, the Markov chain may be set up so that it's also doubly-stochastic, as a permutation of the state space. If we then bound the diameter of the graph, does that help to bound the mixing time of the graph?

I think Nachmias and Peres show that, in general for an Erdos–Renyi random graph, if the walk were lazy (i.e. $p(x,x)=\frac{1}{2}$ and $p(x,y)=\frac{1}{2\text{ deg}(x)}$), then $T_{mix}(G)$ is of order $\text{diam}(G)^3$.

However, if $G$ wasn't an Erdos-Renyi random graph but merely had bounded degree, there might be some bottlenecks that can't be excluded.

(Forgive me if this obvious, or if my terminology is not correct, or if I have too many errors in my question. I'll delete if there are too many errors.)