My question comes from section 7.1.1. of the book "Markov Chains and Mixing Times (2nd edition)" written by David A.Levin and Yuval Peres. Specifically, let $(X_t)$ be a Markov chain with irreducible and aperiodic transition matrix $P$ on a finite state space $\mathcal X$, and suppose that the stationary distribution $\pi$ is uniform over $\mathcal X$. Define $$\Delta := \max_{x\in \mathcal X} |\{y\colon P(x,y)>0\}|$$ and denote by $\mathcal X^x_t$ the set of states accessible from $x$ $\color{red}{\text{in exactly $t$ steps}}$. The author claims that in the reversible case when $\Delta \geq 3$, we have $$|\mathcal X^x_t| \leq 1+\Delta\sum_{j=0}^{t-1} (\Delta-1)^t.$$ However, no explanation or justification is provided and I do not think it is obvious as well. Any help or suggestions will be greatly appreciated!
1 Answer
This is essentially a graph problem. In English, what that inequality you wrote is saying:
If I were to walk on a graph, in t steps, I can at most reach myself, or I can reach someone through one of my neighbors (of which there are at most $\Delta$) in $t-1$ steps. Each of my neighbors have at most $\Delta-1$ new neighbors, (since I was one of their neighbors, and their degree is at most $\Delta$), and we can keep recursing like that all the way up to time $t-1$.
Note that this crucially uses reversibility to go from $\Delta$ to $\Delta -1$, since I know that if I have a neighbor, they also have to neighbor me.
I assume they removed this estimate since you do not need something that sharp for any of their calculations. (I checked the PDF posted in the link, and they write out the cruder estimate $\Delta^t$.)
