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.