Markov Chain Mixing Time of the Complete Graph
Let $M$ be an ergodic Markov chain with stationary probability $\pi$. For a state $x \in M$, let $p_x^t$ denote the distribution of a point which starts at $x$ and performs $t$ steps according to the transition matrix of $M$. The variation distance between $\pi$ and $p_x^t$, which is a measure of the similarity between the distributions, is given by the formula
$$
\|\pi - p_x^t\| = \frac{1}{2} \sum_{\sigma \in M} |\pi(\sigma) - p_x^t(\sigma)|.
$$
The sum goes over all states in $M$. The mixing time of a Markov chain $M$ is the smallest $t$ such that for every state $x$, $\|\pi - p_x^t\| \leq 1/(2e)$ (your account may use a different constant).

Given a graph $G$ without disconnected nodes, we can define a Markov chain as follows. The state space is the vertex set of $G$. When at state $x$, the next state is chosen uniformly at random from the neighbors of $x$.

In the particular case of the complete graph $K_n$, the random walk simply chooses a random vertex different from the current vertex. As you mention, $\pi$ is the uniform distribution. Let us compute some variation distances, for some vertex $x$ (the results are the same for all vertices):
$$
\begin{align*}
&amp;\|\pi - p_x^0\| = \frac{1}{2} \left[|\tfrac{1}{n} - 1| + (n-1) |\tfrac{1}{n}-0|\right] = 1 - \frac{1}{n}. \\
&amp;\|\pi - p_x^1\| = \frac{1}{2} \left[|\tfrac{1}{n} - 0| + (n-1)|\tfrac{1}{n} - \tfrac{1}{n-1}|\right] = \frac{1}{2} \left[\frac{1}{n} + \frac{n-1}{n(n-1)}\right] = \frac{1}{n}.
\end{align*}
$$
In both cases we have split the sum into two parts: $\sigma = x$ and $\sigma \neq x$. For all $n$ we have $\|\pi - p_x^0\| &gt; 1/(2e)$. For $n &gt; 2e$ (i.e., $n \geq 6$), we see that $\|\pi - p_x^1\| &lt; 1/(2e)$. Therefore for $n \geq 6$, the mixing time is $1$.



With some effort, we can compute explicitly the variation distances for larger $t$. The transition matrix of the Markov chain is $(J-I)/(n-1)$ (where $J$ is the all ones matrix and $I$ is the identity matrix). Denoting by $e_x$ the basis vector corresponding to $x$, we have $p_x^t = (J-I)^t/(n-1)^t e_x$. Next, notice that $(J-I)/(n-1) \cdot \mathbf{1} = \mathbf{1}$ (where $\mathbf{1}$ is the constant 1 vector), and all other eigenvectors have the eigenvalue $-1/(n-1)$ (the corresponding eigenspaces being all vectors with zero sum). In particular, we can write $e_x = \frac{1}{n} \mathbf{1} + (e_x - \frac{1}{n} \mathbf{1})$, and so
$$
p_x^t = \left(\frac{J-I}{n-1}\right)^t e_x = \frac{1}{n} \mathbf{1} + \left(-\frac{1}{n-1}\right)^t (e_x - \tfrac{1}{n} \mathbf{1}).
$$
Explicitly, we have
$$
p_x^t(y) = \begin{cases}
\frac{1}{n} + \left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right) &amp; \text{if } y = x, \\
\frac{1}{n} - \left(-\frac{1}{n-1}\right)^t \frac{1}{n} &amp; \text{otherwise}. \end{cases}
$$
Therefore
$$
\begin{align*}
\|p_x^t - \pi\| &amp;= \frac{1}{2}\left|\left(-\frac{1}{n-1}\right)^t \left(1 - \frac{1}{n}\right)\right| + \frac{1}{2} \left|\left(-\frac{1}{n-1}\right)^t \frac{1}{n}\right| \\ &amp;=
\frac{1}{2(n-1)^t} \left[1 - \frac{1}{n} + \frac{n-1}{n} \right] \\ &amp;=
\frac{1}{(n-1)^{t-1}n}.
\end{align*}
$$
Using this explicit formula, we find that the mixing time of $K_2$ is infinity (indeed, the chain is periodic), and the mixing time of all of $K_3,K_4,K_5$ is $2$. For $n \geq 6$, as commented above, the mixing time of $K_n$ is $1$.