# How to show that $d_G(t)$ is decreasing in $t$ for a geometry mixing time?

Let $$P$$ be the transition matrix of a Markov chain with state-space $$\mathcal{X}$$, $$\pi$$ is the stationary distribution with $$\pi=\pi P$$, and $$Z_t$$ be a geometric random variable of parameter $$1/t$$ taking values in $$\{1,2,\dots, \}$$ and independent of $$x$$. Define $$d_G(t):=\max_{x\in\mathcal{X}}\|P_x(X_{Z_t}=\cdot)-\pi\|_{TV}$$ where "TV" means total variation distance between two probability distributions $$\mu$$ and $$\nu$$ on $$\mathcal{X}$$ is defined by $$\|\mu-\nu\|_{TV}:=\max_{A\subset \mathcal{X}}|\mu(A)-\nu(A)|$$

How to show that $$d_G(t)$$ is decreasing in $$t$$?

This is true assuming that $$Z_t$$ is independent of the Markov chain. Indeed, then $$d(t):=d_G(t)=\max_x E\|P_x(Z_t)-\pi\|_{TV},$$ where $$P_x(n):=\delta_x P^n$$ and $$\delta_x$$ is the row matrix $$([a_y]_{y\in\mathcal X})^T$$ with $$a_y:=1_{y=x}$$. It is easy to see that for any probability measures $$\mu$$ and $$\nu$$ $$\|\mu-\nu\|_{TV}=\sup_{0\le f\le1} \int f\,d(\mu-\nu), \tag{0}$$ where $$\sup_{0\le f\le1}$$ is taken over all measurable functions $$f$$ such that $$0\le f\le1$$.
Take now any real $$s$$ and $$t$$ such that $$1\le s\le t$$. We have to show that then $$d(t)\le d(s)$$. So, it suffices to show that for each $$x$$ $$E\|P_x(Z_t)-\pi\|_{TV}\overset{\text{(?)}}\le E\|P_x(Z_s)-\pi\|_{TV}. \tag{1}$$ The random variable $$Z_t$$ is stochastically greater than $$Z_s$$. So, without loss of generality, $$Z_t\ge Z_s$$. Take now any column matrix $$f=[f_x]_{x\in\mathcal X}$$ with $$f_x\in[0,1]$$ for all $$x$$. Then the entries of the (random) column matrix $$P^{Z_t-Z_s}f$$ are in the interval $$[0,1]$$ as well and hence $$(P_x(Z_t)-\pi)f=(P_x(Z_s)-\pi)P^{Z_t-Z_s}f\le\|P_x(Z_s)-\pi\|_{TV}$$ by (0). So, again by (0), $$\|P_x(Z_t)-\pi\|_{TV}\le\|P_x(Z_s)-\pi\|_{TV}.$$ Taking now the expectations, we get (1), as desired.
• Thanks! How about $d(t)$ for general time $t$ rather than geometric time? It seems that we need to prove $\|\mu P-\nu P\|\leq \|\mu-\nu\|$.
• @BobO. : The proof holds for any stochastically increasing family $(Z_t)$ of random variables. For all probability measures $\mu$ and $\nu$, the inequality $\|\mu P-\nu P\|_{TV}\le\|\mu-\nu\|_{TV}$ holds by (0). Jun 23 '20 at 18:03
• Why $Z_t \geq Z_s$? Do not we need to find a coupling $(Z_t, Z_s)$?