Contraction of Markovian Operators in Orlicz Spaces
and Error Bounds for Markov Chain Monte Carlo

A Markov kernel acts on measures “from the right”, i.e., given a measure $\mu$ on $(\Omega,\mathcal{F})$, $\mu K(E)=\mu(K(E|\cdot))=\int d\mu(x)K(E|x),$ and on functions “from the left”, i.e., given a function $f:\Omega\to\mathbb{R}$, $Kf(x)=\int dK(y|x)f(y).$ Hence, given a function $f\in L^{p}(\mu)$, one can see $K$ as a mapping $K:L^{p}(\mu)\to L^{p}(\mu)$. Moreover, an application of Jensen’s inequality gives that $\mu((Kf)^{p})\leq\mu(K(f^{p}))=\mu K(f^{p})$, thus the mapping can be extended to $K:L^{p}(\mu)\to L^{p}(\mu K)$.

Given a Markov kernel $K$ and a measure $\mu$, let $K^{\star}_{\mu}$ denote the dual operator. By definition, the dual kernel can be seen as acting on $(L^{p}(\mu K))^{\star}\cong L^{q}(\mu K)$ with $q=\frac{p-1}{p}$ and returning a function in $(L^{p}(\mu))^{\star}\cong L^{q}(\mu)$. In particular, given a probability measure $\mu$ and two measurable functions $f,g$, one can define the inner-product $\langle f,g\rangle_{\mu}=\int(f\cdot g)d\mu,$ and $K^{\star}_{\mu}$ is the operator such that $\langle Kf,g\rangle_{\mu}=\langle f,K^{\star}_{\mu}g\rangle_{\mu K}$, for all $f$ and $g$. In discrete settings, the dual operator can be explicitly characterised via $K$ and $\mu$ as $K_{\mu}^{\star}(y|x)=K(y|x)\mu(x)/\mu K(y)$, see [13, Eq. (1.2)].

Given a sequence of random variables $(X_{t})_{t\in\mathbb{N}}$, one says that it represents a Markov chain if, given $i\geq 1$, there exists a Markov kernel $K_{i}$ such that for every measurable event $E$:

If for every $i\geq 1$, $K_{i}=K$ for some Markov kernel $K$, then the Markov chain is time-homogeneous, and we suppress the index from $K$. The kernel $K$ of a Markov chain is the probability of getting from $x$ to $E$ in one step, i.e., for every $i\geq 1$, $K(E|x)=\mathbb{P}(X_{i}\in E|X_{i-1}=x)$. One can then define (inductively) the $t$-step kernel $K^{t}$ as $K^{t}(E|x)=\int K^{t-1}(E|y)dK(y|x)$. Note that $K^{t}$ is also a Markov kernel, and it represents the probability of getting from $x$ to $E$ in $t$ steps: $K^{t}(E|x)=\mathbb{P}(X_{t+1}\in E|X_{1}=x)$. If $(X_{t})_{t\in\mathbb{N}}$ is the Markov chain associated to the kernel $K$ and $X_{0}\sim\mu$, then $\mu K^{m}$ denotes the measure of $X_{m+1}$ at every $m\in\mathbb{N}$. Furthermore, a probability measure $\pi$ is a stationary measure for $K$ if $\pi K(E)=\pi(E)$ for every measurable event $E$. When the state space is discrete, $K$ can be represented via a stochastic matrix.

Given a Markov kernel and a measure, one can define the corresponding dual [16] and show the following result, which is pivotal for characterising the convergence of a Markovian process to the stationary measure. The proof is deferred to Appendix A-B.

Furthermore, $K^{\star}_{\mu}$ can be proved to be Markovian [16, Section 2, Lemma 2.2].

Given a Young function $\psi:[0,+\infty)\to\overline{\mathbb{R}}^{+}$, the complementary function to $\psi$ in the sense of Young, denoted as $\psi^{\star}:\mathbb{R}\to\overline{\mathbb{R}}^{+}$, is defined as follows [18, Section 1.3]:

An Orlicz space can be endowed with several norms that render it a Banach space [19]: the Luxemburg norm, the Orlicz norm, and the Amemiya norm. We will henceforth ignore the Orlicz norm, as it is equivalent to the Amemiya norm [19], and we define the Luxemburg norm $L_{\psi}^{L}$ and the Amemiya norm $L_{\psi}^{A}$ as

Orlicz spaces and the corresponding norms recover well-known objects (e.g., $L_{p}$-norms) and characterise random variables according to their “tail”. For more details, see Appendix A-A.

The first application of our framework is stated below and follows from Theorem 3 and Eq. (15).

Corollary 3 relates the contraction coefficient of the dual operator to the mixing time of the corresponding Markov chain, thus motivating our study of said contraction coefficient. Moreover, as $\psi$ is arbitrary, a natural question concerns the choice of the norm. To address it, first we derive a general result providing intuition over what it means to be close in a specific norm. In particular, we relate the probability of any event under $\mu K^{t}$ with the probability of the same event under the stationary measure $\pi$ and an $L^{N}_{\psi}$-norm. We then focus on the well-known family of $L_{p}$-norms (particularly relevant for exponentially decaying probabilities under $\pi$), and show that asking for a bounded norm with larger $p$ guarantees a faster decay of the probability of the same event under $\mu K^{t}$. Finally, we design a Young function tailored to the challenging (and less understood) setting in which $\pi$ behaves like a power law [14].

We now apply Theorem 4 to various $\psi$, and start by demonstrating the advantage of considering $L_{p}$-norms with $p\neq 2$. The result below is proved in Section D-C.

