diff b1f9bc4..56bc728 low_temp_sk_glauber_typical_v2.txt
diff --git a/low_temp_sk_glauber_typical_v2.txt b/low_temp_sk_glauber_typical_v2.txt
index a601425..ccef313 100644
--- a/low_temp_sk_glauber_typical_v2.txt
+++ b/low_temp_sk_glauber_typical_v2.txt
@@ -26,13 +26,13 @@ maketitle
Abstract:
We study single-site heat-bath (Glauber) dynamics for the zero-field
Sherrington--Kirkpatrick spin glass at a fixed inverse temperature
-$beta>1$. We prove that a configuration sampled from equilibrium mixes
-to equilibrium in subexponential time: for every fixed $beta>1$ there
-is a constant $c_beta>0$ such that, with probability tending to one
+beta>1. We prove that a configuration sampled from equilibrium mixes
+to equilibrium in subexponential time: for every fixed beta>1 there
+is a constant c_beta>0 such that, with probability tending to one
over the disorder and the starting configuration, the total-variation
-distance from equilibrium is below $1/4$ by time
-$exp(n^{1-c_beta})$. The proof admits the explicit value
-$c_beta=1/40000000$ for all fixed $beta>1$. The starting
+distance from equilibrium is below 1/4 by time
+exp(n^{1-c_beta}). The proof admits the explicit value
+c_beta=1/40000000 for all fixed beta>1. The starting
configuration is held fixed before the distance to equilibrium is
measured; this is the essential subtlety, since averaging the start into
the law would make the distance zero at every time.
@@ -46,16 +46,16 @@ tableofcontents
## The question in plain terms
-The SK model is a mean-field spin glass: $n$ spins
-$sigma_iin{-1,1}$ interact through random pairwise couplings.
+The SK model is a mean-field spin glass: n spins
+sigma_iin{-1,1} interact through random pairwise couplings.
The heat-bath (Glauber) dynamics is the natural local sampler. Each site
-has an independent rate-one clock; when the clock at site $i$ rings,
-the spin $sigma_i$ is replaced by a fresh value drawn from its
-conditional law given all the other spins. The chain has $2^n$ states
-and is reversible with respect to the Gibbs measure $pi^J_{n,beta}$.
+has an independent rate-one clock; when the clock at site i rings,
+the spin sigma_i is replaced by a fresh value drawn from its
+conditional law given all the other spins. The chain has 2^n states
+and is reversible with respect to the Gibbs measure pi^J_{n,beta}.
At high temperature the chain mixes quickly, in polynomial time
-from every start. At low temperature ($beta>1$ in the
+from every start. At low temperature (beta>1 in the
zero-field SK model) the landscape is glassy: there are deep valleys
separated by high barriers, and a configuration placed in the wrong
valley can take a very long time to escape. Sellke [cite]
@@ -65,50 +65,50 @@ lower bound on the mixing time.
That leaves a sharper question. An adversarial start is unrealistic for
a sampler run on a freshly drawn instance. What happens if we start the
chain from a typical equilibrium configuration, i.e. from one
-sample $sigma_0simpi^J_{n,beta}$? This paper answers the question
-for every fixed $beta>1$: the chain is fast, at most subexponential in
-$n$, from such a start.
+sample sigma_0simpi^J_{n,beta}? This paper answers the question
+for every fixed beta>1: the chain is fast, at most subexponential in
+n, from such a start.
Two conventions are essential and we fix them now.
[label=(roman*)]
-item The start is random and then held fixed. We first draw the
- disorder $J$, then one configuration $sigma_0simpi^J_{n,beta}$,
- and only then look at the law $P_t^{J,beta}(sigma_0,cdot)$ of the chain
- started at that single $sigma_0$. The total-variation distance in the
- mixing time is between this fixed-start law and $pi^J_{n,beta}$. If one
- instead averaged $sigma_0$ into the starting distribution, stationarity
+ The start is random and then held fixed. We first draw the
+ disorder J, then one configuration sigma_0simpi^J_{n,beta},
+ and only then look at the law P_t^{J,beta}(sigma_0,cdot) of the chain
+ started at that single sigma_0. The total-variation distance in the
+ mixing time is between this fixed-start law and pi^J_{n,beta}. If one
+ instead averaged sigma_0 into the starting distribution, stationarity
would force the distance to be zero at every time and the question would
vanish.
-item Time is continuous, one clock per site. Each site rings at
- rate one, so the total jump rate of the chain is exactly $n$.
+ Time is continuous, one clock per site. Each site rings at
+ rate one, so the total jump rate of the chain is exactly n.
## The model
-Let $nge2$ and let $(J_{ij})_{1le i<jle n}$ be independent standard
-Gaussian variables. Put $J_{ji}=J_{ij}$ and $J_{ii}=0$. For a spin
-configuration $sigmain{-1,1}^n$ set
+Let nge2 and let (J_{ij})_{1le i<jle n} be independent standard
+Gaussian variables. Put J_{ji}=J_{ij} and J_{ii}=0. For a spin
+configuration sigmain{-1,1}^n set
H^J_n(sigma)=frac1{sqrt n}sum_{i<j}J_{ij}sigma_isigma_j,
- qquad
+
pi^J_{n,beta}(sigma)
=frac{exp(beta H^J_n(sigma))}{Z^J_{n,beta}},
-where $Z^J_{n,beta}$ is the normalizing constant. There is no external
-field. The local field at site $i$ is
+where Z^J_{n,beta} is the normalizing constant. There is no external
+field. The local field at site i is
[
h_i(sigma)=frac1{sqrt n}sum_{jne i}J_{ij}sigma_j .
]
-When the clock at site $i$ rings, the new value equals $sin{-1,1}$
+When the clock at site i rings, the new value equals sin{-1,1}
with probability
mathbb PbbP{new spin=smidsigma}
=frac{exp(beta s,h_i(sigma))}
{2cosh(beta h_i(sigma))} .
-The update may leave $sigma_i$ unchanged. Let
-$P_t^{J,beta}(sigma,cdot)$ denote the law at time $t$ of this
-continuous-time chain started from the fixed configuration $sigma$, and
+The update may leave sigma_i unchanged. Let
+P_t^{J,beta}(sigma,cdot) denote the law at time t of this
+continuous-time chain started from the fixed configuration sigma, and
let
T^J_{n,beta}(sigma)
@@ -118,36 +118,36 @@ let
be the mixing time from that start. The joint law of interest samples
the disorder and one Gibbs configuration,
-$mathbb P_bbP_{J,,sigma_0simpi^J_{n,beta}}
-=mathbb E_JbbE_J,pi^J_{n,beta}$.
+mathbb P_bbP_{J,,sigma_0simpi^J_{n,beta}}
+=mathbb E_JbbE_J,pi^J_{n,beta}.
## Main results
[Mixing from a typical Gibbs start]
-For every fixed $beta>1$ there is a constant $c_betain(0,1)$ such
+For every fixed beta>1 there is a constant c_betain(0,1) such
that
[
mathbb P_bbP_{J,,sigma_0simpi^J_{n,beta}}Bigl{
T^J_{n,beta}(sigma_0)leexp(n^{1-c_beta})Bigr}
→ 1
- qquad (nto∞).
+ (nto∞).
]
-The constant may be taken as $c_beta=1/40000000$ uniformly over every
-fixed $beta>1$, and it does not depend on the realized disorder.
+The constant may be taken as c_beta=1/40000000 uniformly over every
+fixed beta>1, and it does not depend on the realized disorder.
-Equivalently, in probability over the disorder $J$, the Gibbs mass of
+Equivalently, in probability over the disorder J, the Gibbs mass of
the set of configurations whose mixing time is at most
-$exp(n^{1-c_beta})$ tends to one. The exponent is not optimized, and
+exp(n^{1-c_beta}) tends to one. The exponent is not optimized, and
the dimension from which the estimates hold may depend on the fixed
-$beta$; all such thresholds are absorbed into ``tending to one''.
+beta; all such thresholds are absorbed into ``tending to one''.
The companion lower bound in [cite] gives a matching
stretched-exponential barrier. Combined with Theorem~thm:main it
produces a two-sided statement.
[Two-sided typical-start bound]
-For every fixed $beta>1$, in the model and continuous-time convention
+For every fixed beta>1, in the model and continuous-time convention
above,
[
mathbb P_bbP_{J,,sigma_0simpi^J_{n,beta}}Bigl{
@@ -160,12 +160,12 @@ above,
Proof.
The continuous-time form of cite[Theorem~1.1]{OpenAISKBarriers2026}
states that, with joint probability tending to one,
-$|P^{J,beta}_{exp(n^{1/10000})}(sigma_0,cdot)-pi^J_{n,beta}|_{TV}>1/4$
-for $sigma_0simpi^J_{n,beta}$. By (eq:T) and continuity of the
+|P^{J,beta}_{exp(n^{1/10000})}(sigma_0,cdot)-pi^J_{n,beta}|_{TV}>1/4
+for sigma_0simpi^J_{n,beta}. By (eq:T) and continuity of the
finite-state semigroup this forces the strict lower bound
-$T^J_{n,beta}(sigma_0)>exp(n^{1/10000})$. The upper bound is
+T^J_{n,beta}(sigma_0)>exp(n^{1/10000}). The upper bound is
Theorem~thm:main. Both events use the same joint law of
-$(J,sigma_0)$ and the same rate-one clocks, so their intersection has
+(J,sigma_0) and the same rate-one clocks, so their intersection has
probability tending to one.
@@ -175,41 +175,37 @@ The proof has five logical stages. We describe each in words, then point
to its section.
[label=Stage arabic*.]
-item Equilibrium scalar inputs. The Parisi theory of the SK
- model provides a scalar potential $Phi$ and a magnetization martingale
+ Equilibrium scalar inputs. The Parisi theory of the SK
+ model provides a scalar potential Phi and a magnetization martingale
whose variance in overlap space is dictated by the minimizing Parisi
measure. We state exactly which equilibrium inputs we use, in the
normalization of this paper. See Section~sec:scalar.
-
-item The long diffusion and its entropy--energy identity. We
+ The long diffusion and its entropy--energy identity. We
continue the scalar diffusion past the endpoint of the Parisi support,
where the magnetizations pin down (level sets shrink exponentially). An
exact It^o calculation produces a scalar identity,
equation~(eq:scalar-balance), that balances the information
acquired by matrix queries against the energy gained. This is the engine
of the entropy bound. See Section~sec:scalar.
-
-item The Gaussian-query proposal. We build a random spin by
- querying the matrix $W=W(G)$ along orthogonalized directions. Each query
+ The Gaussian-query proposal. We build a random spin by
+ querying the matrix W=W(G) along orthogonalized directions. Each query
is conditionally Gaussian given the past and constructs a fresh
- coordinate of a driving Brownian motion. The proposal $Q_l$ has two
- controlled features: sublinear relative entropy ${rm KL}(Q_lVert P)$,
+ coordinate of a driving Brownian motion. The proposal Q_l has two
+ controlled features: sublinear relative entropy {rm KL}(Q_lVert P),
and a likelihood bound outside an exponentially unlikely event. See
Section~sec:proposal.
-
-item Reversing the entropy: coverage. Forward entropy alone says
+ Reversing the entropy: coverage. Forward entropy alone says
nothing about reaching a prescribed set. Conditioning the Gibbs joint law
on the spin makes the remaining disorder law strongly log-concave; a
small Gaussian smoothing plus the quadratic transport inequality then
reverses the entropy comparison. The outcome is a coverage statement:
- any Gibbs set of mass at least $n^{-d}$ receives at least
- $exp(-n^{1-2d})$ proposal mass for the realized target disorder and
+ any Gibbs set of mass at least n^{-d} receives at least
+ exp(-n^{1-2d}) proposal mass for the realized target disorder and
smoothing base. See Section~sec:reverse.
-
-item Balancing flows and mixing. Two independent proposals joined
+ Balancing flows and mixing. Two independent proposals joined
across a cut contradict the avoidance of a small boundary unless
every cut of appreciable Gibbs mass carries stationary flow at least
- $B_{min}=exp(-n^{1-b/20})$. The geometry is elementary: a short
+ B_{min}=exp(-n^{1-b/20}). The geometry is elementary: a short
sequence of spins crossing a cut must contain a spin close to the
boundary. Fine-horizon spins supply endpoint coverage; coarse-horizon
spins have rare enough failures along the connecting sequence, and
@@ -226,11 +222,11 @@ stages at the end of Section~sec:mixing.
High-temperature, worst-start. Eldan, Koehler and Zeitouni
cite[Section~6]{EKZ2022} proved polynomial worst-start mixing for
-$beta<1/4$. Wang cite[Theorem~1.1]{Wang2026} established optimal-order
-Glauber mixing for every fixed $beta<1/2$, and Boban, Li and Oveis
+beta<1/4. Wang cite[Theorem~1.1]{Wang2026} established optimal-order
+Glauber mixing for every fixed beta<1/2, and Boban, Li and Oveis
Gharan cite[Corollary~1.6]{BLO2026} extended polynomial worst-start
-mixing in zero field to $beta<1/2+ε_0$ for some absolute
-$ε_0>0$.
+mixing in zero field to beta<1/2+ε_0 for some absolute
+ε_0>0.
Low-temperature, worst-start. Sellke
cite[Theorem~1.1]{Sellke2025} proved exponential worst-start lower
@@ -264,57 +260,57 @@ for finite Markov chains cite[Lemmas~2.5,~2.7]{DiaconisSaloffCoste1996}.
# Notation and Gaussian completion
%======================================================================
-Fix a finite $beta>1$. Constants may depend on this fixed parameter;
-when that dependence matters we write $C_beta$ or $O_beta(cdot)$. All
+Fix a finite beta>1. Constants may depend on this fixed parameter;
+when that dependence matters we write C_beta or O_beta(cdot). All
logarithms are natural.
Distances and inner products.: For probability measures
-$mullnu$ on a common space, set
-${rm KL}(muVertnu)=intlog(dmu/dnu),dmu$. On the spin cube,
-total variation is one half of the $ell^1$ distance. For vectors
-$v,winmathbb R^n$bbR^n$ write
+mullnu on a common space, set
+{rm KL}(muVertnu)=intlog(dmu/dnu),dmu. On the spin cube,
+total variation is one half of the ell^1 distance. For vectors
+v,winmathbb R^nbbR^n write
[
< v,w>_n=frac1nsum_i v_i w_i,
- qquad |v|_n^2=< v,v>_n .
+ |v|_n^2=< v,v>_n .
]
-The symbols $|v|$ and $|A|$ denote the Euclidean norm of a vector and
+The symbols |v| and |A| denote the Euclidean norm of a vector and
the operator norm of a matrix.
-The GOE completion.: A heat-bath update at site $i$ never sees
-$J_{ii}$. We complete the interaction matrix by adding independent
-diagonal entries of law $N(0,2/n)$: define a symmetric matrix $W=W(G)$
-whose entries above the diagonal are $W_{ij}=J_{ij}/sqrt n$ and whose
-diagonal entries are independent $N(0,2/n)$. Write $G$ for the vector of
+The GOE completion.: A heat-bath update at site i never sees
+J_{ii}. We complete the interaction matrix by adding independent
+diagonal entries of law N(0,2/n): define a symmetric matrix W=W(G)
+whose entries above the diagonal are W_{ij}=J_{ij}/sqrt n and whose
+diagonal entries are independent N(0,2/n). Write G for the vector of
independent standard Gaussian drivers of all these entries and
-$gamma$ for its law. Since $x_i^2=1$ for every spin,
+gamma for its law. Since x_i^2=1 for every spin,
[
tfrac12,x^{mathsf T}sfTdiag(W),x
=tfrac12sum_i W_{ii}
]
is the same random constant for every configuration. Hence the diagonal
contributes the same additive constant to every Gibbs weight; it changes
-neither $pi^J_{n,beta}$ nor any heat-bath rate nor the transition
-kernel. Its effect on $mathbb EbbE F(G)$ is a deterministic constant that
-we absorb into the pressure functional $mathcal P$calP$ below.
+neither pi^J_{n,beta} nor any heat-bath rate nor the transition
+kernel. Its effect on mathbb EbbE F(G) is a deterministic constant that
+we absorb into the pressure functional mathcal PcalP below.
-Gibbs weights on the completed matrix.: Define, with $W=W(G)$,
+Gibbs weights on the completed matrix.: Define, with W=W(G),
[
widehatwidehat H_G(x)=H_G(x)=tfrac12 x^{mathsf T}sfTW(G),x,
- quad
+
F(G)=logsum_{xin{-1,1}^n}e^{betawidehatwidehat H_G(x)}H_G(x),
- quad
+
pi_G(x)=e^{betawidehatwidehat H_G(x)-F(G)}H_G(x)-F(G).
]
Because the diagonal is a configuration-independent constant,
-$pi_G=pi^J_{n,beta}$ as probability measures. We work with
-$widehatwidehat H_G$H_G$ everywhere. The Gibbs joint law of disorder and spin is
+pi_G=pi^J_{n,beta} as probability measures. We work with
+widehatwidehat H_GH_G everywhere. The Gibbs joint law of disorder and spin is
[
P(dG,x)=gamma(dG),pi_G(dx).
]
This is exactly the joint law of the starting configuration in
-Theorem~thm:main. It is crucial that $P$ is a joint law:
-downstream we compare a proposal law $Q_l$ to $P$ on the joint
-$(G,x)$-space. The transition kernel for a fixed disorder and a
+Theorem~thm:main. It is crucial that P is a joint law:
+downstream we compare a proposal law Q_l to P on the joint
+(G,x)-space. The transition kernel for a fixed disorder and a
fixed initial configuration is a different object, and the final
mixing argument must separate the two carefully.
@@ -331,24 +327,24 @@ functions of a scalar time; no high-dimensional geometry enters yet.
## Equilibrium inputs, stated once
-Let $mu_beta$ be a minimizing Parisi probability measure for the
-zero-field Gaussian SK model at the fixed finite $beta>1$. We use the
+Let mu_beta be a minimizing Parisi probability measure for the
+zero-field Gaussian SK model at the fixed finite beta>1. We use the
following external inputs.
[leftmargin=*]
-item Pressure. Guerra's finite-volume interpolation bound
- cite[Theorem~3]{Guerra2003}: $mathbb EbbE F(G)le nmathcal P$,calP$, where
- $mathcal P$calP$ is the Parisi pressure functional, whose exact
+ Pressure. Guerra's finite-volume interpolation bound
+ cite[Theorem~3]{Guerra2003}: mathbb EbbE F(G)le nmathcal P,calP, where
+ mathcal PcalP is the Parisi pressure functional, whose exact
normalization we give below.
-item Regularity and stability. Auffinger--Chen
+ Regularity and stability. Auffinger--Chen
cite[Propositions~1--2]{AC2015}: the scalar Parisi equation has
continuous spatial derivatives, and its solution is stable under step
- approximation of the CDF of $mu_beta$.
-item Full support and stationarity. Lopatto
+ approximation of the CDF of mu_beta.
+ Full support and stationarity. Lopatto
cite[Theorem~1.1, Lemma~2.2, Proposition~2.4, Lemma~2.5]{Lopatto2026}:
the minimizing measure has full interval support,
[
- supp(mu_beta)=[0,q_*],qquad 0<q_*<1,
+ supp(mu_beta)=[0,q_*], 0<q_*<1,
]
and the associated scalar solution obeys the stationarity identity used
in (eq:martingale) below.
@@ -357,124 +353,124 @@ item Full support and stationarity. Lopatto
The stationarity identity is also given, in the form we quote, in
Jagannath--Tobasco cite[Proposition~1.1, Corollaries~3.6,~3.10]{JT2017}.
What full support buys is precisely the ability to apply the identity at
-every overlap in $[0,q_*]$; mere infinite support would not suffice.
+every overlap in [0,q_*]; mere infinite support would not suffice.
## Normalization and the scalar Parisi equation
-Use the scalar variance time $v=beta^2 s$ with $s$ the Parisi time
-variable, and put $alpha_v=mu_beta([0,v/beta^2])$ for
-$0le vlebeta^2$. Let $Phi$ solve the backward Parisi equation
+Use the scalar variance time v=beta^2 s with s the Parisi time
+variable, and put alpha_v=mu_beta([0,v/beta^2]) for
+0le vlebeta^2. Let Phi solve the backward Parisi equation
Phi_v=-tfrac12(Phi_{yy}+alpha_vPhi_y^2),
- qquad
+
Phi(beta^2,y)=log(2cosh y),
-with subscripts denoting derivatives. Equivalently, if $u$ is the scalar
+with subscripts denoting derivatives. Equivalently, if u is the scalar
solution in [cite], then
-$Phi(v,y)=u(v/beta^2,y)+log2$. Combining the independent ordered pair
+Phi(v,y)=u(v/beta^2,y)+log2. Combining the independent ordered pair
couplings of the source gives the unordered pair coefficient
-$beta/sqrt n$ used in (eq:H), plus a centered diagonal term. Thus
+beta/sqrt n used in (eq:H), plus a centered diagonal term. Thus
this scalar normalization agrees with our completed Hamiltonian.
-Set $v_*=beta^2 q_*$. The pressure functional and the finite-volume
+Set v_*=beta^2 q_*. The pressure functional and the finite-volume
upper bound read
mathcal P=calP=Phi(0,0)-frac1{2beta^2}int_0^{beta^2}valpha_v,dv,
- qquad
+
mathbb EbbE F(G)le nmathcal PcalP .
-The centered diagonal shifts neither $mathcal P$calP$ nor $mathbb EbbE F(G)$
-in any way that matters below. Since $alpha_v=1$ above $v_*$, the
-Gaussian recursion gives, at $v_*$,
+The centered diagonal shifts neither mathcal PcalP nor mathbb EbbE F(G)
+in any way that matters below. Since alpha_v=1 above v_*, the
+Gaussian recursion gives, at v_*,
Phi(v_*,y)=log(2cosh y)+(beta^2-v_*)/(2) .
## Continuation past the support endpoint
-For all $v>v_*$ we continue the potential by the explicit formula
+For all v>v_* we continue the potential by the explicit formula
Phi(v,y)=log(2cosh y)+(beta^2-v)/(2),
- qquad alpha_v=1 .
+ alpha_v=1 .
-This agrees with the original solution up to $beta^2$ and satisfies the
-same PDE for every $vge v_*$. It describes the regime in which the
+This agrees with the original solution up to beta^2 and satisfies the
+same PDE for every vge v_*. It describes the regime in which the
magnetizations pin down: the level sets of the magnetization
-shrink and the spin becomes deterministic. Continue for every $vge0$
+shrink and the spin becomes deterministic. Continue for every vge0
the two scalar functions
[
- m(v,y)=Phi_y(v,y),qquad a(v,y)=Phi_{yy}(v,y),
+ m(v,y)=Phi_y(v,y), a(v,y)=Phi_{yy}(v,y),
]
-so that on the extension $m(v,y)=tanh y$ and
-$a(v,y)=1-tanh^2 y$.
+so that on the extension m(v,y)=tanh y and
+a(v,y)=1-tanh^2 y.
-Let $Z$ be a standard Brownian motion and let $Y$ solve
+Let Z be a standard Brownian motion and let Y solve
- dY_v=alpha_v,m(v,Y_v),dv+dZ_v,qquad Y_0=0 .
+ dY_v=alpha_v,m(v,Y_v),dv+dZ_v, Y_0=0 .
The drift is bounded and spatially Lipschitz, so the scalar SDE has a
-unique strong solution. Abbreviate $m_v=m(v,Y_v)$ and
-$a_v=a(v,Y_v)$. The stationarity identity, the differentiated PDE, and
+unique strong solution. Abbreviate m_v=m(v,Y_v) and
+a_v=a(v,Y_v). The stationarity identity, the differentiated PDE, and
It^o's formula give the key scalar facts
- m_0=0,qquad dm_v=a_v,dZ_v,qquad
- mathbb EbbE m_v^2=(v)/(beta^2)quad(0le vle v_*),
+ m_0=0, dm_v=a_v,dZ_v,
+ mathbb EbbE m_v^2=(v)/(beta^2)(0le vle v_*),
-and this martingale equation continues past $v_*$ by direct It^o
+and this martingale equation continues past v_* by direct It^o
calculus with the explicit functions (eq:phi-extension). We use,
repeatedly, the deterministic bounds
- 0<a(v,y)le1-m(v,y)^2le1,qquad |m(v,y)|<1 .
+ 0<a(v,y)le1-m(v,y)^2le1, |m(v,y)|<1 .
-paragraph{Why (eq:a-m-bound) holds.} We derive it in the form that
+Why (eq:a-m-bound) holds. We derive it in the form that
behaves well under step approximation. One Parisi step of CDF height
-$lambdain[0,1]$ and variance $delta>0$ maps a profile $f$ to
+lambdain[0,1] and variance delta>0 maps a profile f to
[
(Tf)(y)=frac1lambdalogmathbb EbbE,
- e^{lambda f(y+sqrtdelta U)},qquad Usim N(0,1),
+ e^{lambda f(y+sqrtdelta U)}, Usim N(0,1),
]
-with $Tf(y)=mathbb EbbE f(y+sqrtdelta U)$ when $lambda=0$. Write
-$mathbb E_bbE_lambda$ for the Gaussian expectation tilted by
-$e^{lambda f(y+sqrtdelta U)}$ and renormalized. Differentiating gives
+with Tf(y)=mathbb EbbE f(y+sqrtdelta U) when lambda=0. Write
+mathbb E_bbE_lambda for the Gaussian expectation tilted by
+e^{lambda f(y+sqrtdelta U)} and renormalized. Differentiating gives
the exact formulas
[
- (Tf)'=mathbb E_bbE_lambda f',qquad
+ (Tf)'=mathbb E_bbE_lambda f',
(Tf)''=mathbb E_bbE_lambda f''+lambdaVar_lambda(f') .
]
-Suppose $0<f''le1-(f')^2$. Then
+Suppose 0<f''le1-(f')^2. Then
[
0<(Tf)''le1-((Tf)')^2-(1-lambda)Var_lambda(f')
le1-((Tf)')^2 .
]
-Inducting from $f(y)=log(2cosh y)$ proves the bound for step CDFs;
+Inducting from f(y)=log(2cosh y) proves the bound for step CDFs;
stability cite[Propositions~1--2]{AC2015} passes the non-strict bound to
-the minimizing CDF, and the strict lower bound on $Phi_{yy}$ in
+the minimizing CDF, and the strict lower bound on Phi_{yy} in
cite[Proposition~2.4]{Lopatto2026} gives strict positivity in the limit.
-Hence $m$ is strictly increasing and $|m|<1$, giving
+Hence m is strictly increasing and |m|<1, giving
(eq:a-m-bound). On the extension these assertions follow from
-$tanh$ directly.
+tanh directly.
## Tail estimates for the extended diffusion
Define the three deterministic functions
- p(v)=mathbb EbbE a_v,qquad r(v)=mathbb EbbE a_v^2,
- qquad rho(v)=beta√(r(v)) .
+ p(v)=mathbb EbbE a_v, r(v)=mathbb EbbE a_v^2,
+ rho(v)=beta√(r(v)) .
The martingale second-moment identity (eq:martingale) and
-continuity give $r(v)=1/beta^2$ on $[0,v_*]$, endpoints included. The
-next lemma controls the continuation and confirms that $rho$ is an
-admissible noise-mixing coefficient in $[0,1]$.
+continuity give r(v)=1/beta^2 on [0,v_*], endpoints included. The
+next lemma controls the continuation and confirms that rho is an
+admissible noise-mixing coefficient in [0,1].
[Scalar tail bounds]
-For $vge v_*$ the extended diffusion obeys
+For vge v_* the extended diffusion obeys
- rho(v)le1,qquad -2le(log r)'(v)le0,
- qquad p'(v)=-r(v),
- qquad p(v)le C_beta e^{-v/2} .
+ rho(v)le1, -2le(log r)'(v)le0,
+ p'(v)=-r(v),
+ p(v)le C_beta e^{-v/2} .
-At $v=v_*$ the derivatives are from the right.
+At v=v_* the derivatives are from the right.
Proof.
@@ -483,90 +479,90 @@ cite[Proposition~7.1]{Lopatto2026} and the moment comparison of
cite[Proposition~9.3]{Lopatto2026}, which together give the required
estimates for the arbitrary-time continuation.
-Two moment ratios. For $v>v_*$, the density of $Y_v$ divided by
-$cosh y$ is symmetric and nonincreasing in $|y|$. It suffices to check
+Two moment ratios. For v>v_*, the density of Y_v divided by
+cosh y is symmetric and nonincreasing in |y|. It suffices to check
this for step CDFs and pass to the limit; stability
cite[Propositions~1--2]{AC2015} justifies the passage. For a step CDF
-with masses $alpha^{(j)}$ on intervals $[v_j,v_{j+1}]$, and
-$varphi_t$ the centered Gaussian density of variance $t$, the transition
+with masses alpha^{(j)} on intervals [v_j,v_{j+1}], and
+varphi_t the centered Gaussian density of variance t, the transition
density on one interval is
[
K_j(z,y)=varphi_{v_{j+1}-v_j}(y-z)
expbigl{alpha^{(j)}[Phi(v_{j+1},y)-Phi(v_j,z)]bigr} .
]
-The Gaussian recursion normalizes $K_j$; its Doob transform has drift
-$alpha^{(j)}Phi_y$. In a product of kernels the intermediate factors at
-$y_j$ reduce to
+The Gaussian recursion normalizes K_j; its Doob transform has drift
+alpha^{(j)}Phi_y. In a product of kernels the intermediate factors at
+y_j reduce to
[
expbigl{-(alpha^{(j)}-alpha^{(j-1)})Phi(v_j,y_j)bigr},
]
-which is even and nonincreasing in $|y_j|$ because the masses are
-nondecreasing and $Phi$ is even and convex. The first positive-time
+which is even and nonincreasing in |y_j| because the masses are
+nondecreasing and Phi is even and convex. The first positive-time
Gaussian convolution turns the initial point mass at zero into a
symmetric decreasing density, and multiplication by these factors plus
further Gaussian convolutions preserve that property (using the
centered-interval level-set representation of a symmetric decreasing
profile). Extending the final mass to one leaves an endpoint factor
-proportional to $cosh y$; dividing by it leaves the asserted symmetric
+proportional to cosh y; dividing by it leaves the asserted symmetric
decreasing profile.
-Weighting either $sechy$ or $sech^3y$ by a
+Weighting either sechy or sech^3y by a
decreasing profile can only increase the expectation of
-$sech^2y$, since two nonincreasing functions of $|y|$ have
+sech^2y, since two nonincreasing functions of |y| have
nonnegative covariance. Integration by parts gives
[
frac{int_{mathbb R}bbRsech^{k+2}y,dy}
{int_{mathbb R}bbRsech^{k}y,dy}
- =(k)/(k+1)qquad(k>0).
+ =(k)/(k+1)(k>0).
]
-Consequently $r/pge1/2$ and $mathbb EbbE a_v^3/r(v)ge3/4$.
+Consequently r/pge1/2 and mathbb EbbE a_v^3/r(v)ge3/4.
-Differential identities. On the extension $a_v=1-m_v^2$, and
+Differential identities. On the extension a_v=1-m_v^2, and
direct It^o calculations yield
[
- p'=-r,qquad r'=4r-6,mathbb EbbE a_v^3 .
+ p'=-r, r'=4r-6,mathbb EbbE a_v^3 .
]
-The two moment ratios imply $p'le-p/2$ and $r'le0$. Since
-$0<a_vle1$, the second identity also gives $r'ge-2r$. Integrating
-$p'le-p/2$ gives $p(v)le C_beta e^{-v/2}$. Finally
-$r(v_*)=1/beta^2$ and monotonicity of $r$ imply $rhole1$.
+The two moment ratios imply p'le-p/2 and r'le0. Since
+0<a_vle1, the second identity also gives r'ge-2r. Integrating
+p'le-p/2 gives p(v)le C_beta e^{-v/2}. Finally
+r(v_*)=1/beta^2 and monotonicity of r imply rhole1.
## The entropy--energy identity
-Let $mathcal H(z)$calH(z)$ be the entropy of a sign with mean $zin(-1,1)$:
+Let mathcal H(z)calH(z) be the entropy of a sign with mean zin(-1,1):
[
mathcal H(z)=-(1+z)/(2)calH(z)=-(1+z)/(2)log(1+z)/(2)
-(1-z)/(2)log(1-z)/(2),
]
-with continuous values at $z=pm1$. For $V>v_*$ define the two scalars
+with continuous values at z=pm1. For V>v_* define the two scalars
that will be the energy per spin and the information cost per spin of the
matrix proposal:
e(V)=int_0^V√(r(v)),p(v),rho(v),dv,
- qquad
+
j(V)=frac12int_0^Vrho(v)^2,
mathbb E(a_v^2)/(1-m_v^2)bbE(a_v^2)/(1-m_v^2),dv .
-The factor $rho(v)^2$ inside $j$ accounts for the independent noise we
+The factor rho(v)^2 inside j accounts for the independent noise we
introduce in the proposal. Below the support endpoint, It^o's formula
together with the PDE and stationarity gives
[
mathbb E[Y_bbE[Y_{v_*}m_{v_*}]=int_0^{v_*}(p(v)+alpha_v v/beta^2),dv,
- qquad
+
mathbb EbbEPhi(v_*,Y_{v_*})=Phi(0,0)
+frac12int_0^{v_*}alpha_v v/beta^2,dv .
]
These also follow by step approximation with bounded first and second
spatial derivatives. Substituting the endpoint value (eq:phi-at-vstar)
-and using $mathcal H(tanhcalH(tanh y)=log(2cosh y)-ytanh y$ gives
+and using mathcal H(tanhcalH(tanh y)=log(2cosh y)-ytanh y gives
int_0^{v_*}p(v),dv+mathbb EbbE,mathcal H(m_calH(m_{v_*})
=mathcal P-(calP-(beta^2)/(4)(1-q_*)^2 .
[Entropy--energy identity]
-For every $V>v_*$,
+For every V>v_*,
log2-j(V)+beta e(V)=mathcal P-(calP-(beta^2)/(4),p(V)^2 .
@@ -578,33 +574,33 @@ The same martingale calculation applied to binary entropy yields
frac12int_0^{v_*}mathbb E(a_v^2)/(1-m_v^2)bbE(a_v^2)/(1-m_v^2),dv
=log2-mathbb EbbE,mathcal H(m_calH(m_{v_*}).
]
-Localization justifies It^o's formula near $z=pm1$; the integrand is
-bounded because $ale1-m^2$. Since $rho=1$ and $betasqrt r=1$ on
-$[0,v_*]$, the two identities above prove (eq:scalar-balance) at
-$V=v_*$. Above $v_*$ the derivative of the left side of
-(eq:scalar-balance) is $(beta^2/2),r(v),p(v)$: indeed
-$a_v=1-m_v^2$ there, and $rho^2=beta^2 r$. The derivative of
-$-beta^2p(v)^2/4$ is the same, by $p'=-r$. Integrating from $v_*$
-therefore proves the claim for every $V>v_*$.
+Localization justifies It^o's formula near z=pm1; the integrand is
+bounded because ale1-m^2. Since rho=1 and betasqrt r=1 on
+[0,v_*], the two identities above prove (eq:scalar-balance) at
+V=v_*. Above v_* the derivative of the left side of
+(eq:scalar-balance) is (beta^2/2),r(v),p(v): indeed
+a_v=1-m_v^2 there, and rho^2=beta^2 r. The derivative of
+-beta^2p(v)^2/4 is the same, by p'=-r. Integrating from v_*
+therefore proves the claim for every V>v_*.
-The terminal error $(beta^2)/(4)p(V)^2$ on the right of
-(eq:scalar-balance) is at most $C_beta e^{-V}$ by
-(eq:1). We take $V$ proportional to $log n$, so this error is a
-negative power of $n$ while the spin is nearly pinned.
+The terminal error (beta^2)/(4)p(V)^2 on the right of
+(eq:scalar-balance) is at most C_beta e^{-V} by
+(eq:1). We take V proportional to log n, so this error is a
+negative power of n while the spin is nearly pinned.
%======================================================================
# The Gaussian-query proposal
%======================================================================
-We now build a random spin using the matrix $W=W(G)$ together with
+We now build a random spin using the matrix W=W(G) together with
auxiliary randomness. The construction has a single design principle:
each query of the matrix is orthogonal to the earlier queries and
is independent given the past. This exposes fresh Gaussian information
while leaving a compressed GOE block unrevealed, so that a clean
conditional-Gaussian argument applies at every step. The scalar identity
(eq:scalar-balance) will then control both the relative entropy of
-the resulting law $Q_l$ and its likelihood outside a small exceptional
+the resulting law Q_l and its likelihood outside a small exceptional
event.
The spirit is the same as Bolthausen's iterative TAP construction
@@ -618,49 +614,49 @@ increment.
## Construction and conditional Gaussian laws
Mesh.: Fix a horizon parameterfootnote{We use the letter
-$l$ both for the horizon parameter and, later, for the horizon value.
-Context disambiguates. The final paper uses $l=f$ for fine coverage and
-$l=b$ for the coarse connecting sequence; see Section~sec:reverse.}
-$0<lle1/100$ and set
+l both for the horizon parameter and, later, for the horizon value.
+Context disambiguates. The final paper uses l=f for fine coverage and
+l=b for the coarse connecting sequence; see Section~sec:reverse.}
+0<lle1/100 and set
- h=n^{-1/16},qquad K=lceil llog n/hrceil,qquad
- t_k=kh,qquad V=t_K .
+ h=n^{-1/16}, K=lceil llog n/hrceil,
+ t_k=kh, V=t_K .
-For all sufficiently large $n$, $K<n$, and $V>v_*$ with $v_*$ the support
+For all sufficiently large n, K<n, and V>v_* with v_* the support
endpoint of Section~sec:scalar.
-The two driving streams.: The disorder $G$ retains its ordinary
-Gaussian law $gamma$. We build a vector-valued process whose coordinates
+The two driving streams.: The disorder G retains its ordinary
+Gaussian law gamma. We build a vector-valued process whose coordinates
follow the scalar SDE (eq:Y), driven by two independent streams,
dZ=rho(v),dB+√(1-rho(v)^2),dD .
-Here $D$ is an auxiliary standard Brownian motion, independent of
-everything; $B$ is to be constructed from matrix queries together with
-auxiliary completions so that, after averaging over the disorder, $(B,D)$
-is a standard Brownian pair. By (eq:1) the weight $rhole1$ equals
-one up to $v_*$ and is nonincreasing afterwards; this is exactly what
-keeps the level sets pinning while retaining unit variance in $Z$. Write
-$M(v)_i=m(v,Y_{v,i})$.
+Here D is an auxiliary standard Brownian motion, independent of
+everything; B is to be constructed from matrix queries together with
+auxiliary completions so that, after averaging over the disorder, (B,D)
+is a standard Brownian pair. By (eq:1) the weight rhole1 equals
+one up to v_* and is nonincreasing afterwards; this is exactly what
+keeps the level sets pinning while retaining unit variance in Z. Write
+M(v)_i=m(v,Y_{v,i}).
-Building $B$.: On the first interval $[0,h]$ we generate $B$
+Building B.: On the first interval [0,h] we generate B
entirely from independent auxiliary Brownian noise. For each subsequent
-interval $[t_k,t_{k+1}]$, $1le k<K$, the previous scalar increment
+interval [t_k,t_{k+1}], 1le k<K, the previous scalar increment
determines
s_k^2=int_{t_{k-1}}^{t_k}r(v),dv,
- qquad T_k=frac{M(t_k)-M(t_{k-1})}{s_k} .
+ T_k=frac{M(t_k)-M(t_{k-1})}{s_k} .
-Project $T_k$ off the preceding query directions $u_1,...,u_{k-1}$ and
-normalize the residual to obtain $|u_k|_n=1$. If the residual is exactly
+Project T_k off the preceding query directions u_1,...,u_{k-1} and
+normalize the residual to obtain |u_k|_n=1. If the residual is exactly
zero, choose a new direction measurably from the past: project the
coordinate basis vectors in their fixed order, take the first nonzero
-projection, and normalize it. Since $k<n$, such a direction always
-exists. Let $Pi_{le k}$ be the orthogonal projection onto the span
-through $u_k$, and $Pi_{>k}=I-Pi_{le k}$.
+projection, and normalize it. Since k<n, such a direction always
+exists. Let Pi_{le k} be the orthogonal projection onto the span
+through u_k, and Pi_{>k}=I-Pi_{le k}.
-Query the column $Wu_k$. For an independent standard Gaussian vector
-$z_k$, set the endpoint of the next Brownian increment to be
+Query the column Wu_k. For an independent standard Gaussian vector
+z_k, set the endpoint of the next Brownian increment to be
g_k=h^{-1/2}(B(t_{k+1})-B(t_k))
=Pi_{>k}Wu_k+Pi_{le k}z_k .
@@ -671,32 +667,32 @@ noise is fresh. A deterministic-coefficient integral against this filled
path may equivalently be obtained by conditioning Brownian motion on its
endpoint.
-The spin.: At time $V$, given the path, draw the coordinates
-$x_iin{-1,1}$ independently with means $M_i(V)$. Let $Q_l$ be the
-marginal law of $(G,x)$ produced this way.
+The spin.: At time V, given the path, draw the coordinates
+x_iin{-1,1} independently with means M_i(V). Let Q_l be the
+marginal law of (G,x) produced this way.
-Why $(B,D)$ is a standard Brownian pair.: Condition on the
+Why (B,D) is a standard Brownian pair.: Condition on the
columns already revealed and on the auxiliary inputs already used.
Gaussian orthogonal invariance leaves the unqueried block a GOE matrix on
the orthogonal complement, with the original variance scale. The next
-direction $u_k$ is measurable with respect to this past. In an
-orthonormal basis beginning with $u_k/sqrt n$, the new diagonal entry,
+direction u_k is measurable with respect to this past. In an
+orthonormal basis beginning with u_k/sqrt n, the new diagonal entry,
the remaining entries of that column, and the next compressed block are
-independent. Hence $Pi_{>k}Wu_k$ is a fresh Gaussian with covariance
-$Pi_{>k}$, and
+independent. Hence Pi_{>k}Wu_k is a fresh Gaussian with covariance
+Pi_{>k}, and
[
d_k=< u_k,Wu_k>_nsim N(0,2/n)
]
conditionally, before the column is revealed. The independent completion
-has covariance $Pi_{le k}$, so $g_k$ in (eq:gk) is a fresh
+has covariance Pi_{le k}, so g_k in (eq:gk) is a fresh
standard Gaussian vector. Induction, followed by the independent bridge
-filling, proves that $(B,D)$ in (eq:4) is a standard Brownian pair.
+filling, proves that (B,D) in (eq:4) is a standard Brownian pair.
Coordinate symmetry.: After forgetting the matrix, the
coordinate paths and their final spins are i.i.d. The conditional mean of
-$x$ given the streams through time $v$ is $M(v)$, and its unconditional
+x given the streams through time v is M(v), and its unconditional
law is uniform on the cube by the symmetry of the scalar process. The
-spin marginal of $P$ is also uniform, by coordinate-sign symmetry of the
+spin marginal of P is also uniform, by coordinate-sign symmetry of the
disorder. Both are facts about marginals; the proposal spin remains
correlated with its own matrix.
@@ -705,84 +701,84 @@ correlated with its own matrix.
The next proposition supplies two distinct comparisons. Entropy will
yield coverage after smoothing; the likelihood estimate will keep
intermediate proposals out of the small boundary of a putative low-flow
-cut. Both are stated for the joint law $Q_l$ on $(G,x)$-space.
+cut. Both are stated for the joint law Q_l on (G,x)-space.
[Proposal comparison]
-For every fixed $0<lle1/100$ and all sufficiently large $n$,
+For every fixed 0<lle1/100 and all sufficiently large n,
{rm KL}(Q_lVert P)le2n^{1-l/2} .
Moreover, there is an event in the proposal experiment of probability at
-least $1-exp(-n^{1-10l})$ such that the output subprobability
-restricted to this event is dominated on $(G,x)$-space by
+least 1-exp(-n^{1-10l}) such that the output subprobability
+restricted to this event is dominated on (G,x)-space by
exp(n^{1-l/2}),P .
The good event is determined entirely by the inputs of this one proposal
-run. Finally, the empirical Gram matrix of the $T_k$ is within $n^{-l}$ of
+run. Finally, the empirical Gram matrix of the T_k is within n^{-l} of
the identity in operator norm, except with probability at most
-$exp(-n^{1-10l})$. The dimension from which all this holds may depend on
-the fixed $l$.
+exp(-n^{1-10l}). The dimension from which all this holds may depend on
+the fixed l.
Proof.
-Put $eta=n^{-l}$. We evaluate the proposal energy from empirical inner
+Put eta=n^{-l}. We evaluate the proposal energy from empirical inner
products, then compute the information cost of its matrix channel, and
combine with the pressure bound and the scalar identity
(eq:scalar-balance).
Empirical inner products.: Form the empirical matrix of all
-normalized inner products among $T_k,g_k$ ($1le k<K$) and $x$. It is an
-average of $n$ i.i.d. row outer products, by the coordinate law above.
+normalized inner products among T_k,g_k (1le k<K) and x. It is an
+average of n i.i.d. row outer products, by the coordinate law above.
Every unit linear form of a row is sub-Gaussian with norm at most
-$C_beta e^V$. For the $T_k$ part, use their disjoint martingale
-increments, $|a|le1$, and
+C_beta e^V. For the T_k part, use their disjoint martingale
+increments, |a|le1, and
s_k^2ge c_beta h,e^{-2V},
which follows from (eq:1). An exponential martingale estimate
bounds the linear form by its deterministic quadratic-variation bound.
-The $g_k$ part is Gaussian and the spin term is bounded; the correlations
+The g_k part is Gaussian and the spin term is bounded; the correlations
with the first part do not affect the resulting sub-Gaussian bound: for
squared linear forms the moments are bounded by
-$k!,(C_beta e^{2V})^k$, and expanding the centered exponential moment
-followed by exponential Markov gives, at deviation scale $eta/2$, a
+k!,(C_beta e^{2V})^k, and expanding the centered exponential moment
+followed by exponential Markov gives, at deviation scale eta/2, a
quadratic-form tail
[
2exp(-c_beta neta^2e^{-4V}).
]
-A $1/4$-net of the unit sphere in dimension $O(K)$ has $exp(O(K))$
+A 1/4-net of the unit sphere in dimension O(K) has exp(O(K))
points, by ball packing. The quadratic-form norm inequality and a union
-bound therefore put the whole empirical matrix within $eta$ of its
-expectation, with exceptional probability at most $exp(-n^{1-8l})$.
+bound therefore put the whole empirical matrix within eta of its
+expectation, with exceptional probability at most exp(-n^{1-8l}).
The population identities are
- mathbb E[T_jT_k]_bbE[T_jT_k]_{rm row}=mathbf1_bf1_{j=k},quad
- mathbb E[T_jg_k]_bbE[T_jg_k]_{rm row}=0 (jle k),quad
- mathbb E[T_kx]_bbE[T_kx]_{rm row}=s_k,quad
+ mathbb E[T_jT_k]_bbE[T_jT_k]_{rm row}=mathbf1_bf1_{j=k},
+ mathbb E[T_jg_k]_bbE[T_jg_k]_{rm row}=0 (jle k),
+ mathbb E[T_kx]_bbE[T_kx]_{rm row}=s_k,
mathbb E[g_kx]_bbE[g_kx]_{rm row}=b_k,
where
-$b_k=h^{-1/2}int_{t_k}^{t_{k+1}}p(v)rho(v),dv$. These follow from the
+b_k=h^{-1/2}int_{t_k}^{t_{k+1}}p(v)rho(v),dv. These follow from the
martingale bracket, the conditional mean of the final spin, and
-(eq:4). The vectors $s=(s_k)$ and $b=(b_k)$ each have Euclidean
+(eq:4). The vectors s=(s_k) and b=(b_k) each have Euclidean
norm at most one, by projection of the unit-variance spin onto the
corresponding orthonormal scalar variables.
Triangular Cholesky and matrix norms.: We need a matrix-norm
-estimate that does not lose a factor $K$ under orthogonalization. Taking
-the triangular part of an $mtimes m$ matrix costs at most $Clog(2m)$ in
+estimate that does not lose a factor K under orthogonalization. Taking
+the triangular part of an mtimes m matrix costs at most Clog(2m) in
operator norm: pad to a power of two and partition the strict triangle by
dyadic scales; at each scale the rectangles have disjoint row and column
sets, so retaining that scale is contractive; summing over scales proves
the bound.
-Let $A$ be a Gram matrix with $|A-I|leeta<1/2$, and let
-$R^{mathsf T}sfTR=A$ be its upper Cholesky factor. Along
-$A(t)=I+t(A-I)$, differentiation shows that $dot RR^{-1}$ is the upper
+Let A be a Gram matrix with |A-I|leeta<1/2, and let
+R^{mathsf T}sfTR=A be its upper Cholesky factor. Along
+A(t)=I+t(A-I), differentiation shows that dot RR^{-1} is the upper
triangular part, with half the diagonal, of
-$R^{-mathsf T}sfTdot AR^{-1}$. The norms of $R$ and $R^{-1}$ are uniformly
+R^{-mathsf T}sfTdot AR^{-1}. The norms of R and R^{-1} are uniformly
bounded; the preceding triangular estimate plus integration give
[
|R-I|le Cetalog(2m).
@@ -790,9 +786,9 @@ bounded; the preceding triangular estimate plus integration give
(Differentiability follows directly from the triangular Cholesky
recursion.)
-Apply this with the Gram matrix of the $T_k$. The query matrix with
-columns $u_k$ is the matrix with columns $T_k$ multiplied by $R^{-1}$. So,
-writing $c_k=< u_k,x>_n$, the empirical event gives
+Apply this with the Gram matrix of the T_k. The query matrix with
+columns u_k is the matrix with columns T_k multiplied by R^{-1}. So,
+writing c_k=< u_k,x>_n, the empirical event gives
[
|c-s|&le Cetalog(2K),
@@ -802,11 +798,11 @@ writing $c_k=< u_k,x>_n$, the empirical event gives
]
The middle estimate uses that left multiplication of the population cross
-matrix by the lower-triangular $R^{-mathsf T}sfT$ preserves its zero upper
-triangle, including the diagonal. Also $|c|le1$, because the query
-directions are orthonormal in $|cdot|_n$.
+matrix by the lower-triangular R^{-mathsf T}sfT preserves its zero upper
+triangle, including the diagonal. Also |c|le1, because the query
+directions are orthonormal in |cdot|_n.
-Energy of the final spin.: Let $H_0=Pi_{>K-1}$. Revealing the
+Energy of the final spin.: Let H_0=Pi_{>K-1}. Revealing the
columns in order decomposes the quadratic form exactly as
[
frac{widehatwidehat H_G(x)}H_G(x)n
@@ -814,15 +810,15 @@ columns in order decomposes the quadratic form exactly as
+tfrac12sum_kc_k^2d_k
+tfrac12< x,H_0WH_0x>_n .
]
-The last two terms are $O(eta)$ outside an event of probability at most
-$CKexp(-cneta^2)$: the diagonal estimate follows from the conditional
-Gaussian law and $sum c_k^2le1$, while the residual term uses that the
+The last two terms are O(eta) outside an event of probability at most
+CKexp(-cneta^2): the diagonal estimate follows from the conditional
+Gaussian law and sum c_k^2le1, while the residual term uses that the
spin has not seen the unrevealed block. Removing the projections in the
-first term costs at most $Cetalog(2K)$ by the triangular bound. Its
-remaining value is $scdot b$ up to the same error. The bound on
-$(log r)'$ in (eq:1) implies $s_k/sqrt h$ differs from
-$√(r(v))$ on $[t_k,t_{k+1}]$ by a relative $O(h)$. The missing initial
-interval contributes $O(h)$, and $e(V)$ is bounded. Hence $scdot b=e(V)+O_beta(h)$,
+first term costs at most Cetalog(2K) by the triangular bound. Its
+remaining value is scdot b up to the same error. The bound on
+(log r)' in (eq:1) implies s_k/sqrt h differs from
+√(r(v)) on [t_k,t_{k+1}] by a relative O(h). The missing initial
+interval contributes O(h), and e(V) is bounded. Hence scdot b=e(V)+O_beta(h),
and altogether
widehatwidehat H_G(x)/n=e(V)+O_H_G(x)/n=e(V)+O_beta(h+etalog(2K)).
@@ -831,127 +827,127 @@ This is the energy contribution to the comparison. We next isolate the
entropy paid for the matrix information alone.
The auxiliary reference law.: Start on an enlarged path space
-with an independent uniform spin $x$, the ordinary Gaussian disorder, and
+with an independent uniform spin x, the ordinary Gaussian disorder, and
all unconditioned proposal inputs. Call this the unlinked
experiment. To obtain the actual proposal, multiply the density of the
unlinked experiment by
[
prod_i(1+x_i,m(V,Y_{V,i})).
]
-For fixed $x$, the scalar martingale shows this is a stochastic
+For fixed x, the scalar martingale shows this is a stochastic
exponential with coordinate integrands
[
xi_i(v)=frac{x_i,a(v,Y_{v,i})}{1+x_i,m(v,Y_{v,i})},
- qquad |xi_i(v)|le2,
+ |xi_i(v)|le2,
]
-against the streams $Z_i$ in (eq:4). Call the resulting law the
+against the streams Z_i in (eq:4). Call the resulting law the
linked experiment. Summing the linking density over the uniform
spin shows the path and disorder marginal is unchanged.
-For a continuous local martingale $N$ starting at zero write
-$mathcal E(N)_V=calE(N)_V=exp(N_V-< N>_V/2)$. The linking density
-factors as $E_BE_D$ with
+For a continuous local martingale N starting at zero write
+mathcal E(N)_V=calE(N)_V=exp(N_V-< N>_V/2). The linking density
+factors as E_BE_D with
[
E_B&=mathcal E(calE(sum_iint_0^{cdot}xi_irho,dB_i)_V,
E_D&=mathcal E(calE(sum_iint_0^{cdot}xi_i√(1-rho^2),dD_i)_V,
]
-using the zero quadratic covariation of $B$ and $D$. Define the
-auxiliary reference to have density $E_D$ relative to the unlinked
-law. Its $(G,x)$-marginal is again the independent product of Gaussian
+using the zero quadratic covariation of B and D. Define the
+auxiliary reference to have density E_D relative to the unlinked
+law. Its (G,x)-marginal is again the independent product of Gaussian
disorder and uniform spin. The conditional mean-one assertion behind this
fact needs a filtration check, since the matrix-query endpoints depend on
-the past of $D$.
+the past of D.
-Filtration check.: Let $mathcal A$calA$ contain all primitive
-auxiliary inputs except $D$, and under the unlinked law set
+Filtration check.: Let mathcal AcalA contain all primitive
+auxiliary inputs except D, and under the unlinked law set
[
- mathcal F_v=calF_v=sigma(x,B_{[0,v]},D_{[0,v]}),qquad
+ mathcal F_v=calF_v=sigma(x,B_{[0,v]},D_{[0,v]}),
mathcal G_v=calG_v=sigma(x,G,mathcal A,D_calA,D_{[0,v]}).
]
-Interval by interval, every query direction is determined by past $D$ and
-by information in $mathcal G_0$.calG_0$. Each new endpoint and its entire bridge
-are known before using the current $D$-increment. Deterministic-coefficient
+Interval by interval, every query direction is determined by past D and
+by information in mathcal G_0.calG_0. Each new endpoint and its entire bridge
+are known before using the current D-increment. Deterministic-coefficient
bridge integrals are linear Gaussian integrals with the endpoint term
-fixed by that past. Thus $mathcal F_v⊆calF_v⊆mathcal G_v$.calG_v$. One can
-also see this pathwise: $rho=1$ before $v_*$, and (eq:1) gives
-$-rholerho'le0$ afterward, so $rho$ has bounded variation and the
-identity $intrho,dB=rho B-int B,drho$, applied on successive
-intervals, uses no future $D$.
-
-The pair $(B,D)$ is Brownian in $mathcal F$,calF$, and $D$ is Brownian in
-$mathcal G$calG$ because its time-zero information is independent of $D$. The
-bounded continuous $D$-integrand has the same stochastic integral in
+fixed by that past. Thus mathcal F_v⊆calF_v⊆mathcal G_v.calG_v. One can
+also see this pathwise: rho=1 before v_*, and (eq:1) gives
+-rholerho'le0 afterward, so rho has bounded variation and the
+identity intrho,dB=rho B-int B,drho, applied on successive
+intervals, uses no future D.
+
+The pair (B,D) is Brownian in mathcal F,calF, and D is Brownian in
+mathcal GcalG because its time-zero information is independent of D. The
+bounded continuous D-integrand has the same stochastic integral in
these two filtrations: identical left-endpoint approximations converge in
-$L^2$ by the It^o isometry. The bounded-integrand exponential-martingale
-theorem in $mathcal G$calG$ now gives conditional mean one given
-$(x,G,mathcal A)$,calA)$, proving the claimed marginal. All later Brownian
-changes of measure use $mathcal F$;calF$; no Brownian property for $B$ in the
+L^2 by the It^o isometry. The bounded-integrand exponential-martingale
+theorem in mathcal GcalG now gives conditional mean one given
+(x,G,mathcal A),calA), proving the claimed marginal. All later Brownian
+changes of measure use mathcal F;calF; no Brownian property for B in the
enlarged filtration is required.
Information cost and likelihood.: The density of the linked
-experiment relative to the auxiliary reference is $E_B$, whose logarithm
+experiment relative to the auxiliary reference is E_B, whose logarithm
is
[
L=log E_B=sum_i(int_0^Vxi_irho,dB_i
-tfrac12int_0^Vxi_i^2rho^2,dv).
]
-Under the linked law, compensating the $B_i$-drift by $rhoxi_i$ leaves
-a centered integral with bracket at most $4nV$, so it has
+Under the linked law, compensating the B_i-drift by rhoxi_i leaves
+a centered integral with bracket at most 4nV, so it has
exponential-martingale tails. The remaining half-bracket is a sum of
-independent coordinate variables, each bounded by $2V$. Coordinate
+independent coordinate variables, each bounded by 2V. Coordinate
independence holds after linking because the linking density factors
across the i.i.d. coordinate streams and uniform spins; conditionally on
-the streams through time $v$, the linked spin has probabilities
-$(1pm m(v,Y_{v,i}))/2$. We obtain
+the streams through time v, the linked spin has probabilities
+(1pm m(v,Y_{v,i}))/2. We obtain
- mathbb EbbE L=nj(V),qquad L=nj(V)+O(neta),
+ mathbb EbbE L=nj(V), L=nj(V)+O(neta),
-outside an event of probability at most $exp(-n^{1-4l})$ for large $n$.
+outside an event of probability at most exp(-n^{1-4l}) for large n.
The centered integral is controlled by exponential Markov; the
half-bracket by bounded-variable concentration. The Brownian drift change
follows either from Girsanov's theorem for bounded integrands, or from
bounded predictable step approximation together with the mean-one
exponential identities.
-Changing the reference to $P$.: Change the auxiliary reference a
-second time, multiplying only by the density of $P$ relative to
+Changing the reference to P.: Change the auxiliary reference a
+second time, multiplying only by the density of P relative to
independent disorder and uniform spin. The new reference has
-$(G,x)$-marginal $P$, and the log density of the linked experiment
+(G,x)-marginal P, and the log density of the linked experiment
relative to it is
[
L-nlog2+F(G)-betawidehatwidehat H_G(x).H_G(x).
]
Differentiating the log partition function gives a Gaussian Lipschitz
-constant at most $C_betasqrt n$. The Gaussian concentration inequality
+constant at most C_betasqrt n. The Gaussian concentration inequality
cite[Section~5.4, Theorem~5.6]{BLM2013} together with the pressure bound
(eq:pressure) therefore implies
[
F(G)le nmathcal P+ncalP+neta
]
-outside an event of probability at most $2exp(-c_beta neta^2)$. This
-uses the ordinary Gaussian marginal of $G$, which is unchanged after
+outside an event of probability at most 2exp(-c_beta neta^2). This
+uses the ordinary Gaussian marginal of G, which is unchanged after
linking.
Substituting the scalars.: Insert (eq:scalar-balance),
-(eq:7), $p(V)^2le C_beta e^{-V}$ and (eq:L-conc) into the log
+(eq:7), p(V)^2le C_beta e^{-V} and (eq:L-conc) into the log
density. On the events just proved it is at most
[
C_beta n(h+etalog(2K)+e^{-V})=o(n^{1-l/2}).
]
-Indeed $V=llog n+O(h)$, $log(2K)=O(log n)$, and
-$0<lle1/100<1/16$. The union of the exceptional events has probability
-at most $exp(-n^{1-10l})$ for sufficiently large $n$. Taking the
+Indeed V=llog n+O(h), log(2K)=O(log n), and
+0<lle1/100<1/16. The union of the exceptional events has probability
+at most exp(-n^{1-10l}) for sufficiently large n. Taking the
restricted output marginal gives (eq:6), and its good event is
defined entirely from the inputs of this one proposal run.
The entropy bound.: The same comparison in expectation proves
(eq:5) by contraction of relative entropy under marginalization. The
-exceptional paths contribute negligibly: $L$ has second moment
-$O(n^2(1+V)^2)$, and the supremum of the absolute spin energies has second
-moment $O(n^2)$ by Gaussian tails and a union bound. The log partition
-function is bounded by $nlog2$ plus that energy supremum. Cauchy--Schwarz
+exceptional paths contribute negligibly: L has second moment
+O(n^2(1+V)^2), and the supremum of the absolute spin energies has second
+moment O(n^2) by Gaussian tails and a union bound. The log partition
+function is bounded by nlog2 plus that energy supremum. Cauchy--Schwarz
controls all exceptional contributions. The Gram estimate was already
established.
@@ -960,7 +956,7 @@ established.
# Reversing the entropy: coverage
%======================================================================
-Proposition~prop:proposal controls ${rm KL}(Q_lVert P)$, the
+Proposition~prop:proposal controls {rm KL}(Q_lVert P), the
entropy cost of producing a proposal spin. But entropy in the
forward direction is not enough: a set of large Gibbs mass might still
receive negligible proposal mass, and we will need in
@@ -976,33 +972,33 @@ via the quadratic transport inequality.
For the rest of the proof fix the four exponents
- f=frac1{100},qquad d=frac f{100}=frac1{10000},qquad
- b=frac d{100}=frac1{1000000},qquad delta=n^{-f/4}.
+ f=frac1{100}, d=frac f{100}=frac1{10000},
+ b=frac d{100}=frac1{1000000}, delta=n^{-f/4}.
-The relation $bll dll f$ is the whole hierarchy. The longer horizon
-$l=f$ is used for coverage: it is the one whose proposal mass on Gibbs
-sets will be bounded below. The shorter horizon $l=b$ is reserved for the
+The relation bll dll f is the whole hierarchy. The longer horizon
+l=f is used for coverage: it is the one whose proposal mass on Gibbs
+sets will be bounded below. The shorter horizon l=b is reserved for the
connecting sequence in Section~sec:connections: its exceptional-event
-estimate $exp(-n^{1-10b})$ is far stronger, even though its entropy bound
+estimate exp(-n^{1-10b}) is far stronger, even though its entropy bound
(eq:5) is weaker.
-[Smoothing map $mathcal S$]calS$]
-For any joint law of disorder and spin, let $mathcal S$calS$ retain the spin
+[Smoothing map mathcal S]calS]
+For any joint law of disorder and spin, let mathcal ScalS retain the spin
and replace its disorder by
G^circ=√(1-delta),G+sqrtdelta,barbar G,G,
-where $barbar GGsimgamma$ is independent of everything.
+where barbar GGsimgamma is independent of everything.
-Both $mathcal SP$calSP$ and $mathcal SQ_f$calSQ_f$ have standard Gaussian disorder
-marginal. To generate the conditional spin kernel $nu(cdotmid G^circ)$
-of $mathcal SQ_f$calSQ_f$ given the smoothed disorder, use Gaussian regression:
-given $G^circ$, run the $l=f$ proposal on
+Both mathcal SPcalSP and mathcal SQ_fcalSQ_f have standard Gaussian disorder
+marginal. To generate the conditional spin kernel nu(cdotmid G^circ)
+of mathcal SQ_fcalSQ_f given the smoothed disorder, use Gaussian regression:
+given G^circ, run the l=f proposal on
[
√(1-delta),G^circ+sqrtdelta,G'
]
-with fresh independent standard Gaussian $G'$ and fresh independent
+with fresh independent standard Gaussian G' and fresh independent
auxiliary inputs. This is the conditional law of the proposal given the
smoothed disorder, by the Bayes rule for Gaussian vectors.
@@ -1019,55 +1015,55 @@ The central reverse inequality is the following.
Proof.
The two unsmoothed laws have the same uniform spin marginal (see
-Section~sec:proposal). Given $x$, the conditional disorder density
-of $P$ has negative logarithm, up to a normalizing constant,
+Section~sec:proposal). Given x, the conditional disorder density
+of P has negative logarithm, up to a normalizing constant,
[
U_x(G)=tfrac12|G|^2-betawidehatwidehat H_G(x)+F(G).H_G(x)+F(G).
]
-Its Hessian is at least the identity: the Hamiltonian is linear in $G$
-(hence contributes nothing to the Hessian), and $F$ is a convex
+Its Hessian is at least the identity: the Hamiltonian is linear in G
+(hence contributes nothing to the Hessian), and F is a convex
log-sum-exp of linear functions.
-We use the following consequence of strong convexity. Suppose $mu$ has
-density proportional to $e^{-U}$ with $nabla^2Uge I$, and $lambdallmu$.
-Then there are couplings of $mu,lambda$ whose mean squared displacement
-is at most $2{rm KL}(lambdaVertmu)$ (or tends to that bound). This is
+We use the following consequence of strong convexity. Suppose mu has
+density proportional to e^{-U} with nabla^2Uge I, and lambdallmu.
+Then there are couplings of mu,lambda whose mean squared displacement
+is at most 2{rm KL}(lambdaVertmu) (or tends to that bound). This is
the quadratic transport inequality; the triangular-transport form is
cite[Corollary~3.10]{BKM2005}. We recall the proof for the
finite-dimensional densities used here.
Transport bound on a box. Restrict to a box and suppose both
-densities are smooth and strictly positive up to its boundary. Map $mu$
-to $lambda$ by successive increasing conditional quantile maps. The
-resulting triangular map $T$ has positive diagonal derivatives, whose
+densities are smooth and strictly positive up to its boundary. Map mu
+to lambda by successive increasing conditional quantile maps. The
+resulting triangular map T has positive diagonal derivatives, whose
product is its Jacobian determinant. The entropy formula is
[
{rm KL}(lambdaVertmu)
=int(U(T(z))-U(z)-logdetnabla T(z)),dmu(z).
]
Strong convexity bounds the first difference below by
-$nabla U(z)cdot(T(z)-z)+tfrac12|T(z)-z|^2$. Integration by parts
-replaces the linear term by $div(T-id)$. There is
-no boundary term: on a face where the $i$-th coordinate is an endpoint of
+nabla U(z)cdot(T(z)-z)+tfrac12|T(z)-z|^2. Integration by parts
+replaces the linear term by div(T-id). There is
+no boundary term: on a face where the i-th coordinate is an endpoint of
the box, the conditional quantile map fixes that endpoint, so the normal
-component $T_i-z_i$ vanishes; tangential motion does not matter. The
-Jacobian terms are nonnegative because $z-1-log zge0$ for every positive
-diagonal derivative $z$. This proves the coupling bound on the box.
+component T_i-z_i vanishes; tangential motion does not matter. The
+Jacobian terms are nonnegative because z-1-log zge0 for every positive
+diagonal derivative z. This proves the coupling bound on the box.
-Approximation. For fixed $n$, the conditional proposal density is
+Approximation. For fixed n, the conditional proposal density is
bounded by a constant times a Gaussian density, since its spin probability
is at most one. Truncate both conditional laws to increasing boxes and
-normalize them. On each box, approximate $lambda$ by smoothing and mixing
+normalize them. On each box, approximate lambda by smoothing and mixing
with a small positive constant density; the smooth reference density is
bounded away from zero on the box, so the relative entropies with respect
to the reference converge. The original laws have Gaussian tails up to
-constants for fixed $n$ and finite relative entropy. Thus the truncated
+constants for fixed n and finite relative entropy. Thus the truncated
entropies converge, and tightness plus lower semicontinuity pass the
coupling bound to the original laws.
-Applying to $P$ and $Q_f$. Apply the transport bound with
-$mu=P(cdotmid x)$ and $lambda=Q_f(cdotmid x)$. For any coupling of
-two disorder values $g,widetilde g$, the Gaussian smoothing kernels
+Applying to P and Q_f. Apply the transport bound with
+mu=P(cdotmid x) and lambda=Q_f(cdotmid x). For any coupling of
+two disorder values g,widetilde g, the Gaussian smoothing kernels
satisfy
[
{rm KL}(N(√(1-delta),g,delta I)
@@ -1085,15 +1081,15 @@ transport bound then proves (eq:8).
The smoothed entropy comparison (eq:8) is a joint-law statement. We
now extract a statement for the original Gibbs law at a realized target
-disorder $G$, using only the base $G^circ$ that we also sample. The
+disorder G, using only the base G^circ that we also sample. The
following proposition records both the expected entropy estimate and the
coverage consequence used in the next section.
[Coverage at a target disorder]
-Let $G,barbar G$G$ be independent standard Gaussian disorder vectors, set
-$G^circ=√(1-delta),G+sqrtdelta,barbar G$,G$, and let
-$nu(cdotmid G^circ)$ be the conditional spin kernel of
-$mathcal SQ_f$calSQ_f$ (eq:smoothing). Then
+Let G,barbar GG be independent standard Gaussian disorder vectors, set
+G^circ=√(1-delta),G+sqrtdelta,barbar G,G, and let
+nu(cdotmid G^circ) be the conditional spin kernel of
+mathcal SQ_fcalSQ_f (eq:smoothing). Then
mathbb EbbE,{rm KL}(pi_GVertnu(cdotmid G^circ))
le O_beta(nsqrtdelta)+2n^{1-f/2}/delta .
@@ -1103,62 +1099,62 @@ With probability tending to one over the target/base pair,
{rm KL}(pi_GVertnu(cdotmid G^circ))le n^{1-4d} .
On the same event, simultaneously for every set
-$A⊆{-1,1}^n$ with $pi_G(A)ge n^{-d}$,
+A⊆{-1,1}^n with pi_G(A)ge n^{-d},
nu(Amid G^circ)geexp(-n^{1-2d}).
-The set $A$ may be chosen after the target and base are realized.
+The set A may be chosen after the target and base are realized.
Proof.
-Let $overlinepi(cdotmid G^circ)$ be the conditional spin law of
-$mathcal SP$,calSP$, the conditional mixture of $pi_G$ over the target that
-produced the base $G^circ$. Inserting this law into the logarithmic ratio
+Let overlinepi(cdotmid G^circ) be the conditional spin law of
+mathcal SP,calSP, the conditional mixture of pi_G over the target that
+produced the base G^circ. Inserting this law into the logarithmic ratio
gives the exact decomposition
[
mathbb EbbE,{rm KL}(pi_GVertnu(cdotmid G^circ))
&=mathbb EbbE,{rm KL}(pi_GVert
overlinepi(cdotmid G^circ))
- &quad+{rm KL}(mathcal SPcalSPVertmathcal SQ_f).calSQ_f).
+ &+{rm KL}(mathcal SPcalSPVertmathcal SQ_f).calSQ_f).
]
-Both expectations are over the target/base pair $(G,G^circ)$ of the
+Both expectations are over the target/base pair (G,G^circ) of the
statement. The conditional mixture minimizes averaged divergence among
spin laws depending only on the base, so the first term on the right is
-at most $mathbb EbbE,{rm KL}(pi_GVertpi_{G^circ})$.
+at most mathbb EbbE,{rm KL}(pi_GVertpi_{G^circ}).
-For any two Hamiltonians, the Gibbs divergence is bounded by twice $beta$
+For any two Hamiltonians, the Gibbs divergence is bounded by twice beta
times the supremum of their absolute energy difference. Here those
differences, for each fixed spin, are centered Gaussians of variance
-$O(ndelta)$: the smoothed and unsmoothed disorders differ by coordinate
-strength $O(sqrtdelta)$ on $sqrt n$-scale couplings. A union bound over
-the $2^n$ spins, or an exponential moment argument, bounds the expected
-supremum by $O(nsqrtdelta)$. Combining this estimate with (eq:8)
+O(ndelta): the smoothed and unsmoothed disorders differ by coordinate
+strength O(sqrtdelta) on sqrt n-scale couplings. A union bound over
+the 2^n spins, or an exponential moment argument, bounds the expected
+supremum by O(nsqrtdelta). Combining this estimate with (eq:8)
and (eq:5) proves (eq:9).
-The power-of-$n$ event. Since $4d<f/8$ and $4d<f/4$ (recall
-$d=f/100$ and $f=1/100$), Markov's inequality applied to (eq:9) gives
+The power-of-n event. Since 4d<f/8 and 4d<f/4 (recall
+d=f/100 and f=1/100), Markov's inequality applied to (eq:9) gives
(eq:10) with probability tending to one.
Coverage from the entropy. On the single event (eq:10),
-let $A$ be any set with $pi_G(A)ge n^{-d}$. For $s=pi_G(A)$ and
-$t=nu(Amid G^circ)$, entropy contraction to the two-point partition
-gives $slog(1/t)le{rm KL}(pi_GVertnu)+log2$. Hence
+let A be any set with pi_G(A)ge n^{-d}. For s=pi_G(A) and
+t=nu(Amid G^circ), entropy contraction to the two-point partition
+gives slog(1/t)le{rm KL}(pi_GVertnu)+log2. Hence
[
log(1/t)le n^d(n^{1-4d}+log2)le n^{1-2d}
]
-for sufficiently large $n$. The implication is deterministic once the
+for sufficiently large n. The implication is deterministic once the
target and base are fixed, which proves the simultaneous assertion
(eq:cov).
Note that the coverage bound (eq:cov) deteriorates with
-$d$, but this cost is well within the slack that the mixing argument
-needs. The choice $bll d$ in (eq:exponents) is exactly what makes
+d, but this cost is well within the slack that the mixing argument
+needs. The choice bll d in (eq:exponents) is exactly what makes
the connecting-sequence exception
-$exp(-n^{1-10b})$ in Section~sec:connections smaller than the
-coverage probability $exp(-n^{1-2d})$.
+exp(-n^{1-10b}) in Section~sec:connections smaller than the
+coverage probability exp(-n^{1-2d}).
%======================================================================
# Connecting proposals across a cut
@@ -1172,12 +1168,12 @@ pass near the boundary.
## Setup and statement
-For distinct spins $x,y$, write $c_G(x,y)$ for the heat-bath jump rate and
+For distinct spins x,y, write c_G(x,y) for the heat-bath jump rate and
[
Q_G^{rm edge}(S,S^{rm c})
=sum_{xin S,,ynotin S}pi_G(x),c_G(x,y)
]
-for the stationary flow of the chain across the set $S$. Detailed balance
+for the stationary flow of the chain across the set S. Detailed balance
makes the edge weights symmetric, so this flow is the reversible measure
of the cut; it is also the quantity the mixing Lemma~lem:pruning
of the next section uses.
@@ -1198,62 +1194,62 @@ make this sequence impossible.
## A low-flow cut has a small enlarged boundary
-For a sufficiently large fixed $C$, Gaussian quadratic-form tails on a
-$1/4$-net give $|W(G)|le C$ except with probability $O(e^{-cn})$. On this
-event every one-spin energy difference is $O(sqrt n)$, because flipping a
-single spin changes $x^{mathsf T}sfTWx/2$ by an $O(|W|sqrt n)$ amount. The
+For a sufficiently large fixed C, Gaussian quadratic-form tails on a
+1/4-net give |W(G)|le C except with probability O(e^{-cn}). On this
+event every one-spin energy difference is O(sqrt n), because flipping a
+single spin changes x^{mathsf T}sfTWx/2 by an O(|W|sqrt n) amount. The
heat-bath rate across any one-spin edge is therefore at least
-$exp(-O_beta(sqrt n))$.
+exp(-O_beta(sqrt n)).
-If a cut has stationary flow at most $B_{min}$, then its two-sided vertex
+If a cut has stationary flow at most B_{min}, then its two-sided vertex
boundary
[
∂ S={x:,d_H(x,S)=1 and d_H(x,S^{rm c})=1}
]
-has Gibbs mass at most $2B_{min}exp(O_beta(sqrt n))$, since each
-boundary vertex controls at most $2n$ unit-rate crossings each carrying a
-heat-bath acceptance probability at least $exp(-O_beta(sqrt n))$.
-
-Set $R_n=lceil n^{1-b/4}rceil$ and enlarge $∂ S$ by Hamming
-distance $R_n$. For two spins at Hamming distance at most $R_n$ and with
-$|W(G)|le C$, the logarithmic Gibbs weight ratio is bounded by
-$O_beta(n^{1-b/8})$: the change in $widehatwidehat H_G$H_G$ along any path of
-$R_n$ flips is at most $Csqrt ncdot R_n/sqrt ncdot n^{1/2}=O_beta(n^{1-b/8})$,
-and a Hamming ball of radius $R_n$ has logarithmic cardinality
-$O(n^{1-b/4}log n)$. The enlarged boundary
-$mathcal D_R(G)$calD_R(G)$ therefore has target Gibbs mass at most
+has Gibbs mass at most 2B_{min}exp(O_beta(sqrt n)), since each
+boundary vertex controls at most 2n unit-rate crossings each carrying a
+heat-bath acceptance probability at least exp(-O_beta(sqrt n)).
+
+Set R_n=lceil n^{1-b/4}rceil and enlarge ∂ S by Hamming
+distance R_n. For two spins at Hamming distance at most R_n and with
+|W(G)|le C, the logarithmic Gibbs weight ratio is bounded by
+O_beta(n^{1-b/8}): the change in widehatwidehat H_GH_G along any path of
+R_n flips is at most Csqrt ncdot R_n/sqrt ncdot n^{1/2}=O_beta(n^{1-b/8}),
+and a Hamming ball of radius R_n has logarithmic cardinality
+O(n^{1-b/4}log n). The enlarged boundary
+mathcal D_R(G)calD_R(G) therefore has target Gibbs mass at most
exp(-tfrac12 n^{1-b/20})
-for $n$ large, since $1-b/20<1-b/8$ and $b/20<b/4$.
+for n large, since 1-b/20<1-b/8 and b/20<b/4.
Among cuts violating (eq:11), select the first one in a fixed ordering
-of the subsets of the cube whenever such a cut exists and $|W(G)|le C$.
-Let $mathcal D(G)$calD(G)$ be its enlarged boundary, and set
-$mathcal D(G)=∅$calD(G)=∅$ if no such cut exists or the norm bound fails.
+of the subsets of the cube whenever such a cut exists and |W(G)|le C.
+Let mathcal D(G)calD(G) be its enlarged boundary, and set
+mathcal D(G)=∅calD(G)=∅ if no such cut exists or the norm bound fails.
This is measurable because the cube has finitely many subsets. Let
-$mathcal E$calE$ be the event that a witness cut exists, the target-norm bound
+mathcal EcalE be the event that a witness cut exists, the target-norm bound
holds, and the coverage statement (eq:10) holds for the sampled
-base $G^circ$. The norm and coverage estimates reduce
-(eq:11) to showing $Pr(mathcal E)=o(1)$.calE)=o(1)$.
+base G^circ. The norm and coverage estimates reduce
+(eq:11) to showing Pr(mathcal E)=o(1).calE)=o(1).
## A sequence with independent fine endpoints
-The fine horizon $l=f$ and the coarse horizon $l=b$ serve distinct
+The fine horizon l=f and the coarse horizon l=b serve distinct
purposes.
[leftmargin=*]
-item Fine horizon supplies coverage. On $mathcal E$,calE$, the coverage
+ Fine horizon supplies coverage. On mathcal E,calE, the coverage
statement (eq:cov) gives each side of the cut fine-proposal
- probability at least $exp(-n^{1-2d})$. Two conditionally independent
+ probability at least exp(-n^{1-2d}). Two conditionally independent
fine endpoints therefore cross the cut with probability at least
- $exp(-2n^{1-2d})$.
-item Coarse horizon supplies rare failures. We need an unconditional
+ exp(-2n^{1-2d}).
+ Coarse horizon supplies rare failures. We need an unconditional
bound on the failure probability of the connecting sequence that is
smaller than the endpoint-coverage probability. The fine-horizon
exceptional-event bound of Proposition~prop:proposal is
- $exp(-n^{1-10f})$, which is too weak: $10fgg d$. The coarse bound
- $exp(-n^{1-10b})$ is strong enough, since $10bll dll2d$.
+ exp(-n^{1-10f}), which is too weak: 10fgg d. The coarse bound
+ exp(-n^{1-10b}) is strong enough, since 10bll dll2d.
We therefore use fine spins at the two endpoints for coverage, and
@@ -1261,19 +1257,19 @@ coarse spins along a grid for the connecting sequence. The shared
path prefixes plus the magnetization martingale keep each fine endpoint
close to its coarse output.
-Rotating the inputs.: Given the target $G$ and the base
-$G^circ$ from Section~sec:reverse, introduce independent standard
-Gaussian vectors $G'_1,G'_2$, independent of both, and set
+Rotating the inputs.: Given the target G and the base
+G^circ from Section~sec:reverse, introduce independent standard
+Gaussian vectors G'_1,G'_2, independent of both, and set
G(theta)=√(1-delta),G^circ
+sqrtdelta(costheta,G'_1+sintheta,G'_2),
- qquad 0lethetaletfracpi2 .
+ 0lethetaletfracpi2 .
-Use a deterministic equally spaced grid in $[0,pi/2]$ that includes both
-endpoints, with spacing $O(exp(-n^{1/4}))$ and cardinality
-$O(exp(n^{1/4}))$. Rotate two independent collections of all
+Use a deterministic equally spaced grid in [0,pi/2] that includes both
+endpoints, with spacing O(exp(-n^{1/4})) and cardinality
+O(exp(n^{1/4})). Rotate two independent collections of all
auxiliary Gaussian path inputs by the same cosine-sine rule, so that small
-changes in $theta$ produce small changes in the auxiliary inputs.
+changes in theta produce small changes in the auxiliary inputs.
Running the proposals.: At each grid point, run the coarse
proposal to horizon
@@ -1288,7 +1284,7 @@ and draw a fine spin. Coarse spin draws are not used in any
continuation. All final spin draws may use fresh independent randomness.
Conditional structure.: The two fine endpoints are independent
-conditional on $(G,G^circ)$ and each has law $nu(cdotmid G^circ)$.
+conditional on (G,G^circ) and each has law nu(cdotmid G^circ).
For each individual grid point, averaging over the disorder and
auxiliary inputs on the right side of (eq:rotation) gives the
appropriate proposal law; its primitive auxiliary collection is
@@ -1298,12 +1294,12 @@ grid points. The shared rotation supplies the nearby inputs needed for
continuity along the grid.
We now prove that, outside an event of probability at most
-$exp(-n^{1-d/2})$, the following two properties both hold:
+exp(-n^{1-d/2}), the following two properties both hold:
[label=(alph*)]
-item every coarse spin avoids $mathcal D(G)$;calD(G)$;
-item the sequence consisting of the first fine spin, all coarse spins in
+ every coarse spin avoids mathcal D(G);calD(G);
+ the sequence consisting of the first fine spin, all coarse spins in
grid order, and the last fine spin has consecutive Hamming distances at
- most $R_n$.
+ most R_n.
The probability here is unconditional. Figure~fig:connection shows
the deterministic obstruction that (a) and (b) together create, once we
@@ -1311,16 +1307,16 @@ sample two fine endpoints that provably lie on opposite sides of the cut.
## Avoiding a boundary selected from the target
-At a fixed grid point, the driver difference $G-G(theta)$ has coordinate
-variance $2delta$, by (eq:rotation). Gaussian tails and a union
+At a fixed grid point, the driver difference G-G(theta) has coordinate
+variance 2delta, by (eq:rotation). Gaussian tails and a union
bound over spins show that the supremum of absolute energy differences is
-$O(nsqrtdelta)$, except with probability $O(e^{-cn})$. On the complement,
+O(nsqrtdelta), except with probability O(e^{-cn}). On the complement,
Gibbs weight ratios between the two disorders are at most
-$exp(O_beta(nsqrtdelta))$.
+exp(O_beta(nsqrtdelta)).
-Apply the likelihood estimate (eq:6) with coarse horizon $l=b$. Its
+Apply the likelihood estimate (eq:6) with coarse horizon l=b. Its
good event depends only on this proposal run. If
-$q_{rm good}(dxmid g)$ is the corresponding output subprobability kernel,
+q_{rm good}(dxmid g) is the corresponding output subprobability kernel,
disintegration against the Gaussian disorder marginal gives
q_{rm good}(dxmid g)leexp(n^{1-b/2}),pi_g(dx)
@@ -1328,9 +1324,9 @@ disintegration against the Gaussian disorder marginal gives
The primitive auxiliary inputs and the final spin draw for this run are
independent of all the matrix drivers. Thus, after fixing
-$G(theta)=g$ and adjoining $(G,G^circ)$, this remains the conditional
+G(theta)=g and adjoining (G,G^circ), this remains the conditional
good-output kernel given the past. In particular, the inequality applies
-to the random set $mathcal D(G)$calD(G)$ once those matrices have been fixed.
+to the random set mathcal D(G)calD(G) once those matrices have been fixed.
The separate energy-change event is used only to compare Gibbs weights;
it is not built into the proposal good event.
@@ -1339,10 +1335,10 @@ the energy-change event is at most
[
exp(n^{1-b/2}+O_beta(nsqrtdelta)-tfrac12 n^{1-b/20}).
]
-Add the proposal exceptional probability $exp(-n^{1-10b})$ and the
-energy-change exception. Since $sqrtdelta=n^{-f/8}$ and $f=1/100$, the
-exponent $1-b/20$ dominates both $1-b/2$ and $O_beta(nsqrtdelta)$ for
-large $n$, so this proves the required one-point avoidance bound.
+Add the proposal exceptional probability exp(-n^{1-10b}) and the
+energy-change exception. Since sqrtdelta=n^{-f/8} and f=1/100, the
+exponent 1-b/20 dominates both 1-b/2 and O_beta(nsqrtdelta) for
+large n, so this proves the required one-point avoidance bound.
Correlations with auxiliary inputs at other grid points do not change this
calculation, because the good event depends only on the inputs of the run
at that point.
@@ -1350,56 +1346,56 @@ at that point.
## Continuity of coarse magnetizations
We now control the increments along the grid. At any grid point,
-Proposition~prop:proposal puts the Gram matrix of the coarse $T_k$
-within $n^{-b}$ of the identity except with probability
-$exp(-n^{1-10b})$. On this event all $|T_k|_nle2$, and each
-Gram--Schmidt residual has norm at least $1/2$, so we do not touch
+Proposition~prop:proposal puts the Gram matrix of the coarse T_k
+within n^{-b} of the identity except with probability
+exp(-n^{1-10b}). On this event all |T_k|_nle2, and each
+Gram--Schmidt residual has norm at least 1/2, so we do not touch
the zero-residual fallback of Section~sec:proposal. The reciprocals
-$1/s_k$ are bounded by a fixed power of $n$ on the deterministic coarse
+1/s_k are bounded by a fixed power of n on the deterministic coarse
horizon, by (eq:1).
For neighboring grid points satisfying these Gram conditions, we claim
|M_theta(V_b)-M_{theta'}(V_b)|_n
le(n^{C_1})^{K_b+1},|theta-theta'|,
- qquad K_b=V_b/h,
+ K_b=V_b/h,
provided the primitive inputs have polynomially bounded norms. The
-constant $C_1$ is independent of the grid and of $n$.
+constant C_1 is independent of the grid and of n.
Input bounds.: Bound the operator norms of
-$W(G^circ),W(G'_1),W(G'_2)$ and the normalized norms of all completion
-vectors $z_k$ in the two input collections. For their Brownian and bridge
+W(G^circ),W(G'_1),W(G'_2) and the normalized norms of all completion
+vectors z_k in the two input collections. For their Brownian and bridge
inputs, bound the supremum norms of cumulative integrals against the
-deterministic coefficients $rho$ and $√(1-rho^2)$. On a filled
+deterministic coefficients rho and √(1-rho^2). On a filled
interval include only the centered bridge in this primitive bound; its
-endpoint is handled separately. All these norms are at most $n^3$ outside
-an event of probability $O(e^{-cn})$. Gaussian tails give the matrix and
+endpoint is handled separately. All these norms are at most n^3 outside
+an event of probability O(e^{-cn}). Gaussian tails give the matrix and
vector estimates. For the path integrals, write a bridge as Brownian
motion minus its linearly interpolated endpoint and use the Gaussian
martingale maximal bound for a bounded deterministic integrand. Rotation
(eq:rotation) makes the differences of the primitive inputs at two
-angles at most a polynomial factor times $|theta-theta'|$.
+angles at most a polynomial factor times |theta-theta'|.
Interval induction.: At a Gram--Schmidt step, the difference of
the two projection operators is bounded by twice the sum of preceding
-direction differences in $|cdot|_n$. Normalizing residuals of norm at
-least $1/2$ costs only a fixed factor. Using $1/s_k$, the new direction
+direction differences in |cdot|_n. Normalizing residuals of norm at
+least 1/2 costs only a fixed factor. Using 1/s_k, the new direction
difference is controlled by earlier magnetization and direction
-differences at polynomial cost. The same is true of the new $g_k$, by its
+differences at polynomial cost. The same is true of the new g_k, by its
matrix-query and completion formula (eq:gk). The cumulative driving
signals from (eq:4) differ by the primitive integral differences plus
the endpoint difference multiplied by a deterministic factor at most
-$sqrt h$. Finally, the scalar integral equation (eq:Y) and its
-spatially Lipschitz drift control the differences in $Y$ and $M$ over this
+sqrt h. Finally, the scalar integral equation (eq:Y) and its
+spatially Lipschitz drift control the differences in Y and M over this
interval at constant cost, by Gronwall's inequality. Starting with the
entirely auxiliary first interval and taking successive maxima of these
-differences proves (eq:13) after increasing $C_1$ if necessary.
+differences proves (eq:13) after increasing C_1 if necessary.
Only the Gram conditions at the two endpoints of each grid step were used.
-Since $K_b=O(n^{1/16}log n)$ and the mesh spacing $O(exp(-n^{1/4}))$ is
+Since K_b=O(n^{1/16}log n) and the mesh spacing O(exp(-n^{1/4})) is
exponentially smaller, (eq:13) makes every consecutive coarse
-magnetization difference negligible relative to $n^{-b/3}$.
+magnetization difference negligible relative to n^{-b/3}.
## From magnetizations to spins
@@ -1408,40 +1404,40 @@ coarse magnetization, the normalized squared distance has mean
[
1-mathbb EbbE m_{V_b}^2=p(V_b)le C_beta n^{-b/2},
]
-by $p(V_b)le C_beta e^{-V_b}$ and $V_b=blog n$. For a fine spin this
+by p(V_b)le C_beta e^{-V_b} and V_b=blog n. For a fine spin this
follows from the martingale conditional mean through the continuation.
Under the unconditioned single-run law, each squared distance is an average
of bounded i.i.d. coordinate variables; consequently it is at most
-$n^{-b/3}$ except with probability $O(exp(-n^{1-b}))$. The triangle
-inequality in $|cdot|_n$, along with the negligible magnetization
-increments above, then gives Hamming step sizes at most $R_n$ for large $n$,
-since $n^{-b/3}ll R_n^2/n=n^{1-b/2}/n=n^{-b/2}$.
+n^{-b/3} except with probability O(exp(-n^{1-b})). The triangle
+inequality in |cdot|_n, along with the negligible magnetization
+increments above, then gives Hamming step sizes at most R_n for large n,
+since n^{-b/3}ll R_n^2/n=n^{1-b/2}/n=n^{-b/2}.
Union bound.: We now union bound all one-point and
consecutive-point exceptions for the two desired properties, including the
-primitive-input event. The grid costs only $exp(O(n^{1/4}))$ points, and
-$10b<b/2<d/2$: the boundary exponent $1-b/20$ also exceeds $1-d/2$, since
-$b<d$. The total failure probability is at most $exp(-n^{1-d/2})$ for
-sufficiently large $n$.
+primitive-input event. The grid costs only exp(O(n^{1/4})) points, and
+10b<b/2<d/2: the boundary exponent 1-b/20 also exceeds 1-d/2, since
+b<d. The total failure probability is at most exp(-n^{1-d/2}) for
+sufficiently large n.
## The crossing contradiction
-On $mathcal E$,calE$, the coverage statement (eq:cov) gives each side of
-the chosen cut fine-endpoint probability at least $exp(-n^{1-2d})$.
+On mathcal E,calE, the coverage statement (eq:cov) gives each side of
+the chosen cut fine-endpoint probability at least exp(-n^{1-2d}).
Conditional independence therefore puts the two fine endpoints on opposite
-sides of the cut with probability at least $exp(-2n^{1-2d})$.
+sides of the cut with probability at least exp(-2n^{1-2d}).
But if both sequence properties (a) and (b) hold and the fine endpoints
lie on opposite sides, then some consecutive pair in the sequence must
cross the cut. Each such pair contains a coarse spin. A shortest one-spin
-path between the pair meets $∂ S$ and has length at most $R_n$,
-placing that coarse spin in $mathcal D(G)$.calD(G)$. This contradicts property (a).
+path between the pair meets ∂ S and has length at most R_n,
+placing that coarse spin in mathcal D(G).calD(G). This contradicts property (a).
Consequently
Pr(mathcal E)calE),exp(-2n^{1-2d})leexp(-n^{1-d/2}) .
-Since $d/2<2d$, this implies $Pr(mathcal E)=o(1)$calE)=o(1)$ and proves
+Since d/2<2d, this implies Pr(mathcal E)=o(1)calE)=o(1) and proves
(eq:11). The auxiliary diagonal and smoothing base are used
only in this proof; the resulting flow bound concerns the original heat
bath.
@@ -1461,8 +1457,8 @@ centering
fill[black!3] (-.05,-.75) rectangle (7.3,.9);
fill[blue!3] (7.3,-.75) rectangle (13.5,.9);
draw[densely dotted,black!55] (7.3,-.75) -- (7.3,.9);
- node at (3.6,.63) {$S$};
- node at (10.4,.63) {$S^{mathrm c}rmc$};
+ node at (3.6,.63) {S};
+ node at (10.4,.63) {S^{mathrm c}rmc};
node[fine] (leftfine) at (.65,0) {};
node[coarse] (coarsezero) at (2.5,0) {};
node[coarse] (coarseone) at (4.4,0) {};
@@ -1473,15 +1469,15 @@ centering
draw[black!65] (leftfine) -- (coarsezero) -- (coarseone) -- (crossleft);
draw[black!65] (crossright) -- (coarselast) -- (rightfine);
draw[red!65!black,line width=1.1pt] (crossleft) -- (crossright);
- node[below=1mm] at (leftfine.south) {$x_{rm f}^{(0)}$};
- node[below=1mm] at (rightfine.south) {$x_{rm f}^{(1)}$};
- node[below=1mm] at (crossleft.south) {$u$};
- node[below=1mm] at (crossright.south) {$v$};
- node[fill=white,inner sep=1.5pt] at (7.3,.48) {$d_H(u,v)le R_n$};
+ node[below=1mm] at (leftfine.south) {x_{rm f}^{(0)}};
+ node[below=1mm] at (rightfine.south) {x_{rm f}^{(1)}};
+ node[below=1mm] at (crossleft.south) {u};
+ node[below=1mm] at (crossright.south) {v};
+ node[fill=white,inner sep=1.5pt] at (7.3,.48) {d_H(u,v)le R_n};
node at (6.9,-1.15)
- {Every step has a coarse endpoint; coarse outputs avoid $mathcal D(G)$.}calD(G)$.;
+ {Every step has a coarse endpoint; coarse outputs avoid mathcal D(G).}calD(G).;
node at (7.3,-1.9)
- {Expand the crossing step into single-spin flips: length $ellle R_n$.};
+ {Expand the crossing step into single-spin flips: length ellle R_n.};
draw[densely dotted,black!55] (7.3,-2.25) -- (7.3,-3.35);
node[forced] (pathleft) at (3.8,-2.85) {};
node[boundary] (boundaryleft) at (6.2,-2.85) {};
@@ -1491,27 +1487,17 @@ centering
draw[black!65] (boundaryright) -- (pathright);
draw[red!65!black,line width=1.1pt] (boundaryleft) -- (boundaryright);
node[above=2mm,red!65!black] at (7.3,-2.85) {boundary edge};
- node[below=1mm] at (pathleft.south) {$u=y_0$};
- node[below=1mm] at (boundaryleft.south) {$y_t$};
- node[below=1mm] at (boundaryright.south) {$y_{t+1}$};
- node[below=1mm] at (pathright.south) {$v=y_ell$};
- node at (2.6,-2.85) {$S$};
- node at (12,-2.85) {$S^{mathrm c}rmc$};
+ node[below=1mm] at (pathleft.south) {u=y_0};
+ node[below=1mm] at (boundaryleft.south) {y_t};
+ node[below=1mm] at (boundaryright.south) {y_{t+1}};
+ node[below=1mm] at (pathright.south) {v=y_ell};
+ node at (2.6,-2.85) {S};
+ node at (12,-2.85) {S^{mathrm c}rmc};
node[red!65!black,align=center] at (7.3,-3.8)
- {$d_H(u,∂ S),,d_H(v,∂ S)leellle R_n
- ;⇒; u,vinmathcal D(G)$.}calD(G)$.;
-
-caption{The boundary obstruction for the finite sequence of proposals.
-Squares are fine endpoints, circles are coarse outputs. Consecutive
-configurations in the sequence are at Hamming distance at most $R_n$.
-If the two fine endpoints lie on opposite sides of a cut $S$, some
-consecutive pair $(u,v)$ in the sequence crosses the cut; every pair
-contains a coarse endpoint. Any shortest path of single-spin flips joining
-$u$ to $v$ meets the two-sided boundary $∂ S$, and its length is at
-most $R_n$, so $u$ and $v$ lie in the enlarged boundary $mathcal D(G)$calD(G)$
-used in Section~sec:connections. This contradicts property (a).
-The drawing is schematic: grid outputs are very correlated, and lines do
-not represent continuous spin trajectories.}
+ {d_H(u,∂ S),,d_H(v,∂ S)leellle R_n
+ ;⇒; u,vinmathcal D(G).}calD(G).;
+
+
%----------------------------------------------------------------------
@@ -1526,66 +1512,66 @@ information into a mixing statement about typical fixed starting states.
The finite-state argument below has three steps:
[label=arabic*.,leftmargin=*]
-item Find a set $C$ of large stationary mass with good internal expansion,
+ Find a set C of large stationary mass with good internal expansion,
by repeatedly pruning away subsets that do not expand.
-item On $C$, obtain a Poincar'e inequality from the coarea proof of the
+ On C, obtain a Poincar'e inequality from the coarea proof of the
reversible Cheeger inequality.
-item Use entropy dissipation of the full chain plus stationarity to
- bound the $pi$-average of the fixed-start total variation at time $T$,
+ Use entropy dissipation of the full chain plus stationarity to
+ bound the pi-average of the fixed-start total variation at time T,
and finish with Markov's inequality over the starting state.
-Crucially, the argument never asks a trajectory to stay inside $C$; that
+Crucially, the argument never asks a trajectory to stay inside C; that
is exactly what lets rare slow starting states be excluded later rather
than obstructing the bound.
## The pruning lemma
[Pruning and averaged mixing]
-Let $Ω$ be a finite set, $pi$ a strictly positive probability on
-$Ω$, and $P_t$ a continuous-time Markov semigroup reversible with
-respect to $pi$ with jump rates $c(x,y)$. Assume that for some $R>0$
+Let Ω be a finite set, pi a strictly positive probability on
+Ω, and P_t a continuous-time Markov semigroup reversible with
+respect to pi with jump rates c(x,y). Assume that for some R>0
[
sum_{yne x}c(x,y)le Rqquad(xinΩ).
]
-Let $0<ε<1/3$ and $B>0$. Suppose that
+Let 0<ε<1/3 and B>0. Suppose that
[
Q(S,S^{rm c}):=sum_{xin S,,ynotin S}pi(x)c(x,y)>B
quadwhenever εlepi(S)le1-ε.
]
-Then for every $T>0$,
+Then for every T>0,
sum_{xinΩ}pi(x)bigl|P_T(x,cdot)-pibigr|_{rm TV}
lefrac{√(2R,H(pi))}{Bsqrt T}+2ε,
- qquad H(pi)=-sum_xpi(x)logpi(x).
+ H(pi)=-sum_xpi(x)logpi(x).
Proof.
-Put $q(x,y)=pi(x)c(x,y)=q(y,x)$, and use the unordered-edge Dirichlet form
+Put q(x,y)=pi(x)c(x,y)=q(y,x), and use the unordered-edge Dirichlet form
[
mathfrak D(u)=frakD(u)=sum_{{x,y}}q(x,y)(u(x)-u(y))^2.
]
Only distinct vertices occur, and every unordered pair is counted once.
Step 1: removing sets that do not expand.: Start with
-$C=Ω$. Whenever a nonempty $Usubset C$ satisfies
+C=Ω. Whenever a nonempty Usubset C satisfies
[
- pi(U)lepi(C)/2,qquad Q(U,C∖ U)<Bpi(U),
+ pi(U)lepi(C)/2, Q(U,C∖ U)<Bpi(U),
]
-remove $U$ from $C$. This terminates because each removal eliminates at
-least one vertex. If $A$ denotes all vertices removed so far, then every
-edge between $A$ and its current complement was counted when its first
-endpoint was removed, so whenever $Ane∅$,
+remove U from C. This terminates because each removal eliminates at
+least one vertex. If A denotes all vertices removed so far, then every
+edge between A and its current complement was counted when its first
+endpoint was removed, so whenever Ane∅,
[
Q(A,Ω∖ A)<Bpi(A).
]
-Suppose the removed mass first reached $ε$. Its preceding mass
-$a$ was less than $ε$, and the newly removed set has mass at
-most $(1-a)/2$. The new total is therefore at most
-$(1+a)/2<(1+ε)/2<1-ε$. This contradicts the
-balanced-cut hypothesis, since $Bpi(A)le B$. Consequently the terminal
-set satisfies $pi(C)>1-ε$ and
+Suppose the removed mass first reached ε. Its preceding mass
+a was less than ε, and the newly removed set has mass at
+most (1-a)/2. The new total is therefore at most
+(1+a)/2<(1+ε)/2<1-ε. This contradicts the
+balanced-cut hypothesis, since Bpi(A)le B. Consequently the terminal
+set satisfies pi(C)>1-ε and
Q(U,C∖ U)ge Bpi(U)
quadfor every Usubset C with pi(U)lepi(C)/2 .
@@ -1594,15 +1580,15 @@ set satisfies $pi(C)>1-ε$ and
Step 2: a Poincar'e inequality on the retained set.: Use the
coarea proof of the reversible Cheeger inequality
cite[Theorem~3.5]{LawlerSokal1988}, keeping the original unnormalized
-weights on $C$. The resulting estimate is
+weights on C. The resulting estimate is
sum_{yin C}pi(y)(u(y)-barbar u_C)^2u_C)^2
le(2R)/(B^2),mathfrak D(u),frakD(u),
- qquad barbar u_C=u_C=frac1{pi(C)}sum_{yin C}pi(y)u(y).
+ barbar u_C=u_C=frac1{pi(C)}sum_{yin C}pi(y)u(y).
-To prove it, choose a weighted median $m$ of $u$ on $C$. Each of
-$w=(u-m)_+$ and $w=(m-u)_+$ has support of mass at most $pi(C)/2$.
-Integrating (eq:internal-expansion) over the level sets of $w^2$
+To prove it, choose a weighted median m of u on C. Each of
+w=(u-m)_+ and w=(m-u)_+ has support of mass at most pi(C)/2.
+Integrating (eq:internal-expansion) over the level sets of w^2
gives
[
Bsum_Cpi w^2
@@ -1613,58 +1599,58 @@ By Cauchy--Schwarz this is at most
(sum_{{x,y}subset C}q(x,y)(w(x)-w(y))^2)^{1/2}
(2Rsum_Cpi w^2)^{1/2},
]
-since $(w(x)+w(y))^2le2(w(x)^2+w(y)^2)$ and the total outgoing rate is at
-most $R$. If $sum_Cpi w^2$ vanishes the estimate is immediate; otherwise
+since (w(x)+w(y))^2le2(w(x)^2+w(y)^2) and the total outgoing rate is at
+most R. If sum_Cpi w^2 vanishes the estimate is immediate; otherwise
divide and square. The sum of the energies of the positive and negative
-parts is at most $mathfrak D(u)$.frakD(u)$. The weighted mean minimizes squared
+parts is at most mathfrak D(u).frakD(u). The weighted mean minimizes squared
error, proving (eq:14).
Step 3: entropy dissipation for the full chain.: For a fixed
-starting state $x$, set $f_t^x(y)=P_t(x,y)/pi(y)$. Reversibility together
-with $(a-b)(log a-log b)ge4(sqrt a-sqrt b)^2$ for $a,b>0$ gives the
+starting state x, set f_t^x(y)=P_t(x,y)/pi(y). Reversibility together
+with (a-b)(log a-log b)ge4(sqrt a-sqrt b)^2 for a,b>0 gives the
entropy-dissipation estimate
cite[Lemmas~2.5,~2.7]{DiaconisSaloffCoste1996}
int_0^Tsum_xpi(x),mathfrak D(√(f_t^x))frakD(√(f_t^x)),dt
letfrac14 H(pi).
-Indeed, the derivative of $sum_ypi(y)f_t^x(y)log f_t^x(y)$ is
+Indeed, the derivative of sum_ypi(y)f_t^x(y)log f_t^x(y) is
[
-sum_{{y,z}}q(y,z)
(f_t^x(y)-f_t^x(z))(log f_t^x(y)-log f_t^x(z)).
]
-The initial entropy is $log(1/pi(x))$ and the final entropy is
-nonnegative. Averaging in $xsimpi$ and integrating proves (eq:15).
+The initial entropy is log(1/pi(x)) and the final entropy is
+nonnegative. Averaging in xsimpi and integrating proves (eq:15).
Vanishing densities and reducible chains cause no problem: start with
-$(1-eta)f_0^x+eta$ and pass to $eta↓0$, or calculate on
+(1-eta)f_0^x+eta and pass to eta↓0, or calculate on
communicating classes.
Step 4: averaging fixed-state distances.: Combining (eq:14)
-and (eq:15) supplies some $tin(0,T]$ with
+and (eq:15) supplies some tin(0,T] with
[
sum_xpi(x)r_x^2le(R,H(pi))/(2TB^2),
- quad
+
r_x^2=sum_Cpi(y)(√(f_t^x(y))-a_x)^2,
- quad
+
a_x=frac1{pi(C)}sum_Cpi(y)√(f_t^x(y)) .
]
-Cauchy--Schwarz and $a_x^2pi(C)lesum_Cpi f_t^xle1$ imply
+Cauchy--Schwarz and a_x^2pi(C)lesum_Cpi f_t^xle1 imply
[
sum_Cpi|f_t^x-a_x^2|le2r_x .
]
Also, total normalization gives
-$|sum_Cpi(f_t^x-1)|lesum_{C^{rm c}}pi(f_t^x+1)$.
-Comparing $f_t^x$ first with $a_x^2$ and then with $1$ on $C$, and adding
+|sum_Cpi(f_t^x-1)|lesum_{C^{rm c}}pi(f_t^x+1).
+Comparing f_t^x first with a_x^2 and then with 1 on C, and adding
the complement, yields
[
sum_Ωpi|f_t^x-1|
le4r_x+2sum_{C^{rm c}}pi(f_t^x+1).
]
-The last sum before its factor two has average $2pi(C^{rm c})$ over
-$xsimpi$, because stationarity gives $sum_xpi(x)f_t^x(y)=1$. Dividing
-by two for total variation and applying Cauchy--Schwarz in $x$ proves the
-upper bound at time $t$. Contraction under $P_{T-t}$ gives the same bound
-at the prescribed time $T$, establishing (eq:averaged-mixing).
+The last sum before its factor two has average 2pi(C^{rm c}) over
+xsimpi, because stationarity gives sum_xpi(x)f_t^x(y)=1. Dividing
+by two for total variation and applying Cauchy--Schwarz in x proves the
+upper bound at time t. Contraction under P_{T-t} gives the same bound
+at the prescribed time T, establishing (eq:averaged-mixing).
## Proof of the main theorem
@@ -1673,11 +1659,11 @@ Proof. [Proof of Theorem~thm:main]
On the disorder event of Proposition~prop:cuts, apply
Lemma~lem:pruning to the SK chain with
[
- ε=n^{-d},qquad B=exp(-n^{1-b/20}),qquad R=n .
+ ε=n^{-d}, B=exp(-n^{1-b/20}), R=n .
]
-The last choice is valid because there are exactly $n$ rate-one update
-clocks, so the total jump rate at any vertex is $n$. Also
-$H(pi_G)le nlog2$, since the state space has $2^n$ elements. Hence
+The last choice is valid because there are exactly n rate-one update
+clocks, so the total jump rate at any vertex is n. Also
+H(pi_G)le nlog2, since the state space has 2^n elements. Hence
[
sum_xpi_G(x)bigl|P_T^G(x,cdot)-pi_Gbigr|_{rm TV}
lefrac{√(2log2);n}{Bsqrt T}+2n^{-d}.
@@ -1694,31 +1680,31 @@ Then the first term tends to zero, because
The flow event (eq:11) itself has disorder probability tending to
one. Markov's inequality therefore shows that the Gibbs mass of fixed
-states whose distance at time $T$ exceeds $1/4$ tends to zero in disorder
+states whose distance at time T exceeds 1/4 tends to zero in disorder
probability. The added diagonal changes neither this Gibbs law nor the
-transition rates, so the same statement holds for the model $H^J_n$ in
+transition rates, so the same statement holds for the model H^J_n in
(eq:H). This proves Theorem~thm:main with
[
c_beta=(b)/(40)=frac1{40000000}.
]
-All threshold dimensions may depend on the fixed $beta>1$.
+All threshold dimensions may depend on the fixed beta>1.
## Reading the final exponents
For orientation, here is the chain of inequalities that governs the
-constants, all in the ``$1-exponent$'' scale:
+constants, all in the ``1-exponent'' scale:
[
10b ll b/4 ll b/2 ll b/20 ll d
=100b ll 2dll fll 1 .
]
The two competing probabilities in Section~sec:connections were the
-coverage probability $exp(-2n^{1-2d})$ and the sequence failure
-probability $exp(-n^{1-d/2})$: the ratio of their exponents is $2d$ versus
-$d/2$, and $d/2ll d<2d$ gives the gap. The mixing time $T=exp(n^{1-b/40})$
-sits below both because $b/40ll b/20$, so the exponential
-$exp(-n^{1-b/20})$ flow bound has enough time to accumulate. Nothing here
-is optimized; the only requirement was a positive $b$, and the constants
+coverage probability exp(-2n^{1-2d}) and the sequence failure
+probability exp(-n^{1-d/2}): the ratio of their exponents is 2d versus
+d/2, and d/2ll d<2d gives the gap. The mixing time T=exp(n^{1-b/40})
+sits below both because b/40ll b/20, so the exponential
+exp(-n^{1-b/20}) flow bound has enough time to accumulate. Nothing here
+is optimized; the only requirement was a positive b, and the constants
were chosen in a strict hierarchy to keep every exponent well separated.
%======================================================================
@@ -1726,7 +1712,7 @@ were chosen in a strict hierarchy to keep every exponent well separated.
%======================================================================
{99}
-bibitem{AC2015}
+
A.~Auffinger and W.-K.~Chen,
newblock On properties of Parisi measures,
newblock Probab. Theory Related Fields 161 (2015),
@@ -1734,21 +1720,21 @@ newblock Probab. Theory Related Fields 161 (2015),
newblock doi:10.1007/s00440-014-0563-y;
arXiv:1303.3573v1.
-bibitem{BLO2026}
+
M.~Boban, A.~Li and S.~Oveis Gharan,
newblock Rank-1-perturbed trickledown theorems: mixing time of Glauber
dynamics for the Sherrington--Kirkpatrick model up to
-$betaletfrac12+ε$,
+betaletfrac12+ε,
newblock preprint (2026),
arXiv:2609.13138v1.
-bibitem{BKM2005}
+
V.~I. Bogachev, A.~V. Kolesnikov and K.~V. Medvedev,
newblock Triangular transformations of measures,
newblock Sbornik: Math. 196 (2005), no.~3, 309--335.
newblock doi:10.1070/SM2005v196n03ABEH000882.
-bibitem{Bolthausen2014}
+
E.~Bolthausen,
newblock An iterative construction of solutions of the TAP equations for
the Sherrington--Kirkpatrick model,
@@ -1756,12 +1742,12 @@ newblock Comm. Math. Phys. 325 (2014), 333--366.
newblock doi:10.1007/s00220-013-1862-3;
arXiv:1201.2891.
-bibitem{BLM2013}
+
S.~Boucheron, G.~Lugosi and P.~Massart,
newblock Concentration Inequalities: A Nonasymptotic Theory of
Independence, Oxford University Press, 2013.
-bibitem{Chen2017}
+
W.-K.~Chen,
newblock Variational representations for the Parisi functional and the
two-dimensional Guerra--Talagrand bound,
@@ -1769,13 +1755,13 @@ newblock Ann. Probab. 45 (2017), no.~6A, 3929--3966.
newblock doi:10.1214/16-AOP1154;
arXiv:1501.06635v2.
-bibitem{DiaconisSaloffCoste1996}
+
P.~Diaconis and L.~Saloff-Coste,
newblock Logarithmic Sobolev inequalities for finite Markov chains,
newblock Ann. Appl. Probab. 6 (1996), no.~3, 695--750.
newblock doi:10.1214/aoap/1034968224.
-bibitem{EKZ2022}
+
R.~Eldan, F.~Koehler and O.~Zeitouni,
newblock A spectral condition for spectral gap: fast mixing in
high-temperature Ising models,
@@ -1784,7 +1770,7 @@ nos.~3--4, 1035--1051.
newblock doi:10.1007/s00440-021-01085-x;
arXiv:2007.08200v1.
-bibitem{Guerra2003}
+
F.~Guerra,
newblock Broken replica symmetry bounds in the mean field spin glass
model,
@@ -1792,36 +1778,36 @@ newblock Comm. Math. Phys. 233 (2003), 1--12.
newblock doi:10.1007/s00220-002-0773-5;
arXiv:cond-mat/0205123v1.
-bibitem{JT2017}
+
A.~Jagannath and I.~Tobasco,
-newblock Some properties of the phase diagram for mixed $p$-spin glasses,
+newblock Some properties of the phase diagram for mixed p-spin glasses,
newblock Probab. Theory Related Fields 167 (2017),
615--672.
newblock doi:10.1007/s00440-015-0691-z;
arXiv:1504.02731v2.
-bibitem{LawlerSokal1988}
+
G.~F. Lawler and A.~D. Sokal,
-newblock Bounds on the $L^2$ spectrum for Markov chains and Markov
+newblock Bounds on the L^2 spectrum for Markov chains and Markov
processes: a generalization of Cheeger's inequality,
newblock Trans. Amer. Math. Soc. 309 (1988), no.~2,
557--580.
newblock doi:10.1090/S0002-9947-1988-0930082-9.
-bibitem{Lopatto2026}
+
P.~Lopatto,
newblock Full replica symmetry breaking in the Sherrington--Kirkpatrick
model,
newblock preprint (2026),
arXiv:2607.11756v3.
-bibitem{LugosiNeu2022}
+
G.~Lugosi and G.~Neu,
newblock Generalization bounds via convex analysis,
newblock Proc. Mach. Learn. Res. 178 (2022), 3524--3546.
newblock Proceedings article.
-bibitem{Montanari2021}
+
A.~Montanari,
newblock Optimization of the Sherrington--Kirkpatrick Hamiltonian,
newblock SIAM J. Comput. 54 (2025), no.~4,
@@ -1829,32 +1815,32 @@ FOCS19-1--FOCS19-38 (online 2021).
newblock doi:10.1137/20M132016X;
arXiv:1812.10897v2.
-bibitem{OpenAISKBarriers2026}
+
OpenAI,
newblock Stretched-exponential barriers for typical SK initial states,
newblock
OpenAI Math Release preprint, 2026.
-bibitem{Sellke2025}
+
M.~Sellke,
newblock Exponentially slow mixing of the low temperature SK model,
newblock preprint (2025),
arXiv:2511.22621v2.
-bibitem{SK1975}
+
D.~Sherrington and S.~Kirkpatrick,
newblock Solvable model of a spin-glass,
newblock Phys. Rev. Lett. 35 (1975), no.~26, 1792--1796.
newblock doi:10.1103/PhysRevLett.35.1792.
-bibitem{Wang2026}
+
S.~Wang,
newblock Optimal mixing of Glauber dynamics for the
-Sherrington--Kirkpatrick model at $beta<1/2$,
+Sherrington--Kirkpatrick model at beta<1/2,
newblock preprint (2026),
arXiv:2608.22159v2.
-bibitem{Zhou2026}
+
Y.~Zhou,
newblock Existence of full replica symmetry breaking for the
Sherrington--Kirkpatrick model at low temperature,