1. Introduction
Perturbation theory concerns the investigation of the stability of a given system under small changes. In the context of Markov chains, one typically studies the impact of perturbing the transition mechanism, namely the transition kernel or matrix, on the behavior of the corresponding chain. For example, one can study the resultant effect on the limiting distribution and approximation properties, see e.g. [Reference Kartashov17, Reference Mitrophanov30, Reference Mitrophanov31, Reference Roberts, Rosenthal and Schwartz35, Reference Rudolf and Schweizer36] and the references therein.
In this work, we extend the study of perturbation theory to the setting of killed Markov processes which possess quasi-stationary distributions. This is particularly motivated by recent developments in Markov chain Monte Carlo methods, where killed diffusions have been used to construct scalable algorithms to perform Bayesian inference for large data sets; see [Reference Kumar21, Reference Pollock, Fearnhead, Johansen and Roberts33]. Convergence properties of this approach, known as the quasi-stationary Monte Carlo (QSMC) method, have been investigated in [Reference Wang, Kolb, Roberts and Steinsaltz43].
Given that such methods have been applied to perform Bayesian inference, it is important to study their stability. We ask the following question: Can the quasi-stationary distribution be adversely affected by small perturbations of the system, which could arise, for instance, due to data corruption or missing data?
We start by modeling the perturbation as a bounded self-adjoint operator and quantify the difference in a general setting between the eigenfunctions of the smallest eigenvalues with respect to the perturbed and unperturbed generators; see Theorem 1. As a consequence, we can develop
$\mathcal{L}^1$
-bounds on the difference between the corresponding quasi-stationary distributions, which is illustrated in the QSMC framework for logistic regression; see Proposition 4.
In addition, we also consider a specific unbounded perturbation, which corresponds to truncating a divergent killing rate. In practical implementations of QSMC methods, such a truncation can significantly reduce the complexity of the implementation, since simulating arrivals from a Poisson process with a bounded intensity is straightforward using Poisson thinning, whereas unbounded intensities are much more intricate. We give an explicit bound on the
$\mathcal{L}^2$
-norm, depending on the truncation level, of the difference of the eigenfunctions of the smallest eigenvalue of the generators with and without truncation; see Theorem 5. We apply this result to an Ornstein–Uhlenbeck diffusion with killing and obtain an estimate of the difference between the perturbed quasi-stationary distribution and a Gaussian target distribution in terms of an
$\mathcal{L}^1$
-norm; see Propositions 6 and 7. In this setting, we find that truncation is robust with respect to the dimension; in any dimension
$d\ge 1$
, the error decays exponentially as a function of the truncation level.
1.1. Related results and literature review
Quasi-stationary distributions have been, and continue to be, actively studied within the probability theory literature; see, for instance, the book of [Reference Collet, Martínez and Martín8] or the review paper [Reference Méléard and Villemonais27]. More recently, the construction of schemes with a desired quasi-stationary distribution has been investigated in the context of computational statistics; see [Reference Kumar21, Reference Pollock, Fearnhead, Johansen and Roberts33, Reference Wang, Kolb, Roberts and Steinsaltz43]. Quasi-stationary distributions have also been utilized recently as a tool to analyse other algorithms; see, for instance, [Reference Baudel, Guyader and Lelièvre2, Reference Lelièvre23] for analyses of Monte Carlo algorithms in the context of molecular dynamics.
Perturbation theory in the context of Markov chains (without killing) is richly studied in the literature; see, for instance, the references [Reference Fuhrmann, Kupper and Nendel13, Reference Hosseini and Johndrow15–Reference Kartashov17, Reference Medina-Aguayo, Rudolf and Schweizer26, Reference Mitrophanov30–Reference Negrea and Rosenthal32, Reference Roberts, Rosenthal and Schwartz35, Reference Rudolf and Schweizer36]. However, there are key differences between the classical Markov chain setting and our quasi-stationary setting. For a Markov chain with killing, we typically study the conditional distribution after n steps conditional on survival. This distribution often converges to a quasi-stationary distribution, whereas in the classical Markov chain setting there is no such conditioning. This makes the approximate discrete-time Markov chain with killing setting more demanding, and we present a result in the subsequent Section 1.2.
However, following our motivation of QSMC methods [Reference Pollock, Fearnhead, Johansen and Roberts33], the main focus of this work will be on continuous-time diffusion processes with killing and their quasi-stationary distributions. This is a departure from the traditional Markov chain perturbation theory literature, as cited above, and requires new tools. Thus we apply functional analytic tools, building on techniques developed for the study of perturbations of linear operators, which is a rich and mature field [Reference Baumgärtel3, Reference Kato18, Reference Reed and Simon34]. Several of our results will thus consist of translating these abstract results appropriately into the setting of killed diffusions.
1.2. Result for discrete-time Markov chains
We now give a result for discrete-time Markov chains with killing; in our discussion [Reference Rudolf and Wang37] this has already been reported without proof. We repeat the specific setting and the following statement: Let
$(S_0,\mathcal{S}_0)$
be a measurable space and
$\partial\not\in S_0$
an additional element, which serves as a ‘trap’ of the killed Markov chain. Moreover,
$Q\colon S_0\times \mathcal{S}_0 \to [0,1]$
is a transition kernel and
$\kappa \colon S_0 \to [0,1]$
is used to describe a state-dependent killing probability. For a probability space
$(\Omega,\mathcal{F},\mathbb{P})$
, let
$(X_n)_{n\in\mathbb{N}_0}$
be a sequence of random variables
$X_n\colon \Omega \to S_0\cup \{\partial \}$
determined by the following transition mechanism, depending on Q and
$\kappa$
with
$X_0:=x_0\in S_0$
. Given
$X_n=x$
with
$x\in S_0 \cup \{\partial \}$
, the distribution of
$X_{n+1}$
is specified by two steps.
-
(i) If
$x=\partial$
, then return
$X_{n+1}:\!= \partial$
. -
(ii) Otherwise, draw a uniformly distributed sample
$u\sim \textrm{Unif}[0,1]$
. Independently, draw a sample
$y\sim Q(x,\cdot)$
. Then, return
\begin{align*} X_{n+1}:\!= \begin{cases} \partial & \textrm{if } u\leq \kappa(x),\\ y & \textrm{if } u>\kappa(x). \end{cases} \end{align*}
Thus,
$(X_n)_{n\in\mathbb{N}_0}$
is a Markov chain with killing, determined by Q,
$\kappa$
, and initialization
$x_0$
. Now suppose we only have access to
$\kappa$
through an approximation
$\widetilde\kappa\colon S_0 \to [0,1]$
with
$\Vert \kappa-\widetilde{\kappa} \Vert_\infty$
small. Setting
$\widetilde{X}_0 :\!= x_0$
, let
$(\widetilde{X}_n)_{n\in\mathbb{N}_0}$
be another sequence of random variables on
$(\Omega,\mathcal{F},\mathbb{P})$
which is constructed identically to
$(X_n)_{n\in\mathbb{N}_0}$
, except that
$\widetilde{\kappa}$
is used in step 2 above instead of
$\kappa$
. For the convenience of the reader, we write
$\mathbb{P}_{x_0}$
instead of
$\mathbb{P}$
to indicate the initialization at
$x_0$
. Now, under suitable regularity conditions we can quantify the difference of the conditional distributions of interest, derived from the Markov chains with killing rates
$\kappa$
and
$\widetilde{\kappa}$
.
Proposition 1.
Assume that there exist
$\alpha,\widetilde{\alpha}\in (0,1)$
, and
$c_\ell,\widetilde{c}_\ell,c_u,\widetilde{c}_u\colon S_0 \to (0,\infty)$
, such that for any
$n\in\mathbb{N}$
we have
Then
where
and
$\Vert \cdot \Vert_{\mathrm{tv}}$
denotes the total variation distance.
Note that for irreducible chains on finite state spaces the conditions (1) and (2) are generally mild assumptions; these can be straightforwardly seen to hold for some
$\alpha, \widetilde \alpha\in (0,1)$
by the Perron–Frobenius theorem; see [Reference Seneta38].
At first glance (for finite
$K(x_0)$
), this would appear to be a particularly good estimate; however, in the regime when
$\Vert \kappa - \widetilde{\kappa} \Vert_{\infty}$
is small, it is probable that
$\vert \alpha-\widetilde{\alpha} \vert$
is also small. Regardless, given n and if
$\Vert \kappa - \widetilde{\kappa} \Vert_{\infty}$
is negligible compared to
$n^{-1}$
—say
$\Vert \kappa - \widetilde{\kappa} \Vert_{\infty}\leq n^{-2}$
—then the right-hand side of the stated estimate is of order
$n^{-1}$
.
The proof of Proposition 1 is provided in Appendix A.1. A key aspect in the reasoning is handling the different normalizing constants in the conditional probabilities. It is not clear how this approach could be extended to the continuous-time killed Markov process setting, on which the QSMC setting relies. Therefore, we follow here a different route based on Hilbert space techniques and spectral properties.
1.3. Background to quasi-stationary Monte Carlo schemes
We provide some background to the framework and theoretical properties used in the development of QSMC schemes, largely following [Reference Wang, Kolb, Roberts and Steinsaltz43].
For fixed dimension
$d\in\mathbb{N}$
, let
$\nabla$
be the gradient operator, i.e. the d-dimensional vector with components
$\nabla_i:=\partial /\partial x_i$
for
$i=1,\ldots,d$
. Let
$X=(X_t)_{t\geq0}$
be the d-dimensional reversible diffusion, which is defined as the (weak) solution of the stochastic differential equation (SDE)
Here
$W=(W_t)_{t\geq 0}$
denotes a standard d-dimensional Brownian motion and
$A:\mathbb R^d \to \mathbb R$
is an infinitely differentiable function such that the SDE (3) has a unique nonexplosive weak solution. To be more precise, let C be the space of all continuous functions mapping from the nonnegative real numbers into
$\mathbb{R}^d$
. For
$\omega \in C$
and each
$t\geq 0 $
, define
$X_t \colon C \to \mathbb{R}^d$
to be the coordinate map
$X_t(\omega)=\omega(t)$
and let
$\mathcal{C}:\!= \sigma(\{X_t\colon t\geq 0 \})$
. For
$X_0=x$
, with
$x\in\mathbb{R}^d$
, let
$\widetilde{\mathbb{P}}_x$
be the probability measure on
$(C,\mathcal{C})$
, such that
$X=(X_t)_{t\geq0}$
is the weak solution of (3) under
$\widetilde{\mathbb{P}}_x$
. For an arbitrary initial distribution
$\mu$
on
${\mathbb{R}^d}$
, that is,
$X_0\sim \mu$
, we have
$\widetilde{\mathbb{P}}_\mu(\cdot) = \int_{{\mathbb{R}^d}} \widetilde{\mathbb{P}}_x(\cdot) \mu(\mathrm{d} x)$
. We then augment the probability space with an additional independent unit exponential random variable
$\xi$
, denoting the resulting probability space by
$(\Omega,\mathcal{F},\mathbb{P}_x)$
(or
$(\Omega,\mathcal{F},\mathbb{P}_\mu)$
, respectively). Now fix a measurable nonnegative function
$\kappa: {\mathbb{R}^d} \to [0,\infty)$
, the killing rate, and define the killing time,
By convention, set
$\inf \emptyset =\infty$
.
Now let
$\pi$
be the probability measure of interest on
$\mathbb{R}^d$
given through a positive, infinitely differentiable, and integrable Lebesgue density. By an abuse of notation we also denote this density by
$\pi$
. The idea is to choose the function
$\kappa$
in such a way that
$\pi$
is the unique quasi-stationary distribution of X killed at rate
$\kappa$
: for each
$t\ge 0$
, we have that
In [Reference Wang, Kolb, Roberts and Steinsaltz43] it has been shown that (5) is satisfied, under mild regularity conditions, if
with
$K>0$
being chosen such that
$\kappa\geq0$
, and with
$\Delta :\!= \sum_{i=1}^d \frac{\partial^2}{\partial^2 x_i}$
being the Laplacian operator. In this reference it is shown that
$\pi$
is the unique quasi-stationary distribution of X and that the convergence of the distribution of
$X_t$
given
$\tau_\partial >t$
to
$\pi$
can take place geometrically.
1.4. Outline
In Section 2, we consider the case of general bounded self-adjoint perturbations for self-adjoint generators. We give a general perturbation result in Theorem 1, and then apply this to logistic regression in Section 2.4, which is the main current application of QSMC methods; see [Reference Kumar21, Reference Pollock, Fearnhead, Johansen and Roberts33].
In Section 3, we turn to study one particular unbounded perturbation, which corresponds to truncating a divergent killing rate. We first give a general perturbation result in Theorem 5, and then apply this to an Ornstein–Uhlenbeck setting where explicit bounds on the incurred bias can be derived.
Finally, in the Appendix we present some deferred proofs.
2. Bounded perturbations
In this section we provide a self-contained proof of a norm estimate of the difference between the eigenfunctions of two (potentially unbounded) self-adjoint operators, where one is considered to be a bounded perturbation of the other.
In the context of the QSMC algorithm, such bounds are reassuring for practitioners wishing to implement QSMC methods, since our bound will say that small self-adjoint perturbations of the generator will not substantially affect the resulting quasi-stationary distribution. Such self-adjoint perturbations can arise in practical situations when the target density has been perturbed slightly, since the target density typically only enters the QSMC algorithm via the killing rate (which is a multiplication operator and hence self-adjoint). For example, in a logistic regression scenario, such a perturbation could correspond to corrupted or missing data; see Section 2.4.
2.1. Assumptions and first consequences
Let
$\mathcal{H}$
be a real separable Hilbert space with inner product
$\langle\cdot,\cdot\rangle$
and denote by
$\mathsf S(\mathcal{H}):=\{f\in\mathcal{H}:\|f\|=1\}$
the corresponding unit sphere. For a linear subspace
$\mathbb V$
, we write
$\mathbb V^\perp$
for its orthogonal complement and define the linear operator
$P_{\mathbb{V}}\colon \mathcal{H} \to \mathbb{V}$
as the orthogonal projection from
$\mathcal{H}$
to
$\mathbb{V}$
.
Suppose we have a densely defined self-adjoint positive semi-definite linear operator
$L \colon \mathcal{H} \to \mathcal{H}$
with domain
${\mathcal{D}}(L) \subseteq \mathcal{H}$
; we will simply write
$(L, {\mathcal{D}}(L))$
. Recall that the positive semi-definiteness implies that
$\langle Lf,f\rangle \ge 0$
for all
$f\in {\mathcal{D}}(L)$
. Then the spectrum of L, denoted by
$\sigma(L)$
, is nonempty and nonnegative:
$\sigma(L) \subset [0,\infty)$
; cf. [Reference Hislop and Sigal14, Proposition 5.12]. We define
which are crucial quantities that appear in the following assumption.
Assumption 1.
For the operator L we have that
$\nu :\!= \lambda_1-\lambda_0 >0$
, that is, L possesses a spectral gap. Additionally, we assume that the eigenspace corresponding to
$\lambda_0$
is one-dimensional.
Note that under the assumption
$\nu>0$
,
$\lambda_0$
is indeed an eigenvalue of L (see e.g. [Reference Kulkarni, Nair and Ramesh20, Theorem 4.1]), which we assume to have a one-dimensional eigenspace. Therefore, we have
$L\varphi = \lambda_0 \varphi$
, where
$\varphi\in \mathsf S(\mathcal{H})$
denotes an eigenfunction of L with eigenvalue
$\lambda_0$
. By [Reference Reed and Simon34, Theorem XIII.1], we in fact have the following variational representations of
$\lambda_0$
and
$\lambda_1$
:
\begin{equation} \begin{split} \lambda_0 &= \inf_{f\in \mathsf S(\mathcal{H})\cap {\mathcal{D}}(L)} \langle f,Lf\rangle,\\ \lambda_1 &= {\sup}_{\mathbb V \in \mathcal V_1}\inf_{f\in \mathbb{V}^\perp \cap \mathsf S(\mathcal{H})\cap {\mathcal{D}}(L)} \langle f, Lf\rangle, \end{split} \end{equation}
where
$\mathcal V_1$
denotes the set of one-dimensional linear subspaces of
$\mathcal{H}$
. Note that
$\lambda_1$
is not necessarily an eigenvalue of L.
Fix a bounded self-adjoint linear operator
$H\colon \mathcal{H} \to \mathcal{H}$
, which serves as a ‘small’ perturbation. With this we set
Note that we have
${\mathcal{D}}(\widehat L) = {\mathcal{D}}(L)$
, self-adjointness of
$\widehat{L}$
, and
$\langle \widehat L f, f\rangle \geq -\Vert H \Vert$
for any
$f\in {\mathcal{D}}(L)$
, with
$\Vert H \Vert$
being the operator norm of H. Define
\begin{equation} \begin{split} \widehat \lambda_0 &:\!= \inf_{f\in \mathsf S(\mathcal{H})\cap {\mathcal{D}}(L)} \langle f,\widehat Lf\rangle,\\ \widehat\lambda_1 &:\!= {\sup}_{\mathbb V \in \mathcal V_1} \inf_{f\in \mathbb V^\perp \cap \mathsf S(\mathcal{H})\cap {\mathcal{D}}(L)} \langle f, \widehat Lf\rangle. \end{split} \end{equation}
The following lemma is a classical result; see e.g. [Reference Reed and Simon34, Section XIII.15]. For completeness we give a proof in Appendix A.2.
Lemma 1.
(Weyl’s lemma.) For
$j=0,1$
, we have
In the next assumption we formalize the notion that H is a ‘small’ perturbation.
Assumption 2.
Suppose that the operator norm of H satisfies
$\|H\|<\nu/2$
, where
$\nu = \lambda_1-\lambda_0$
is the spectral gap; see Assumption 1.
Under the formulated assumptions we have two important consequences which follow from fairly standard functional analytic techniques; see Appendix A.3 for a full proof.
Lemma 2.
Under Assumption 1 and 2 we have that
$\widehat{\lambda}_0 < \widehat{\lambda}_1$
, and that
$\widehat \lambda_0$
is an eigenvalue of
$\widehat{L}$
. Furthermore, the perturbed operator
$\widehat L$
possesses a unique eigenfunction, up to a sign,
$\widehat \varphi \in \mathsf S(\mathcal{H})$
with respect to eigenvalue
$\widehat{\lambda}_0$
, that is,
Without loss of generality, we may assume that
$\rho :\!= \langle \varphi, \widehat \varphi\rangle \ge 0$
.
Remark 1. A consequence of the previous results is that
and the supremum in the definition of
$\widehat \lambda_1$
in equation (8) is attained by
$\mathbb V = {\mathrm{span}}\{\widehat{\varphi}\}$
.
2.2. Main estimate
The goal now is to estimate
$\|\varphi-\widehat \varphi\|$
. We state and prove the main estimate.
Theorem 1. Under Assumption 1 and 2 we have
Proof. Recall that
$\rho :\!= \langle \widehat \varphi, \varphi\rangle \ge 0$
and with
$\mathbb{G}:={\mathrm{span}}\{ \varphi\}$
define
(If
$\rho=1$
, then
$\widehat \varphi = \varphi$
and the result trivially holds true.) Note that
$\|h\|=1$
and
$h\perp \varphi$
as well as
$L h \perp \varphi$
by the self-adjointness of L. Consequently, by using the representation of h,
$L\varphi = \lambda_0 \varphi$
, and
$\widehat L=L+H$
we have that
Taking the inner product with h, employing
$\langle \widehat \varphi,h \rangle = \sqrt{1-\rho^2}$
,
$\varphi\perp h$
, and rearranging yields
Moreover, by
$\widehat{L}=L+H$
,
$h\perp \varphi$
, and Lemma 1 we have
which is, due to Assumption 2, strictly positive. Squaring (12), rearranging, and taking a square root, with
$A:=|\langle H \varphi ,h\rangle|$
we obtain
Then
from which we have that
$\sqrt{2(1-\rho)}\le A/B$
. The fact that we can represent
$\widehat \varphi$
by the orthogonal decomposition
gives, with
$\rho = \langle \widehat \varphi, \varphi\rangle \ge 0$
, that
$\widehat \varphi - \varphi = (\rho-1)\varphi + \sqrt{1-\rho^2} h.$
Consequently,
which finishes the proof.
Remark 2. A similar, and to some extent complementary, bound to (11) can be obtained via the sin
$\theta$
theorem of [Reference Davis and Kahan10], which is stated in Section 3.1. Under Assumptions 1 and 2, we obtain
For the convenience of the reader we provide in Appendix A.4 arguments to derive (13).
2.3. Additional auxiliary estimates
We now give some additional estimates which are useful for our subsequent examples. Let
$\pi,\widetilde \pi$
be probability density functions on
${\mathbb{R}^d}$
. Fix a positive function
$\gamma: {\mathbb{R}^d} \to (0,\infty)$
, and let
$\Gamma(\mathrm{d} x)=\gamma(x)\mathrm{d} x$
be the corresponding measure on
${\mathbb{R}^d}$
. By
$\mathcal L^2({\mathbb{R}^d},\Gamma)$
we denote the space of
$\Gamma$
-square-integrable functions
$f\colon \mathbb{R}^d \to \mathbb{R}$
equipped with the norm
$\Vert f \Vert_2 :\!= \left( \int_{\mathbb{R}^d} \vert f(x) \vert^2 \,\Gamma(\mathrm{d} x) \right)^{1/2}$
. Now define the functions
We assume that
$\phi,\widetilde \phi \in \mathcal L^2(\Gamma)$
: we have that
Under this condition we state the first auxiliary estimate.
Lemma 3.
Assume that (14) holds, and furthermore that
$\Gamma$
is a finite measure, i.e.
$\Lambda:\!= \Gamma(\mathbb{R}^d)^{1/2}<\infty$
. Then
Proof. We straightforwardly calculate
\begin{equation*} \begin{split} \int_{\mathbb{R}^d}|\pi(x)-\widetilde \pi(x)|\mathrm{d} x&=\int_{\mathbb{R}^d} |\phi-\widetilde \phi|\mathrm{d} \Gamma \\ &\le \left( \int_{\mathbb{R}^d} |\phi-\widetilde \phi|^{2}\mathrm{d} \Gamma \right)^{1/2}\left (\int_{\mathbb{R}^d} \mathrm{d} \Gamma \right )^{1/2} = \Lambda \|\phi-\widetilde \phi\|_2, \end{split} \end{equation*}
where we use the Cauchy–Schwarz inequality.
For the formulation of the next statement we need normalized functions
$\phi$
and
$\widetilde{\phi}$
with respect to the
$\mathcal L^2({\mathbb{R}^d},\Gamma)$
-norm, that is, we define
with
$Z:\!= \|\phi\|_2, \widetilde Z:\!= \|\widetilde \phi\|_2$
.
Lemma 4.
Suppose that (14) holds and
$\Lambda:\!= \Gamma(\mathbb{R}^d)^{1/2}<\infty$
. Additionally, let
with
$0<\epsilon<\Lambda^{-1} Z^{-1}$
being satisfied. Then, we have
and
with
$C=Z^2 \Lambda/(1-\Lambda Z \epsilon)$
.
Proof. Note that (15) immediately implies (16). Then, we have
\begin{align*} \left |1-\frac{Z}{\widetilde Z}\right|&=\left | \int_{\mathbb{R}^d} \left(\phi-\frac{Z}{\widetilde Z}\,\widetilde \phi\right)\mathrm{d} \Gamma \right| \le \int \left| \phi - \frac{Z}{\widetilde Z}\,\widetilde \phi \,\right|\mathrm{d} \Gamma\\ &\le \left( \int_{\mathbb{R}^d}\left| \phi - \frac{Z}{\widetilde Z}\,\widetilde \phi \,\right|^2\mathrm{d} \Gamma \right)^{1/2} \left( \int_{\mathbb{R}^d} \mathrm{d} \Gamma\right)^{1/2} \le \Lambda Z \epsilon. \end{align*}
We can then conclude (17), for instance by considering the behaviour of the function
$t\mapsto h(t):=Z/t$
. Namely, the former inequality implies
$ h(Z)-\Lambda Z\varepsilon \leq h(\widetilde{Z}) \leq h(Z)+\Lambda Z\varepsilon. $
Now, taking the inverse and performing suitable transformations yields the result.
Lemma 5.
Assume that (14) and (15) hold, and that
$\Lambda:\!= \Gamma(\mathbb{R}^d)^{1/2}<\infty$
. Then, we have
where
$C>0$
is defined as in Lemma 4.
Proof. We calculate
where we have used the triangle inequality and Lemma 4.
Putting together the estimates of the former lemmas we obtain the following.
Proposition 2.
Assume that (14) and (15) hold, and that
$\Gamma$
is a finite measure, with
$\Lambda :\!= \Gamma(\mathbb{R}^d)^{1/2}<\infty$
. Then,
where
$C>0$
is defined in Lemma 4.
2.4. Example: logistic regression
We demonstrate how Theorem 1, in combination with Proposition 2, can be applied to the setting of logistic regression, which is currently the most popular application of QSMC methods; see [Reference Kumar21, Reference Pollock, Fearnhead, Johansen and Roberts33]. In that scenario we justify that QSMC methods are robust to small perturbations in the observations, such as could arise from corrupted or missing data.
We consider the following model. There are n observed binary response variables
$(y_1,\ldots,y_n)\in \{0,1\}^n$
, and we have a design matrix of covariates
$\mathbf X = (\mathbf{X}_{i,j})\in \mathbb{R}^{n\times d}$
, writing
$\mathbf X_{[i]}\in {\mathbb{R}^d}$
for the ith row,
$i\in \{1,\ldots,n\}$
. We consider the response variables and design matrix to be fixed a priori. For a parameter vector
$x\in{\mathbb{R}^d}$
(interpreted as regression coefficients) the likelihood function for the response variables is given as
with
Following [Reference Kumar21, Reference Pollock, Fearnhead, Johansen and Roberts33], we place an improper uniform prior on the parameters x, and obtain the Lebesgue density
$\pi$
of the posterior distribution on
${\mathbb{R}^d}$
, which satisfies
We assume that the response and design matrix are such that (18) defines a bona fide probability density function (that is, the right-hand side of (18) is Lebesgue integrable).
For our stochastic process, we are using a general reversible diffusion of the form (3), namely
where the drift A is chosen independently of the data. We assume that the relevant technical conditions on A detailed in [Reference Wang, Kolb, Roberts and Steinsaltz43] hold, to ensure that
$\pi$
is a valid quasi-stationary distribution; for details see also Section 1.3. As in [Reference Wang, Kolb, Roberts and Steinsaltz43], we work on the Hilbert space
$\mathcal H = \mathcal L^2({\mathbb{R}^d},\Gamma)$
, where
$\Gamma(\mathrm{d} x)=\gamma(x)\mathrm{d} x$
with
$\gamma(x)=\exp\!(2A(x))$
.
Note that the observations
$y_1,\ldots,y_n$
and covariates
$\mathbf X$
only influence the killed diffusion through the killing rate
$\kappa$
and so any perturbation of the data results in a perturbation of the killing rate.
From (6) and following the calculations in [Reference Kumar21, Appendix C], we can express the killing rate as
\begin{equation}\begin{split} \kappa(x) = \frac{1}{2}\bigg( \sum_{j=1}^d\left[ \sum_{i=1}^n \left (y_i-p_i(x)\right )\mathbf X_{i,j} \right]^2 - \sum_{j=1}^d \sum_{i=1}^n p_i(x)\left (1-p_i(x)\right )\mathbf X^2_{i,j} \\ -2\Delta A - 2\left \langle \nabla A, \sum_{i=1}^n \left (y_i - p_i(x)\right ) {\mathbf X_{[i]}} \right \rangle \bigg)-\Phi, \end{split}\end{equation}
where the constant
$\Phi \in \mathbb{R}$
is chosen to ensure that
$\kappa \ge 0$
everywhere; see Condition (1) of [Reference Pollock, Fearnhead, Johansen and Roberts33] for a further discussion. Let
$L^\kappa$
be the generator of the diffusion
$X=(X_t)_{t\geq 0}$
killed at rate
$\kappa$
, which possesses
$\varphi = \pi/\gamma$
as its minimal eigenfunction corresponding to the bottom of the spectrum. The fact that the eigenspace is one-dimensional follows from the Perron–Frobenius theorem; see [Reference Reed and Simon34, Chapter XIII.12]. Let us write
${\lambda_0^\kappa}$
for the bottom of the spectrum of
${L^\kappa}$
. Then in fact it follows that
${\lambda_0^\kappa}=-\Phi$
; see [Reference Wang, Kolb, Roberts and Steinsaltz43, Section 3.3]. That is, the bottom of the spectrum of the resulting operator is in fact equal to
$-\Phi$
.
We first consider the common choice of
$A\equiv 0$
, as in [Reference Kumar21, Reference Pollock, Fearnhead, Johansen and Roberts33]. In this case, the expression (19) simplifies, and the resulting killing rate
$\kappa$
is uniformly bounded from above. Moreover, since we are assuming that
$\pi$
is integrable, it follows that
with
$\vert \cdot \vert$
denoting the Euclidean norm.
As already mentioned, we imagine having corrupted or missing data, giving us access only to a perturbed killing rate
$\widetilde{\kappa} \colon \mathbb{R}^d \to [0,\infty)$
.
Remark 3. For example, it may be the case that our covariates are corrupted, so we only have access to
$\widetilde{\mathbf X}_{i,j}:=\mathbf X_{i,j}+\epsilon_{i,j}$
, where the
$(\epsilon_{i,j})\in\mathbb{R}^{n\times d}$
models some corrupting noise (alternatively, the case
$\epsilon_{i,j}=-\mathbf X_{i,j}$
could be considered a case of missing data). Assume that the corresponding additive constants are equal,
$\Phi=\widetilde \Phi$
(which can be done by setting both equal to the maximum value
$\Phi \vee \widetilde \Phi$
). If we write
$\|\mathbf A\|_\infty = {\sup}_{1\leq i\leq n,\; 1\leq j\leq d}|\mathbf A_{i,j}|$
for a matrix
$\mathbf A= (\mathbf{A}_{i,j})\in \mathbb{R}^{n\times d}$
, a straightforward calculation shows that for a fixed constant
$C>0$
we have
Thus, provided the data corruption level
$\|\epsilon\|_\infty$
is sufficiently small,
$\|\widetilde\kappa -\kappa\|_\infty$
can be made arbitrarily small.
Now we ask whether the difference of the eigenfunctions that determine the quasi-stationary distributions of the killed Markov processes based on
$\kappa$
and
$\widetilde{\kappa}$
is small when
$\Vert \kappa - \widetilde{\kappa} \Vert_\infty$
is sufficiently small. Thus, we consider a perturbation operator
$H\colon \mathcal{L}^2({\mathbb{R}^d},\Gamma)\to \mathcal{L}^2({\mathbb{R}^d},\Gamma)$
given by
Note that since H is just a multiplication operator it is self-adjoint, and the operator norm coincides with
$\Vert \kappa - \widetilde{\kappa} \Vert_\infty$
. We obtain the following result.
Proposition 3.
We work in the case
$A\equiv 0$
and assume that
$\lim_{\|x\|\to\infty}\kappa(x)$
exists. Then there exist a
$\delta >0$
and constant
$C>0$
such that, for any (perturbed) killing rate
$\widetilde \kappa$
with
$\|\kappa-\tilde \kappa\|_\infty < \delta$
, there is a quasi-stationary distribution of the killed Markov process killed at rate
$\widetilde\kappa$
. In particular, this quasi-stationary distribution has a
$\Gamma$
-density
$\widehat\varphi \in \mathcal L^2({\mathbb{R}^d},\Gamma)$
with
$\Vert \widehat{\varphi} \Vert_2 = 1$
, which satisfies
Proof. We start by arguing that the generator
$L^\kappa$
has a spectral gap
$\nu>0$
. This fact follows readily by (20) and the fact that the base of the essential spectrum must be strictly larger than
$\lambda_0^\kappa$
by [Reference Davies9, Lemma 14.4.1] (see also [Reference Kolb and Steinsaltz19, Lemma 3.3(v)] and [Reference Wang, Kolb, Roberts and Steinsaltz43, Remark 1, Section 1.4]). We choose
$\delta$
to be
Let
$\|H\|$
be the
$\mathcal L^2({\mathbb{R}^d},\Gamma)$
-operator norm. Then, we have
The latter inequality ensures that the resulting minimal eigenfunction
$\widehat \varphi$
is also in
$\mathcal L^1({\mathbb{R}^d},\Gamma)$
, by [Reference Champagnat and Villemonais7, Theorem 4.5]. The fact that the quasi-stationary distribution corresponds to the bottom of the spectrum follows from the argument of [Reference Simon39]; see also [Reference Kolb and Steinsaltz19, Section 4.2]. The rest follows by applying our abstract result, Theorem 1.
Remark 4. The bound in Proposition 3 is in terms of the norm
$\|\cdot \|_2$
of
$\mathcal L^2({\mathbb{R}^d},\Gamma)$
and concerns the functions
$\varphi$
and
$\widehat{\varphi}$
which are normalized in
$\mathcal L^2({\mathbb{R}^d},\Gamma)$
, that is,
$\|{\varphi}\|_2=\|\widehat{\varphi}\|_2 =1$
. This cannot be straightforwardly translated into a bound on the corresponding densities
$\pi$
and
$\widehat\pi$
, which are normalized in
$\mathcal L^1({\mathbb{R}^d},\Gamma)$
, since in this case
$\Gamma(\mathrm{d} x)=\mathrm{d} x$
is not a finite measure.
In light of the above remark, it is of interest to ask whether or not it is possible to construct an alternative diffusion to the case
$A\equiv 0$
, which still possesses
$\pi$
as a valid quasi-stationary distribution, but such that
$\Gamma$
is a finite measure. This would enable us, by an application of the Cauchy–Schwarz inequality, to conclude robustness in
$\mathcal L^1({\mathbb{R}^d},\Gamma)$
and not only in
$\mathcal L^2({\mathbb{R}^d},\Gamma)$
. This can be indeed done, by choosing A to satisfy the following properties.
Assumption 3.
The function
$A:{\mathbb{R}^d}\to \mathbb{R}$
is a smooth function, and there exist some
$M>0, \alpha >0$
such that
$A(x)=-\alpha \vert x\vert$
for all
$x\in {\mathbb{R}^d}$
with
$\vert x\vert \ge M$
, and
$\pi/\exp\!(2A)$
is uniformly bounded from above.
This is largely a technical assumption for the following proof, although, in addition, the resulting diffusion process with drift
$\nabla A$
will also be relatively straightforward to simulate in the tails due to its simple form. However, such an A exists since
$\pi$
is a log-concave density function. With this choice of A, we have the following result.
Proposition 4.
Assume that the function
$A\colon \mathbb{R}^d \to \mathbb{R}$
satisfies Assumption 3 and that
$\lim_{\|x\|\to\infty}\kappa(x)$
exists. Then, there exist a
$\delta >0$
and
$C>0$
, such that, for any perturbed killing rate
$\widetilde{\kappa}$
that satisfies
$\|\widetilde \kappa - \kappa\|_\infty < \delta$
, there is a quasi-stationary distribution
$\widehat \pi \in \mathcal L^1({\mathbb{R}^d},\Gamma)$
of the killed Markov process based on
$\widetilde{\kappa}$
. In particular, we have
Proof. Note that by Assumption 3 we have that the killing rate
$\kappa$
from (19), which appears in the unperturbed killed Markov process, is bounded from above. Moreover, (20) is satisfied and therefore there exists similarly by [Reference Davies9, Lemma 14.4.1] a spectral gap
$\nu>0$
for the generator
$L^\kappa$
. As in the proof of Proposition 3, it follows that
for the corresponding
$\mathcal L^2({\mathbb{R}^d},\Gamma)$
-normalized eigenfunctions for some
$\widetilde{C}>0$
. The desired
$\mathcal L^1({\mathbb{R}^d},\Gamma)$
bound (21) follows since
$\Gamma$
is assumed to be a finite measure. Therefore, we can apply Proposition 2 and obtain the assertion.
3. Unbounded perturbation: truncation
In this section we consider a particular unbounded perturbation corresponding to truncating the killing rate. This is of practical importance, since for all current implementations of QSMC methods, when using either particles [Reference Burdzy, Hoyst and March6, Reference Del Moral and Miclo11, Reference Pollock, Fearnhead, Johansen and Roberts33] or a stochastic approximation [Reference Aldous, Flannery and Palacios1, Reference Kumar21, Reference Mailler and Villemonais25, Reference Wang, Roberts and Steinsaltz45], it is necessary to simulate the killing times (4). This simulation is an intricate task when
$\kappa$
is unbounded; see [Reference Pollock, Fearnhead, Johansen and Roberts33]. On the other hand, when
$\kappa$
is uniformly bounded from above, simulation of such killing times is straightforward using Poisson thinning; see [Reference Lewis and Shedler24].
The simulation of piecewise-deterministic Markov processes in the context of the Monte Carlo method [Reference Bierkens, Fearnhead and Roberts4, Reference Bouchard-Côté, Vollmer and Doucet5] also requires the simulation of first event times. In that context, stability investigations with respect to truncation of the event rate have also appeared; see [Reference Durmus, Guillin and Monmarché12, Section 10].
3.1. Projection notation
Following [Reference Davis and Kahan10], we make use of projections onto invariant subspaces. Now we describe the appropriate setting and notation, which will be used throughout Section 3.
For an unbounded self-adjoint operator
$(L, {\mathcal{D}}(L))$
on a separable Hilbert space
$\mathcal{H}$
, we suppose that we have a one-dimensional L-invariant subspace, given by its orthogonal projection
$P=v_0 \langle \cdot, v_0\rangle$
, for some
$v_0\in\mathcal{H}$
with
$\|v_0\|=1$
. In fact
$v_0$
must be an eigenvector of L, with eigenvalue
$\lambda_0\in\mathbb{R}$
, say. Let
$P^{\perp}$
denote the orthogonal projection onto the complement subspace
$({\mathrm{span}}\{v_0\})^\perp$
.
Following [Reference Davis and Kahan10], we can define isometric mappings
$E_0: \mathcal K(E_0) \to \mathcal{H}$
and
$E_1: \mathcal K (E_1) \to \mathcal{H}$
, with source Hilbert spaces
$\mathcal K(E_0), \mathcal K(E_1)$
, which satisfy
where
$E_0^*: \mathcal{H} \to \mathcal K(E_0)$
and
$E_1^*: \mathcal{H} \to \mathcal K(E_1)$
are the corresponding adjoint operators.
Since P projects onto the one-dimensional subspace
${\mathrm{span}}\{v_0\} \subseteq \mathcal{H}$
, we can identify
$\mathcal K(E_0) \equiv \mathbb{R}$
, equipped with the Euclidean inner product. This allows the explicit characterization
By the L-invariance of
${\mathrm{span}}\{v_0\}$
, we can now decompose
$L\colon \mathcal{D}(L) \to \mathcal{H}$
as
for
$v\in {\mathcal{D}}(L)$
, where
$L_0:\mathbb{R} \to \mathbb{R}$
is the bounded linear operator given by
$L_0\theta = \lambda_0 \theta$
, and
$L_1:{\mathcal{D}}(L_1)\to \mathcal K(E_1)$
is the unbounded operator given by
$L_1 = E_1^* L E_1$
with
${\mathcal{D}}(L_1)=E_1^* {\mathcal{D}}(L)$
.
Given another self-adjoint operator
$(\widehat L, {\mathcal{D}}(\widehat L))$
on the same Hilbert space
$\mathcal{H}$
, which we will later think of as the perturbed operator, we assume that we have a one-dimensional
$\widehat L$
-invariant subspace given by the orthogonal projection
$Q = \widehat v_0 \langle \cdot, \widehat v_0\rangle$
, where
$\|\widehat v_0\|=1$
. So
$\widehat v_0$
is an eigenvector of
$\widehat L$
, with corresponding eigenvalue
$\widehat{\lambda}_0\in\mathbb{R}$
, say. Let us write
$Q^{\perp}$
for the projection onto the orthogonal complement of
${\mathrm{span}}\{\widehat{v}_0\}$
.
As above, we can similarly define corresponding isometric mappings
$F_0:\mathcal{R}\to \mathcal{H}$
and
$F_1:\mathcal K(F_1)\to \mathcal{H}$
with
$F_0 \theta = \theta \widehat{v}_0$
and
$F_0^* v = \langle v,\widehat{v}_0 \rangle$
, such that
$F_0 F_0^* = Q$
and
$F_1F_1^*=Q^\perp$
. Moreover, with these definitions,
$\widehat{L} \colon {\mathcal{D}}(\widehat{L})\to \mathcal{H} $
can be decomposed for
$v\in {\mathcal{D}}(\widehat L)$
as
where
$\widehat{L}_0\colon \mathbb{R} \to \mathbb{R}$
is given by
$\widehat{L}_0\theta = \widehat{\lambda}_0 \theta $
and
$\widehat{L}_1 \colon \mathcal{D}(\widehat{L}_1) \to \mathcal{K}(F_1)$
is the unbounded operator given by
$\widehat{L}_1 = F_1^* \widehat{L} F_1$
with
$\mathcal{D}(\widehat{L}_1) = F_1^* \mathcal{D}(\widehat{L})$
.
With these definitions we are able to formulate the remarkable sin
$\theta$
theorem of [Reference Davis and Kahan10]. For the convenience of the reader, we state it here in our present notation.
Theorem 2.
(The sin
$\theta$
theorem [Reference Davis and Kahan10].) Suppose that there is some real interval
$[a_0, a_1]$
and
$\delta>0$
such that the spectrum of
$L_0$
is contained within
$[a_0, a_1]$
and the spectrum of
$\widehat L_1$
lies entirely outside the interval
$(a_0-\delta, a_1+\delta)$
. Then, for
$\sin \Theta_0 :\!= \sqrt{1-\langle v_0,\widehat v_0 \rangle^2}$
and the operator
$R:=\widehat LE_0 - E_0 L_0$
, we have
$|\sin \Theta_0|\le \|R \|/\delta $
.
In fact, this is a slight modification of the
$\sin \,\theta$
theorem as stated in [Reference Davis and Kahan10], since our operators
$L, \widehat L$
are in general unbounded; however, see the discussion immediately preceding [Reference Davis and Kahan10, Theorem 5.2]. These subtleties will be addressed in the sequel.
3.2. Further notation and results
We consider the situation described in Section 1.3 and set
$\mathcal{H} = \mathcal L^2({\mathbb{R}^d}, \Gamma)$
, which consists of all measurable real-valued functions
$f\colon {\mathbb{R}^d} \to \mathbb{R} $
satisfying
where the measure
$\Gamma$
is given by
$\mathrm{d} \Gamma(y)=\gamma(y)\mathrm{d} y$
and
$\gamma:\!= \exp\!(2A)$
, with
$\mathrm{d} y$
denoting the Lebesgue measure on
${\mathbb{R}^d}$
. In other words,
$\mathcal{H}$
is the Hilbert space of functions, equipped with the inner product
where
$f,g:{\mathbb{R}^d} \to \mathbb{R}$
. As before, by
$\mathsf{S}(\mathcal{H})$
we denote the unit sphere in
$\mathcal{H}$
with respect to
$\Vert\cdot\Vert_2$
.
The infinitesimal generator of the diffusion X killed at rate
$\kappa$
, see (3), is given by
where
$\Delta$
denotes the Laplacian operator. As in [Reference Wang42, Section 3.3.3], the operator
$L^\kappa$
can be realized as a densely defined self-adjoint positive semi-bounded linear operator on
$\mathcal{H}$
with domain
where the derivatives are understood in the weak sense. Note that
${\mathcal{D}}({L^\kappa})$
contains
$C_c^\infty({\mathbb{R}^d})$
, the set of smooth, compactly supported functions on
${\mathbb{R}^d}$
. Therefore, we have a self-adjoint unperturbed operator on
$\mathcal{H}$
given by (23) with domain
${\mathcal{D}}(L^\kappa)$
.
For brevity, we write
$L^0=-\frac{1}{2}\Delta-\nabla A\cdot \nabla$
for the (formal) unkilled differential operator. We impose the following condition on the killing rate.
Assumption 4.
The killing rate is measurable, locally bounded and nonnegative with
$\kappa(x)\to \infty$
as
$\vert x\vert \to \infty $
.
In the case where
$A\equiv0$
and
$\kappa$
is given by (6), i.e. in the setting of QSMC with Brownian motion, Assumption 4 corresponds to a scenario where
$\pi$
has tails decaying at a faster-than-exponential rate (such as Gaussian or lighter). A standard consequence of the assumption is the following.
Lemma 6.
Under Assumption 4, there is a strictly positive eigenfunction
$\varphi_0 \in \mathsf S(\mathcal{H})$
of
$L^\kappa$
with eigenvalue
$\lambda_0^\kappa$
satisfying
$\lambda_0^\kappa = \inf \sigma({L^\kappa})$
, i.e. it is given by the bottom of the spectrum of
${L^\kappa}$
. Moreover,
$\varphi_0$
corresponds to the unique quasi-stationary distribution of X.
Proof. Existence and uniqueness of the quasi-stationary distribution follows from [Reference Champagnat and Villemonais7, Theorem 4.5]. Furthermore, that the function
$\varphi_0$
is in
$\mathcal L^2$
and can be chosen to be strictly positive follows, for instance, from the fact that, under Assumption 4, the operator
$L^\kappa$
has a purely discrete spectrum; see [Reference Reed and Simon34, Theorems XIII.67 and XIII.44].
Remark 5. Setting
$\lambda_1^\kappa :\!= \inf \{\sigma(L^\kappa)\backslash \{\lambda^\kappa_0\} \}$
, we have by the fact that
${L^\kappa}$
is self-adjoint and bounded from below, see [Reference Reed and Simon34, Theorem XIII.1], the variational representations as in (7), that is,
\begin{equation*} \begin{split} {\lambda_0^\kappa} &= \inf_{f\in \mathsf S(\mathcal{H})\cap {\mathcal{D}}({L^\kappa})} \langle f,{L^\kappa} f\rangle,\\ \lambda_1^\kappa &= {\sup}_{\mathbb V \in \mathcal V_1} \inf_{f\in \mathbb V^\perp \cap \mathsf S(\mathcal{H})\cap {\mathcal{D}}({L^\kappa})} \langle f, {L^\kappa} f\rangle. \end{split} \end{equation*}
We are interested in truncating the unbounded killing rate
$\kappa$
and understanding the resulting impact on the quasi-stationary distribution. So, we define, for arbitrary
$M\ge 0$
, the truncated killing rate
$\kappa_M:{\mathbb{R}^d}\to [0,\infty)$
; writing
$a\wedge b :\!= \min\{a,b\}$
, it is given pointwise by
With this we can define our perturbed operator,
$\widehat{L}^M :=L^{\kappa_M}$
on
$\mathcal{H}$
, i.e.
Similarly to
${L^\kappa}$
,
$\widehat{L}^M$
can also be realized as a self-adjoint operator, with corresponding domain
${\mathcal{D}} (\widehat{L}^M)$
given analogously to (24). This corresponds to our diffusion X killed at state-dependent rate
$\kappa_M$
.
We require some further notation to state the resulting perturbation. For any function
$f:{\mathbb{R}^d} \to \mathbb{R}$
, we write
$f_+$
for the positive part;
$f_+(x)=\max\{f(x),0\}$
for each
$x\in {\mathbb{R}^d}$
. Now define our (unbounded) perturbation
$H_M$
on
$\mathcal{H}$
as the multiplication operator given by
for
$f \in {\mathcal{D}}(H_M)$
with
${\mathcal{D}}(H_M):=\{f\in \mathcal{H}: \int_{{\mathbb{R}^d}} |(\kappa - M)_+ f|^2 \mathrm{d} \Gamma <\infty\} $
. We can characterize
${\mathcal{D}}(H_M)$
.
Lemma 7.
For any
$M\geq 0$
, we have
Consequently,
${\mathcal{D}}(H_M)$
is independent of M.
Proof. The statement of (26) follows immediately by observing that
$|(\kappa-M)_+f - \kappa f|\le M|f|$
holds pointwise.
To emphasize that the domain of
$H_M$
does not depend on M, we define
${\mathcal{D}}(\kappa):\!= {\mathcal{D}}(H_M)$
.
Lemma 8.
Suppose
$g\in {\mathcal{D}}({L^\kappa})\cap{\mathcal{D}}(\kappa)$
. Then
$g\in {\mathcal{D}}(\widehat{L}^M)$
and
Proof. We take similar steps to the proof of [Reference Wang, Pollock, Roberts and Steinsaltz44, Lemma 15]. For a sequence of mollifiers
$(f_n)_{n\in\mathbb{N}}$
as in the proof, similarly consider
$g_n :\!= f_n g$
. Since
$g \in {\mathcal{D}}(L^\kappa)$
, it is twice weakly differentiable. Then each
$g_n$
is a compactly supported, twice weakly differentiable function. Furthermore,
$g_n \to g$
in the Sobolev space
$W^{2,1}({\mathbb{R}^d})$
, and we have that
$|g_n| \le C|g|$
for some constant C, pointwise, and uniformly over n.
Hence, using the fact that
$L^\kappa$
is closed and
$\kappa g \in \mathcal H$
, and also the dominated convergence theorem, we have the following convergence in
$\mathcal H$
:
From now on, we impose the following standard assumption.
Assumption 5.
The eigenfunction
$\varphi_0$
of
$L^\kappa$
with eigenvalue
$\lambda_0^\kappa$
satisfies
$\varphi_0 \in {\mathcal{D}}(\kappa)$
, that is,
$\kappa \varphi_0 \in \mathcal{H}$
.
Remark 6. In the QSMC context with Brownian motion, i.e.
$A\equiv 0$
, Assumption 5 corresponds to requiring that
$\Delta \pi$
is square integrable, which is certainly true for densities of the form
$\exp\!(\!-\vert x\vert^\alpha)$
with
$\alpha \ge 2$
.
Together Lemma 8 and Assumption 5 immediately imply the following.
Lemma 9.
Under Assumption 5 we have
$\varphi_0\in {\mathcal{D}}(\widehat{L}^M)$
.
We now turn to the question of existence of a perturbed quasi-stationary distribution, corresponding to a minimal eigenfunction of
$\widehat{L}^M$
. Clearly, if we set
$M=0$
there is no killing, and so there is no quasi-stationary distribution to speak of. Thus it is necessary to enforce a minimum truncation level.
Assumption 6.
The truncation level satisfies
$M \ge {\lambda_0^\kappa}$
.
Theorem 3.
Under Assumptions 4, 5, and 6, the diffusion X killed at rate
$\kappa_M$
with generator
$\widehat{L}^M$
possesses a unique quasi-stationary distribution, and there is a corresponding strictly positive eigenfunction
$\widehat \varphi_0 \in \mathcal{H}$
of
$\widehat{L}^M$
with (minimal) eigenvalue
$\widehat{\lambda}_0^M :\!= \inf \sigma(\widehat{L}^M)$
.
Proof. Since
$\widehat{L}^M$
is a self-adjoint semi-bounded operator, we have the variational representation [Reference Reed and Simon34, Theorem XIII.1]:
From Lemma 9, we have
$\varphi_0 \in {\mathcal{D}}(\widehat{L}^M)\cap \mathsf S(\mathcal{H})$
. Hence, making use of Lemma 8, we have
\begin{equation*} \begin{split} \widehat{\lambda}_0^M &\le \langle \varphi_0, \widehat{L}^M \varphi_0\rangle \\ &= \langle \varphi_0, {L^\kappa} \varphi_0\rangle+\langle \varphi_0, H_M \varphi_0\rangle\\ &= {\lambda_0^\kappa} -\int_{{\mathbb{R}^d}} (\kappa-M)_+ \varphi_0^2\mathrm{d} \Gamma < M, \end{split} \end{equation*}
since we are assuming that
${\lambda_0^\kappa} \le M$
, and the final term is strictly negative, since
$\varphi_0$
is strictly positive.
Thus the bottom of the spectrum
$\widehat{\lambda}_0^M$
of
$\widehat{L}^M$
is strictly smaller than M, which is the limit of the killing at infinity; hence, by [Reference Champagnat and Villemonais7, Theorem 4.5] (and cf. [Reference Kolb and Steinsaltz19, Theorem 4.3]), there is a unique quasi-stationary distribution, and there is a corresponding eigenfunction
$\widehat \varphi_0$
with eigenvalue
$\widehat{\lambda}_0^M$
.
Remark 7. The constant
${\lambda_0^\kappa}$
corresponds to the constant
$-\Phi$
in Condition (1) of [Reference Pollock, Fearnhead, Johansen and Roberts33]. It can also be expressed as the expected value of
$\kappa$
with respect to distribution
$\pi$
.
Remark 8. It follows by [Reference Davies9, Lemma 14.4.1] that, for the bottom of the essential spectrum, we have
$\inf \sigma_\mathrm{ess}(\widehat{L}^M)\ge M$
, and hence
$\widehat{L}^M$
also possesses a spectral gap. This can also be read off from the proof of Theorem 3. The calculation there shows that
Now we define, for arbitrary
$M\geq 0$
,
Then, by [Reference Reed and Simon34, Theorem XIII.1],
$\widehat \lambda_1^M$
is either an eigenvalue of
$\widehat L^M$
or coincides with the bottom of the essential spectrum
$\sigma_\mathrm{ess}(\widehat L^M)$
.
Proposition 5.
Fix
$M_2>M_1>0$
. Then
$\lambda_1^\kappa\ge\widehat \lambda_1^{M_2} \ge \widehat \lambda_1^{M_1}$
.
Proof. This follows from a routine calculation, which we include for completeness. Since the set of smooth, compactly supported functions
$C_\mathrm c^\infty({\mathbb{R}^d})\subset \mathcal{H}$
is a core for
${L^\kappa}$
and for
$\widehat L^M$
for any
$M>0$
, in the variational representation of eigenvalues we can restrict to functions
$f\in C_\mathrm c^\infty({\mathbb{R}^d})$
. Then,
\begin{equation*} \begin{split} \widehat \lambda_1^{M_2} &= {\sup}_{\mathbb V \in \mathcal V_1} \inf_{f\in \mathbb V^\perp \cap \mathsf S(\mathcal{H})\cap C_\mathrm c^\infty} \left (\langle f,\widehat L^0 f\rangle + \langle f,(\kappa \wedge M_2)f\rangle \right )\\ &= {\sup}_{\mathbb V \in \mathcal V_1} \inf_{f\in \mathbb V^\perp \cap \mathsf S(\mathcal{H})\cap C_\mathrm c^\infty} \left ( \langle f,\widehat L^0 f\rangle + \langle f,(\kappa \wedge M_1)f\rangle + \langle f, (\kappa\wedge M_2 - \kappa \wedge M_1)f\rangle \right)\\ &\ge {\sup}_{\mathbb V \in \mathcal V_1} \inf_{f\in \mathbb V^\perp \cap \mathsf S(\mathcal{H})\cap C_\mathrm c^\infty} \left ( \langle f,\widehat L^0 f\rangle + \langle f,(\kappa \wedge M_1)f\rangle \right)\\ &= \widehat \lambda_1^{M_1}. \end{split} \end{equation*}
An analogous argument also gives
$\lambda_1^\kappa\ge\widehat \lambda_1^{M_2}$
.
We have established in Theorem 3 the existence of a minimal eigenfunction
$\widehat \varphi_0$
of
$\widehat L^M$
, under Assumptions 4, 5, and 6 which we assume to hold in the following. We can thus define one-dimensional invariant subspaces of
${L^\kappa}$
and
$\widehat L^M$
, respectively
${\mathrm{span}}\{\varphi_0\}$
and
${\mathrm{span}}\{\widehat \varphi_0\}$
, and make use of the projection operators as previously defined in Section 3.1. Thus, with
$E_0: \mathbb{R} \to \mathcal{H}$
and
$E_1: \mathcal K(E_1)\to \mathcal{H}$
we have for
$f\in {\mathcal{D}}({L^\kappa})$
that
In particular,
$\Lambda_0:\mathbb{R}\to\mathbb{R}$
is the bounded linear operator given by
and
$\Lambda_1$
is the self-adjoint operator given by
$\Lambda_1=E_1^* {L^\kappa} E_1$
with domain
${\mathcal{D}}(\Lambda_1) = E_1^* {\mathcal{D}}({L^\kappa})$
. For our perturbed operator
$\widehat L^M$
, we have with
$F_0: \mathbb{R}\to \mathcal{H}$
and
$F_1: \mathcal K(F_1)\to \mathcal{H}$
the decomposition
for
$f \in {\mathcal{D}}(\widehat L^M)$
, where
$\widehat{\Lambda}_0 \colon \mathbb{R} \to\mathbb{R}$
with
$\widehat{\Lambda}_0 a = \widehat{\lambda}_0^M a$
and
$\widehat \Lambda_1=F_1^* \widehat L^M F_1$
are self-adjoint operators. Note that throughout the norm of an operator always refers to the corresponding operator norm.
Our goal is to bound
$\|\varphi_0-\widehat\varphi_0\|_2$
. For this we aim to apply the results of [Reference Davis and Kahan10]. However, we cannot immediately use the sin
$\theta$
theorem as described in [Reference Davis and Kahan10], because of the unbounded nature of our operators. In order to overcome this issue, we begin by defining an operator
$R: \mathbb{R} \to \mathcal{H}$
, given by
Lemma 10.
The operator
$R \colon \mathbb{R}\to\mathcal{H}$
as defined in (27) is a bounded linear operator, which can be represented as
Moreover, the adjoint operator
$R^*: \mathcal{H} \to \mathbb{R}$
is given by
Proof. Since
$\mathrm{Ran}(E_0):\!= \{E_0 a:a\in \mathbb{R}\} ={\mathrm{span}}\{\varphi_0\}$
, by using Lemma 9 we obtain that R is well-defined. Thus
$\widehat L^M E_0$
is a bounded operator and, since
$E_0 \Lambda_0$
is also a bounded operator, R is a bounded operator.
Furthermore, we can directly compute that
\begin{equation*} \begin{split} Ra &= \widehat L^M a \varphi_0 - \lambda_0^\kappa a \varphi_0\\ &= a [L^\kappa \varphi_0 + H_M\varphi_0- \lambda_0^\kappa \varphi_0]\\ &= a[ \lambda_0^\kappa \varphi_0+H_M\varphi_0- \lambda_0^\kappa \varphi_0] = a H_M \varphi_0, \end{split} \end{equation*}
where we have made use of Lemma 8.
For the adjoint, recall that
$R^*: \mathcal{H} \to \mathbb{R}$
is the unique operator with the property that, for arbitrary
$f\in\mathcal H$
and
$a \in \mathbb{R}$
, we have that
A simple calculation then gives (28).
Now consider the bounded operator
$R^* F_1: \mathcal K(F_1) \to \mathbb{R}$
. By (28), we have, for
$h \in \mathcal K(F_1)$
,
Lemma 11.
The bounded operator
$R^* F_1$
is the closure of the densely defined operator
on smooth compactly supported functions.
Proof. Let
$f\in \mathcal{H}$
be a smooth compactly supported function and consider
$h :\!= F_1^* f\in \mathcal K(F_1)$
. Let
$Q^\perp=F_1^*F_1$
be the projection onto
${\mathrm{span}}\{\widehat\varphi_0\}^\perp$
, P be the projection onto
${\mathrm{span}}\{\varphi_0\}$
, and
$P^{\perp}$
be the projection onto
${\mathrm{span}}\{\varphi_0\}^\perp$
. We can straightforwardly compute the following, using the fact that
$\widehat L^M$
is invariant on
$\mathrm{Ran}(F_1)$
and the fact that
${L^\kappa}$
is invariant on
${\mathrm{span}}\{\varphi_0\}$
and its orthogonal complement:
\begin{equation*} \begin{split} E^*_0 F_1 \widehat\Lambda_1 h - \Lambda_0 E_0^* F_1 h &= E_0^* (Q^\perp\widehat L^M F_1 h) - \Lambda_0 E_0^* F_1 h\\ &= E_0^* (\widehat L^M F_1 h) - \Lambda_0 E_0^* F_1 h\\ &= \langle \widehat L^M F_1 h - \lambda_0^\kappa F_1 h , \varphi_0\rangle \\ &= \langle L^\kappa F_1 h + H_M F_1 h - \lambda_0^\kappa F_1 h , \varphi_0\rangle\\ &= \langle L^\kappa (P F_1 h + P^\perp F_1 h) + H_M F_1 h- \lambda_0^\kappa F_1 h , \varphi_0\rangle\\ &= \langle \lambda_0^\kappa PF_1 h +0 + H_M F_1 h - \lambda_0^\kappa F_1 h , \varphi_0\rangle\\ &= \lambda_0^\kappa\langle F_1 h,\varphi_0\rangle \langle \varphi_0,\varphi_0\rangle +\langle H_M F_1 h, \varphi_0\rangle - \langle\lambda_0^\kappa F_1 h , \varphi_0\rangle\\ &= \langle F_1 h, H_M\varphi_0\rangle = R^* F_1 h. \end{split} \end{equation*}
At the end we also used self-adjointness of
$H_M$
and (28).
We require an additional technical condition.
Assumption 7.
There exists some
$\delta >0$
such that
$\widehat \lambda_1^M >{\lambda_0^\kappa}+\delta$
.
The following auxiliary estimate is a consequence of the latter assumption, Lemma 11, i.e.
$R^* F_1 = E_0^* F_1 \widehat \Lambda_1 - \Lambda_0 E_0^* F_1$
on a dense subset of
$\mathcal{H}$
, and [Reference Davis and Kahan10, Theorem 5.1]; see their comments preceding [Reference Davis and Kahan10, Theorem 5.2] concerning the unbounded case.
Lemma 12. Suppose that Assumption 7 holds. Then
Now we state our perturbation result, whose proof follows that of the sin
$\theta$
theorem of [Reference Davis and Kahan10].
Theorem 4.
Suppose that Assumption 7 holds and without loss of generality let
$\widehat \varphi_0$
be chosen in such a way that
$\langle \varphi_0, \widehat \varphi_0\rangle \geq 0$
. Then
Proof. We set
$\sin \Theta_0 :\!= \sqrt{1-\langle \varphi_0, \widehat \varphi_0\rangle^2}$
. As in the proof of the sin
$\theta$
theorem of [Reference Davis and Kahan10], our operator
$E^*_0 F_1$
corresponds to a rotation from
$\widehat \varphi$
to
$\varphi$
, and thus its angle corresponds to
$\sin \Theta_0$
. Hence, making use of (29), we see that
We can then complete the argument as in the proof of Theorem 1 to get the following bound.
Theorem 5.
Again with
$\widehat \varphi_0$
be chosen in such a way that
$\langle \varphi_0, \widehat \varphi_0\rangle \geq 0$
, under Assumptions 4, 5, 6, and 7 we have
Note that
where on the left-hand side we have the corresponding operator norm and on the right-hand side we have the Hilbert space norm. Moreover, observe that since we have Assumption 5, as the truncation
$M\to \infty$
, we obtain
$\|H_M \varphi_0\|_2 \to 0$
and at the same time, by Proposition 5, we have that
$\delta$
remains constant with M.
Remark 9. When
$\Gamma$
is a finite measure, then the
$\mathcal{L}^2(\mathbb{R}^d,\Gamma)$
-norm-based perturbation bound from Theorem 5 can also be translated into an
$\mathcal{L}^1(\mathbb{R}^d,\Gamma)$
-norm-based perturbation bound, analogously to our previous Proposition 4. We refer to our subsequent Proposition 6 for an application of this procedure.
3.3. Example: unbounded case
We now illustrate our former truncation result on a Gaussian example. In this setting, many relevant quantities are analytically available, so we can carefully isolate the effect of the truncation. We consider a similar example to [Reference Wang, Kolb, Roberts and Steinsaltz43], namely an Ornstein–Uhlenbeck diffusion targeting a Gaussian quasi-stationary distribution. We will see that in any dimension
$d\ge 1$
, for a truncation level M, the error decays like
$\exp\!(\!-M)$
up to some (dimension-dependent) multiplicative constant. In the univariate setting
$d=1$
, we will be able to explicitly compute this constant. Thus truncating the killing rate in this example appears to be robust with respect to dimension, in that the error decays exponentially for any dimension.
Throughout, we write
$\mathcal N(\mu, \sigma^2)$
for the univariate Gaussian distribution with mean
$\mu\in\mathbb{R}$
and variance
$\sigma^2>0$
, and
$\mathcal N(\mu, \Sigma)$
for the corresponding multivariate Gaussian distribution with mean vector
$\mu \in {\mathbb{R}^d}$
and covariance matrix
$\Sigma \in \mathbb{R}^{d\times d}$
. Moreover,
$I_d$
denotes the identity matrix on
${\mathbb{R}^d}$
. We take the diffusion to be a multivariate Ornstein–Uhlenbeck process on
${\mathbb{R}^d}$
determined by
which possesses an invariant measure
$\Gamma(\mathrm{d} x) = \exp{\!(\!-\vert x\vert ^2/2)}\mathrm{d} x$
proportional to the
$\mathcal N(0,I_d)$
distribution.
We take the target to be
$\pi=\mathcal N(0,I_d/2)$
, in which case the killing rate has a particularly simple form,
It follows by [Reference Wang, Kolb, Roberts and Steinsaltz43] that
$\pi$
is the quasi-stationary distribution of the killed Markov process based on
$X=(X_t)_{t\geq0}$
, see also Section 1.3. We are now interested in deriving quantitative bounds on the effect of truncating this divergent killing rate at a level M. In order to obtain explicit constants, we now focus on the univariate case
$d=1$
, where all necessary calculations are analytically tractable. We will return to the general multivariate case in Proposition 7.
Having this, the normalized (in
$\mathcal L^2(\mathbb{R},\Gamma)$
) eigenfunction
$\varphi_0\colon\mathbb{R}\to\mathbb{R}$
of the corresponding unperturbed generator
$L^\kappa$
is given by
with
$C=(\frac{3}{2\pi})^{1/4}$
.
Moreover, the bottom of the spectrum of the unperturbed operator is given by
as in [Reference Wang, Kolb, Roberts and Steinsaltz43, (2.4)], and the entire spectrum can be represented as
with spectral gap
see [Reference Metafune, Pallara and Priola28].
Clearly our killing rate
$\kappa$
as defined in (31) is unbounded, and we are interested in studying the effect of truncating this killing rate upon the quasi-stationary distribution. For
$M\geq 0$
we consider a truncation at level M and set
This gives rise to our perturbed Markov process with killing rate
$\kappa_M$
with generator
$\widehat{L}^M$
. Note that we use the notation of the previous section.
In order to utilize the estimate of Theorem 5 to obtain a quantitative result, we need to calculate the
$\delta$
-separation between
${\lambda_0^\kappa}$
and
$\widehat \lambda_1^M$
as in Assumption 7, since
$\delta$
appears in the bounds. Calculating the spectrum in general is a difficult problem, so we resort to a scheme which was utilized in [Reference Mielnik and Reyes29] to numerically calculate the energy levels of the quantum truncated harmonic oscillator (which correspond to a killed Brownian motion). Since we are interested in a killed Ornstein–Uhlenbeck process (30) rather than a killed Brownian motion, we extend their technique into our present setting.
Considering (25), we obtain the eigenvalue problem
that is, we seek
$\lambda\in\mathbb{R}$
and
$\varphi\in\mathcal{L}^2(\mathbb{R},\Gamma)$
such that (34) is satisfied. By the fact that the killing rate
$\kappa_M$
is constant for
$|x|>\sqrt M$
, using [Reference Taylor40], we can explicitly write down the form of the eigenfunctions in the tails. Define
Then, given
$\lambda\in\mathbb{R}$
, the solution of (34) when
$|x|>\sqrt M$
is
\begin{equation} \varphi(x) = \varphi^{(\lambda)} (x) = \begin{cases} c_1 K_{2(M-\lambda)}^+(x), \quad x< -\sqrt M, \\ c_1 K_{2(M-\lambda)}^- (x),\quad x> \sqrt M, \end{cases} \end{equation}
since the eigenfunction must be square integrable. Note that here we have a common constant
$c_1>0$
by symmetry. Now, following [Reference Mielnik and Reyes29], we substitute
and change to polar coordinates: for suitable functions
$\rho\colon\mathbb{R}\to(0,\infty)$
and
$\alpha\colon\mathbb{R} \to \mathbb{R}$
we have
With this substitution, we can modify (34) to the following equations:
Note that in contrast to [Reference Mielnik and Reyes29, (17)] we require the additional final term in (37).
Then by multiplying (36) by
$-\sin \alpha$
and adding it to
$\cos \alpha$
times (37), we obtain a first-order differential equation for
$\alpha$
, given by
Noting that
we can compute that in the tails,
\begin{equation} \tan \alpha(x) = \frac{p(x)}{q(x)}= \begin{cases} \frac{\sqrt 2 \int_0^\infty r^{\beta^*} \exp\!(-r^2 + \sqrt 2 rx)\mathrm{d} r }{\int_0^\infty r^{{\beta^*}-1} \exp\!(-r^2 + \sqrt 2 rx)\mathrm{d} r} , \quad x\le -\sqrt M, \\ \frac{-\sqrt 2 \int_0^\infty r^{\beta^*} \exp\!(-r^2 - \sqrt 2 rx)\mathrm{d} r }{\int_0^\infty r^{{\beta^*}-1} \exp\!(-r^2 - \sqrt 2 rx)\mathrm{d} r},\quad x\ge \sqrt M, \end{cases} \end{equation}
with
${\beta^*} = 2(M-\lambda)$
.
Since we know that the evolution of
$\alpha(x)$
is given by (38), and we have boundary values given by (39), in order for
$\lambda$
to be a valid eigenvalue, we require the following compatibility condition, analogously to [Reference Mielnik and Reyes29]: for some integer n,
where
$\alpha'$
is defined by (38) and
$\alpha (\pm \sqrt M)$
are defined by (39).
Thus, again following the approach of [Reference Mielnik and Reyes29], we define
where the right-hand side can be computed numerically to arbitrary accuracy using a numerical ordinary differential equation solver. Thus we need to find values of
$\lambda$
such that
for integers n. The corresponding values of
$\lambda$
for which (41) hold are precisely the eigenvalues for the truncated operator with truncation level M. We have plotted the function
$\lambda\mapsto s_M(\lambda)$
in the cases
$M=2,10,40$
in Figure 4.
For analogous plots in the case of Brownian motion (rather than our Ornstein–Uhlenbeck process (30)), see Figure 3 of [Reference Mielnik and Reyes29]. We can see that our truncated eigenvalues are all strictly smaller than their untruncated counterparts given by (33), and this difference vanishes as
$M\to \infty$
, as is intuitively reasonable.
Thus we can utilize Theorem 5 to derive the following bounds in
$\mathcal L^2(\mathbb{R},\Gamma)$
.
Lemma 13.
For our Ornstein–Uhlenbeck diffusion (30) with quasi-stationary distribution
$\pi=\mathcal N(0,1/2)$
, for any
$M\ge 2$
, there exists a perturbed quasi-stationary distribution
$\pi_M$
, and writing
$\varphi_0, \widehat{\varphi}_{0,M}$
for the corresponding normalized (in
$\mathcal L^2(\mathbb{R},\Gamma)$
) eigenfunctions, we have
with
$c_2=\frac{\sqrt{3}\cdot 35^{1/4}}{2\delta}$
.
Note that we do not prove Assumption 7, but rather, as detailed above, we use the numerical method of [Reference Mielnik and Reyes29] to verify that indeed for this example
$\delta >0$
as required. For computation of its value, see Remark 10.
Proof. From Theorem 5, we only need to compute
$\|H_M E_0\|=\|H_M \varphi_0\|_2$
. With
$C=\left( \frac{3}{2\pi}\right)^{1/4}$
we obtain
\begin{align*} \|H_M \varphi_0\|^2_2 &= C^2 \int_{-\infty}^\infty (\kappa(x)-M)_+^2 \exp\!(\!-x^2) \mathrm{d} \Gamma(x)\\ &= 2C^2 \int_{\sqrt M}^\infty (x^2-M)^2 \exp\!(\!-3x^2/2)\mathrm{d} x\\ &\le C^2 \left (\int_{\mathbb{R}} x^8 \exp\!(\!-x^2) \mathrm{d} x\right)^{1/2} \left( \int_{\sqrt M}^\infty \exp\!(\!-2x^2)\mathrm{d} x \right)^{1/2}\\ &\le C^2 (105 \sqrt{\pi}/16)^{1/2} \left( \sqrt{\pi/2} \exp\!(\!-2M) \right)^{1/2}, \end{align*}
where we have used the Cauchy–Schwarz inequality, the fact that for
$\mathcal N(0,\sigma^2)$
the eighth moment is
$105\sigma^8$
, and standard Gaussian tail bounds; see e.g. [Reference Wainwright41, Proposition 2.5]. Tidying up the constants, the lemma is proved.
We now translate our previous
$\mathcal L^2(\mathbb{R},\Gamma)$
estimate into a bound on the corresponding (normalized) quasi-stationary distributions in
$\mathcal L^1(\mathbb{R},\Gamma)$
.
Proposition 6.
In the same setting as Lemma 13 we obtain, for any
$M> 2\log(2(2\pi)^{1/4} Zc_1)\approx 5.58$
, that there exists a perturbed quasi-stationary distribution
$\pi_M$
, and
for
$c_3\approx 5.49$
defined explicitly in (44).
Proof. We first relate
$\int_{\mathbb{R}} |\pi(x)- \pi_M(x)|\mathrm{d} x$
to our previous bound. With
$\gamma(x):\!= \exp\!(\!-x^2/2)$
let us write
$\phi:\!= \pi/\gamma$
,
$\widehat\phi_M:=\pi_M/\gamma$
for the corresponding normalized densities with respect to
$\Gamma$
. Thus we have
$\varphi_0 = \phi/Z$
and
$\widehat\varphi_{0,M} = \widehat\phi_M/Z_M$
, where the normalizing constants are given by
$Z :\!= \|\phi\|_2 = (\frac{2}{3\pi})^{1/4}$
and
$Z_M :\!= \|\widehat\phi_M\|_2$
.
Plots of the function
$\lambda\mapsto s_M(\lambda)$
, as defined in (40), for
$M=2,10,40$
.

