Let $G(V,E)$ be the following graph: The vertex set $V$ is a $n\times n$ grid, and two vertices are connected $(E)$ if they lie on either the same row or the same column. This is the rook's graph: It can be thought of as a $n\times n$ chess board with two vertices connected $i$ they represent a legal move by a rook. What is the mixing time of a random walk of a rook on the chess board (graph $G$)?
So far, I noticed that the graph is ergodic (strongly connected and aperiodic) - so there is a stationary distribution for this random walk. Moreover, I observe that this problem is closely related to the random walk on $K_n$ with a rapid mixing time of $e^{\Omega(-t)}$. But I could not procced
First lets reference an abbreviation of a theorem from Levin, Peres, and Williams:
Theorem 12.4 (LPW): Let $P$ be the transition matrix of a reversible, irreducible Markov chain with state space $\mathcal{X}$ and let $\displaystyle\pi_{\min} := \min_{x\in\mathcal{X}} \pi(x)$. Then $t_{\text{mix}} (\varepsilon) \leq t_{\text{rel}} \log (\frac{1}{\varepsilon\,\pi_{\text{min}}})$.
You noted that the Rook's walk's graph is ergodic. This is good, and we can say further it is symmetric, so we know that the stationary distribution, $\pi$, is uniform. Kim calculated the relaxation time, $t_\text{rel} = \frac{d(n-1)}{n}$, which therefore gives a loose bound on the mixing times. Note, $(d,n)$ is the dimension and length of the board. Chessboards in real life have $(d,n) = (2,8)$.
Proposition 2.3 (SSK): For the rook's walk on $\mathbb{Z}_n^d$ where $n>2$,
$$ \frac{d(n-1)}{n} \log \left(\frac{1}{2\varepsilon}\right) \leq t_{\text{mix}} (\varepsilon) \leq \frac{d(n-1)}{n} \log \left(\frac{n^d}{\varepsilon}\right).$$
Later, McLeman et al. calculated bounds for the Rook's walks by employing a path coupling technique. These results for the 2-dimensional case are asymptotically tight.
Theorem 6.1 (MORS): For the $n^d$ rook's walk, we have $$ t_{\text{mix}}(\varepsilon) \leq \left\lceil \frac{\log \frac{d}{\varepsilon}}{\log \frac{d(n-1)}{(d-1)(n-1)+1}} \right\rceil.$$
Sources:
(LPW): Markov Chains and Mixing Times, second edition. David A. Levin, and Yuval Peres, with contributions by Elizabeth L. Wilmer, 2009.
(SSK): Mixing Time of a Rook’s Walk, Steven S. Kim, 2012
(MORS): Mixing times for the rook's walk via path coupling. Cam McLeman, Peter T. Otto, John Rahmani, Matthew Sutter, 2017