I am reading the "Markov Chains and mixing time 1st edition" by Levin and Peres, I got stuck on exercise $6.7$ and have a hard time to understand its solution.
Here is the description direct from the page. $80$ of this book.
Consider the graph $G$ obtained by taking two complete graphs on n vertices and “gluing” them together at a single vertex. We analyze here simple random walk on a slightly modified graph, $G'$. Let $v^{\ast}$ be the vertex where the two complete graphs meet. After gluing, $v^{\ast}$ has degree $2n − 2$, while every other vertex has degree $n − 1$. To make the graph regular and to ensure non-zero holding probability at each vertex, in $G'$ we add one loop at $v^{\ast}$ and $n $ loops at all other vertices. (See Figure 6.2 for an illustration when $n = 4$.) The uniform distribution is stationary for simple random walk on $G'$, since it is regular of degree $2n − 1$.Figure 6.2 \
the exercise $6.7$ in page. $84$ is asked to prove a lower bound of of mixing time of this random walk by considering the set $A \subset \mathcal{X} $ of all the vertices in one of the two complete graph. Where $\mathcal{X}$ is the set of vertices.
Solution in page. $333$ the authors claims that the transition distribution of $A$ after $t$ steps from initial vertex $x \not \in A$ is
$$P^{t}(x, A) = 1-(1-\alpha_n)^t$$ where
$$\alpha_n =\frac{1}{2}\left[ 1- \frac{1}{2n-1}\right] \frac{1}{n-1}$$
how does this comes out?
The solution in the book seems to me to be incorrect (at least, I can't see how to make sense of the expression for $P^{t}(x,A)$ they give). I'll give an alternate solution here. I'm assuming the vertex $v^{*}$ is in $A.$
Since the stationary distribution is uniform, we have $\pi(A)=\frac{n}{2n-1}>\frac{1}{2}.$ From the definition of total variation distance, for any vertex $x$ we have $$|| P^{t}(x, \cdot)-\pi ||_{TV} \geq |P^{t}(x,A)-\pi(A)| \geq \pi(A)-P^{t}(x,A)>\frac{1}{2}-P^{t}(x,A)$$
If $x \not\in A$, then for the walk started at $x$ to be in $A$ at $t$ steps, it must first travel through $v^{*}$. Let $\tau_{v^{*}}$ be the hitting time of $v^{*}$, i.e., the first time the walk visits $v^{*}.$ From the preceding observation, we must have $P^{t}(x, A) \leq \mathbf{P}_{x}(\tau_{v^{*}} \leq t).$ Since $P(v,v^{*})=\frac{1}{2n-1}$ for any vertex $v$, we have $$\mathbf{P}_{x}(\tau_{v^{*}}>t)=\left(1-\frac{1}{2n-1}\right)^{t}=\left(1-\frac{1}{2n}(1+o(1))\right)^{t}.$$ Therefore, $$P^{t}(x,A) \leq \mathbf{P}_{x}(\tau_{v^{*}})=1-\mathbf{P}_{x}(\tau_{v^{*}}>t)=1-\left(1-\frac{1}{2n}(1+o(1))\right)^{t}$$
which, combined with the first inequality, yields
$$|| P^{t}(x, \cdot)-\pi ||_{TV} \geq \left(1-\frac{1}{2n}(1+o(1))\right)^{t}-\frac{1}{2}.$$
From here, the proof in the book proceeds correctly.