**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.1What 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.2What 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.

infon the kernels, not asup. So the fact that diagonal kernels are "bad" (i.e there all have $L(K,\mu)=1$) is not a problem; $\mathcal K_{\varepsilon,\delta}$ contains other non-trivial kernels when $\varepsilon > 0$. Makes sense ? $\endgroup$ – dohmatob Dec 26 '19 at 11:062more comments