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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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