Canonical path method for simple random walk on a box 
I have a question on Perla Sousi's lecture notes on "Mixing times of Markov chains". Specifically, in Claim 4.1 it is mentioned that "since there are $n^d$ points in the box and for each point $x$, there are at most $n$ points $y$ such that $e ∈ \Gamma_{xy}$".
However it seems easy to find counterexamples to this statement (based on the choice of canonical path which match the coordinate one at a time, i.e., the path from $(x_1,x_2,...,x_d) \to (y_1,y_2,...,y_d)$ is given by  $$(x_1,x_2,...,x_d) \to (y_1,x_2,...,x_d) \to (y_1, y_2, ..., x_d) \to ... \to (y_1,y_2,...,y_d).$$ Each time, the changes in coordinates is monotone). A easy counterexample I found is as follows: take $n = 3$ and $d = 2$, so the state space $\{1,2,3\}^2$ looks like a "田", with the lower-left-corner labelled $(1,1)$ and the upper-right-corner labelled $(3,3)$, fix $x = (1,1)$ and the edge $e = (1,1) \to (2,1)$ (the horizontal edge joining (1,1) to (2,1)), then it seems that there are $6 = 2·n $ points $y$ such that $e ∈ \Gamma_{xy}$, namely $y$ can be $(2,1), (2,2), (2,3), (3,1), (3,2)$ and $(3,3)$. This is true because of the way we choose the path between $x$ and $y$ (i.e., update coordinate by coordinate, and the 1st coordinate is updated first). So I am really confused about the statement in bold. Thank you very much any help! Note: In the statement of Claim 4.1., I prefer to use/work with $\{1,2,\ldots,n\}^d$ in place of $[0,n]^d \cap \mathbb{Z}^d$.
 A: We can fix the argument by rephrasing it as follows (in two dimensions):

*

*If $e$ is a vertical edge, then to have $e \in \Gamma_{xy}$, there are $\le n^2$ ways to choose $x$ (because that's a general bound) and $\le n$ ways to choose $y$ (because $e$ can only be followed by more vertical edges).

*If $e$ is a horizontal edge, then to have $e \in \Gamma_{xy}$, there are $\le n$ ways to choose $x$ (because $e$ can only be preceded by more horizontal edges) and $\le n^2$ ways to choose $y$ (because that's a general bound).

In general, for $d$-dimensional grids, to have $e \in \Gamma_{xy}$, we will have $\le n^k$ choices for $x$ and $\le n^{d+1-k}$ choices for $y$, where $k$ will depend on the orientation of $e$. Suppose that $e = vw$ is changing the $k^{\text{th}}$ coordinate: $v_k \ne w_k$. Then

*

*The previous edges on $\Gamma_{xy}$ were changing coordinates $1, 2, \dots, k$ only. So $$(x_{k+1}, \dots, x_d) = (v_{k+1}, \dots, v_d) = (w_{k+1}, \dots, w_d)$$ and only $(x_1, \dots, x_k)$ are unknown. There are at most $n^k$ ways to pick those coordinates.

*Subsequent edges on $\Gamma_{xy}$ will only change coordinates $k, k+1, \dots, d$. So $$(y_1, \dots, y_{k-1}) = (v_1, \dots, v_{k-1}) = (w_1, \dots, w_{k-1})$$ and only $(y_k, \dots, y_d)$ are unknown. There are at most $n^{d-k+1}$ ways to pick those coordinates.

In all cases, $e$ lies on at most $n^k \cdot n^{d-k+1} = n^{d+1}$ paths $\Gamma_{xy}$.
