Mixing Time of the Lazy Random Walk on Kₙ

Consider the lazy random walk on the complete graph $K_n$: at each step, the walker stays put with probability $\tfrac{1}{2}$ and moves to a uniformly random neighbor with probability $\tfrac{1}{2}$.

(a) Show that the transition matrix has two distinct eigenvalues: $\lambda_0 = 1$ (with multiplicity $1$) and $\lambda_1 = \tfrac{1}{2}\bigl(1 - \frac{1}{n-1}\bigr) = \frac{n-2}{2(n-1)}$ (with multiplicity $n-1$).

(b) Find the spectral gap $\gamma = 1 - \lambda_1$ and determine the mixing time $t_{\text{mix}}$ up to leading order in $n$.