Asymptotic variance for Random walk Metropolis chains in high dimensions: logarithmic growth via the Poisson equation
Aleksandar Mijatović Jure Vogrinc
math.PR 60J10, 60J22



There are two ways of speeding up MCMC algorithms: (1) construct more
complex samplers that use gradient and higher order information about
the target and (2) design a control variate to reduce the asymptotic
variance. While the efficiency of (1) 
as a function of dimension has been studied extensively, this paper provides 
the first results linking the efficiency of (2) with dimension.
Specifically, we construct a control variate for a  
d-dimensional Random walk Metropolis chain with an IID target 
using the solution of the Poisson equation for the 
scaling limit in <cit.>. 
We prove that 






the asymptotic variance of the corresponding estimator is bounded above by a multiple of 
log(d)/d over the spectral gap of the chain. 

The proof hinges on 
large deviations theory, optimal Young's inequality and
Berry-Esseen type bounds. 
Extensions of the result to non-product targets are discussed. 




[
    [
    December 30, 2023
=====================





§ INTRODUCTION



Markov Chain Monte Carlo (MCMC) methods are designed to approximate 
expectations of high dimensional random vectors, see e.g. <cit.>. 
It is hence important to understand how the efficiency of MCMC algorithms
scales with dimension. The optimal scaling literature, initiated by the seminal
paper <cit.>, indicates that for the high-dimensional algorithms
it is the growth of the asymptotic variance with dimension that 
provides perhaps the most natural measure of efficiency for MCMC (see <cit.>,
<cit.>).
For instance, for a product target, the asymptotic variance for the Random walk Metropolis (RWM) chain on
^d is 
heuristically of the order Ø(d)  <cit.>. 
Moreover, 
the asymptotic variances 
of the d-dimensional 
Metropolis-adjusted Langevin algorithm (MALA), 
Hamiltonian Monte Carlo  and the fast-MALA
are
Ø(d^1/3) <cit.>, Ø(d^1/4) <cit.> and Ø(d^1/5) <cit.>, respectively.


This paper constructs a dimension-dependent estimator (see (<ref>) below)
and proves a bound on its asymptotic variance, 
suggesting the order Ø(log(d)), for a RWM chain with an IID target.
The idea is to exploit the following facts:
(I) the law of the diffusion scaling limit for the RWM chain 
(as d→∞) from <cit.>
is close (in the weak sense) to that of the law of the chain 
itself and (II) the Poisson equation for the limiting Langevin diffusion
has an explicit solution. 
Following ideas from <cit.>,  
we construct and analyse the estimator using (I) and (II). 


Specifically, let ρ be a density on  and 
ρ_d(𝐱^d):=∏_i=1^dρ(x^d_i)
the corresponding d-dimensional product density, 
where
𝐱^d=(x_1^d,…,x_d^d)∈^d.
Let
𝐗^d={𝐗^d_n}_n∈
be the RWM chain converging to ρ_d
with the normal proposal with variance 
l^2/d· I_d
(here 

I_d𝐱^d=𝐱^d, for all 𝐱^d∈^d, and 
l a constant),  
analysed in <cit.>.
If
f(𝐱^d) depends only on the first coordinate x_1^d, 
then 
ρ_d(f):=∫_^d f(𝐱^d)ρ_d(𝐱^d)d𝐱^d= ∫_ f(x)ρ(x)dx=:ρ(f).
Under appropriate conditions, 
the asymptotic variance σ^2_f,d in the Central limit theorem (CLT) for the 
estimator
∑_i=1^n f(𝐗^d_i)/n
of
ρ_d(f)
satisfies


    σ_f,d^2≤ 2Var_ρ(f)/(1-λ_d)    and, heuristically, 
        σ_f,d^2= Ø(d) as d→∞.

Here 
Var_ρ(f):=ρ(f^2)-ρ(f)^2 and 
1-λ_d denotes the spectral gap of the chain 
𝐗^d. The inequality follows by the spectral representation of σ_f,d^2 
in <cit.>.
The reasoning analogous to that 
applied to the integrated autocorrelation time
in <cit.> can be used to argue that 
the spectral gap 1-λ_d is of the order Ø(1/d).
Hence the asymptotic variance σ_f,d^2 is Ø(d).

The Poisson equation for the Langevin diffusion arising in the scaling limit of  𝐗^d
in <cit.> is a second order linear ODE with solution f̂ given explicitly in 
terms of f and the density ρ, see (<ref>) below.
For large d, the function f̂ ought to approximate the solution of the Poisson equation for
𝐗^d. 
The reasoning in <cit.> then suggests the form of an estimator for ρ_d(f), which 
under appropriate technical assumptions,
satisfies the following CLT:

    √(n)(1/n∑_i=1^n(f+d(P_df̂-f̂))(𝐗^d_i)-ρ_d(f))
    N(0,σ̂^2_f,d)  as n→∞,

where P_d is the transition kernel of the chain 𝐗^d. 
The main result of this paper (Theorem <ref> below) states that for some constant C>0 
the following inequality 
holds 

    σ̂_f,d^2≤  Clog(d)/(d(1-λ_d))      and, heuristically,    σ̂_f,d^2=Ø(log(d)) as d→∞.

Theorem <ref> also gives the explicit dependence of the constant C on the function f. 

This result suggests that to achieve the same level
of accuracy as when estimating ρ_d(f) by an average over an IID sample 
form ρ_d,
only  Ø(log d) times as many RWM samples are
needed if the control variate d (P_df̂-f̂) is added.  This should be
contrasted to  Ø(d) (resp. Ø(d^1/3), Ø(d^1/4), Ø(d^1/5)) times as many samples
for the RWM (resp. MALA, Hamiltonian Monte Carlo, fast-MALA) 
without the control
variate, 
see <cit.>. 

The optimal scaling for the proposal variance of a d-dimensional RWM chain is Ø(1/d), 
see <cit.>
for a review  
and <cit.> for the proof that other scalings lead to suboptimal behaviour. 
To get a non-trivial scaling limit in <cit.>,
it is necessary to accelerate the chains (𝐗^d)_d∈ linearly 
in dimension. The weak convergence of the accelerated chain to the Langeivn diffusion
suggests that 
df̂ is close to the solution of the Poisson equation for P_d and f,
making d (P_df̂-f̂) a good control variate. Using an
approximate solution to the Poisson equation to construct control variates is a
common variance reduction technique, see e.g. <cit.>. 
In this context, more often than not, 
an approximate solution used is a solution of a
Poisson equation of a simpler related process. For instance, in <cit.> 
a sequence of Markov chains on a finite state space, converging weakly to a given RWM chain,
is constructed. 
Then a solutions to the  Poisson equation of the finite state chain
is used to construct a control variate capable of reducing the 
asymptotic variance of the RWM chain arbitrarily. 
Here this idea is turned on its head: 
a solution to the Poisson equation of the limiting diffusion is used to construct a
control variate for a RWM chain from a weakly convergent sequence in <cit.>.
Since the complexity of the RWM increases arbitrarily as dimension d→∞, 
it is infeasible to get an arbitrary variance reduction as in <cit.>.  
However, heuristically, the amount of 
variance reduction  measured by the ratio σ_f,d^2/σ̂_f,d^2 
still tends to infinity at the rate d/log(d).

If the solution of the Poisson equation for 𝐗^d and f were available,
we could construct an estimator for ρ_d(f) with zero variance (see e.g. <cit.>).
Put differently, in this case there would be no need for the chain to explore its state space
at all.
In our setting,
since the jumps of 
𝐗^d
are of size 
Ø(1/√(d)) <cit.>,
after Ø(log d) steps 
the chain will have explored the distance of 
Ø(log(d)/√(d)). In line with the observation above this distance
tends to zero as d→∞ since, heuristically, 
df̂ approximates the solution of the Poisson equation for P_d and f
arbitrarily well. 

The key technical step 
in the proof of our result
(Theorem <ref> below)
is a type of concentration inequality.
It generalises the limit in <cit.>, 
which essentially states that generators of the accelerated chains (𝐗^d)_d∈ converge 
to the generator of the Langevin limit when applied to a compactly supported and infinitely smooth function,
in two ways: (A) it extends the limit to a class of functions of sub-exponential growth
and (B) provides estimates for the rate of convergence.
Both of these extensions are key for our main result. (A) allows us to apply 
Theorem <ref> to a solution of the Poisson equation, which is not compactly supported.
Note that this step in the proof entails identifying the correct space of functions that is closed under the operation of
solving the Poisson equation (see Proposition <ref> below). Estimate (B) allows us to control the asymptotic variance 
via a classical spectral-gap bound.
The proof of Theorem <ref>, outlined in Sec. <ref> below,
crucially depends on the large deviations theory (Sec. <ref>), the form of the constant in optimal 
Young's inequality (Sec. <ref>)
and Berry-Esseen type bounds (Sec. <ref>). 

We conclude the introduction with a comment on how the present paper fits into the literature.
Since, as discussed above, the asymptotic variance 
σ_f,d^2 
is approximately equal to the product
2Var_ρ(f)/(1-λ_d), 
two “orthogonal” approaches to speeding up MCMC algorithms are feasible. 
(a) The MCMC method itself can be modified, with the aim of increasing the
spectral gap, leading to many well-known reversible samplers such as 
MALA and  Hamiltonian Monte Carlo <cit.>
as well as 
non-reversible ones <cit.>. 
There is a plethora of papers (see <cit.> and the references therein)
studying the asymptotic properties of such sampling algorithms as dimension increases to infinity. 
(b) A control variate g, satisfying ρ(g)=0, may be added to f 
with the aim of reducing Var_ρ(f) to
Var_ρ(f+g) 
without modifying the MCMC algorithm. 
A number of control variates have been proposed in the MCMC literature <cit.>.  Thematically, the present paper fits under (b) and, to the best of our knowledge,
is the first to investigate the growth of the asymptotic variance as the dimension d→∞ in this context.  
Moreover, it is feasible that our method could be generalised to some of the algorithms  under (a), 
see Section <ref> below for a discussion of possible extensions.

The remainder of paper is structured as follows. Section <ref> 
gives a detailed description of the assumptions and states the results. 
Section <ref> illustrates algorithms based on our main result with numerical examples and discusses (without proof) potential extensions of our results for other MCMC methods, more general targets, etc.
In Section <ref> we prove our results. Section <ref> 
develops the tools needed for the proofs of Section <ref>.
Section <ref> 
uses results from probability and analysis but
is independent of all that
precedes it in the paper. 



§ RESULTS


Let
𝐗^d={𝐗^d_n}_n∈
be a RWM chain in ^d with a transition kernel P_df:=(1/d)𝒢_df + f, where 

    𝒢_df(𝐱^d):=d𝔼_𝐘^d[(f(𝐘^d)-f(𝐱^d)) α(𝐱^d,𝐘^d)
    ],    α(𝐱^d,𝐘^d):=1∧ρ_d(𝐘^d)/ρ_d(𝐱^d),

𝐱^d∈^d,
𝐘^d=(Y_1^d,…,Y_d^d)∼ N(𝐱^d,l^2/d· I_d)
and x∧ y:=min{x,y} for all x,y∈,
started in stationarity 𝐗^d_1∼ρ_d.
Let 𝒮^n consists of all the functions  with their
first n derivatives growing slower then any exponential function. 
More precisely, 
for any n∈∪{0}, define

    𝒮^n:={g∈𝒞^n()∑_i=0^ng^(i)_∞,s<∞∀ s>0},
        where g_∞,s:=sup_x∈(e^-s|x||g(x)|)

and
𝒞^n() (resp. 𝒞^0())
denotes n-times continuously differentiable (resp. continuous) functions.
Our main result (Theorem <ref> below) applies to the space 𝒮^1, 
containing functions f for which 
ρ(f):=∫_f(x)ρ(x) dx is typically of interest in applications (e.g. polynomials).  
In addition, spaces in (<ref>) are closed for solving Poisson's equation in (<ref>), see Proposition <ref> below. 

Throughout the paper 
ρ denotes a strictly positive density on  with log(ρ)∈𝒮^4 and 

    lim_|x|→∞x/|x|·log(ρ(x))'=-∞,
 
unless otherwise stated.
Assumption (<ref>) implies that the tails of ρ decay faster
then any exponential, i.e. 
𝔼[e^sX]<∞ 
for any s∈ for X∼ρ (cf. <cit.>). 
The assumption log(ρ)∈𝒮^4 prohibits ρ from
decaying to quickly, e.g. proportionally to e^-e^|x|. 
Both of these assumptions serve brevity and clarity of the proofs and it is feasible they can
be relaxed. Nevertheless, 
a large class of densities of interest satisfy these
assumptions, e.g. mixtures of Gaussian densities or any density
proportional to e^-p(x) for a positive polynomial p.

The scaling limit, introduced in <cit.>, 
of the chain 𝐗^d as the dimension d tends to infinity is key 
for all that follows. 
Consider a continuous-time process {U^d_t}_t≥0, given by U^d_t:=X^d_⌊ d· t⌋,1,
where ⌊·⌋ is the integer-part function
and 
X^d_·,1 is the first coordinate of 𝐗^d (since the proposal distribution for 
X^d_·,1
has variance  
l^2/d,  time needs to be accelerated to get a non-trivial limit). 
As shown in <cit.> (see also <cit.>), the weak convergence 
U^d⇒ U holds as d↑∞,
where U is the Langevin diffusion
started in stationarity, U_0∼ρ, with generator acting on f∈𝒞^2() as

    𝒢f:=(h(l)/2)(f”+(logρ)'f'),   where 
    h(l):=2l^2Φ(-l√(J)/2) and J:=ρ((log(ρ)')^2)

and Φ is the distribution of N(0,1).
Poisson's equation for U and a function f takes the form 

    𝒢f̂(x)
    =ρ(f)-f(x).

It is immediate that a solution f̂ of (<ref>) is given by the formula 

    f̂(x):=∫_0^x2dy/h(l)ρ(y)∫_-∞^yρ(z)(ρ(f)-f(z))dz,     x∈.

In the remainder of the paper
f̂ denotes the particular solution in (<ref>)
of the equation in (<ref>).  

As usual, for p∈[1,∞), f:^d→
is in L^p(ρ_d) if and only if f_p:=ρ_d(|f|^p)^1/p<∞.



Finally, note that under our assumptions on ρ, the kernel P_d of the RWM chain
𝐗^d defined above is a self-adjoint bounded operator on the Hilbert space
{g∈ L^2(ρ_d)ρ_d(g)=0} with norm 
λ_d<1 


If f∈𝒮^1, then f̂∈𝒮^3
and CLT (<ref>) holds for 
the function f+dP_df̂-df̂ and the RWM chain
𝐗^d introduced above. 
Furthermore, 
there exists a constant C_1>0, such that for all f∈𝒮^1 and d∈∖{1}, 
the asymptotic variance
σ̂^2_f,d
in CLT (<ref>)
satisfies:   

    σ̂^2_f,d≤ C_1 (∑_i=1^3f̂^(i)_∞,1/2)^2log(d)/(1-λ_d)d.



The proof of Theorem <ref> is given in Section <ref> below. 
It is based on the spectral-gap estimate of the asymptotic variance 
σ̂_f,d^2≤ 2𝒢_df̂-𝒢f̂^2_2/(1-λ_d) 
from <cit.>, the uniform ergodicity of the chain 
𝐗^d 
and the following proposition.


There exists a constant C_2  such that for every
f∈𝒮^3 and all d∈∖{1} we have:
𝒢f-𝒢_df_2≤
C_2(∑_i=1^3f^(i)_∞,1/2)√(log(d)/d).  


The proof of Proposition <ref>, given in Section <ref> below,
requires a pointwise control of the difference 𝒢f-𝒢_df on a large subset of ^d. 
To formulate this precisely, we need the following. 


A positive sequence a={a_d}_d∈ is sluggish if the following holds:

    lim_d→∞ a_d=∞  and  sup_d∈∖{1}a_d/√(logd)<∞.
 


Theorem <ref> below is the main technical result of the paper. 
It generalises the limit in <cit.> to a class of unbounded functions
and provides an error estimate for it. 
The bound in Theorem <ref> yields sufficient control of the difference 
𝒢f-𝒢_df to establish Proposition <ref>.


Let a={a_d}_d∈ be a sluggish sequence. There exist 
constants c_3,C_3>0 (dependent on a)
and measurable sets
𝒜_d⊂^d,
such that for all d∈ we have
ρ_d(^d∖𝒜_d)≤ c_3 e^-a_d^2
and 

    |𝒢f(x^d_1)-𝒢_df(𝐱^d)|≤
    C_3(∑_i=1^3f^(i)_∞,1/2) e^|x^d_1|a_d/√(d)    for any f∈𝒮^3 and 𝐱^d∈𝒜_d.



The proof of Theorem <ref>
is outlined and given in Sections <ref> and <ref> below, respectively.


The dependence on f in the bound of Theorem <ref> is not sharp. The factor
∑_i=1^3f^(i)_∞,1/2 
is used because it
states concisely that the speed of the convergence of
𝒢_df to 𝒢f depends linearly on the first three derivatives of
f.  
Moreover, it is not clear if 
the bound in Theorem <ref> and
Proposition <ref> is optimal in d. However, if an improvement were possible, the proof
would have to be significantly different to the one presented here. 
In particular, a better control of the difference
|𝒢f-𝒢_df| on ^d∖𝒜_d would be
required. 




§ DISCUSSION AND NUMERICAL EXAMPLES



 §.§ Discussion











In this section we discuss potential extensions of Theorem <ref> to settings satisfying weaker assumptions or involving related MCMC chains. 



  §.§.§ IID target for non-RWM chains in stationarity


Perhaps the most natural generalisation of Theorem <ref>
would be to the MALA and fast-MALA chains (in <cit.> and <cit.>) for which it is also possible to obtain non-trivial weak Langevin diffusion limits under appropriate scaling. Since the form of the Poisson equation in (<ref>) is preserved it is possible to define an estimator like the one in (<ref>) and it seems feasible that a version of Theorem <ref> can be established in this context using methods analogous to the ones in this paper.











  §.§.§ IID target in the transient phase for the RWM chain



















Theorem <ref> is a result only about the stationary behaviour of the chain. As in practice MCMC chains are typically started away from stationarity it is important to understand the transient behaviour. In <cit.>
it is shown that the scaling limit described in Section <ref> above
has mean-field behaviour of the McKean type, i.e. the limiting process is a continuous semimartingale with characteristics 
that at time t depend on the law of the process at t. 
This suggests that an appropriately chosen time-dependent function f̂ in 
the estimator in (<ref>) could further reduce the constant in the bound of Theorem <ref>.




  §.§.§ General product target density

The class of target distributions considered in <cit.>, 
preserves the independence (i.e. product) structure but allows for a different, dimension dependent, scaling of each of
the components of the target law. If the proposal variances appropriately reflect the scaling in the target, 
each component in the infinite dimensional limit is a Langevin diffusion. Again, as in Section <ref> above, the estimator in (<ref>) can be applied directly and an extension of 
Theorem <ref> to this setting appears feasible.







  §.§.§ Gaussian targets in high dimensions

Let π_0 denote a Gaussian target on ^d with mean μ and covariance matrix
diag(σ^2_11,…,σ^2_dd). Inspired by <cit.>
and the proof of Theorem <ref>, 
a good control variate for the ergodic average estimator for
π_0(f)
takes the form 
d(P_df̃-f̃), 
where f̃ solves the ODE

    f̃”+((∂/∂ x^d_1)logπ_0)f̃'=2/h_0(l)·(π_0(f)-f),

with h_0(l):=2l^2Φ(-l√(J_0)/2) and J_0:=1/d·∑_j=2^d1/σ^2_jj. 
In the case of the mean, f(x^d_1)=x^d_1, we can
solve the ODE explicitly: f̃(x^d_1)=2σ^2_11/h(l)· x^d_1.

If π_0 has a general non-degenerate covariance matrix Σ,
we have an ODE analogous to the one above for each eigen-direction of Σ. 
The control variate for the mean of the first coordinate,
f(x^d_1)=x^d_1, 
is then a linear combination of the 
control variates for the means in eigen-directions. 
Specifically, 
f̃:^d→
in the estimator analogous to the one in (<ref>)
(see the numerical example for h=0 in Section <ref>) takes the form 

    f̃(𝐱^d)=2/h_0(l) ·∑_j=1^dx^d_jΣ_j1,  with
     h_0(l)=2l^2Φ(-l√(J_0)/2)  and  J_0=1/d·Tr((Σ^-1)_2:d,2:d).

Note that 
f̃
does not depend on the mean of the target, a special feature of the
Gaussian setting.  






  §.§.§ Non-product target density


A typical non-product target density 
considered in the literature <cit.>
is a projection of a probability measure Π on a separable real Hilbert space ℋ
onto a d-dimensional subspace, where Π is given via its Radon-Nikodym derivative 
d Π/d Π_0(x)∝exp(-Ψ(x)). Here Ψ is a densely defined positive functional on 
ℋ
and  
Π_0
is a Gaussian measure on ℋ
specified via a positive trace-class operator on ℋ (see e.g. <cit.> for a detailed description
and <cit.> for the motivation for this class of measures).
A key feature of this framework is that there exists an ℋ-valued Langevin diffusion z, driven by a cylindrical Brownian motion
on ℋ (i.e. a solution of an SPDE), that describes the scaling limit of the appropriately accelerated sequence of chains 
(𝐗^d)_d∈, see <cit.>. 

An estimator analogous to the one in (<ref>)
would require the solution f̂ of the Poisson equation of z. 

While this might be a feasible strategy theoretically, it would likely be difficult to numerically evaluate the solution 
f̂. 
However, inspired by the Simplified Langevin Algorithm in <cit.>, which uses as the proposal chain 
an Euler scheme for the Langevin diffusion with target Π_0 (not Π), 
we suggest constructing the estimator 
for Π(f) in (<ref>),
with f̂ the solution of the Poisson equation for the Langevin diffusion converging to  
Π_0 (not Π).
This strategy is feasible 
as we are able to produce good control variates for Gaussian product targets
in high dimensions  in the spirit of Theorem <ref>,
see Section <ref> above.

The main theoretical question in this context is to find 
suitable assumptions on the functional Ψ in the Radon-Nikodym derivative above that guarantee the asymptotic variance 
reduction as d→∞. Expecting an improvement from polynomial to logarithmic growth is unrealistic as we
are solving the Poisson equation for Π_0 instead of Π. 
However, the numerical example in Section <ref> suggests that this idea may work in practice if Π is close from Gaussian Π_0. Understanding in which settings does it lead to significant variance reduction is another relevant and important question.



 §.§ Numerical examples







The basic message of the present paper is that the process in the scaling limit
of an MCMC algorithm contains useful information that can be utilised to achieve significant savings in 
high dimensions. 





In both examples presented below the problem is to estimate the mean of the
first coordinate ρ_d(f), where f(𝐱^d):=x^d_1. 
A run of T steps of a well-tuned RWM algorithm with kernel
P_d, defined in the beginning of Section <ref>,

started in stationarity, produces a RWM sample
{𝐗^d_n}_n=1,2,⋯ T and an estimate
ρ̂_d(f):=∑_n=1^Tf(𝐗^d_n)/T of ρ_d(f). Take f̃ to be the associated solution of the Poisson equation, that we obtain numerically in the first example <ref> and using formula (<ref>) in the second example <ref>. In both cases we estimate the required unknown quantities (ρ_d(f) and Σ) from the sample {𝐗^d_n}_n=1,2,⋯ T.

Using the same sample, 
define
ρ̃_d(f):=1/T∑_n=1^T(f+dP_df̃-df̃)(𝐗^d_n).
Since the function 
P_df̃-f̃
is not accessible in closed form,
for every n≤ T we use IID Monte Carlo to estimate the value
(P_df̃-f̃)(𝐗^d_n)  
as
∑_j=1^n_MC(1∧
(ρ_d(𝐘^d,j_n)/ρ_d(𝐗^d_n)))(f̃(𝐘^d,j_n)-f̃(𝐗^d_n))/n_MC,
where


𝐘^d,1_n,…,𝐘^d,n_MC_n is an IID sample 
of size n_MC from N(𝐗^d_n,l^2/d· I_d). This estimation step can be parallelised (i.e. run on n_MC cores simultaneously).

We measure the variance reduction due to the post processing above by comparing the mean 
square errors of ρ̂_d(f) and
ρ̃_d(f) as estimators of ρ_d(f) over n_R
independent runs of the RWM chain, 

    VR(ρ,f):=∑_k=1^n_R((ρ̂_d(f))_k-ρ_d(f))^2/∑_k=1^n_R((ρ̃_d(f))_k-ρ_d(f))^2,

where (ρ̂_d(f))_k and (ρ̃_d(f))_k are the averages in the k-th run of the chain. Heuristically, this means the estimator ρ̃_d(f) of ρ_d(f) based on T sample points is as good as estimator  ρ̂_d(f) based on VR(ρ,f)· T sample points.



  §.§.§ Multi-modal product target


To verify that what theory predicts also happens in practice we first present an example of an IID target with each coordinate a bimodal mixture of two Gaussian densities. Given the results in Table <ref>, we wish to highlight the robustness of the method with respect to numerically estimating f̃ and (P_df̃-f̃)(𝐗^d_n)  for each n≤ T.

Let ρ be a mixture of two normal densities 
N(μ_1,σ_1^2) and 
N(μ_2,σ_2^2), with the first arising in the mixture with probability 2/5
and
μ_1=-3, μ_2=4 and σ_1=σ_2=7/4. 
The potential of the density ρ has two wells and is in a well know
class arising in models of molecular dynamics, see e.g. <cit.>. 
Note that the corresponding density 
ρ_d on ^d, defined in the introduction, has 
2^d modes. 

With variance reduction (<ref>) we measure how much the estimator ρ̃_d(f) outperforms the estimator ρ̂_d(f) of the mean of the first coordinate ρ_d(f)=6/5. The results across a range of dimensions d and values of the parameter n_MC (that corresponds to the accuracy of the estimation of P_df̃-f̃) are presented in Table <ref>. All the entries were computed using n_R=500 independent runs of length T=2· 10^5.





To numerically solve the Poisson equation in (<ref>), substitute the
derivatives of f and log(ρ) with symmetric finite differences and use the estimate
ρ̂(f) for ρ(f). 
Recall that the standard deviation of the proposal in our RWM algorithm is
l/√(d).
The solver uses a grid of hundred points equally 
spaced 
in the interval 
[min_n≤ T 𝐗^d_n,1- 3 · l/√(d), max_n≤ T𝐗_n,1+3· l/√(d)],
where 𝐗^d_n,1 is the first coordinate of the n-th sample point. 
We use the Moore-Penrose pseudoinverse as the linear system is not of full rank. 
Finally, we take f̃ to be the linear interpolation of the solution on the grid.
Note that this is a crude approximation of the solution of (<ref>), which does not exploit
analytical properties of either f or ρ.

The results in Table <ref> contain a lot of noise due to numerically solving the ODE, using an approximation ρ̂_d(f) for ρ_d(f) and using IID Monte Carlo to estimate ρ̃_d(f). It is interesting to note, that despite these additional sources of error, the variance reduction is considerable and behaves as the theoretical results predict. The estimator ρ̃_d(f) improves with dimension, and with n_MC. Increasing n_MC, however, has diminishing effect which is particularly clear in the case d=5. Due to the asymptotic nature of our result we can only expect limited gain for any fixed d, even if P_df̃-f̃ could be evaluated exactly (corresponding to n_MC=∞).


























































  §.§.§ Bi-modal non-product target


Can the theoretical findings of this paper help us construct control variates in more realistic cases with non-product target densities? It is unreasonable to expect a simple general answer to this question. A more realistic approach for future work seems to be trying to establish specific forms of control variates that work well for classes of targets of certain type. We briefly explore one such instance in this section. Sections <ref> and <ref> as well as the results in Table <ref> suggest we can construct useful control variates when the target is close to a Gaussian. 

Let μ_d,h be a d-dimensional vector with entries (h/2,0,…,0) for h≥ 0 and let Σ^(d) be a d× d covariance matrix with the largest eigenvalue equal to λ=25 with the corresponding eigenvector being (1,1… 1) and all other eigenvalues being equal to one. 
Take Π_d,h to be the mixture of two d-dimensional normal densities 
N(-μ_d,h,Σ^(d)) and 
N(μ_d,h,Σ^(d)), both arising in the mixture with probability 1/2. 

We wish to estimate the mean of the first coordinate Π_d,h(f)=0 (for f(𝐱^d)=x^d_1). To produce a control variate we simply pretend, that we are dealing with a Gaussian target instead of Π_d,h. Let Σ^Π_d,h be the covariance of Π_d,h and Σ̂^Π_d,h an estimate of Σ^Π_d,h obtained from the RWM sample {X^d_n}_n=1,2,…,T. Define f̃_d,h as in (<ref>) using Σ̂^Π_d,h. We compare the performance of estimators Π̂_d,h(f) and Π̃_d,h(f) of  Π_d,h(f)=0, respectively defined as 1/T∑_n=1^Tf(X^d_n) and 1/T∑_n=1^T(f+dP_df̃_d,h-df̃_d,h)(X^d_n), according to variance reduction (<ref>).

Table <ref> shows the results across a range of dimensions d and distances between modes h, which measures the 'non-Gaussianity' of the target. Note that when h=0 the target is Gaussian N(0,Σ^(d)) which we include to demonstrate the validity of control variate (<ref>) for Gaussian targets. All the entries were calculated using n_R=500 independent runs of length T=2· 10^5 and n_MC=50 IID Monte Carlo steps for computing P_df̃-f̃ at each time step.



The quality of results decays with dimension because the proposal is scaled as 1/d in each coordinate. This results in the first coordinate mixing slower and for h≠ 0 also being less able to cross between modes, hence our estimate Σ̂^Π_d,h of the covariance becomes worse as we are working with fixed RWM sample length T. When h=10 (and some cases of h=8) it is unlikely that the RWM sample will reach the other mode at all which results in no gain from the method.

If we use the true covariance Σ^Π_d,h of the target in the control variate (<ref>), instead of learning it from the sample Σ̂^Π_d,h, the corresponding results for d=50 are presented in Table <ref>.



Unsurprisingly the estimator Π̃_d,h(f) does not perform well when the distance between modes h is large. Interestingly though, the method does offer considerable gain in cases h=2 and h=4, even a noticeable gain in h=6. For h=4 and h=6 the target is already clearly bimodal and different from the Gaussian, the RWM sample stays in the same mode for hundreds, respectively thousands of time-steps at a time.


























































§ PROOFS

Throughout this section we assume the sluggish sequence a={a_d}_d∈
is given and fixed and, as mentioned above, the density ρ satisfies log(ρ)∈𝒮^4
and has sub-exponential tails (<ref>).
Section <ref>
outlines the proof of Theorem <ref> by 
stating the sequence of results that are needed to establish it. 
The proofs of these results, given in Section <ref>, rely on the  
theory developed in Section <ref> below. 
Sections <ref> and <ref> establish 
Proposition <ref> and Theorem <ref>, respectively.



 §.§ Outline of the proof of Theorem <ref>



We start by specifying sets 𝒜_d⊂^d that have large probability under ρ_d. We need the following fact.


There exists a constant 
c_A>0, such that  
the following open subset of , 
A:={x∈; |log(ρ)”(x)|< (log(ρ)'(x))^2,1/c_A<|log(ρ)'(x)|< c_A},
satisfies ρ(A)>0.


Let A satisfy the conclusion of Proposition <ref> and 
recall the notation ρ(f)=∫_f(x)ρ(x) dx for any appropriate function f:→.
Recall
J=ρ(((logρ)')^2)=-ρ((logρ)”),
where the equality follows from assumptions log(ρ)∈𝒮^4 and (<ref>).
Define the sets 𝒜_d as follows.


Any 𝐱^d∈^d is in 𝒜_d 
if and only if 
the following four assumptions hold: 

    1/d-1∑_i=2^de^|x^d_i|< 2∫_ e^|x|ρ(x)dx,
          1/d-1∑_i=2^d1_A(x^d_i)> ρ(A)/2,
          1/d-1|∑_i=2^d (log(ρ)'(x^d_i))^2-J|<a_d/√(d)√(3∫_((log(ρ)'(x))^2-J)^2ρ(x)dx),
          1/d-1|∑_i=2^d log(ρ)”(x^d_i)+J|<a_d/√(d)√(3∫_(log(ρ)”(x)+J)^2ρ(x)dx).




The precise form of the constants in Definition <ref> is chosen purely for convenience.
It is important that ∫_ e^|x|ρ(x)dx<∞
by (<ref>), ρ(A)>0 by Proposition <ref> and that
the constants in (<ref>)–(<ref>) are in (0,∞).
Moreover, 
for any 𝐱^d∈𝒜_d
there are no restrictions on its first coordinate x_1^d 
and
the sets 𝒜_d are typical in the following sense. 



There exists a constant c_1, such that ρ_d(^d∖𝒜_d)≤ c_1 e^-a_d^2 for all d∈.

Using the theory of large deviations and classical inequalities,  
the proof of the proposition bounds the probabilities of sets where each of the above four assumptions 
in Definition <ref> fails 
(see Sections <ref>
and <ref> below for details).

Pick any f∈𝒮^3
and express the generator 𝒢_d, defined in (<ref>), 
 as follows: 

    𝒢_df(𝐱^d)=d·𝔼_Y^d_1[(f(𝐘^d)-f(𝐱^d))
    𝔼_𝐘^d-[1∧ρ_d(𝐘^d)/ρ_d(𝐱^d)]],
        𝐱^d∈^d,

where 
𝔼_𝐘^d-[·]
is the expectation with respect to all the coordinates of the proposal 
𝐘^d in ^d, except the first one 
(identify f∈ L^1(ρ) with f∈ L^1(ρ_d) by ignoring the last d-1 coordinates).
The strategy of the proof of Theorem <ref> is to define a
sequence of operators, “connecting” 𝒢_d and 𝒢,
such that each approximation can be controlled for f∈𝒮^3 and
𝐱^d∈𝒜_d.

First, for f∈𝒮^3, define 

    𝒢̃_df(𝐱^d):=d·𝔼_Y^d_1[(f(Y^d_1)-f(x^d_1))β(𝐱^d,Y^d_1)],    𝐱^d∈^d,

where for any y∈,

    β(𝐱^d, y):=𝔼_𝐘^d-[1∧exp(log(ρ)'(x^d_1)(y-x^d_1)+∑_i=2^d K(x^d_i, Y^d_i))],    𝐱^d∈^d,

and for any (x,y)∈^2 we define

    K(x, y):=log(ρ)'(x)(y-x)+log(ρ)”(x)/2(y-x)^2+(log(ρ)'(x))^31_A(x)/3(y-x)^3.


In (<ref>), the set A satisfies the conclusion of Proposition <ref>
and the coefficient before (y-x)^3 is chosen so that it is uniformly bounded 
for all x∈. This property plays an important role in proving that we have uniform control over the supremum norms of certain
densities, cf. Lemmas <ref> and <ref> below.
We can now prove the following.

 There exists a constant C, such that for every f∈𝒮^3 and all d∈ we have:

    |𝒢_df(𝐱^d)-𝒢̃_df(𝐱^d)|≤ C f'_∞,1/2 e^|x^d_1|d^-1/2  ∀𝐱^d∈𝒜_d.



The proof of Proposition <ref>
relies only on the elementary bounds from Section <ref> below. 
The idea is to use the Taylor series of log(ρ)(Y_i) around x^d_i for every i∈{1,…,d} 
and then prove 
that modifying terms of order higher then two if i∈{2,…,d}
(resp. one if i=1) is inconsequential.

Define the operator 
𝒢̂_df(𝐱^d) for any f∈𝒮^3 and 𝐱^d∈^d by

    𝒢̂_df(𝐱^d)   :=   l^2/2f”(x^d_1)𝔼_𝐘^d-[1∧
    e^∑_i=2^d K(x^d_i, Y^d_i)]
       +   l^2f'(x^d_1)log(ρ)'(x^d_1)𝔼_𝐘^d-[e^∑_i=2^d
    K(x^d_i, Y^d_i)1_{∑_i=2^d K(x^d_i,
    Y^d_i)<0}].

We can now prove the following fact.  


There exists a constant C, such that for every f∈𝒮^3, 
and all d∈ we have:

    |𝒢̂_df(𝐱^d)-𝒢̃_df(𝐱^d)|≤
    C(∑_i=1^3f^(i)_∞,1/2)e^|x^d_1|d^-1/2  ∀𝐱^d∈𝒜_d.
 


Note that, if we freeze the coordinates x_2^d,…,x_d^d in 𝐱^d,
the operator mapping f∈𝒮^3 to  
x_1^d↦𝒢̂_df(𝐱^d) 
generates a one-dimensional diffusion with coefficients of the same functional form as in 
𝒢, but with slightly modified parameter values. 
The proof of Proposition <ref> 
is based on the third and second degree Taylor's expansion of y↦ f(y)  and
 y↦β(𝐱^d,y) (around x^d_1), respectively, 
applied to the definition of 𝒢̃_d in (<ref>).
The difficult part in proving that the remainder terms can be omitted
consist of controlling
∂^2/∂ y^2β(𝐱^d,y), as this entails 
bounding the supremum norm of the density of ∑_i=2^d K(x^d_i, Y^d_i) uniformly in d. 
Condition (<ref>), which forces a portion of the coordinates x^d_i of
𝐱^d to be in the set A where the densities of the corresponding
summands K(x^d_i,Y^d_i) can be controlled, was introduced for this purpose. The details, explained in
Sections <ref> and <ref> below, rely crucially on the optimal version of Young's 
inequality.

Introduce the following 
normal random variable with mean
μ_𝒩(𝐱^d)=l^2/2d∑_i=2^dlog(ρ)”(x^d_i)
and variance
σ^2_𝒩(𝐱^d)=l^2/d∑_i=2^d(log(ρ)'(x^d_i))^2:

    𝒩(𝐱^d,𝐘^d):=l^2/2d∑_i=2^dlog(ρ)”(x^d_i)+∑_i=2^dlog(ρ)'(x^d_i)(Y^d_i-x^d_i).

Define the operator 
𝒢̆_df(𝐱^d)
for f∈𝒮^3 and
𝐱^d∈^d by: 

    𝒢̆_df(𝐱^d)   :=   l^2/2f”(x^d_1)𝔼_𝐘^d-[1∧ e^𝒩(𝐱^d,𝐘^d)]
       +   l^2f'(x^d_1)log(ρ)'(x^d_1)𝔼_𝐘^d-[e^𝒩(𝐱^d,𝐘^d)1_{𝒩(𝐱^d,𝐘^d)<0}].



There exists a constant C, such that for every f∈𝒮^3 and all d∈ we have:

    |𝒢̆_df(𝐱^d)-𝒢̂_df(𝐱^d)|≤ C(∑_i=1^2f^(i)_∞,1/2) e^|x^d_1|d^-1/2  ∀𝐱^d∈𝒜_d.



First we show that |𝔼_𝐘^d-[1∧ e^∑_i=2^d
K(x^d_i, Y^d_i)]-𝔼_𝐘^d-[1∧
e^𝒩(𝐱^d,𝐘^d)]| is small (Lemma <ref> below). 
Proving that 
𝔼_𝐘^d-[e^∑_i=2^d K(x^d_i,
Y^d_i)1_{∑_i=2^d K(x^d_i, Y^d_i)<0}] and
𝔼_𝐘^d-[e^𝒩(𝐱^d,𝐘^d)1_{𝒩(𝐱^d,𝐘^d)<0}]
are close is challenging, as it requires showing that the supremum norm of the difference
between the distributions of 𝒩(𝐱^d,𝐘^d)
and ∑_i=2^d K(x^d_i, Y^d_i) decays as d^-1/2 uniformly in its argument. 
The proof of this fact mimics the proof of the Berry-Esseen theorem and relies on the closeness of the
CFs (characteristic functions) of 𝒩(𝐱^d,𝐘^d) and
∑_i=2^d K(x^d_i, Y^d_i). The particular form of K(x,Y) makes it
possible to explicitly calculate the CF of K(x,Y), if x∉ A, and bound
it appropriately, if x∈ A. The details are explained
in Sections <ref> and <ref> below.

Since 𝒩(𝐱^d,𝐘^d) is normal,  it is
possible to explicitly calculate the expectations
𝔼_𝐘^d-[1∧ e^𝒩(𝐱^d,𝐘^d)] and
𝔼_𝐘^d-[e^𝒩(𝐱^d,𝐘^d)1_{𝒩(𝐱^d,𝐘^d)<0}],
see <cit.>.
Using these formulae, 
Proposition <ref>, which implies Theorem <ref>,
can be deduced from  assumptions (<ref>)–(<ref>). 


There exists a constant C, such that for every f∈𝒮^3 and all d∈ we have:

    |𝒢f(x^d_1)-𝒢̆_df(𝐱^d)|≤ C(∑_i=1^2f^(i)_∞,1/2)  e^|x^d_1|a_d/√(d)  ∀𝐱^d∈𝒜_d.




The bounds in Propositions <ref>–<ref> 
are of the order Ø(d^-1/2). The order  Ø(a_d/√(d)) of the bound in Proposition <ref> 
gives the order in the bound of Theorem <ref>.




 §.§ Proof of Theorem <ref>


Let Ã:={ x∈;|log(ρ)”(x)|< (log(ρ)'(x))^2}.
It suffices to show that the open set Ã
is not empty, since 
Ã=∪_n∈(Ã∩{x∈; 1/n< |log(ρ)'(x)|<n}),
so for some large n_0 the open set 
Ã∩{x∈; 1/n_0<|log(ρ)'(x)|< n_0} must have positive Lebesgue measure and we can take c_A:=n_0.

Assume that Ã=∅, i.e. 
|u'|≥ u^2 
on
, 
where
u:=log(ρ)'.
Since ρ satisfies (<ref>),
there exists x_0<0 and C>0 such that u>C 
on the interval (-∞,x_0). Moreover,  since
|u'|≥ u^2>C^2>0,
u' has no zeros on (-∞,x_0) and satisfies
either
u'≥ u^2  or -u'≥ u^2
on the half-infinite interval. 
Since (1/u)'=-u'/u^2, integrating the inequalities
-u'/u^2≤ -1  or -u'/u^2≥1 from  any
x∈(-∞,x_0) to x_0,
we get
1/u(x_0)+x_0-x≤ 1/u(x)
and 
1/u(x_0)+x-x_0≥ 1/u(x).
Since by assumption it holds
0<1/u<1/C
on (-∞,x_0), we get a contradiction in both cases. 



Let B^d_1, B^d_2, B^d_3 and B^d_4 be the subsets of
^d where assumptions (<ref>), (<ref>),
(<ref>) and (<ref>) are not satisfied, respectively. Note that
^d∖𝒜_d=B^d_1∪ B^d_2∪ B^d_3 ∪ B^d_4.

Recall that by (<ref>), the L'Hospital's rule implies lim_|x|→∞logρ(x)/x→-∞ and hence
ρ(e^s|x|)<∞ for any s>0.
Since {a_d}_d∈ is sluggish, there exists 
n∈
such that 
a_d≤√(nlog d) for all d∈.
Then, by Proposition <ref> applied to 
functions x↦ (e^|x|-ρ(e^|x|))/ρ(e^|x|) and x↦ 2(ρ(A)-1_A(x))/ρ(A), respectively,
there
exist constants c_1', c_2' such that the inequalities 
ρ(B^d_1)≤ c_1'd^-n≤ c_1'e^-a_d^2 and ρ(B^d_2)≤ c_2'd^-n≤ c_2'e^-a_d^2 hold for all d∈. 

Likewise, there exist constants c_3', c_4' such that ρ(B^d_3)≤ c_3'
e^-a^2_d and ρ(B^d_4)≤ c_4' e^-a^2_d. This follows by
Proposition <ref>, applied to the sequence
{a_d}_d∈ and functions g_3(x):=(log(ρ)'(x))^2-J (with
t:=√(3ρ(g_3^2)))
and g_4(x):=log(ρ)”(x)+J (with
t:=√(3ρ(g_4^2))), respectively.
Hence
ρ(^d∖𝒜_d)≤ρ(B^d_1)+ρ(B^d_2)+ρ(B^d_3 )+ρ(B^d_4)≤
c_1 e^-a_d^2 for c_1:=max{c_1',c_2',c_3',c_4'}.  



The proof above shows that 
the subsets B^d_1 and B^d_2 are of negligible
size in comparison to B^d_3 and B^d_4, since the n∈ can be chosen arbitrarily large.




Pick an arbitrary 𝐱^d∈𝒜_d
and recall that α(𝐱^d,𝐘^d) is defined in (<ref>). 
Since |1∧ e^x-1∧ e^y|≤ |x-y| for all x,y∈, 
for every realization Y^d_1,
Taylor's theorem implies 

    |𝔼_𝐘^d-[α(𝐱^d,𝐘^d)]-β(𝐱^d,
    Y^d_1)|≤
    |log(ρ)”(W^d_1)|(Y^d_1-x^d_1)^2+T^d_1(𝐱^d)+T^d_2(𝐱^d),

where W^d_1 satisfies  
log(ρ)”(W^d_1)(Y^d_1-x^d_1)^2/2=log(ρ)(Y^d_1)-log(ρ)(x^d_1)-logρ'(x^d_1)(Y^d_1-x^d_1)
and

    T^d_1(𝐱^d)   :=   1/6𝔼_𝐘^d-[|∑_i=2^d(log(ρ)”'(x^d_i)-2(log(ρ)'(x^d_i))^31_A(x^d_i))(Y_i-x^d_i)^3|],
    
    T^d_2(𝐱^d)   :=   1/24𝔼_𝐘^d-[∑_i=2^d|log(ρ)^(4)(Z^d_i)|(Y_i-x^d_i)^4].

Here Z^d_i satisfies 
log(ρ)^(4)(Z^d_i)(Y^d_i-x^d_i)^4/4!=log(ρ)(Y^d_i)-∑_j=0^3(logρ)^(j)(x^d_i)(Y^d_i-x^d_i)^j/j!
for any 2≤ i≤ d.  
Recall Y^d_i-x^d_i is normal N(0,l^2/d), for some constant l>0,
and
log(ρ)∈𝒮^4. 
Hence we may apply 
Proposition <ref> to the function 
x↦log(ρ)”'(x)-2(log(ρ)'(x))^31_A(x) 
to get
T^d_1(𝐱^d)≤ C_1 (l^6/d^3∑_i=2^d e^|x^d_i|)^1/2 
for some constant 
C_1>0, independent of 𝐱^d.
Since 𝐱^d∈𝒜_d, 
the assumption in (<ref>) yields  
T^d_1(𝐱^d)≤ C_1 l^3 (2ρ(e^|x|))^1/2/d. 
Similarly, we apply Proposition <ref> 
(with f=logρ, n=k=4, m=1, s=1 and σ^2=l^2/d) and assumption (<ref>) 
to get T^d_2(𝐱^d)≤ C_2 d^-2∑_i=2^de^|x^d_i|≤ C_2 d^-1 for some constant
C_2>0 and all 𝐱^d∈𝒜_d.

Recall f∈𝒮^3 and let
W̃^d_1 be as in Proposition <ref>, satisfying
f'(W̃^d_1)(Y^d_1-x^d_1)=f(Y^d_1)-f(x^d_1).
Let C>0 be such that T^d_1(𝐱^d)+T^d_2(𝐱^d)≤ Cd^-1 for all 𝐱^d∈𝒜_d.
The bound in (<ref>),
Taylor's theorem applied to f and Cauchy's inequality yield:  

    |𝒢_df(𝐱^d)-𝒢̃_df(𝐱^d)|≤ d 𝔼_Y^d_1[|f(Y^d_1)-f(x^d_1)|
    (|log(ρ)”(W^d_1)|(Y^d_1-x^d_1)^2+Cd^-1)]
          =d𝔼_Y^d_1[|f'(W̃^d_1)log(ρ)”(W^d_1)(Y^d_1-x^d_1)^3|]+C𝔼_Y^d_1[|f'(W̃^d_1)(Y^d_1-x^d_1)|]
          ≤ d(𝔼_Y^d_1[|f'(W̃^d_1)^2(Y^d_1-x^d_1)^3|]𝔼_Y^d_1[|(log(ρ)”)^2(W^d_1)(Y^d_1-x^d_1)^3|])^1/2
             +C𝔼_Y^d_1[|f'(W̃^d_1)(Y^d_1-x^d_1)|]≤C̅ d(f'_∞,1/2^2 e^|x_1^d| d^-3/2·  e^|x_1^d|d^-3/2)^1/2 + C̅f'_∞,1/2e^|x_1^d| d^-1/2.

The last inequality follows by three applications of 
Proposition <ref>, where C̅>0 is a constant that does not depend on 
f 
or
𝐱^d∈𝒜_d.  
This concludes the proof of the proposition. 


Before tackling the proof of
Proposition <ref>, we need the following three lemmas.
Recall that 
K(x,Y) is defined in (<ref>)
and the set A satisfies the conclusion of Proposition <ref>.


Pick x∈ A and let Y∼ N(x,l^2/d) for some constant l>0. Then K(x,Y)
has a density q_x satisfying q_x_∞≤ 4c_A√(d)/(3l√(2π)).  



 
Existence of q_x follows from (<ref>) and Proposition <ref>.
By Proposition <ref> we have
|log(ρ)”(x)|<(log(ρ)'(x))^2 and
c_A>|log(ρ)'(x)|>1/c_A. Consider the 
polynomial
y↦ p(y):=log(ρ)'(x)y+log(ρ)”(x)y^2/2+(log(ρ)'(x))^3y^3/3.
By (<ref>) it holds p(Y-x)=K(x,Y).
Since 
p'(y)=log(ρ)”(x)y+log(ρ)'(x)(1+log(ρ)'(x)^2y^2),
we have

    |p'(y)|
       ≥   |log(ρ)'(x)|(1+log(ρ)'(x)^2y^2) -|log(ρ)”(x)||y|
       >   |log(ρ)'(x)|(1-|log(ρ)'(x)y|+|log(ρ)'(x)y|^2)> 3/4c_A,

where 
the second inequality holds since 
|log(ρ)”(x)|<(log(ρ)'(x))^2
and the third follows from  inf_z∈{1-|z|+z^2}=3/4
and |log(ρ)'(x)|>1/c_A.
The lemma now follows by Proposition <ref>.  


Recall that the proposal is normal 𝐘^d=(Y_1^d,…,Y_d^d)∼ N(𝐱^d,l^2/d· I_d).


For any 𝐱^d∈𝒜_d, the sum 
∑_k=2^dK(x_i^d,Y_i^d) possesses a density 𝐪^d_𝐱^d. 
Moreover, there exists a constant C_K such that 𝐪^d_𝐱^d_∞≤
C_K holds for all d∈ and all 𝐱^d∈𝒜_d.



Fix 𝐱^d∈𝒜_d and, for each i, let q_i denote the density of
K(x^d_i,Y^d_i) as in the previous lemma. 
Since the components of 
𝐘^d
are IID, 
we have 𝐪^d_𝐱^d=_i=2^d q_i=q_A  q_∖ A,
where
q_A:= _x^d_i∈ Aq_i
and
q_∖ A:=_x^d_i∉ Aq_i.
By the definition of convolution and the fact that 
q_∖ A is a density, 
it follows that 
𝐪^d_𝐱^d_∞≤q_A_∞q_∖ A_1=q_A_∞.
By Lemma <ref> 
there exists C>0 such that,   
for any d∈,
it holds 
q_i_∞<C√(d) if x^d_i∈ A.
Condition (<ref>) implies there are at least 
(d-1)ρ(A)/2 
factors in the convolution q_A=_x^d_i∈ Aq_i. Hence
Proposition <ref> applied to q_A yields
𝐪^d_𝐱^d_∞≤q_A_∞≤ c  C√(d)/√((d-1)ρ(A)/2).
This concludes the proof of the lemma. 



Let 𝐱^d∈𝒜_d. The function y↦β(𝐱^d,y), defined in (<ref>), 
is in 𝒞^2() and the following holds:  


  * 0<β(𝐱^d,y)≤1 for all y∈;

  * β(𝐱^d,x^d_1)=𝔼_𝐘^d-[1∧ e^∑_i=2^dK(x^d_i,Y^d_i)];

  * |∂/∂ yβ(𝐱^d,y)|≤|log(ρ)'(x^d_1)| for all y∈;

  * ∂/∂ yβ(𝐱^d,x^d_1)=log(ρ)'(x^d_1)𝔼_𝐘^d-[e^∑_i=2^dK(x^d_i,Y^d_i)1_{∑_i=2^dK(x^d_i,Y^d_i)<0}];

  * |∂^2/∂ y^2β(𝐱^d,y)|≤|log(ρ)'(x^d_1)|^2(C_K+1) for all y∈ and constant C_K from Lemma <ref>.



 (i) and (ii) follow from the definition in (<ref>). 
Since x↦ 1∧ e^x is Lipschitz (with Lipschitz constant 1) on , 
the family of functions {x↦ (1∧ e^x+h- 1∧ e^x)/h; h∈∖{0}}
is bounded by one and converges pointwise to 1_{x<0}e^x for all x∈∖{0},
as h→0.
Hence the DCT implies that 
∂/∂ yβ(𝐱^d,y) 
exists and can be expressed as 

    log(ρ)'(x^d_1)𝔼_𝐘^d-[e^log(ρ)'(x^d_1)(y-x^d_1)
    +∑_i=2^dK(x^d_i,Y^d_i)1_{log(ρ)'(x^d_1)(y-x^d_1)+∑_i=2^dK(x^d_i,Y^d_i)<0}],

implying (iii) and (iv). 
Let Φ^d_K denote the distribution of ∑_i=2^dK(x^d_i,Y^d_i)
and recall that by definition we have e^x 1_{x<0} = 1∧ e^x - 1_{x≥ 0} for all x∈.
Hence, by (<ref>), it follows 

    ∂/∂ yβ(𝐱^d,y)     =    log(ρ)'(x^d_1)(β(𝐱^d,y)-1+Φ^d_K(-log(ρ)'(x^d_1)(y-x^d_1))),

By Lemma <ref>, Φ_K^d is differentiable. Hence, by (<ref>), 
∂^2/∂ y^2β(𝐱^d,y) also exists and takes the form: 

    (log(ρ)'(x^d_1))^2(β(𝐱^d,y)-1
    +Φ^d_K(-log(ρ)'(x^d_1)(y-x^d_1))-𝐪^d_𝐱^d(-log(ρ)'(x^d_1)(y-x^d_1))).

Part (v) follows from this representation of ∂^2/∂ y^2β(𝐱^d,y)
and Lemma <ref>.



Fix an arbitrary 𝐱^d∈𝒜_d. 
Let 
Z_1,W_1 be random variables, as in
Proposition <ref>,
that satisfy

    f(Y^d_1)-f(x^d_1)     =     f'(x^d_1)(Y^d_1-x^d_1)+f”(x^d_1)/2(Y^d_1-x^d_1)^2+f”'(Z_1)/6(Y^d_1-x^d_1)^3, 
    β(𝐱^d,Y^d_1)     =    β(𝐱^d,x^d_1)+∂/∂
    yβ(𝐱^d,x^d_1)(Y^d_1-x^d_1)+∂^2/∂
    y^2β(𝐱^d,W_1)/2(Y^d_1-x^d_1)^2.

Then, by the definition of 
𝒢̃_df(𝐱^d)
in (<ref>) and the fact Y_1^d-x_1^d∼ N(0,l^2/d), we find 

    𝒢̃_df(𝐱^d)   =   l^2f”(x^d_1)/2β(𝐱^d,x^d_1)+l^2f'(x^d_j)∂/∂ yβ(𝐱^d,x^d_1)
       +   d𝔼_Y^d_1[(β(𝐱^d,x^d_1)f”'(Z_1)/6+f'(x^d_1)∂^2/∂ y^2β(𝐱^d,W_1)/2)(Y^d_1-x^d_1)^3]
       +   d𝔼_Y^d_1[(f”(x^d_1)/2∂^2/∂ y^2β(𝐱^d,W_1)/2+f”'(Z_1)/6∂/∂ yβ(𝐱^d,x^d_1))(Y^d_1-x^d_1)^4]
       +   d𝔼_Y^d_1[f”'(Z_1)/6∂^2/∂ y^2β(𝐱^d,W_1)/2(Y^d_1-x^d_1)^5].

By parts (ii) and (iv) in Lemma <ref>
and the definition of 𝒢̂_df(𝐱^d) in (<ref>)
we have
𝒢̂_df(𝐱^d)=
l^2f”(x^d_1)/2β(𝐱^d,x^d_1)+l^2f'(x^d_j)∂/∂ yβ(𝐱^d,x^d_1). 
The three expectations in the display above can each be bounded
by a constant times (∑_i=1^3f^(i)_∞,1/2)e^|x^d_1|d^-1/2 using
Proposition <ref> and Lemma <ref>.
For instance, the first expectation can be bounded above using 
(v) in Lemma <ref>: 

    d/6𝔼_Y^d_1[|f”'(Z_1)||Y^d_1-x^d_1|^3]+d(C_K+1)/2|f'(x^d_1)||log(ρ'(x^d_1))|^2𝔼_Y^d_1[|Y^d_1-x^d_1|^3].

Proposition <ref> yields 
d/6𝔼_Y^d_1[|f”'(Z_1)||Y^d_1-x^d_1|^3]
≤ C_0 e^|x^d_1|f”'_∞,1 d^-1/2≤ C_0 e^|x^d_1|f”'_∞,1/2 d^-1/2 for some C_0>0. 
Moreover, |f'(x^d_1)||log(ρ'(x^d_1))|^2≤f'_∞,1/2(log(ρ)')^2_∞,1/2e^|x^d_1|
as log(ρ)∈𝒮^4 and f∈𝒮^3.
Hence
d(C_K+1)/2|f'(x^d_1)||log(ρ'(x^d_1))|^2𝔼_Y^d_1[|Y^d_1-x^d_1|^3]
≤ C_1 e^|x^d_1|f'_∞,1/2 d^-1/2
for some C_1>0. 
Similarly, it follows that the second and third expectations above decay as d^-1 and d^-3/2, respectively.
This concludes the proof of the proposition. 



Recall that 𝒩(𝐱^d,𝐘^d) and ∑_i=2^dK(x^d_i,Y^d_i)
are defined in (<ref>) and (<ref>), respectively. Then there
exists a constant C such that for all d∈ we have:

    𝔼_𝐘^d-[|∑_i=2^dK(x^d_i,Y^d_i)-𝒩(𝐱^d,𝐘^d)|]≤
    Cd^-1/2  ∀𝐱^d∈𝒜_d.
 



The difference in question is smaller than the sum of the following two terms:

    T^d_3(𝐱^d)   =   𝔼_𝐘^d-[|∑_i=2^dlog(ρ)”(x^d_i)/2((Y^d_i-x^d_i)^2-l^2/d)|],
    
    T^d_4(𝐱^d)   =   𝔼_𝐘^d-[|∑_i=2^d(log(ρ)'(x^d_i))^31_A(x^d_i)/3(Y^d_i-x^d_i)^3|].

Note that X_i:=(Y^d_i-x^d_i)^2-l^2/d, 2≤ i≤ d, are zero mean IID with 𝔼[X_i^4] = 2l^4/d^2.
Hence, as log(ρ)∈𝒮^4, we may apply
Proposition <ref> with the function x↦log(ρ)”(x) 
and X_i,2≤ i≤ d,  
to get 
T^d_3(𝐱^d)≤log(ρ)”_∞,1/2(2(l^4/d^2)∑_i=2^d e^|x^d_i|)^1/2≤ C_0 d^-1/2 for some
constant
C_0>0,
where the second inequality follows from (<ref>). 
Similarly,
Proposition <ref> and assumption (<ref>), applied to 
the function x↦ (log(ρ)'(x))^31_A(x) and random variables
Y^d_i-x^d_i, yield T^d_4(𝐱^d)≤ C_1 (∑_i=2^d
e^|x^d_i|/d^3)^1/2≤ C_2 d^-1 for some constants C_1,C_2>0 and all d∈. 



There exist constants c_1,c'_1>0, such that
for any d∈, i∈{2,⋯,d}, 𝐱^d∈𝒜_d and  x^d_i∉ A,
it holds 

    |logφ_i(t)-(il^2/2dlog(ρ)”(x^d_i)t-l^2/2d(log(ρ)'(x^d_i))^2t^2)|≤c_1/d^3/2(t^2+|t|^3),   |t|≤ c'_1√(d),

where
φ_i(t):=𝔼_Y_i^d[exp(itK(x^d_i,Y^d_i))], t∈, is the CF of K(x^d_i,Y^d_i)
(cf. (<ref>)).



Recall that the set A satisfies the conclusion of Proposition <ref>. 
The proof of 
Lemma <ref> requires the control of the functions log(ρ)' and log(ρ)”
on the complement of A, where they are unbounded. It is hence crucial that their argument x_i^d is 
the i-th coordinate of a point 𝐱^d∈𝒜_d, 
since, through assumption (<ref>),
we have control over the size of x_i^d in terms of the dimension d of the chain. 
For an analogous reason we need i>1. These facts plays a key role in the proof. 



By Lemma <ref>,
the following inequality holds for all |t|≤ d/(4l^2|log(ρ)”(x^d_i)|):

    |logφ_i(t)-(il^2/2dlog(ρ)”(x^d_i)t-l^2/2d(log(ρ)'(x^d_i))^2t^2)|
    ≤l^4/d^2(1/2(log(ρ)”(x^d_i))^2t^2+(log(ρ)'(x^d_i))^2|log(ρ)”(x^d_i)||t|^3),

Since 𝐱^d∈𝒜_d and i>1,
assumption (<ref>)
implies that 
for any 
f∈𝒮^0 there exists C_f>0 such that 
|f(x^d_i)|^2/C_f≤ e^|x^d_i|≤∑_i=2^de^|x^d_i|≤ 2dρ(e^|x|). 
Hence
|f(x^d_i)|≤ c_f √(d) for all d∈ and all 2≤ i≤ d, where c_f:=(2C_fρ(e^|x|))^1/2.
Since log(ρ)∈𝒮^4, both functions f_1(x):=l^4(log(ρ)”(x))^2/2 
and 
f_2(x):=(log(ρ)'(x))^2|log(ρ)”(x)| 
are in 𝒮^0. 
Then (<ref>) and the constants c_1:=max{c_f_1,c_f_2} 
and c_1':=1/(4√(2c_f_1)) yield the inequalities in the lemma. 


We now deal with the coordinates of 𝒜_d that are in A. Compared to 
Lemma <ref>,
this is straightforward as it does not involve the remainder of the coordinates 
of the point in 𝒜_d. 


If x∈ A, then K(x,Y) (cf. (<ref>)), where Y∼ N(x,l^2/d), satisfies: 


  * μ_K:=𝔼_Y[K(x,Y)]≤l^2c_A^2/2d, where c_A>0 is the constant in Proposition <ref>;

  * |𝔼_Y[(K(x,Y)-μ_K)^2]- (log(ρ)'(x))^2l^2/d| ≤ C_1 d^-2 for some 
constant C_1>0 and all d∈;

  * 𝔼_Y[|K(x,Y)-μ_K|^3]≤ C_2d^-3/2 for some
constant C_2>0 and all d∈.

Moreover, the constants C_1 and C_2 do not depend on the choice of x∈ A.



By definition of A in Proposition <ref> we have
|log(ρ)'(x)|≤ c_A and |log(ρ)”(x)|≤
c^2_A for x∈ A. 
By (<ref>),
μ_K=l^2/2dlog(ρ)”(x) and (a) follows.
Recall 𝔼_Y[(Y-x)^n] is either zero (if n is odd) or of order d^-n/2 (if n is even)
and 𝔼_Y[(Y-x)^2]=l^2/d. Hence the definition of K in (<ref>), the fact x∈ A and part (a) imply the inequality in 
part (b). For part (c), note that an analogous argument yields
𝔼_Y[(K(x,Y)-μ_K)^6]≤ C'd^-3 for some constant C'>0. Cauchy's inequality concludes the proof of the lemma. 



Let assumptions of Lemma <ref> hold 
and denote by φ the characteristic function of K(x,Y).  
There exist positive constants c_2 and c'_2, such that the following holds for all x∈ A:

    |logφ(t)-(itl^2/2dlog(ρ)”(x)-t^2l^2/2dlog(ρ)'(x)^2)|≤
    c_2(t^2/d^2+|t|^3/d^3/2+t^4/d^2),  
    |t|≤ c'_2√(d).




Let σ^2_K:=𝔼_Y[(K(x,Y)-μ_K)^2] and recall μ_K=l^2/2dlog(ρ)”(x). 
By Lemma <ref> we have

    |logφ(t)-(itl^2/2dlog(ρ)”(x)-t^2/2σ^2_K)|
    ≤|t|^3𝔼_Y|K(x,Y)-μ_K|^3/6+t^4σ^4_K/4,   |t|≤1/σ_K.

By  Lemma <ref>(b) we  have 
|σ^2_K-l^2log(ρ)'(x)^2/d|≤ C_1d^-2.
Hence 
σ^2_K≤ d^-1/√(c_2'),
where
c_2':= 1/(l^2c_A^2+ C_1)^2,
and
σ^4_K≤ C_1'd^-2 for some C_1'>0.
This, together with Lemma <ref>(c), implies that there exists  a constant c_2>0, 
such that the inequality in (<ref>) follows from (<ref>)
for all |t|≤ c_2' d^1/2≤ 1/σ_K and x∈ A. 



For any d∈ and 𝐱^d∈𝒜_d, let  Φ^d_K and
Φ^d_𝒩 be the distribution functions of ∑_i=2^dK(x^d_i,Y^d_i) and
𝒩(𝐱^d,𝐘^d). Then there exists C>0 such
that   

    sup_x∈|Φ^d_𝒩(x)-Φ^d_K(x)|≤ C
    d^-1/2    for every d∈ and 𝐱^d∈𝒜_d.




Let φ_K and φ_𝒩  be the CFs of
∑_i=2^dK(x^d_i,Y^d_i) and 𝒩(𝐱^d,𝐘^d), respectively. 
We will compare φ_K and φ_𝒩   
and apply Proposition <ref> to establish the lemma. 
Let φ_i be the CF of K(x^d_i,Y^d_i) and recall, by (<ref>), 
φ_𝒩(t)=exp(1/2itl^2/d∑_i=2^dlog(ρ)”(x^d_i)-1/2t^2l^2/d∑_i=2^d(log(ρ)'(x^d_i))^2).
Define the positive constants
c:=max{c_1,c_2} and c':=min{1,l^2J/(32c),c'_1,c'_2}, where 
the constants c_1,c_1' (resp. c_2,c_2') are given in Lemma <ref> 
(resp. Lemma <ref>) and J is as in assumption (<ref>). 
Note that the constants c,c' do not depend on the choice of 𝐱^d∈𝒜_d.
Lemmas <ref> and <ref> imply the following inequality 
for all d∈ and 
𝐱^d∈𝒜_d:

    |logφ_K(t)-logφ_𝒩(t)|≤∑_i=2^d|logφ_i(t)-(itl^2/2dlog(ρ)”(x^d_i)-t^2l^2/2d(log(ρ)(x^d_i)^2)| ≤
    R(t),

for all |t|≤ r, where r:= c'√(d)
and
R(t):= c(t^2+|t|^3+t^4/√(d))/√(d).
Since |t|^3≤√(d)c't^2 and t^4≤ dc'^2t^2 for 
|t|≤ r,
we have 

    R(t)≤ t^2(c/√(d)+cc'+cc'^2) ≤ t^2 (c/√(d)+2cc')    for all t∈[-r,r].


By assumption (<ref>), there exists d_0'∈ such that 
the variance 
σ^2_𝒩(𝐱^d)=l^2/d∑_i=2^d(log(ρ)'(x^d_i))^2
of 
𝒩(𝐱^d,𝐘^d) 
satisfies σ^2_𝒩(𝐱^d)≥ l^2J/2 for all 
d≥ d_0' and  𝐱^d∈𝒜_d. 
Let γ:=1/2 and pick 
d_0∈, greater than 
max{d_0',(16cl^-2/J)^2}.
Then, for any d≥ d_0, the inequality c/√(d)≤γ l^2J/8 holds.
Since c'≤ l^2J/(32c), we have 
2cc'≤γ l^2J/8, 
and the bound in (<ref>) implies
R(t)≤1/2t^2 γ l^2J/2
≤1/2t^2 γσ^2_𝒩(𝐱^d)
for all t∈[-r,r].
By Proposition <ref>, 
for all d≥ d_0,
sup_x∈|Φ^d_𝒩(x)-Φ^d_K(x)| is bounded above 
by

    ∫_R(t)/π |t|exp(-(1-γ)σ^2_𝒩(𝐱^d)t^2/2)dt
    +12√(2)/π^3/2σ_𝒩(𝐱^d) r≤ C'/√(d),

where
C':= c∫_(|t|+t^2+|t|^3)exp(-l^2Jt^2/8)dt
+ 24√(2)/π^3/2l^2Jc'.
Since the left-hand side of the inequality in the lemma is bounded above by 1,
the inequality holds for all d∈ if we define 
C:=max{C',√(d_0)}. 



Since |1∧ e^y- 1∧ e^x|≤ |x-y| for all x,y∈, by Lemma <ref> we have 

    |𝔼_𝐘^d-[1∧
    e^𝒩(𝐱^d,𝐘^d)]-𝔼_𝐘^d-[1∧
    e^∑_i=2^dK(x^d_i,Y^d_i)]|≤ C' d^-1/2

for some constant C'>0 and all d∈.
Recall
e^x 1_{x<0} = 1∧ e^x - 1 + 1_{x≤ 0} for all x∈∖{0}.
Hence Lemmas <ref> and <ref> yield

    |𝔼_𝐘^d-[e^𝒩(𝐱^d,𝐘^d)1_{𝒩(𝐱^d,𝐘^d)<0}]-𝔼_𝐘^d-[e^∑_i=2^dK(x^d_i,Y^d_i)1_{∑_i=2^dK(x^d_i,Y^d_i)<0}]|
    ≤|𝔼_𝐘^d-[1∧
    e^𝒩(𝐱^d,𝐘^d)]-𝔼_𝐘^d-[1∧
    e^∑_i=2^dK(x^d_i,Y^d_i)]|+|Φ^d_𝒩(0)-Φ^d_K(0)|≤
    C” d^-1/2

for some C”>0 and all d∈. The proposition follows. 



For any 𝐱^d∈𝒜_d, by <cit.>, we have

    𝔼_𝐘^d-[e^𝒩(𝐱^d,𝐘^d)1_{𝒩(𝐱^d,𝐘^d)<0}]=e^μ_𝒩(𝐱^d)+σ^2_𝒩(𝐱^d)/2Φ(-σ_𝒩(𝐱^d)-μ_𝒩(𝐱^d)/σ_𝒩(𝐱^d)),
          𝔼_𝐘^d-[1∧ e^𝒩(𝐱^d,𝐘^d)]=
    𝔼_𝐘^d-[e^𝒩(𝐱^d,𝐘^d)1_{𝒩(𝐱^d,𝐘^d)<0}]
    +
    Φ(μ_𝒩(𝐱^d)/σ_𝒩(𝐱^d)).

where Φ is the distribution of a standard normal random variable.
Note first that it is sufficient to prove the inequality in the proposition for all d> d_0 for some d_0∈,
since the expectations above are bounded by 1 and we can hence increase the constant C so that 
the first d_0 inequalities are also satisfied. 

Recall the formulas for μ_𝒩(𝐱^d) and
σ^2_𝒩(𝐱^d) from (<ref>). By assumptions (<ref>) and (<ref>) it follows that 
|μ_𝒩(𝐱^d)+σ^2_𝒩(𝐱^d)/2|≤ c a_d/√(d) for some constant c>0 
and all  large d
and 𝐱^d∈𝒜_d. 
Note that S_a:=sup_d∈(a_d/√(d))<∞ since {a_d}_d∈ is sluggish. 
The function x↦ e^x is Lipschitz on [-cS_a,cS_a] with constant e^cS_a. 
Consequently |e^μ_𝒩(𝐱^d)+σ^2_𝒩(𝐱^d)/2-1|≤ e^cS_aa_d/√(d) 
for large d and uniformly in 𝐱^d∈𝒜_d.

By assumption (<ref>), 
for all large  d∈ and all 𝐱^d∈𝒜_d, we have
σ_𝒩(𝐱^d)≥ l√(J)/√(2). 
Hence, since the function x↦√(x) is Lipschitz with
constant c_1:=1/(l√(2J)) on [l^2J/2,∞), we get
|σ_𝒩(𝐱^d)/2-l√(J)/2|≤ (c_1/2) |σ^2_𝒩(𝐱^d)-l^2J|
≤ c_2 a_d/√(d), where constant c_2>0 exists by (<ref>). 
Moreover,
|(μ_𝒩(𝐱^d)+σ^2_𝒩(𝐱^d)/2)/σ_𝒩(𝐱^d)|≤ c_3 a_d/√(d) 
for c_3>0 and all large d. 

Since
σ_𝒩(𝐱^d)+μ_𝒩(𝐱^d)/σ_𝒩(𝐱^d)
=(μ_𝒩(𝐱^d)+
σ^2_𝒩(𝐱^d)/2)/σ_𝒩(𝐱^d)+σ_𝒩(𝐱^d)/2,
the inequalities in the previous paragraph imply that there exists c_4>0 such that 
|σ_𝒩(𝐱^d)+μ_𝒩(𝐱^d)/σ_𝒩(𝐱^d) - l√(J)/2|≤ c_4 a_d/√(d)
for large d and uniformly in 𝐱^d∈𝒜_d.
Since Φ is Lipschitz with constant
1/√(2π), there exists a constant C_1'>1, 
such that 

    |𝔼_𝐘^d-[e^𝒩(𝐱^d,𝐘^d)1_{𝒩(𝐱^d,𝐘^d)<0}]-Φ(-l√(J)/2)|≤ C_1'a_d/√(d)

holds 
for 
all large d and all 
𝐱^d∈𝒜_d. 
Similarly, 
|𝔼_𝐘^d-[1∧ e^𝒩(𝐱^d,𝐘^d)]
-2Φ(-l√(J)/2)|≤ C_2'a_d/√(d)
for some C_2'>0
all large d and all 
𝐱^d∈𝒜_d, 
and the proposition follows. 




 §.§ Proof of Proposition <ref>


We will now prove the following result.


Let a={a_d}_d∈ be a sluggish sequence and p∈[1,∞). There
exists a constant C_4 (depending on a and p) such that for every
f∈𝒮^3 and all d∈ we have:

    𝒢f-𝒢_df_p≤
    C_4(∑_i=1^3f^(i)_∞,1/2) (a_d/√(d)
    +e^-a_d^2/p).



In the case p=2, define a_d:=√(2log(d)) for d∈∖{1}
and note that Proposition <ref> then 
follows as a special case of Proposition <ref>.



There exists a constant C such that for all f∈𝒮^3 and all
d∈ we have: 
    max{|𝒢f(𝐱^d)|,|𝒢_df(𝐱^d)|}≤ C
    e^|x^d_1|∑_i=1^2f^(i)_∞,1/2  ∀𝐱^d∈^d.




The triangle inequality, definition (<ref>) and log(ρ)'(x)f'(x)≤log(ρ)'_∞,1/2f'_∞,1/2e^|x|
imply the bound in the lemma for |𝒢f(𝐱^d)|.
To bound |𝒢_df(𝐱^d)|,
define

    β̃(𝐱^d,y):=𝔼_𝐘^d-[1∧exp(log(ρ)(y)-log(ρ)(x^d_1)+∑_i=2^dlog(ρ)(Y^d_i)-log(ρ)(x^d_i))]

for any y∈. 
Then, if q denotes the density of Y^d_1-x^d_1∼ N(0,l^2/d), we get 

    |𝒢_df(𝐱^d)|=d| 𝔼_Y^d_1[(f(Y^d_1)-f(x^d_1))β̃(𝐱^d,Y^d_1)]|
    
    ≤ d∫_0^∞z|f'(w_1)β̃(𝐱^d,x^d_1+z)-f'(w_2)β̃(𝐱^d,x^d_1-z)|q(z)dz,

where w_1∈(x_1^d,x_1^d+z) and w_2∈(x_1^d-z,x_1^d) satisfy zf'(w_1)=f(x_1^d+z)-f(x_1^d) and -zf'(w_2)=f(x_1^d-z)-f(x_1^d), respectively.
Moreover, 
|f'(w_1)-f'(w_2)|≤ 2z|f”(w_3)| 
holds for some w_3 in the interval (x_1^d-z,x_1^d+z). Since x↦ 1∧ e^x is Lipschitz with constant 1, we get 

    |β̃(𝐱^d,x^d_1+z)-β̃(𝐱^d,x^d_1-z)|≤|log(ρ)(x_1^d+z)-log(ρ)(x_1^d-z)|
    ≤ 2z|log(ρ)'(w_4)|

for some w_4∈ (x_1^d-z,x_1^d+z).  
By adding and subtracting 
f'(w_2)β̃(𝐱^d,x^d_1+z)
on the right-hand side of (<ref>), applying the two bounds we just derived and noting that β̃≤ 1, 
we get

    |𝒢_df(𝐱^d)|   ≤    2d∫_0^∞ z^2|f”(w_3)|q(z)dz+ 2d∫_0^∞ z^2|f'(w_2)log(ρ)'(w_4)|q(z)dz.

Note that, 
since
max{|w_3|,|w_2|,|w_4|}≤ |x_1^d|+z and f”_∞,1≤f”_∞,1/2,
we have

    |f”(w_3)|≤f”_∞,1 e^|w_3|≤f”_∞,1/2 e^|x_1^d|+z,  log(ρ)'(w_4)f'(w_2)≤log(ρ)'_∞,1/2f'_∞,1/2e^|x_1^d|+z,

which, together with inequality (<ref>), implies the lemma. 




By Theorem <ref> (on 𝒜_d) and Lemma <ref> (on ^d∖𝒜_d), there exists a constant 
C>0 such that for any  f∈𝒮^3 the following inequality holds:

    𝒢_df-𝒢f^p_p=
    ∫_𝒜_d|𝒢_df(𝐱^d)-𝒢f(𝐱^d)|^pρ_d(𝐱^d)d𝐱^d+
    ∫_^d∖𝒜_d|𝒢_df(𝐱^d)-𝒢f(𝐱^d)|^pρ_d(𝐱^d)d𝐱^d
    ≤ Cρ(e^p|x|)(a_d^p/d^p/2ρ_d(𝒜_d)+
    ρ_d(^d∖𝒜_d))(∑_i=1^3f^(i)_∞,1/2)^p.

Apply Proposition <ref> and raise both sides of the inequality  
to the power 1/p to conclude the proof of the proposition.




 §.§ Proof of Theorem <ref>




Assume that ρ is a strictly positive density in 
𝒞^1 and that (<ref>) holds. Then, for any d∈, the RWM chain {𝐗^d_n}_n∈ is
V-uniformly ergodic with V:=1/√(ρ_d).  



The lemma follows from <cit.> if we prove that the target ρ_d satisfies

    lim_|𝐱^d|→∞𝐱^d/|𝐱^d|·∇log(ρ_d(𝐱^d))=
    lim_|𝐱^d|→∞∑_i=1^dx^d_i/|x^d_i|log(ρ)'(x^d_i)=-∞,


    lim inf_|𝐱^d|→∞ℙ_𝐘^d[ρ_d(𝐘^d)≥ρ_d(𝐱^d)]>0.

Assumption (<ref>) implies that the expression x/|x|·log(ρ)'(x) 
is bounded above and takes arbitrarily large negative values as |x|→∞.
This yields (<ref>), since |𝐱^d|→∞ implies that |x^d_i|→∞ holds for at least one
i∈{1,…,d}.

Condition (<ref>)
states that the acceptance probability in the RWM chain is bounded away from zero sufficiently far from the origin.
To prove this, 
recall that 
𝐘^d∼ N(𝐱^d,l^2/d· I_d)
and
define the set 

    B(𝐱^d):={𝐲^d∈^dx^d_i/|x^d_i|·(y^d_i-x^d_i)∈(-2l/√(d),-l/√(d)) for all i≤
    d},
 where we interpret x^d_i/|x^d_i|:=1 if x^d_i=0. Clearly
inf_𝐱^d∈^dℙ_𝐘^d[B(𝐱^d)
]>0. 
We now prove that if |𝐱^d| is sufficiently large, then  
ρ_d(𝐲^d)≥ρ_d(𝐱^d) for all 𝐲^d∈ B(𝐱^d),
which implies (<ref>).

By (<ref>), far enough from zero,
ρ is decreasing in a direction away from the origin. Therefore, there
exists a compact interval K⊂ such that
(-2l/√(d),2l/√(d))⊂ K and ρ(y)≥ρ(x) whenever
x∉ K and x/|x|· (y-x)∈ (-2l/√(d),-l/√(d)). 
We claim that 
for every 𝐲^d∈ B(𝐱^d), 
the inequality 
ρ(y^d_i)/ρ(x^d_i)≥ (min_x∈ Kρ(x))/(max_x∈ρ(x))∈(0,1)
holds. 
If
x^d_i∈ K, 
then
y^d_i∈ K
and the inequality follows trivially. 
If
x^d_i∉ K,
then, by the definition of K, 
we have
ρ(y^d_i)/ρ(x^d_i)≥ 1. 
This proves the claim. 
Hence, for 𝐲^d∈ B(𝐱^d) 
we have

    ρ_d(𝐲^d)/ρ_d(𝐱^d)≥(max_i≤ dρ(y^d_i)/ρ(x^d_i))·(min_x∈
    Kρ(x)/max_x∈ρ(x))^d-1.


We now prove that the ratio
ρ(y^d_i)/ρ(x^d_i) takes arbitrarily large values as |x^d_i|→∞. 
To show this,  
pick 𝐲^d∈ B(𝐱^d) 
and assume the inequality y_i^d>x_i^d. 
Then  
x_i^d<0 and 
y_i^d-x_i^d>l/√(d).
Moreover the following holds 

    ρ(y^d_i)/ρ(x^d_i)=exp(log(ρ(y^d_i)/ρ(x^d_i)))≥
    1+∫_x^d_i^y^d_ilog(ρ)'(z)dz≥
    1+l/√(d)inf_z<x^d_i+2l/√(d)log(ρ)'(z)→∞

as x_i^d→-∞ by (<ref>). 
This, together with (<ref>), implies (<ref>).  
The case y_i^d<x_i^d is analogous and the lemma follows.



If a strictly positive ρ 
satisfies (<ref>)
and
log(ρ)∈𝒮^n_ρ and f∈𝒮^n_f for some
integers n_ρ,n_f∈∪{0}, then the function f̂, defined in (<ref>),
satisfies
f̂∈𝒮^min(n_f+2,n_ρ+1).  



Clearly, if f∈𝒞^n_f and ρ∈𝒞^n_ρ and if
ρ is strictly positive, then
f̂∈𝒞^min(n_f+2,n_ρ+1).  Pick s>0. 
The L'Hospital's rule implies:

    lim_x→∞f̂(x)/e^s|x|=
    2/sh(l)lim_x→∞∫_-∞^xρ(y)(ρ(f)-f(y))dy/e^sxρ(x)=2/sh(l)lim_x→∞ρ(f)-f(x)/se^sx+e^sx(log(ρ))'(x).

The last limit is zero by (<ref>). An analogous argument shows 
lim_x→-∞f̂(x)/e^s|x|=0. 
Hence f̂_∞,s<∞ holds for all s>0. 
Since h(l)f̂'(x)/2=(∫_-∞^xρ(y)(ρ(f)-f(y))dy)/ρ(x), 
this argument implies that f̂'_∞,s<∞ holds for all s>0. 
Hence f̂∈𝒮^1.

Proceed by induction: assume that for all k≤ n (where 1≤
n<min(n_f+2,n_ρ+1)) we have f̂^(k)_∞,s<∞
for any s>0.
Pick an arbitrary u>0. 
By differentiating (<ref>) we obtain

    f̂^(n+1)=-∑_k=0^n-1n-1k(log(ρ))^(k+1)f̂^(n-k)+2/h(l)(ρ(f)-f)^(n-1).

Since n≤min(n_ρ, n_f+1), the induction hypothesis implies
f̂^(k)_∞,u/2<∞ for all 1≤ k≤ n.
By assumption we have 
f^(n-1)_∞,u<∞ and 
(log(ρ))^(k)_∞,u/2<∞
for all 1≤ k≤ n.
Hence
f̂^(n+1)_∞,u<∞ holds for an arbitrary u>0 and the proposition follows. 



By Lemma <ref>,
the RWM chain 𝐗^d with the transition kernel 
P_d is V-uniformly ergodic with
V=ρ_d^-1/2. 
Moreover, by <cit.>[Prop. 2.1 and Thm 2.1], P_d defines
a self-adjoint operator on {g∈ L^2(ρ_d)ρ_d(g)=0} with norm
λ_d<1.
Proposition <ref>
implies 
f̂∈𝒮^3,
since by assumption we have
f∈𝒮^1 and log(ρ)∈𝒮^4. 
By Remark <ref>(c) in Section <ref> below we have
f̂^2∈𝒮^3.
Since P_df̂ = (1/d)𝒢_df̂+f̂, Lemma <ref> implies that
(P_df̂)^2(𝐱^d)≤ C_f̂ e^2 |x_1^d| for some positive
constant C_f̂ and all 𝐱^d∈^d. 
Hence (<ref>) and the definition of V
imply  the inequality 
max{f̂^2,(P_df̂)^2}≤ cV for some constant c>0. 
Consequently, by <cit.>, the CLT for the chain 
𝐗^d and function f+dP_df̂-df̂ holds with some
asymptotic variance σ̂^2_f,d.

By <cit.> we can represent σ̂^2_f,d 
in terms of a positive spectral measure E_d(dλ) associated with the
function
f-ρ(f)+dP_df̂-df̂=𝒢_df̂-𝒢f̂ as

    σ̂^2_f,d=∫_Λ_d1+λ/1-λE_d(dλ),

where Λ_d⊂[-λ_d,λ_d] denotes the spectrum of the self-adjoint operator P_d acting on the Hilbert space
{g∈ L^2(ρ_d)ρ_d(g)=0}. 
By the definition of the spectral measure E_d(dλ) we obtain
We can bound

    σ̂^2_f,d≤1+λ_d/1-λ_d∫_Λ_dE_d(dλ)=1+λ_d/1-λ_dP_d(df̂)-df̂+f-ρ(f)^2_2≤2/1-λ_d𝒢_df̂-𝒢f̂^2_2.

Finally, the result follows by Proposition <ref>. 




§ TECHNICAL RESULTS

The results in Section <ref> use the ideas of Berry-Esseen theory and large deviations as well as the
optimal Young inequality, and do not depend on anything in this paper that precedes them. 



 §.§ Bounds on the expectations of test functions

We start with elementary observations. 


Recall that 𝒮^n, n∈∪{0}, is defined in (<ref>). The following statements hold.


  * If n≤ m, then 𝒮^m⊂𝒮^n.

  * For n∈, f∈𝒮^n if and only if f'∈𝒮^n-1.

  * If f∈𝒮^n and g∈𝒮^m then f+g, fg∈𝒮^min(n,m).




 Pick an arbitrary n∈. Assume f∈𝒮^n, k≤ n,
x∈ and Y∼ N(x,σ^2). 
Then there exists measurable Z satisfying
f^(k)(Z)(Y-x)^k/k!=f(Y)-∑_i=0^k-1f^(i)(x)(Y-x)^i/i! and 
|Z-x|<|Y-x|. Furthermore  
there exists a constant C>0
(depending on n) such that,
for any m∈ and s>0 we have

    𝔼_Y[|f^(k)(Z)|^m|Y-x|^n]≤
    Ce^s^2σ^2𝔼_Y[|Y-x|^n]f^(k)_∞,s/m^me^s|x|.




A random variable Z, defined via the integral form of the remainder in Taylor's theorem, lies a.s. between Y and x, implying 
|Z-x|<|Y-x|. 
Cauchy's inequality yields 

    𝔼_Y[|f^(k)(Z)|^m|Y-x|^n]^2≤𝔼_Y[|f^(k)(Z)|^2m]𝔼_Y[|Y-x|^2n].

Since f∈𝒮^n⊂𝒮^k, we have
sup_x∈|f^(k)(x)|^2me^-2s|x|=f^(k)^2m_∞,s/m<∞.
As Y∼ N(x,σ^2), the equality 
𝔼_Y[|Y-x|^2n]= C^2
𝔼_Y[|Y-x|^n]^2
holds,
where
C:=(2√(π)Γ((2n+1)/2))^1/2/Γ((n+1)/2) 
and
Γ(·) is the Euler gamma function. 
Hence, by (<ref>),
we get

    𝔼_Y[|f^(k)(Z)|^m|Y-x|^n]≤C/√(2)f^(k)^m_∞,s/m√(𝔼_Y[e^2s|Z|])𝔼_Y[|Y-x|^n].

It remains to
note 
𝔼_Ye^2s(|Z|-|x|)≤𝔼_Ye^2s|Z-x|≤𝔼_Ye^2s|Y-x|≤2 𝔼_Ye^2s(Y-x)= 2e^2s^2σ^2.



Let f→ be a measurable (not necessary continuous)
function such that f_∞,1/2<∞. 
 Fix n∈,
𝐱^d∈^d and let X_1, X_2…, X_d be IID copies of X,
satisfying 𝔼[X^n]=0 and
𝔼[X^2n]<∞. Then the following inequality holds: 

    |𝔼[∑_i=1^df(x^d_i)X_i^n]|≤f_∞,1/2(𝔼[X^2n]∑_i=1^de^|x^d_i|)^1/2.




Note that the assumptions of Proposition <ref> imply that, if X is a non-zero random variable, then  n∈
has to be odd. 



By Jensen's inequality, the fact that 𝔼[X]=0 and the assumption on f we get 

    𝔼[∑_i=1^df(x^d_i)X_i^n]^2≤𝔼[(∑_i=1^df(x^d_i)X_i^n)^2]=
    ∑_i=1^d (f(x^d_i))^2𝔼[X_i^2n]≤f^2_∞,1/2𝔼[X^2n]∑_i=1^de^|x^d_i|.





 §.§ Deviations of the sums of IID random variables



 Let f∈𝒮^0 be such
that ρ(f)=0 and let a={a_d}_d∈ be a sluggish sequence. If the random vector 
(X_1,d,…, X_d,d) follows the density ρ_d for all d∈, then for every t>0 the
following inequality
holds for all but finitely many d∈:

    ℙ_ρ_d[|1/d-1∑_i=2^df(X_i,d)|≥ta_d/√(d)]≤exp(-t^2a_d^2/(3ρ(f^2))).




Proposition <ref> is an elementary consequence
of a deeper underlying result, that the sequence of random variables
{∑_i=1^df(X_i,d)/(a_d√(d))}_d∈ 
satisfies a moderate deviation principle with a good rate function t↦ t^2/(2ρ(f^2)) and speed a_d^2
(see <cit.> for details). The key inequality needed in the proof of 
Proposition <ref> is given in the next lemma. 





Let assumptions of Proposition <ref> hold. If ρ(f^2)>0, then for every closed F⊆ 
the following holds:

    lim sup_d→∞a^-2_dlogℙ_ρ_d[∑_i=1^df(X_i,d)/(a_d√(d))∈
    F]≤ -inf{ x^2/(2ρ(f^2));x∈ F}.




 The moderate deviations results <cit.>  
yield a sufficient condition for the above inequality.  
More precisely, for X∼ρ, 
we need to establish: 

    lim sup_d→∞ a_d^-2log(d·ℙ_ρ[|f(X)|≥ a_d√(d)])=-∞.

Fix an arbitrary m∈. Since f∈𝒮^0, we have |f(x)|≤f_∞,1/m e^|x|/m for every x∈. 
Consequently, for all large d, we get 

    ℙ_ρ[|f(X)|≥ a_d√(d)]≤ℙ_ρ[f_∞,1/m^m e^|X|≥ d^m/2]≤f_∞,1/m^m ρ(e^|X|)d^-m/2.

Since {a_d}_d∈ is sluggish,
∃ C_0>0 such that
a_d^-2log(f_∞,1/m^m ρ(e^|X|))<C_0< a_d^-2log(d) for all large d∈.
Hence

    a_d^-2log (d·ℙ_ρ[|f(X)|≥ a_d√(d)])≤
    a_d^-2(log(f_∞,1/m^m ρ(e^|X|))-(m/2-1)log(d))<
    -C_0(m/2-2),

for all large d∈.
Since m was arbitrary, (<ref>) follows. 



Note that the proposition holds if ρ(f^2)=0. Assume now ρ(f^2)>0
and fix an arbitrary t>0. Note that since {a_d}_d∈ is sluggish, 
so is {a'_d}_d∈, a'_d:=a_d+1√(d/(d+1)). 
Apply Lemma <ref> to
F=∖ (-t,t) and 
{a'_d}_d∈
to get the following inequality 

    ℙ_ρ_d-1[|∑_i=1^d-1f(X_i,d-1)/(a'_d-1√(d-1))|≥
    t]≤exp(-3 (a'_d-1)^2t^2/(8ρ(f^2)))

for all large enough d∈. 
Since
3(a'_d-1)^2/4≥ 2a^2_d/3 
for all but finitely many d∈,
the right-hand side in (<ref>) is bounded above by exp(-(a_d)^2t^2/(3ρ(f^2))). 
Recall
ρ_d(𝐱^d)=ρ_d-1(𝐱^d-1)ρ(x_d^d)
and a_d-1'√(d-1)=a_d(d-1)/√(d).
Hence the left-hand side in inequality (<ref>) equals
ℙ_ρ_d[|∑_i=2^df(X_i,d)/(d-1)|≥ ta_d/√(d)]
and the proposition follows. 


The next result is based on a combinatorial argument. A special case 
of Proposition <ref> was used in <cit.>.


Let n∈ and a measurable f→ satisfy ρ(f)=0 and
ρ(f^2n)< ∞. 
If the random vector (X_1,d,…,X_d,d) is distributed according to ρ_d,
then there exists a constant C, independent of d, such that
ℙ_ρ_d[|1/d-1∑_i=2^df(X_i,d)|≥
1]≤ C d^-n.  



The constant C in Proposition <ref> may depend on n∈ and the function f.



Fix n∈
and let _0:=∪{0}.
Markov's inequality and the Multinomial theorem yield: 

    ℙ_ρ_d[|1/d-1∑_i=2^df(X_i,d)|≥
    1]=ℙ_ρ_d[|1/d-1∑_i=2^d
    f(X_i,d)|^2n≥ 1]≤𝔼_ρ_d(1/d-1∑_i=2^d
    f(X_i,d))^2n
          =(d-1)^-2n∑_k_2+k_3+⋯
    +k_d=2n
    k_2,k_3…,k_d∈_0∖{1}2nk_2,k_3,…,k_d∏_i=2^d𝔼_ρ[f(X_i,d)^k_i],

where last equality holds, because the expectation of any summand of the form
∏_i=2^df(X_i,d)^k_i is zero if any of the indices k_i=1 since ρ_d has a product structure and
ρ(f)=0.  
By Jensen's inequality, 
∏_i=2^d𝔼_ρ[f(X_i,d)^k_i]≤∏_i=2^d𝔼_ρ[f(X_i,d)^2n]^k_i/2n=ρ(f^2n)
^∑_i=2^dk_i/2n=ρ(f^2n), and hence  

    ℙ_ρ_d[|1/d-1∑_i=2^df(X_i,d)|≥
    1]≤ (2n)!·ρ(f^2n)(d-1)^-2n·|𝒩_d|,

where |𝒩_d| stands
for the cardinality of the set 

    𝒩_d:={(k_2,k_3,…, k_d)∈^d-1_0;  ∑_i=2^dk_d=2n and  k_i≠ 1 for all 
     2≤ i≤ d}.

Inequality (<ref>) and the next Claim prove the proposition. 

Claim. 
|𝒩_d|≤ C' d^n for a constant C' independent of d. 

Proof of Claim.
Consider a function ζ^d-1_0→^d-1_0, 
ζ(a_2,a_3,…, a_d):=(2⌊a_2/2⌋,2⌊a_3/2⌋,…
2⌊a_d/2⌋ ), that rounds each entry down to the
nearest even number. Every element in the image ζ(𝒩_d) is a
(d-1)-tuple of non-negative even integers with sum at most 2n.
Recall the number of k-combinations with repetition, chosen from a set of
d-1 objects, equals k+d-2k. There exists C”>0, such that  

    |ζ(𝒩_d)|   ≤   |{(k_2,k_3,…, k_d)∈^d-1_0;   ∑_i=2^dk_d≤ n}|
       =   ∑_k=0^n|{(k_2,k_3,…, k_d)∈^d-1_0;  ∑_i=2^dk_d=k}|=∑_k=0^nk+d-2k≤ C” d^n.


Note that the pre-image of a singleton under ζ contains at most 2^n elements (i.e. (d-1)-tuples) of 𝒩_d. 
Indeed, by the definition of
𝒩_d, at most n coordinates of an element are not zero and each can
either reduce by one or stay the same. Hence, for C':=C” 2^n, we have
|𝒩_d|≤ 2^n·|ζ(𝒩_d)|≤ C'd^n. 




 §.§ Bounds on the densities of certain random variables


The key step in the proof of Proposition <ref> below is 
the optimal Young's inequality:
for p,q≥ 1 and r∈[1,∞], such that  1/p+1/q=1+1/r, 
and functions f∈ L^p() and g∈ L^q(), their convolution  f*g
satisfies the inequality

    f*g_r≤C_pC_q/C_rf_pg_q,  where   
    C_s:=√(s^1/s/s'^1/s'),
     if s∈(1,∞) and 1/s+1/s'=1,
    
    1, if s∈{1,∞}.

For s∈[1,∞),
·_s is the usual norm on L^s() and ·_∞
denotes the essential supremum norm on L^∞(). 
The proof of (<ref>) for r<∞ is given in <cit.>.
In the case r=∞, we have C_pC_q/C_r=1 and the inequality in (<ref>)
follows from the definition of the convolution, translation invariance of the Lebesgue measure 
and Hölder's inequality. 

 
Let X_1,X_2,…, X_d be
independent random variables, each X_i with a bounded density q_i. The density
Q_d of the sum ∑_i=1^d X_i satisfies
Q_d_∞≤ c  max_i≤ dq_i_∞/√(d)
for some constant c>0.



The factor d^-1/2  in the inequality of Proposition <ref>
above comes from (<ref>)
and is crucial for the analysis in this paper. The standard Young's inequality for convolutions would only yield 
Q_d_∞≤ c max_i≤ dq_i_∞, which gives insufficient control over Q_d. 



Since random variables X_i are independent, the density of their sum is a
convolution of the respective densities, Q_d=_i=1^d q_i.
For all i and each t>1 we have 
q_i∈ L^∞()∩ L^1()⊂ L^t(). 
Moreover, the following inequality holds 
for every k≤ d-1:

    Q_d_∞=_i=1^d q_i_∞≤(C_d/d-1)^kC_d/k(∏_i=1^kq_i_d/d-1)_i=k+1^d
    q_i_d/k


We prove (<ref>)  by induction on k. 
For k=1, note that 
d and d/d-1 are Hölder conjugates, i.e. 1/d +1/(d/(d-1))=1
Hence (<ref>) for r=∞, q=d, p=d/(d-1), f=q_1
and 
g=_i=2^d q_i implies
Q_d_∞≤q_1_d/d-1_i=2^d q_i_d 
and C_d/d-1=C^-1_d.
Now assume (<ref>) holds for some k≤ d-2. 
Since
(d/(d-1))^-1+(d/(k+1))^-1=1+(d/k)^-1,
the inequality in (<ref>) implies 
    _i=k+1^d q_i_d/k≤C_d/d-1C_d/k+1/C_d/kq_k+1_d/d-1_i=k+2^d q_i_d/k+1.

This inequality and the induction hypothesis (i.e. (<ref>) for k) implies (<ref>) for k+1.

Since q_1 is a density, we have q_i_1=1. Hence we find
q_i_d/d-1≤q_i_1^d-1/dq_i_∞^1/d=q_i_∞^1/d
for each i, and in particular
∏_i=1^dq_i_d/d-1≤max_i≤ d(q_i_∞).
By (<ref>) for k=d-1 we get	

    Q_d_∞≤(C_d/d-1)^d∏_i=1^dq_i_d/d-1≤max_i≤ d(q_i_∞)(C_d/d-1)^d.

Since
 lim_d→∞√(d)(C_d/d-1)^d=√(e), 
there exists c>0 such that 
(C_d/d-1)^d≤ c/ √(d) for all d∈. 

Polynomials of continuous random variables play an important role in the proofs of Section <ref>.


Let X be a continuous random variable and p a polynomial. Then the random variable p(X) has a density.



The set
B:=p((p')^-1({0})) has finitely many points.
Moreover, p is locally invertible on ∖ B by the inverse function theorem
and the inverses are differentiable. Hence, for any x∉ B, the set p^-1((-∞,x])
is a disjoint union of intervals with boundaries that depend smoothly on x.
Since ℙ[p(X)≤ x]=ℙ[X∈ p^-1((-∞,x])], the proposition follows. 


 
Let N=N(μ,σ^2) be a normal
random variable and p a polynomial satisfying inf_x∈|p'(x)|≥ c_p for some constant c_p>0.
Then the random variable p(N) has a probability density function q_p(N),
which satisfies q_p(N)_∞≤ (c_pσ√(2π))^-1.


 Obviously, p is strictly monotonic and thus a bijection.
Moreover, the distribution Φ_p(N)(·) of p(N) takes the form 
ℙ[N≤ p^-1(·)] or ℙ[N>p^-1(·)].
Hence, for any x∈,  the density q_p(N) of p(N) satisfies
q_p(N)(x)=q_N(p^-1(x))|(p^-1)'(x)|
=q_N(p^-1(x))/|p'(p^-1(x))|≤ 1/(c_pσ√(2π)),
as the density of N, q_N, 
is bounded above by 
(σ√(2π))^-1.  




 §.§ CFs and distributions of near normal random variables





Let N be a normal random variable with mean μ and variance σ^2
and X a continuous random variable. Denote with φ_X,
φ_N and Φ_X, Φ_N the CFs and the distributions of X and
N, respectively. Assume there exist constants r>0, γ∈ (0,1) and a function
R→ such that
|logφ_X(t)-logφ_N(t)|≤ R(t)≤γσ^2
t^2/2 holds on |t|≤ r.  Then 

    sup_x∈|Φ_N(x)-Φ_X(x)|≤∫_-r^rR(t)/π |t|exp(-(1-γ)σ^2t^2/2)dt+12√(2)/π^3/2σ r.
 



The result is a direct consequence of the Smoothing theorem (see <cit.>) commonly used to prove Berry-Esseen-type bounds, that relate CFs and distribution functions of random variables. 



The Smoothing theorem implies 

    sup_x∈|Φ_N(x)-Φ_X(x)|
    ≤∫_-r^r|φ_N(t)-φ_X(t)|/(π|t|)dt+24sup_x∈|Φ_N'(x)|/(π
    r).
 
Note that, for any z∈ℂ, it holds 
|e^z-1|≤ |z|e^|z|. For 
z:=log(φ_X(t)/φ_N(t)), this implies

    |φ_X(t)-φ_N(t)|≤ |φ_N(t)| 
    |logφ_X(t)-logφ_N(t)| exp(|logφ_X(t)-logφ_N(t)|)     ∀ t∈.

The result follows from this inequality, sup_x∈|Φ_N'(x)|=1/(σ√(2π)) and |φ_N(t)|=e^-σ^2t^2/2:

    ∫_-r^r|φ_N(t)-φ_X(t)|/π |t|dt≤∫_-r^r|φ_N(t)|R(t)/π |t|e^R(t)dt≤∫_-r^rR(t)/π
    |t|exp(-(1-γ)σ^2t^2/2)dt.





Let X be random variable with finite mean μ, variance σ^2 and
absolute third central moment
κ:=𝔼[|X-μ|^3]. Then, the characteristic
function φ_X of X satisfies: 
    |logφ_X(t)-(iμ
    t-σ^2/2t^2)|≤κ|t|^3/6+σ^4t^4/4  ∀
    t∈[-1/σ,1/σ].




The result can be established by combining the elementary bound 

    |𝔼[e^i(X-μ)t-∑_k=0^n(it)^n/n!(X-μ)^n]|≤|t|^n+1/(n+1)!𝔼[|X-μ|^n+1]  ∀ t∈

and the fact that z∈ℂ, |z|≤ 1/2 implies
|(log(1+z)-z|≤ |z|^2 (see <cit.> for both).




Let N=N(0,σ^2) and let u,v∈. The random variable uN+vN^2 has a characteristic function that satisfies

    |logφ_uN+vN^2(t)-(ivσ^2t-u^2σ^2/2t^2)|≤ 2v^2σ^4t^2+2u^2|v|σ^4|t|^3  ∀ t∈[-1/4|v|σ^2,1/4|v|σ^2].




The CF φ_uN+vN^2 can be explicitly computed using standard complex analysis

    φ_uN+vN^2(t)=𝔼[e^i(uN+vN^2)t]=1/√(1-2ivσ^2t)exp(-u^2σ^2t^2/2(1-2ivσ^2t))  ∀ t∈.

The rest can then be shown using the elementary inequalities: z∈ℂ,
|z|≤ 1/2 implies |(log(1+z)-z|≤ |z|^2 and
|1/(1-z)-1|≤ 2|z|.  



alpha