Thus, with
$(\int_{\mathbb{R}} \mathrm{d} \Gamma)^{1/2}=(2\pi)^{1/4}$
, we have from Lemma 3 that
From Lemma 13, we obtain
By Lemma 4 this gives
provided that
$M>2\log((2\pi)^{1/4} Zc_2)$
. By using Lemma 5 we also have
Furthermore, if
$M>2\log(2(2\pi)^{1/4} Zc_2)$
, the final term of the former bracket expression is bounded from above by
$2(2\pi)^{1/4} Z^2 c_2$
. Putting the pieces together, for all
$M>2\log(2(2\pi)^{1/4} Zc_2)$
, by applying Proposition 2 we have
with
Remark 10. Note that the numerical solutions plotted in Figures 1a, 1b and 1c indicate that we may choose
$\delta = 1.3$
in our setting. By the former proposition this leads to (42) for
$M>2 \log(2(2\pi)^{1/4} Zc_1)\approx 5.58$
and
$c_3 \approx 5.49 $
.
The above approach can be applied to the more general multivariate Gaussian case at the outset of this subsection. In this more general case, we are unable to apply our extension of [Reference Mielnik and Reyes29], so can no longer obtain explicit constants as in Remark 10, but can still bound the effect of truncating at level M up to a constant.
Proposition 7.
In the multivariate setting
$d>1$
, given some
$\delta$
-separation between
${\lambda_0^\kappa}$
and
$\widehat \lambda_1^M$
, we have the bound for some constant
$C_d>0$
,
Proof. The previous lemmas still go through in the multivariate setting, up to a constant factor which depends on the dimension. In place of a Gaussian tail bound as in the proof of Lemma 13, we can use a
$\chi^2$
tail bound, as in, say, [Reference Laurent and Massart22, Lemma 1].
Appendix A. Deferred proofs
A.1. Proof of Proposition 1
Let
$G(y) :\!= 1-\kappa(y)$
and
$\widetilde{G}(y) :\!= 1 - \widetilde{\kappa}(y)$
for all
$y\in S_0$
. Furthermore, let
$(Y_n)_{n\in\mathbb{N}_0}$
be a Markov chain on
$S_0$
with transition kernel Q starting at
$x_0$
. Then, for arbitrary
$A \in \mathcal S_0$
, with
$y_0:\!= x$
, we have
\begin{align*} \mathbb{P}_{x_0}(X_n\in A) & = \int_{S_0} \ldots \int_{S_0} \mathbf{1}_A(y_n) \prod_{j=0}^{n-1} G(y_j) Q(y_{n-1},\mathrm{d}y_n) \ldots Q(y_1,\textrm{ d}y_2) Q(y_0,\mathrm{d} y_1)\\ & = \mathbb{E}_{x_0} \left[\mathbf{1}_A(Y_n) \prod_{j=0}^{n-1} G(Y_j) \right], \end{align*}
and by the same arguments
$ \mathbb{P}_{x_0}(\widetilde{X}_n\in A) = \mathbb{E}_{x_0} \left[ \mathbf{1}_A(Y_n) \prod_{j=0}^{n-1} \widetilde{G}(Y_j) \right]$
. In addition to that,
\begin{align*} & \left \vert \mathbb{P}_{x_0}(X_n\in A\mid X_n\in S_0) - \mathbb{P}_{x_0}(\widetilde{X}_n\in A\mid \widetilde{X}_n\in S_0)\right \vert \\= & \left \vert \frac{\mathbb{P}_{x_0}(X_n\in A)}{\mathbb{P}_{x_0}(X_n\in S_0)} - \frac{\mathbb{P}_{x_0}(\widetilde{X}_n\in A)}{\mathbb{P}_{x_0}(\widetilde{X}_n\in S_0)} \right \vert \\\leq & \left \vert \frac{\mathbb{P}_{x_0}(X_n\in A)}{\mathbb{P}_{x_0}(X_n\in S_0)} - \frac{\mathbb{P}_{x_0}(\widetilde{X}_n\in A)}{\mathbb{P}_{x_0}(X_n\in S_0)} \right \vert + \left\vert \frac{\mathbb{P}_{x_0}(\widetilde{X}_n\in A)}{\mathbb{P}_{x_0}(X_n\in S_0)} - \frac{\mathbb{P}_{x_0}(\widetilde{X}_n\in A)}{\mathbb{P}_{x_0}(\widetilde{X}_n\in S_0)} \right \vert\\\leq & \frac{\mathbb{E}_{x_0}\left \vert \prod_{j=0}^{n-1} G(Y_j) - \prod_{j=0}^{n-1} \widetilde{G}(Y_j) \right \vert}{\mathbb{P}_{x_0}(X_n\in S_0)} + \frac{\mathbb{P}_{x_0}(\widetilde{X}_n\in A)\cdot \mathbb{E}_{x_0}\left \vert \prod_{j=0}^{n-1} G(Y_j) - \prod_{j=0}^{n-1} \widetilde{G}(Y_j) \right \vert}{\mathbb{P}_{x_0}(X_n\in S_0) \mathbb{P}_{x_0}(\widetilde{X}_n\in S_0)}\\\leq & \frac{2 \cdot \mathbb{E}_{x_0}\left \vert \prod_{j=0}^{n-1} G(Y_j) - \prod_{j=0}^{n-1} \widetilde{G}(Y_j) \right \vert}{\mathbb{P}_{x_0}(X_n\in S_0)}. \end{align*}
By the same arguments, just by adding and subtracting
$\frac{\mathbb{P}_{x_0}(X_n\in A)}{\mathbb{P}_{x_0}(\widetilde{X}_n\in S_0)}$
instead of
$\frac{\mathbb{P}_{x_0}(\widetilde{X}_n\in A)}{\mathbb{P}_{x_0}(X_n\in S_0)}$
before the first inequality of the previous estimation, we obtain
\begin{align*} & \left \vert \mathbb{P}_{x_0}(X_n\in A\mid X_n\in S_0) - \mathbb{P}_{x_0}(\widetilde{X}_n\in A\mid \widetilde{X}_n\in S_0)\right \vert \leq \frac{2 \mathbb{E}_{x_0}\left \vert \prod_{j=0}^{n-1} G(Y_j) - \prod_{j=0}^{n-1} \widetilde{G}(Y_j) \right \vert}{\mathbb{P}_{x_0}(\widetilde{X}_n\in S_0)},\end{align*}
such that
\begin{align} & \left \vert \mathbb{P}_{x_0}(X_n\in A\mid X_n\in S_0)- \mathbb{P}_{x_0}(\widetilde{X}_n\in A\mid \widetilde{X}_n\in S_0)\right \vert\leq \frac{2 \mathbb{E}_{x_0}\left \vert \prod_{j=0}^{n-1} G(Y_j) - \prod_{j=0}^{n-1} \widetilde{G}(Y_j) \right \vert}{\max\{\mathbb{P}_{x_0}(\widetilde{X}_n\in S_0),\mathbb{P}_{x_0}(X_n\in S_0)\}}.\end{align}
By induction over n we can verify for any
$z_0,\ldots,z_{n-1}\in S_0$
that
\begin{align*} \prod_{j=0}^{n-1} G(z_j) - \prod_{j=0}^{n-1} \widetilde{G}(z_j) = \sum_{i=0}^{n-1} \left[ \prod_{j=0}^{i-1} G(z_j) (G(z_i)-\widetilde G(z_i)) \prod_{m=i+1}^{n-1} \widetilde{G} (z_m) \right].\end{align*}
Using this we get
\begin{equation} \mathbb{E}_{x_0}\left \vert \prod_{j=0}^{n-1} G(Y_j) - \prod_{j=0}^{n-1} \widetilde{G}(Y_j) \right \vert \leq \Vert \kappa-\widetilde{\kappa}\Vert_{\infty} \sum_{i=0}^{n-1} \mathbb{E}_{x_0} \left \vert \prod_{j=0}^{i-1}G(Y_j) \prod_{m=i+1}^{n-1} \widetilde{G}(Y_{m}) \right \vert\end{equation}
and eventually
\begin{align*} & \mathbb{E}_{x_0} \left \vert \prod_{j=0}^{i-1}G(Y_j) \prod_{m=i+1}^{n-1} \widetilde{G}(Y_{m}) \right\vert\\= & G(x_0) \underbrace{\int_{S_0} \ldots \int_{S_0}}_{i-1 \text{\,int.}} \int_{S_0} \underbrace{\int_{S_0} \ldots \int_{S_0}}_{n-i-1 \text{\,int.}} \widetilde{G}(y_{n-1}) Q(y_{n-2},\mathrm{d}y_{n-1}) \,\cdots\, \widetilde{G}(y_{i+1}) Q(y_i,\mathrm{d}y_{i+1}) \\ & \qquad \quad \times Q(y_{i-1},\mathrm{d} y_{i}) G(y_{i-1}) Q(y_{i-2},\mathrm{d}y_{i-1}) \cdot \ldots \cdot G(y_1) Q({x_0},\mathrm{d}y_1)\\= & G({x_0}) \underbrace{\!\int_{S_0} \!\ldots\! \int_{S_0}}_{i-1 \text{\,int.}} \!\int_{S_0} \!\mathbb{P}_{y_i}(\widetilde{X}_{n-i-1}\in S_0) Q(y_{i-1},\mathrm{d} y_{i})G(y_{i-1}) Q(y_{i-2},\mathrm{d}y_{i-1}) \cdot \ldots \cdot G(y_1) Q({x_0},\mathrm{d}y_1)\\ \leq & {\sup}_{z\in S_0} \int_{S_0} \mathbb{P}_{\widetilde{x}}(\widetilde{X}_{n-i-1}\in S_0) Q(z,\mathrm{d} \widetilde{x}) \cdot \mathbb{P}_{x_0}(X_{i}\in S_0) \\\leq & {\sup}_{z\in S_0} \int_{S_0} \widetilde{c}_u(\widetilde{x}) Q(z,\mathrm{d}\widetilde{x})\, \widetilde{\alpha}^{n-i-1} \cdot c_u({x_0}) \alpha^{i} ,\end{align*}
where the last inequality follows from (1) and (2). Additionally, these conditions lead to
Hence, by the previous two estimates as well as (45) and (46) we obtain
\begin{align*} \left \vert \mathbb{P}_{x_0}(X_n\in A\mid X_n\in S_0) - \mathbb{P}_{x_0}(\widetilde{X}_n\in A\mid \widetilde{X}_n\in S_0)\right \vert \leq K({x_0}) \Vert \kappa-\widetilde{\kappa} \Vert_\infty \sum_{i=0}^{n-1} \frac{\alpha^{i}\widetilde{\alpha}^{n-i-1}}{\max\{\alpha,\widetilde{\alpha}\}^n}.\end{align*}
Estimating the sum independently for the two cases
$\alpha<\widetilde{\alpha}$
and
$\alpha\geq\widetilde{\alpha}$
leads to
\begin{align*} \sum_{i=0}^{n-1} \frac{\alpha^{i}\widetilde{\alpha}^{n-i-1}}{\max\{\alpha,\widetilde{\alpha}\}^n} \leq \min\{n,\vert \alpha-\widetilde{\alpha} \vert^{-1}\}\end{align*}
and the statement is proven.
A.2. Proof of Lemma 1
We prove the inequality for
$j=1$
. The case
$j=0$
works entirely analogously. We have
\begin{equation*} \begin{split} \widehat \lambda_1 &= {\sup}_{\mathbb V \in \mathcal V_1} \inf_{f\in \mathbb V^\perp \cap \mathsf S(\mathcal{H})\cap {\mathcal{D}}(L)} \langle f, \widehat Lf\rangle\\ &\ge {\sup}_{\mathbb V \in \mathcal V_1} \left( \inf_{f\in \mathbb V^\perp \cap \mathsf S(\mathcal{H})\cap {\mathcal{D}}(L)} \langle f,Lf\rangle + \inf_{f\in \mathbb V^\perp \cap \mathsf S(\mathcal{H})\cap {\mathcal{D}}(L)} \langle f,Hf\rangle \right)\\ &\ge {\sup}_{\mathbb V \in \mathcal V_1} \left \{ \inf_{f\in \mathbb V^\perp \cap \mathsf S(\mathcal{H})\cap {\mathcal{D}}(L)} \langle f,Lf\rangle - \|H\| \right \}\\ &= \lambda_1 - \|H\| . \end{split} \end{equation*}
Exchanging the roles of
$\lambda_1$
and
$\widehat\lambda_1$
, we conclude (9) for
$j=1$
.
A.3. Proof of Lemma 2
By Lemma 1 and Assumption 2, we have that
Adding the inequalities and exploiting
$\nu = \lambda_1-\lambda_0$
gives the first statement.
We now turn to the second statement. Clearly we have
$\widehat\lambda_0 \in \sigma(\widehat L)$
, see [34, Theorem XIII.1]. This is an eigenvalue since
$\widehat\lambda_0$
is an isolated point in
$\sigma(\widehat L)$
. The fact that this is furthermore a one-dimensional eigenspace follows from the simplicity of
$\lambda_0$
: suppose not, so we have two orthogonal eigenfunctions of
$\widehat\lambda_0$
,
$\varphi_1, \varphi_2$
, each with norm 1. Then given any one-dimensional linear subspace
$\mathbb{V}\subseteq \mathcal{H}$
, for some
$\alpha\in [0,1]$
we have that
$\varphi^*:=\alpha \varphi_1 + \sqrt{1-\alpha^2}\varphi_2 \in \mathbb{V}^\perp\cap \mathsf{S}(\mathcal{H})\cap \mathcal{D}(L)$
, and note that
$\varphi^*$
is also an eigenfunction of
$\widehat\lambda_0$
with norm 1. Then we have that
which contradicts the definition of
$\lambda_1$
in (7). Thus the function which generates the eigenspace and has norm 1 is unique, up to the sign. Therefore, changing the sign if necessary, we may assume that the function
$\widehat\varphi\in \mathsf{S}(\mathcal{H})$
from the eigenspace satisfies
$\langle \varphi , \widehat \varphi\rangle \ge 0$
.
A.4. Proof of (13) from Remark 2
From Lemma 2 we have that
$\widehat \lambda_0$
is an isolated point in the spectrum, i.e. an eigenvalue of
$\widehat L$
with eigenvector
$\widehat \varphi$
. Thus
$\widehat L$
is invariant on
${\mathrm{span}}\{\widehat \varphi\}$
and on the orthogonal complement
${\mathrm{span}}\{\widehat \varphi\}^\perp$
.
Then writing
$\widehat L_1$
for the action of
$\widehat L$
on
$({\mathrm{span}}\{\widehat \varphi\})^\perp$
as in (22), we have that
$\sigma(\widehat L_1)\subset [\widehat \lambda_1,\infty)\subset [\lambda_1 - \|H\|,\infty)\subset [\lambda_0 + \nu/2,\infty)$
, by Lemma 1 and Assumption 2.
Translating the sin
$\theta$
theorem of [Reference Davis and Kahan10] (Section 3.1) into the present setting, we obtain
since
$\sigma(L_0) = \{\lambda_0\}$
and
$\sigma(\widehat L_1)\subset [\lambda_0 + \nu/2,\infty)$
. Here
$L_0$
denotes the action of L on
${\mathrm{span}} \{\varphi\}$
.
The proof of (13) from Remark 2 is eventually completed by following a calculation analogous to those in the proof of Theorem 1.
Acknowledgements
We would like to thank the following for interesting discussions on topics related to this work: Abraham Ng, Murray Pollock, Sam Power, Lionel Riou-Durand. We would like to thank the Oberwolfach Uncertainty Quantification meeting, March 2019 for facilitating discussions which lead to this work. We would particularly like to thank the anonymous referees whose comments substantially improved the paper, including shortening the proofs of Theorem 1 and Lemma 2.
Funding information
DR acknowledges support of the DFG within project 389483880. AQW was funded by EPSRC grant CoSInES (EP/R034710/1).
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.


