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$?


1 Answer 1


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.

  • $\begingroup$ 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\|$. $\endgroup$
    – Hermi
    Commented Jun 23, 2020 at 1:44
  • $\begingroup$ @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). $\endgroup$ Commented Jun 23, 2020 at 18:03
  • $\begingroup$ Why $Z_t \geq Z_s$? Do not we need to find a coupling $(Z_t, Z_s)$? $\endgroup$
    – Hermi
    Commented Jun 24, 2020 at 18:16
  • $\begingroup$ @BobO. : The existence of such a coupling is well known. See e.g. projecteuclid.org/euclid.aop/1176995659 $\endgroup$ Commented Jun 24, 2020 at 23:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.