As an immediate consequence, if $\left\lVert\frac{d\mu K^{t}}{d\pi}-1\right\rVert_{L_{p}(\pi)}\leq\epsilon,$ then for every $E$

The following setting is especially interesting for the applicability of Corollary 4. Consider a function $f:\mathcal{X}^{n}\to\mathbb{R}$ and $E=\{(x_{1},\ldots,x_{n}):|f(x_{1},\ldots,x_{n})-\pi(f)|\geq\eta\}$ for some fixed $\eta>0$. If $f(x_{1},\ldots,x_{n})=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x_{i})$ for $f_{1},\ldots,f_{n}$ with $0\leq f_{i}(x)\leq C$, by Hoeffding’s inequality one has:

where the constant $C^{2}$ at the exponent can be improved under additional assumptions, see e.g. [21]. Notice that Equation 20 does not require $\pi$ to be a product distribution. Indeed, for example, if the Markov chain has spectral gap $1-\lambda$, then Equation 20 holds with the additional constant at the exponent of $(1-\lambda)/(1+\lambda)$, see [11, Theorem 1]. Then, given $t\geq\tau_{\varphi_{p}}(K,\epsilon)$ and $q=\frac{p}{p-1}$, we have

Starting from Equation 21, one can now select $\epsilon$ such that the probability is exponentially decaying in the dimension of the ambient space $n$. In fact, a bound that decays exponentially in the dimension $n$ is guaranteed whenever, for a given $\eta$, $f$, and finite $p$,

For example, $\epsilon=\exp\left(n\eta^{2}/qC^{2}\right)$ guarantees exponential convergence in Equation 21 and plugging this choice in Equation 16 gives the bound below on the mixing time:

where $L_{p}^{\star}(\pi)=\sup_{\nu\ll\pi}\left\lVert\frac{d\nu}{d\pi}-1\right\rVert_{L^{p}(\pi)}$. We note that, besides $\epsilon$, both $L_{p}^{\star}(\pi)$ and $\left\lVert K^{\star}\right\rVert_{L_{p}^{0}\to L_{p}^{0}}$ depend on the dimension $n$. To maximise the rate of exponential decay in Equation 21, one has to take $p\to\infty$, which implies $q\to 1$. The price to pay is an increase of the mixing time and, to quantify such increase, it is crucial to provide tight bounds on the contraction coefficient of Markovian operators, beyond the usual $L_{2}$ space. Theorem 3 can then be leveraged to compute said bounds, and we now compare it with the standard approach in the literature, i.e., the Riesz-Thorin interpolation theorem between norms, which is stated below for convenience.

As an example, consider the binary symmetric channel of parameter $\lambda$. Then, $\gamma=(1-2\lambda)$ and Proposition 2 with $p>2$ yields:

In contrast, Theorem 3 gives:

which improves over Equation 26 for every $p$. Notably, Equation 27 holds even if $p\to 1$ and $p\to\infty$, while the result of Proposition 2 is vacuous in both cases (cf. Equation 25). Figure 2 considers Markov kernels induced by $5\times 5$ randomly generated stochastic matrices, and it shows that while the bound in Proposition 2 is always vacuous (red dots), the bound given by Equation 11 is always below $1$ and often very close to $0$ (blue dots). Moreover, given that we are in a discrete setting one can explicitly compute the $L_{\infty}$/$L_{1}$-operator norm for a specific kernel $K$ and interpolate between the $L_{\infty}$/$L_{1}$–operator and the spectral gap. The comparison yields the following results:

• •

  For $n=5,t=20,p=10$, our upper bound is roughly 50% smaller than Riesz-Thorin interpolation (on average over the 100 random trials)

• •

  For $n=5$, $t=200$, $p=100$, our upper bound is roughly 70% smaller than Riesz-Thorin interpolation (on average over the 100 random trials);

• •

  For $n=3,t=4,p=1.1$, our upper bound is roughly 23% smaller than Riesz-Thorin interpolation (on average over the 100 random trials);

• •

  For $n=3,t=4,p=1.5$, our upper bound is roughly 20% smaller than Riesz-Thorin interpolation (on average over the 100 random trials).

Proposition 2 was used by [11] to prove concentration for MCMC methods. Here, we show how an application of Theorem 3 improves over such results.

Let us briefly recall the setup. Given a function $f$, we want to estimate the mean $\pi(f)$ with respect to a measure $\pi$ which cannot be directly sampled. A common approach is to consider a Markov chain $\{X_{i}\}_{i\geq 1}$ with stationary distribution $\pi$, and estimate $\pi(f)$ via empirical averages of samples $\{X_{i}\}_{t_{0}+1}^{t_{0}+t}$, where the burn-in period $t_{0}$ ensures that the Markov chain is close to $\pi$.

We start by considering again the binary symmetric channel with parameter $\lambda$. The stationary distribution is $\pi=(1/2,1/2)$ and the spectral gap is $|1-2\lambda|$. Assume $X_{1}\sim\nu$ for some measure $\nu\neq\pi$ and $\lambda<1/2$. Applying Theorem 12 by [11] to $f$ s.t. $f\in[0,\frac{1}{t}]$, yields

where $p>1$, $q=p/(p-1)$, $\pi^{\otimes t}$ denotes the tensor product of $\pi$, and

In contrast, an application of Theorem 3 yields $\left\lVert(K-1_{\pi})^{t_{0}}\right\rVert_{L_{p}\to L_{p}}\leq(1-2\lambda)^{t_{0}}$ for every $p\in(1,+\infty]$. Hence, leveraging Equation 18 leads to