Uniform upper bound on contraction coefficient w.r.t total-variation metric, of a certain set of block-diagonal Markov kernels

Question

Disclaimer. This is related to another question I've asked on the TCS site https://cstheory.stackexchange.com/q/46097/44644. I'm new to information theory (and other relevant fields). It's even possible that I'm not using the appropriate language / terminology to describe my problem. Please any kind of insight, clarification, solution would be very much appreciated.

Keywords: data-processing inequalities; Markov kernel; ergodicity; contractive Markov kernels; Dobrushin coefficient

I $-$ Setup

Let $X=(X,d)$ be a Polish space equipped with the Borel sigma-algebra. Let $\mathcal P(X)$ the the space of all probability distributions on $X$ and let $\mathcal K(X,X)$ be the space of all Markov kernels $K:X \rightarrow \mathcal P(X)$ on $X$.

Now, for $\varepsilon > 0$, $\delta \in [0, 1)$, and some fixed $\mu \in \mathcal P(X)$, define

$$ \mathcal K_{\varepsilon,\delta} := \{K \in \mathcal K(X,X) \mid \mathbb P_{\tilde{x} \sim K(\cdot|x)}(d(\tilde{x},x) > \varepsilon) \le \delta\;\text{for }\mu\text{-a.e }x \in X\}. $$ For simplicity (and if it helps to simplify things), "...$\text{for }\mu\text{-a.e }x \in X$" may be replaced with "...for all $x \in X$".

I'm interested in obtaining upper-bounds on the quantity $L(\mathcal K_{\varepsilon,\delta},\mu)$ defined by $$ L(\mathcal K_{\varepsilon,\delta},\mu):=\inf_{K \in \mathcal K_{\varepsilon,\delta}}L(K,\mu), $$ where $$ L(K,\mu):= \sup_{\nu \in \mathcal P(X),\; TV(\mu,\nu) > 0}\frac{TV(\mu K,\nu K)}{TV(\mu,\nu)}. $$ Likewise, I'd like to upper-bound $L(\mathcal K_{\varepsilon,\delta})$ defined by

$$ L(\mathcal K_{\varepsilon,\delta}) := \sup_{\mu}L(\mathcal K_{\varepsilon,\delta},\mu) $$

Thus $L(\mathcal K_{\varepsilon,\delta})$ is a kind of uniform Lipschitz constant for the kernels in $\mathcal K_{\varepsilon,\delta}$ w.r.t to the total-variation metric on $\mathcal P(X)$. One could consider a modified scenario replacing TV with some other "distance" like relative entropy, Wasserstein, etc. Not sure that would simplify the analysis though...

I.1 $-$ Main focus

For concreteness, we may restrict to the cases where $\mu$ has some "measure-concentration properties" (I'm not yet sure what form this should take...) and

• $X$ is $\mathbb R^n$ or $[0, 1]^n$ equipped with and $\ell_p$-norm;
• $X$ is the Hamming cube $\{0,1\}^n$;
• etc.

II $-$ Questions

Question 2.1 What are good upper-bounds for $L(\mathcal K_{\varepsilon,\delta},\mu)$ and $L(\mathcal K_{\varepsilon,\delta})$ ?

Of course such a "good" upper-bound must somehow depend on the problem parameters $\varepsilon,\delta$ explicitly.

II.2 $-$ A rough bound via Dobrushin coefficients

In view of obtain a (presumably very rough) bound, define the Dobrushin coefficient $D(K) \in [0, 1]$ of a Markov kernel $K$ by $$ D(K) := \max_{x,x'}TV(K(\cdot|x),K(\cdot|x')) = \frac{1}{2}\max_{A,x,x'}|K(A|x)-K(A|x')|, $$ where the supremum is taken over all measurable $A \subset X$ and distint points $x,x' \in X$. By, the (Dobrushin's) data-processing inequality, we have the bound $L(K,\mu) \le D(K)$, from where we get the (perhaps very loose) bound $$ L(\mathcal K_{\varepsilon,\delta}) \le L(\mathcal K_{\varepsilon,\delta,\mu}) \le \inf_{K \in \mathcal K_{\varepsilon,\delta}} D(K). $$ However, evening computing a good upper bound on $\inf_{K \in \mathcal K_{\varepsilon,\delta}} D(K)$ seems daunting.

Question 2.2 What is a good upper-bound for $\inf_{K \in \mathcal K_{\varepsilon,\delta}}D(K)$?

II.3 $-$ The case $\delta=0$

We now turn to the important particular case when $\delta = 0$. Consider the subset of deterministic Markov kernels $$ \mathcal K_\varepsilon := \{K_f \mid f \in \mathcal F_{\varepsilon}\}, $$

• $\mathcal F_\varepsilon$ is the set of measurable functions $f:X \rightarrow X$ such that $d(f(x),x) \le \varepsilon$ for all $x \in X$.
• $K_f$ is the Markov kernel on $X$ defined by setting $K_f(A|x) := 1_{f^{-1}(A)}(x)$, for every $x \in X$ and measurable $A \subseteq X$.

Somethings to note:

• $\nu K_f = f_{\#}\nu$ for every measurable function $f:X \rightarrow X$ and probability distribution $\nu \in \mathcal P(X)$. For such Markov kernels, we therefore have the following formula $$ L(K_f,\mu) = \sup_{\nu}\frac{TV(f_{\#}\mu,f_{\#}\nu)}{TV(\mu,\nu)}. $$
• $\mathcal K_\varepsilon \subseteq \mathcal K_{\varepsilon,0}$; thus $L(\mathcal K_{\varepsilon,0},\mu) \le L(\mathcal K_{\varepsilon},\mu)$ and $L(\mathcal K_{\varepsilon,0}) \le L(\mathcal K_{\varepsilon})$.
• $\mathcal K_{\varepsilon}$ is precisely the set of Markov kernels considered in my TCS post here https://cstheory.stackexchange.com/q/46097/44644.

Question 2.3. What are good upper-bounds for $L(\mathcal K_{\varepsilon},\mu)$, $L(\mathcal K_{\varepsilon})$, and $\inf_{K \in \mathcal K_\varepsilon} D(K)$?

III $-$ Maybe-be-useful references

• The paper https://arxiv.org/pdf/1411.3575.pdf seems to a relevant reference for my problems, but I'm still reading it and learning IT at the same time.

Answer 1

Although you mention the Hamming cube among your examples, my impression is that you are still more interested in the situation when the arising measure spaces are not atomic (discrete). I am afraid there is not much one can do in the continuous situation. The point is that although you are imposing conditions requiring "locality" of the transition probabilities (you require that for any point $x$ the corresponding transition probability $\pi_x$ have the property that $\pi_x B(x,\epsilon)>1-\delta$), these conditions (quite appropriate when talking about weak convergence) do not help at all in what concerns the possible singularity of the transition probabilities, and it is this singularity that is responsible for the total variation distance.

A very clear illustration of this phenomena is provided precisely by the deterministic case you mention at the end of your question. If the measure $f(\mu)$ (which you denote $f_\#\mu$) is not finitely supported, then $L(K_f,\mu)=1$ (take an $f(\mu)$-small subset of $X$, and let $\nu$ be the normalized restriction of $\mu$ to its preimage).

Returning to the general case, you would have to assume that $\mu$-almost all (if you work with the measures $\nu$ absolutely continuous with respect to $\mu$) or all (if you work with all measures $\nu$) transition probabilities $\pi_x$ are absolutely continuous with respect to a common measure $\lambda$ and impose further conditions on the total variation distances $\|\pi_x-\lambda\|$.