I assume that a result of the following kind is known, and I would really appreciate a reference for it... Or at least, some hints as to where to start looking.



> 
> **Theorem(?)**: Let $\varepsilon>0$ and Let $\Gamma=(V,E)$ be a finite regular non-bipartite graph of degree $d$, with $V=\{v\_1,\dots, v\_n\}$ and with isoperimetric constant $\delta>0$. Suppose we start at $v\_1$ and take a random walk on $\Gamma$ for $t$ steps. Then, provided $t>f(\varepsilon, \delta, n, d)$, we have
>  $$ \frac{1}{n}-\varepsilon \leq \mathbb{P}(\textrm{we are at vertex }v\_i) \leq \frac{1}{n}+\varepsilon$$
>  for every $i=1,\dots, n$.
> 
> 
> 


Obviously, the proper version of this theorem would give an explicit form for the function $f(\varepsilon, \delta, n, d)$. I'm figuring such a function would need to depend on all of these four variables, although I'm not sure about $d$.


I'm also interested in the case where the random walk is "lazy"; indeed, I'm generally interested in any results of this type, although the precise form given above is my primary focus.


Any hints would be appreciated. Thanks in advance!



Random walk and isoperimetric constant
Given the proper keywords, a quick search gives 


<https://ocw.mit.edu/courses/mathematics/18-409-topics-in-theoretical-computer-science-an-algorithmists-toolkit-fall-2009/lecture-notes/MIT18_409F09_scribe4.pdf>


as one of many many references.


Assume $\mu\_t$ is the measure at the $t^\text{th}$-step of your random walk and $\pi$ is the uniform distribution (which is the stationary one in this case).


Then $\| \mu\_t -\pi \|\_{\ell^2} \leq 2 \rho^t$ where $\rho$ is the spectral radius (see below).


To get a bound on the $\ell^1$-norm, one can add a factor of $\sqrt{n}$ due to the distortion of the $\ell^2$ and $\ell^1$ norm in a $n$-dimensional vector space $\| \mu\_t -\pi \|\_{\ell^1} \leq \sqrt{n} 2 \rho^t$


In the lazy case, this estimate is worse (because the corresponding $\rho$ is bigger), but it works also on bipartite graphs.


If $\Delta$ is the Laplacian on your graph (normalised so that its norm is 2, i.e. $\Delta f(x) = f(x) - \tfrac{1}{d} \sum\_{y \sim x} f(x)$), the the isoperimetric constant gives you a bound on the smallest non-zero eigenvalue, call it $\lambda$. There is some debate as to who you should name for this inequality (and whether one should write $\lambda\_1$ and $\lambda\_2$). But it depends on $d$, $\delta$ and that's it: $\lambda \geq \delta^2 / 2d^2$ (or $\lambda \geq 1 - \sqrt{ 1 - \delta^2/d^2}$ which is better but less known).


The spectral radius $\rho$ above is just $1-\lambda$ for the random walk, and $1-\lambda/2$ for the lazy walk.


Here is an outline of the proof. Your random walk is encoded as a matrix operator. This is $P = 1-\Delta$. Since $\Delta$ has spectrum in $[0,2]$ so $P$ has spectrum in $[-1,1]$. The (usual) lazy walk is given by $L = I - \tfrac{1}{2} \Delta$.


The estimate on the first positive eigenvalue of $\Delta$ (thanks to the isoperimetric constant), tells you that *orthogonal to the constant function*, the spectrum of $P$ is inside $[-1,1-\lambda]$ (and the spectrum of $L$ is inside $[0,1-\lambda/2]$.


The only "tricky" part for $P$, is that if the graph is not bipartite, you can prove there is nothing to worry about on the negative part of the spectrum, that is the spectrum is inside $[-1+\lambda,1-\lambda]$.


Now you know that if a vector lies orthogonal to the eigenspace for the eignevalue 1, then $\|Pv\|\_2 \leq c \|v\|\_2$ where $c$ is the next biggest eignevalue. Applying this to $v = s - \pi$ (where $s$ is some starting distribution), you get: $\| P(s-\pi) \|\_2 \leq \rho \|s - \pi\|\_2$.


This is because $s - \pi$ is orthogonal to constant functions (i.e. it sums to 0). After another step of the random walk its
$$
\| P^2(s-\pi) \|\_2 \leq \rho \| P(s-\pi) \|\_2 \leq \rho^2 \|s - \pi\|\_2
$$


Since the norm of $\|s - \pi\|\_2 \leq 2$ (in your case its $1+1/\sqrt{n}$) one gets the estimate:
$$
\| P^t(s -\pi) \|\_{\ell^2} \leq 2 \rho^t
$$
Now use that $P^t s = \mu\_t$ and $P^t \pi = \pi$ (because $P\pi =\pi$) to get:
$$
\| \mu\_t -\pi\|\_{\ell^2} = \| P^t( s -\pi) \|\_{\ell^2} \leq 2 \rho^t
$$
which is the estimate claimed above.


