1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Consider $K(x) = \delta_x$... $\endgroup$ – Martin Hairer Dec 26 '19 at 9:43
  • $\begingroup$ @MartinHairer Please could you be more explicit. Except I'm missing something, this suggestion cannot work (i.e cannot produce any informative bound) as it disregards all problem parameters: $\varepsilon$, $\delta$, etc. $\endgroup$ – dohmatob Dec 26 '19 at 9:55
  • $\begingroup$ @MartinHairer If fact, if $K(x) = \delta_x$, then $TV(\mu K,\nu K) \equiv TV(\mu,\nu)$, which is tautological. No ? $\endgroup$ – dohmatob Dec 26 '19 at 10:07
  • $\begingroup$ This is my point. Unless I misread your definitions, the trivial example belongs to all the $\mathcal{K}_{\varepsilon,\delta}$, so you can't improve on the trivial bound $1$ unless you restrict yourself to smaller classes of kernels. $\endgroup$ – Martin Hairer Dec 26 '19 at 11:02
  • $\begingroup$ @MartinHairer You probably misread the definitions. For example, $L(\mathcal K_{\varepsilon,\delta},\mu) := \inf_{K \in \mathcal K_{\varepsilon,\delta}} L(K,\mu)$. It's an inf on the kernels, not a sup. 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:06
1
$\begingroup$

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\|$.

$\endgroup$
  • $\begingroup$ Thanks for the detailed response; upvoted! The singularities you talk about would go away if I consider Wasserstein metric instead of TV in my questions, right ? Back to TV, I've tried to compute bounds for Gibbs kernels $K_\varphi(x'|x) = e^{-2\varphi(x,'x)/\lambda}d\gamma$ for base measure $\gamma \in \mathcal P(X)$, a bandwidth parameter $\lambda$ and potentials $\varphi: X\times X \rightarrow \mathbb R$ which are $R$-Lipschitz w.r.t first argument, and I obtain useful bounds of the form $L(K,\mu) \le D(K) \le (e^{2RD/\lambda}-1) / (e^{2RD/\lambda} + 1) < 1$, where $D=diam(X)$. $\endgroup$ – dohmatob Dec 26 '19 at 20:40
  • $\begingroup$ My motivation for considering the kernels in $\mathcal K_{\varepsilon,\delta}$ and later $K_{\varepsilon}$ was to create kernels which don't move too far per step. The Gibbs distribution seems to be a "mollified" version of this idea. I wonder if there are other ways to do this. $\endgroup$ – dohmatob Dec 26 '19 at 20:45
  • $\begingroup$ I mean the usual singularity of measures (so that two probability measures are singular if the total variation of their diference is 2) which indeed does not affect the transportation distance. Of course, in your Gibbs setup there won't be any singular transition probabilities, and the Markov operator can well be contracting in the total variation metric. $\endgroup$ – R W Dec 26 '19 at 22:14
  • $\begingroup$ OK, thanks. It's possible my quick-and-dirty bound for Gibbs kernels is not very optimal. Q: Is there any concrete reference on TV-contraction of Gibbs kernels ? Thanks in advance. $\endgroup$ – dohmatob Dec 26 '19 at 22:41
  • $\begingroup$ If I understand correctly you just use the fact that for these transition probabilities $\|\pi_x-\pi_y\|$ is bounded away from 2 - which is essentially Doeblin's condition. $\endgroup$ – R W Dec 26 '19 at 23:31

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.