diff b34550f..b1f9bc4 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 b2148e0..a601425 100644
--- a/low_temp_sk_glauber_typical_v2.txt
+++ b/low_temp_sk_glauber_typical_v2.txt
@@ -10,35 +10,35 @@
-\usetikzlibrary{arrows.meta,calc,positioning}
+usetikzlibrary{arrows.meta,calc,positioning}
-\allowdisplaybreaks
+allowdisplaybreaks
-# A typical-start upper bound for low-temperature\\Sherrington--Kirkpatrick Glauber dynamics
+# A typical-start upper bound for low-temperatureSherrington--Kirkpatrick Glauber dynamics
-\maketitle
+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
+$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.
-\tableofcontents
+tableofcontents
%======================================================================
# Introduction
@@ -47,15 +47,15 @@ the law would make the distance zero at every time.
## The question in plain terms
The SK model is a mean-field spin glass: $n$ spins
-$\sigma_i\in\{-1,1\}$ interact through random pairwise couplings.
+$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
+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}$.
+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,107 +65,107 @@ 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_0\sim\pi^J_{n,\beta}$? This paper answers the question
-for every fixed $\beta>1$: the chain is fast, at most subexponential in
+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_0\sim\pi^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
+[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
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
+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$.
## The model
-Let $n\ge2$ and let $(J_{ij})_{1\le i<j\le n}$ be independent standard
+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 $\sigma\in\{-1,1\}^n$ set
+configuration $sigmain{-1,1}^n$ set
- H^J_n(\sigma)=\frac1{\sqrt n}\sum_{i<j}J_{ij}\sigma_i\sigma_j,
- \qquad
- \pi^J_{n,\beta}(\sigma)
- =\frac{\exp(\beta H^J_n(\sigma))}{Z^J_{n,\beta}},
+ 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
+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_{j\ne i}J_{ij}\sigma_j .
-\]
-When the clock at site $i$ rings, the new value equals $s\in\{-1,1\}$
+[
+ 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}$
with probability
- \mathbb P\{new spin=s\mid\sigma\}
- =\frac{\exp(\beta s\,h_i(\sigma))}
- {2cosh(\beta h_i(\sigma))} .
+ 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)
- =\inf\Bigl\{t\ge0:
- \bigl\|P_t^{J,\beta}(\sigma,\cdot)-\pi^J_{n,\beta}\bigr\|_{TV}
- \le\tfrac14\Bigr\}
+ T^J_{n,beta}(sigma)
+ =infBigl{tge0:
+ bigl|P_t^{J,beta}(sigma,cdot)-pi^J_{n,beta}bigr|_{TV}
+ letfrac14Bigr}
be the mixing time from that start. The joint law of interest samples
the disorder and one Gibbs configuration,
-$\mathbb P_{J,\,\sigma_0\sim\pi^J_{n,\beta}}
-=\mathbb E_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_\beta\in(0,1)$ such
+For every fixed $beta>1$ there is a constant $c_betain(0,1)$ such
that
-\[
- \mathbb P_{J,\,\sigma_0\sim\pi^J_{n,\beta}}\Bigl\{
- T^J_{n,\beta}(\sigma_0)\le\exp(n^{1-c_\beta})\Bigr\}
+[
+ mathbb P_bbP_{J,,sigma_0simpi^J_{n,beta}}Bigl{
+ T^J_{n,beta}(sigma_0)leexp(n^{1-c_beta})Bigr}
→ 1
- \qquad (n\to∞).
-\]
-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.
+ qquad (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.
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_{J,\,\sigma_0\sim\pi^J_{n,\beta}}\Bigl\{
- \exp(n^{1/10000})<T^J_{n,\beta}(\sigma_0)
- \le\exp(n^{1-1/40000000})\Bigr\}
+[
+ mathbb P_bbP_{J,,sigma_0simpi^J_{n,beta}}Bigl{
+ exp(n^{1/10000})<T^J_{n,beta}(sigma_0)
+ leexp(n^{1-1/40000000})Bigr}
→ 1 .
-\]
+]
Proof.
-The continuous-time form of \cite[Theorem~1.1]{OpenAISKBarriers2026}
+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_0\sim\pi^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.
@@ -174,42 +174,42 @@ probability tending to one.
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
+[label=Stage arabic*.]
+item 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
+item 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,
+ 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
+item 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_l\Vert P)$,
+ 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
+item 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
+ $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
+item 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
@@ -225,92 +225,92 @@ stages at the end of Section~sec:mixing.
## Relation to prior work
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
-Gharan \cite[Corollary~1.6]{BLO2026} extended polynomial worst-start
-mixing in zero field to $\beta<1/2+ε_0$ for some absolute
+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
+Gharan cite[Corollary~1.6]{BLO2026} extended polynomial worst-start
+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
+cite[Theorem~1.1]{Sellke2025} proved exponential worst-start lower
bounds and distinguished the worst-start obstruction from fast mixing
after Gibbs-distributed start. Theorem~thm:main resolves the latter
throughout the fixed low-temperature phase.
Equilibrium Parisi theory. The stationarity conditions that drive
the argument come from the variational theory of the Parisi functional:
-Chen \cite[Theorem~2, Proposition~1]{Chen2017}, Jagannath and Tobasco
-\cite[Proposition~1.1, Corollaries~3.6,~3.10]{JT2017}, and Zhou
-\cite[Theorem~1]{Zhou2026}. For the whole low-temperature phase we use
-full interval support from Lopatto \cite[Theorem~1.1]{Lopatto2026}
-(version~3). Guerra \cite[Theorem~3]{Guerra2003} supplies the pressure
-upper bound, and Auffinger--Chen \cite[Propositions~1--2]{AC2015}
+Chen cite[Theorem~2, Proposition~1]{Chen2017}, Jagannath and Tobasco
+cite[Proposition~1.1, Corollaries~3.6,~3.10]{JT2017}, and Zhou
+cite[Theorem~1]{Zhou2026}. For the whole low-temperature phase we use
+full interval support from Lopatto cite[Theorem~1.1]{Lopatto2026}
+(version~3). Guerra cite[Theorem~3]{Guerra2003} supplies the pressure
+upper bound, and Auffinger--Chen cite[Propositions~1--2]{AC2015}
supplies spatial regularity and step-approximation stability of the
Parisi equation.
Techniques. The Gaussian-query construction is the exact
finite-dimensional analogue of Bolthausen's iterative TAP construction
-\cite[Sections~2--3]{Bolthausen2014} and of Montanari's incremental
-approximate message passing \cite[Sections~2--3]{Montanari2021}: query,
+cite[Sections~2--3]{Bolthausen2014} and of Montanari's incremental
+approximate message passing cite[Sections~2--3]{Montanari2021}: query,
orthogonalize, reveal. The reverse-entropy step uses triangular transport
-under strong convexity \cite[Corollary~3.10]{BKM2005} together with the
-convolution comparison recorded in \cite[Lemma~11]{LugosiNeu2022}. The
+under strong convexity cite[Corollary~3.10]{BKM2005} together with the
+convolution comparison recorded in cite[Lemma~11]{LugosiNeu2022}. The
mixing step combines the coarea proof of the reversible Cheeger
-inequality \cite[Theorem~3.5]{LawlerSokal1988} with entropy dissipation
-for finite Markov chains \cite[Lemmas~2.5,~2.7]{DiaconisSaloffCoste1996}.
+inequality cite[Theorem~3.5]{LawlerSokal1988} with entropy dissipation
+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
-$\mu\ll\nu$ on a common space, set
-${\rm KL}(\mu\Vert\nu)=\int\log(d\mu/d\nu)\,d\mu$. On the spin cube,
-total variation is one half of the $\ell^1$ distance. For vectors
-$v,w\in\mathbb R^n$ write
-\[
- < v,w>_n=\frac1n\sum_i v_i w_i,
- \qquad |v|_n^2=< v,v>_n .
-\]
-The symbols $\|v\|$ and $\|A\|$ denote the Euclidean norm of a vector and
+$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
+[
+ < v,w>_n=frac1nsum_i v_i w_i,
+ qquad |v|_n^2=< v,v>_n .
+]
+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
+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,
-\[
- \tfrac12\,x^{\mathsf T}diag(W)\,x
- =\tfrac12\sum_i W_{ii}
-\]
+$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 E F(G)$ is a deterministic constant that
-we absorb into the pressure functional $\mathcal P$ 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 P$calP$ below.
Gibbs weights on the completed matrix.: Define, with $W=W(G)$,
-\[
- \widehat H_G(x)=\tfrac12 x^{\mathsf T}W(G)\,x,
- \quad
- F(G)=\log\sum_{x\in\{-1,1\}^n}e^{\beta\widehat H_G(x)},
- \quad
- \pi_G(x)=e^{\beta\widehat H_G(x)-F(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
-$\widehat H_G$ everywhere. The Gibbs joint law of disorder and spin is
-\[
- P(dG,x)=\gamma(dG)\,\pi_G(dx).
-\]
+$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
+[
+ 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
@@ -331,126 +331,126 @@ 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 E F(G)\le n\mathcal P$, where
- $\mathcal P$ is the Parisi pressure functional, whose exact
+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
normalization we give below.
-\item Regularity and stability. Auffinger--Chen
- \cite[Propositions~1--2]{AC2015}: the scalar Parisi equation has
+item 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
- \cite[Theorem~1.1, Lemma~2.2, Proposition~2.4, Lemma~2.5]{Lopatto2026}:
+ approximation of the CDF of $mu_beta$.
+item 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_*],qquad 0<q_*<1,
+ ]
and the associated scalar solution obeys the stationarity identity used
in (eq:martingale) below.
The stationarity identity is also given, in the form we quote, in
-Jagannath--Tobasco \cite[Proposition~1.1, Corollaries~3.6,~3.10]{JT2017}.
+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.
## 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
-$0\le v\le\beta^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_v\Phi_y^2),
- \qquad
- \Phi(\beta^2,y)=\log(2cosh y),
+ 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
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=\Phi(0,0)-\frac1{2\beta^2}\int_0^{\beta^2}v\alpha_v\,dv,
- \qquad
- \mathbb E F(G)\le n\mathcal P .
+ 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$ nor $\mathbb E F(G)$
-in any way that matters below. Since $\alpha_v=1$ above $v_*$, the
+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_*$,
- \Phi(v_*,y)=\log(2cosh y)+(\beta^2-v_*)/(2) .
+ 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
- \Phi(v,y)=\log(2cosh y)+(\beta^2-v)/(2),
- \qquad \alpha_v=1 .
+ Phi(v,y)=log(2cosh y)+(beta^2-v)/(2),
+ qquad alpha_v=1 .
-This agrees with the original solution up to $\beta^2$ and satisfies the
-same PDE for every $v\ge 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 $v\ge0$
+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),qquad 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$.
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,qquad 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
-It\^o's formula give the key scalar facts
+It^o's formula give the key scalar facts
- m_0=0,\qquad dm_v=a_v\,dZ_v,\qquad
- \mathbb E m_v^2=(v)/(\beta^2)\quad(0\le v\le v_*),
+ m_0=0,qquad dm_v=a_v,dZ_v,qquad
+ mathbb EbbE m_v^2=(v)/(beta^2)quad(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)^2\le1,\qquad |m(v,y)|<1 .
+ 0<a(v,y)le1-m(v,y)^2le1,qquad |m(v,y)|<1 .
-\paragraph{Why (eq:a-m-bound) holds.} We derive it in the form that
+paragraph{Why (eq:a-m-bound) holds.} We derive it in the form that
behaves well under step approximation. One Parisi step of CDF height
-$\lambda\in[0,1]$ and variance $\delta>0$ maps a profile $f$ to
-\[
- (Tf)(y)=\frac1\lambda\log\mathbb E\,
- e^{\lambda f(y+\sqrt\delta U)},\qquad U\sim N(0,1),
-\]
-with $Tf(y)=\mathbb E f(y+\sqrt\delta U)$ when $\lambda=0$. Write
-$\mathbb E_\lambda$ for the Gaussian expectation tilted by
-$e^{\lambda f(y+\sqrt\delta U)}$ and renormalized. Differentiating gives
+$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),
+]
+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_\lambda f',\qquad
- (Tf)''=\mathbb E_\lambda f''+\lambdaVar_\lambda(f') .
-\]
-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;
-stability \cite[Propositions~1--2]{AC2015} passes the non-strict bound to
-the minimizing CDF, and the strict lower bound on $\Phi_{yy}$ in
-\cite[Proposition~2.4]{Lopatto2026} gives strict positivity in the limit.
+[
+ (Tf)'=mathbb E_bbE_lambda f',qquad
+ (Tf)''=mathbb E_bbE_lambda f''+lambdaVar_lambda(f') .
+]
+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;
+stability cite[Propositions~1--2]{AC2015} passes the non-strict bound to
+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
(eq:a-m-bound). On the extension these assertions follow from
$tanh$ directly.
@@ -459,49 +459,49 @@ $tanh$ directly.
Define the three deterministic functions
- p(v)=\mathbb E a_v,\qquad r(v)=\mathbb E a_v^2,
- \qquad \rho(v)=\beta√(r(v)) .
+ p(v)=mathbb EbbE a_v,qquad r(v)=mathbb EbbE a_v^2,
+ qquad 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
+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 $v\ge v_*$ the extended diffusion obeys
+For $vge v_*$ the extended diffusion obeys
- \rho(v)\le1,\qquad -2\le(\log r)'(v)\le0,
- \qquad p'(v)=-r(v),
- \qquad p(v)\le C_\beta e^{-v/2} .
+ rho(v)le1,qquad -2le(log r)'(v)le0,
+ qquad p'(v)=-r(v),
+ qquad p(v)le C_beta e^{-v/2} .
At $v=v_*$ the derivatives are from the right.
Proof.
We use the transformed-density method of
-\cite[Proposition~7.1]{Lopatto2026} and the moment comparison of
-\cite[Proposition~9.3]{Lopatto2026}, which together give the required
+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
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
+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
density on one interval is
-\[
- K_j(z,y)=\varphi_{v_{j+1}-v_j}(y-z)
- \exp\bigl\{\alpha^{(j)}[\Phi(v_{j+1},y)-\Phi(v_j,z)]\bigr\} .
-\]
+[
+ 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
+$alpha^{(j)}Phi_y$. In a product of kernels the intermediate factors at
$y_j$ reduce to
-\[
- \exp\bigl\{-(\alpha^{(j)}-\alpha^{(j-1)})\Phi(v_j,y_j)\bigr\},
-\]
+[
+ 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
+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
@@ -514,83 +514,83 @@ 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
nonnegative covariance. Integration by parts gives
-\[
- \frac{\int_{\mathbb R}sech^{k+2}y\,dy}
- {\int_{\mathbb R}sech^{k}y\,dy}
- =(k)/(k+1)\qquad(k>0).
-\]
-Consequently $r/p\ge1/2$ and $\mathbb E a_v^3/r(v)\ge3/4$.
+[
+ frac{int_{mathbb R}bbRsech^{k+2}y,dy}
+ {int_{mathbb R}bbRsech^{k}y,dy}
+ =(k)/(k+1)qquad(k>0).
+]
+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
-direct It\^o calculations yield
-\[
- p'=-r,\qquad r'=4r-6\,\mathbb E a_v^3 .
-\]
-The two moment ratios imply $p'\le-p/2$ and $r'\le0$. Since
-$0<a_v\le1$, 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 $\rho\le1$.
+direct It^o calculations yield
+[
+ p'=-r,qquad 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 entropy--energy identity
-Let $\mathcal H(z)$ be the entropy of a sign with mean $z\in(-1,1)$:
-\[
- \mathcal H(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
+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
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)=\frac12\int_0^V\rho(v)^2\,
- \mathbb E(a_v^2)/(1-m_v^2)\,dv .
+ 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
-introduce in the proposal. Below the support endpoint, It\^o's formula
+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_{v_*}m_{v_*}]=\int_0^{v_*}(p(v)+\alpha_v v/\beta^2)\,dv,
- \qquad
- \mathbb E\Phi(v_*,Y_{v_*})=\Phi(0,0)
- +\frac12\int_0^{v_*}\alpha_v v/\beta^2\,dv .
-\]
+[
+ 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(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 E\,\mathcal H(m_{v_*})
- =\mathcal P-(\beta^2)/(4)(1-q_*)^2 .
+ 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_*$,
- \log2-j(V)+\beta e(V)=\mathcal P-(\beta^2)/(4)\,p(V)^2 .
+ log2-j(V)+beta e(V)=mathcal P-(calP-(beta^2)/(4),p(V)^2 .
Proof.
The same martingale calculation applied to binary entropy yields
-\[
- \frac12\int_0^{v_*}\mathbb E(a_v^2)/(1-m_v^2)\,dv
- =\log2-\mathbb E\,\mathcal H(m_{v_*}).
-\]
-Localization justifies It\^o's formula near $z=\pm1$; the integrand is
-bounded because $a\le1-m^2$. Since $\rho=1$ and $\beta\sqrt r=1$ on
+[
+ 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_*$
+(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
+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.
%======================================================================
@@ -608,8 +608,8 @@ the resulting law $Q_l$ and its likelihood outside a small exceptional
event.
The spirit is the same as Bolthausen's iterative TAP construction
-\cite[Sections~2--3]{Bolthausen2014} and Montanari's incremental
-approximate message passing \cite[Sections~2--3]{Montanari2021}, both of
+cite[Sections~2--3]{Bolthausen2014} and Montanari's incremental
+approximate message passing cite[Sections~2--3]{Montanari2021}, both of
which reveal Gaussian information along orthogonalized directions. What
is new here is the exact conditional-law bookkeeping for a finite
mesh, including the independent auxiliary noises that complete each
@@ -617,53 +617,53 @@ increment.
## Construction and conditional Gaussian laws
-Mesh.: Fix a horizon parameter\footnote{We use the letter
+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<l\le1/100$ and set
+$0<lle1/100$ and set
- h=n^{-1/16},\qquad K=\lceil l\log n/h\rceil,\qquad
- t_k=kh,\qquad V=t_K .
+ h=n^{-1/16},qquad K=lceil llog n/hrceil,qquad
+ t_k=kh,qquad V=t_K .
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
+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 .
+ 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 $\rho\le1$ equals
+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$
entirely from independent auxiliary Brownian noise. For each subsequent
-interval $[t_k,t_{k+1}]$, $1\le 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} .
+ 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} .
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}$.
+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
g_k=h^{-1/2}(B(t_{k+1})-B(t_k))
- =\Pi_{>k}Wu_k+\Pi_{\le k}z_k .
+ =Pi_{>k}Wu_k+Pi_{le k}z_k .
Fill the interval by linear interpolation between its endpoints plus an
independent centered Brownian bridge. Every new bridge and completion
@@ -672,7 +672,7 @@ path may equivalently be obtained by conditioning Brownian motion on its
endpoint.
The spin.: At time $V$, given the path, draw the coordinates
-$x_i\in\{-1,1\}$ independently with means $M_i(V)$. Let $Q_l$ be the
+$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
@@ -680,15 +680,15 @@ 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,
+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
-\[
- d_k=< u_k,Wu_k>_n\sim N(0,2/n)
-\]
+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.
@@ -708,63 +708,63 @@ 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.
[Proposal comparison]
-For every fixed $0<l\le1/100$ and all sufficiently large $n$,
+For every fixed $0<lle1/100$ and all sufficiently large $n$,
- {\rm KL}(Q_l\Vert P)\le2n^{1-l/2} .
+ {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
+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 .
+ 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
the identity in operator norm, except with probability at most
-$\exp(-n^{1-10l})$. The dimension from which all this holds may depend on
+$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$ ($1\le k<K$) and $x$. It is an
+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^2\ge c_\beta h\,e^{-2V},
+ 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
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
-\[
- 2\exp(-c_\beta n\eta^2e^{-4V}).
-\]
-A $1/4$-net of the unit sphere in dimension $O(K)$ has $\exp(O(K))$
+[
+ 2exp(-c_beta neta^2e^{-4V}).
+]
+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]_{\rm row}=\mathbf1_{j=k},\quad
- \mathbb E[T_jg_k]_{\rm row}=0\ (j\le k),\quad
- \mathbb E[T_kx]_{\rm row}=s_k,\quad
- \mathbb E[g_kx]_{\rm row}=b_k,
+ 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[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
norm at most one, by projection of the unit-variance spin onto the
@@ -772,60 +772,60 @@ 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 $m\times m$ matrix costs at most $C\log(2m)$ in
+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\|\le\eta<1/2$, and let
-$R^{\mathsf T}R=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}\dot 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 C\eta\log(2m).
-\]
+[
+ |R-I|le Cetalog(2m).
+]
(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
-\[
+[
- \|c-s\|&\le C\eta\log(2K),\\
- \left\|(\mathbf1_{j\le k}< u_j,g_k>_n)_{jk}\right\|
- &\le C\eta\log(2K),\\
- \bigl\|(< g_k,x>_n)_k-b\bigr\|&\le\eta .
+ |c-s|&le Cetalog(2K),
+ left|(mathbf1_bf1_{jle k}< u_j,g_k>_n)_{jk}right|
+ &le Cetalog(2K),
+ bigl|(< g_k,x>_n)_k-bbigr|&leeta .
-\]
+]
The middle estimate uses that left multiplication of the population cross
-matrix by the lower-triangular $R^{-\mathsf T}$ 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{\widehat H_G(x)}n
- =\sum_kc_k< x,\Pi_{>k}g_k>_n
- +\tfrac12\sum_kc_k^2d_k
- +\tfrac12< x,H_0WH_0x>_n .
-\]
-The last two terms are $O(\eta)$ outside an event of probability at most
-$CK\exp(-cn\eta^2)$: the diagonal estimate follows from the conditional
-Gaussian law and $\sum c_k^2\le1$, while the residual term uses that the
+[
+ frac{widehatwidehat H_G(x)}H_G(x)n
+ =sum_kc_k< x,Pi_{>k}g_k>_n
+ +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
spin has not seen the unrevealed block. Removing the projections in the
-first term costs at most $C\eta\log(2K)$ by the triangular bound. Its
-remaining value is $s\cdot b$ up to the same error. The bound on
-$(\log r)'$ in (eq:1) implies $s_k/\sqrt h$ differs from
+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 $s\cdot b=e(V)+O_\beta(h)$,
+interval contributes $O(h)$, and $e(V)$ is bounded. Hence $scdot b=e(V)+O_beta(h)$,
and altogether
- \widehat H_G(x)/n=e(V)+O_\beta(h+\eta\log(2K)).
+ widehatwidehat H_G(x)/n=e(V)+O_H_G(x)/n=e(V)+O_beta(h+etalog(2K)).
This is the energy contribution to the comparison. We next isolate the
entropy paid for the matrix information alone.
@@ -835,28 +835,28 @@ 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})).
-\]
+[
+ prod_i(1+x_i,m(V,Y_{V,i})).
+]
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)=frac{x_i,a(v,Y_{v,i})}{1+x_i,m(v,Y_{v,i})},
+ qquad |xi_i(v)|le2,
+]
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=\exp(N_V-< N>_V/2)$. The linking density
+$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(\sum_i\int_0^{\cdot}\xi_i\rho\,dB_i)_V,\\
- E_D&=\mathcal E(\sum_i\int_0^{\cdot}\xi_i√(1-\rho^2)\,dD_i)_V,
+ 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
@@ -864,51 +864,51 @@ 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$.
-Filtration check.: Let $\mathcal A$ contain all primitive
+Filtration check.: Let $mathcal A$calA$ contain all primitive
auxiliary inputs except $D$, and under the unlinked law set
-\[
- \mathcal F_v=\sigma(x,B_{[0,v]},D_{[0,v]}),\qquad
- \mathcal G_v=\sigma(x,G,\mathcal A,D_{[0,v]}).
-\]
+[
+ mathcal F_v=calF_v=sigma(x,B_{[0,v]},D_{[0,v]}),qquad
+ 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$. Each new endpoint and its entire bridge
+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⊆\mathcal G_v$. One can
-also see this pathwise: $\rho=1$ before $v_*$, and (eq:1) gives
-$-\rho\le\rho'\le0$ afterward, so $\rho$ has bounded variation and the
-identity $\int\rho\,dB=\rho B-\int B\,d\rho$, applied on successive
+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$, and $D$ is Brownian in
-$\mathcal G$ because its time-zero information is independent of $D$. The
+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
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$ now gives conditional mean one given
-$(x,G,\mathcal A)$, proving the claimed marginal. All later Brownian
-changes of measure use $\mathcal F$; no Brownian property for $B$ in the
+$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
enlarged filtration is required.
Information cost and likelihood.: The density of the linked
experiment relative to the auxiliary reference is $E_B$, whose logarithm
is
-\[
- L=\log E_B=\sum_i(\int_0^V\xi_i\rho\,dB_i
- -\tfrac12\int_0^V\xi_i^2\rho^2\,dv).
-\]
-Under the linked law, compensating the $B_i$-drift by $\rho\xi_i$ leaves
+[
+ 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
exponential-martingale tails. The remaining half-bracket is a sum of
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
-$(1\pm m(v,Y_{v,i}))/2$. We obtain
+$(1pm m(v,Y_{v,i}))/2$. We obtain
- \mathbb E L=nj(V),\qquad L=nj(V)+O(n\eta),
+ mathbb EbbE L=nj(V),qquad 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
@@ -920,29 +920,29 @@ 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
relative to it is
-\[
- L-n\log2+F(G)-\beta\widehat H_G(x).
-\]
+[
+ L-nlog2+F(G)-betawidehatwidehat H_G(x).H_G(x).
+]
Differentiating the log partition function gives a Gaussian Lipschitz
-constant at most $C_\beta\sqrt n$. The Gaussian concentration inequality
-\cite[Section~5.4, Theorem~5.6]{BLM2013} together with the pressure bound
+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 n\mathcal P+n\eta
-\]
-outside an event of probability at most $2\exp(-c_\beta n\eta^2)$. This
+[
+ 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
linking.
Substituting the scalars.: Insert (eq:scalar-balance),
-(eq:7), $p(V)^2\le 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+\eta\log(2K)+e^{-V})=o(n^{1-l/2}).
-\]
-Indeed $V=l\log n+O(h)$, $\log(2K)=O(\log n)$, and
-$0<l\le1/100<1/16$. The union of the exceptional events has probability
-at most $\exp(-n^{1-10l})$ for sufficiently large $n$. Taking the
+[
+ 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
restricted output marginal gives (eq:6), and its good event is
defined entirely from the inputs of this one proposal run.
@@ -951,7 +951,7 @@ The entropy bound.: The same comparison in expectation proves
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 $n\log2$ plus that energy supremum. Cauchy--Schwarz
+function is bounded by $nlog2$ plus that energy supremum. Cauchy--Schwarz
controls all exceptional contributions. The Gram estimate was already
established.
@@ -960,7 +960,7 @@ established.
# Reversing the entropy: coverage
%======================================================================
-Proposition~prop:proposal controls ${\rm KL}(Q_l\Vert 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,32 +976,32 @@ 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},qquad d=frac f{100}=frac1{10000},qquad
+ b=frac d{100}=frac1{1000000},qquad delta=n^{-f/4}.
-The relation $b\ll d\ll f$ is the whole hierarchy. The longer horizon
+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$]
-For any joint law of disorder and spin, let $\mathcal S$ retain the spin
+[Smoothing map $mathcal S$]calS$]
+For any joint law of disorder and spin, let $mathcal S$calS$ retain the spin
and replace its disorder by
- G^\circ=√(1-\delta)\,G+\sqrt\delta\,\bar G,
+ G^circ=√(1-delta),G+sqrtdelta,barbar G,G,
-where $\bar G\sim\gamma$ is independent of everything.
+where $barbar GGsimgamma$ is independent of everything.
-Both $\mathcal SP$ and $\mathcal SQ_f$ have standard Gaussian disorder
-marginal. To generate the conditional spin kernel $\nu(\cdot\mid G^\circ)$
-of $\mathcal SQ_f$ given the smoothed disorder, use Gaussian regression:
-given $G^\circ$, run the $l=f$ proposal on
-\[
- √(1-\delta)\,G^\circ+\sqrt\delta\,G'
-\]
+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
+[
+ √(1-delta),G^circ+sqrtdelta,G'
+]
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.
@@ -1012,8 +1012,8 @@ The central reverse inequality is the following.
[Smoothing reverses KL]
- {\rm KL}(\mathcal SP\Vert\mathcal SQ_f)
- \le\delta^{-1}\,{\rm KL}(Q_f\Vert P) .
+ {rm KL}(mathcal SPcalSPVertmathcal SQ_f)calSQ_f)
+ ledelta^{-1},{rm KL}(Q_fVert P) .
@@ -1021,43 +1021,43 @@ 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,
-\[
- U_x(G)=\tfrac12\|G\|^2-\beta\widehat H_G(x)+F(G).
-\]
+[
+ 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
log-sum-exp of linear functions.
-We use the following consequence of strong convexity. Suppose $\mu$ has
-density proportional to $e^{-U}$ with $\nabla^2U\ge I$, and $\lambda\ll\mu$.
-Then there are couplings of $\mu,\lambda$ whose mean squared displacement
-is at most $2{\rm KL}(\lambda\Vert\mu)$ (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
+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
+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}(\lambda\Vert\mu)
- =\int(U(T(z))-U(z)-\log\det\nabla T(z))\,d\mu(z).
-\]
+[
+ {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
+$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 z\ge0$ for every positive
+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
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
@@ -1066,16 +1066,16 @@ 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(\cdot\mid x)$ and $\lambda=Q_f(\cdot\mid x)$. For any coupling of
-two disorder values $g,\widetilde g$, the Gaussian smoothing kernels
+$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)
- \Vert N(√(1-\delta)\,\widetilde g,\delta I))
- =(1-\delta)/(2\delta)\|g-\widetilde g\|^2 .
-\]
+[
+ {rm KL}(N(√(1-delta),g,delta I)
+ Vert N(√(1-delta),widetilde g,delta I))
+ =(1-delta)/(2delta)|g-widetilde g|^2 .
+]
The convolution comparison is also recorded in
-\cite[Lemma~11]{LugosiNeu2022}. Joint convexity of entropy bounds the
+cite[Lemma~11]{LugosiNeu2022}. Joint convexity of entropy bounds the
divergence between the mixtures by this averaged kernel quantity. Average
over the common spin marginal and use the entropy chain rule. The
transport bound then proves (eq:8).
@@ -1085,56 +1085,56 @@ 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,\bar G$ be independent standard Gaussian disorder vectors, set
-$G^\circ=√(1-\delta)\,G+\sqrt\delta\,\bar G$, and let
-$\nu(\cdot\mid G^\circ)$ be the conditional spin kernel of
-$\mathcal SQ_f$ (eq:smoothing). Then
+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
- \mathbb E\,{\rm KL}(\pi_G\Vert\nu(\cdot\mid G^\circ))
- \le O_\beta(n\sqrt\delta)+2n^{1-f/2}/\delta .
+ mathbb EbbE,{rm KL}(pi_GVertnu(cdotmid G^circ))
+ le O_beta(nsqrtdelta)+2n^{1-f/2}/delta .
With probability tending to one over the target/base pair,
- {\rm KL}(\pi_G\Vert\nu(\cdot\mid G^\circ))\le n^{1-4d} .
+ {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(A\mid G^\circ)\ge\exp(-n^{1-2d}).
+ nu(Amid G^circ)geexp(-n^{1-2d}).
The set $A$ may be chosen after the target and base are realized.
Proof.
-Let $\overline\pi(\cdot\mid G^\circ)$ be the conditional spin law of
-$\mathcal SP$, 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 E\,{\rm KL}(\pi_G\Vert\nu(\cdot\mid G^\circ))
- &=\mathbb E\,{\rm KL}(\pi_G\Vert
- \overline\pi(\cdot\mid G^\circ))\\
- &\quad+{\rm KL}(\mathcal SP\Vert\mathcal SQ_f).
+ 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).
-\]
-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 E\,{\rm KL}(\pi_G\Vert\pi_{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(n\delta)$: the smoothed and unsmoothed disorders differ by coordinate
-strength $O(\sqrt\delta)$ on $\sqrt n$-scale couplings. A union bound over
+$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(n\sqrt\delta)$. Combining this estimate with (eq:8)
+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
@@ -1142,12 +1142,12 @@ $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(A\mid G^\circ)$, entropy contraction to the two-point partition
-gives $s\log(1/t)\le{\rm KL}(\pi_G\Vert\nu)+\log2$. Hence
-\[
- \log(1/t)\le n^d(n^{1-4d}+\log2)\le n^{1-2d}
-\]
+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
target and base are fixed, which proves the simultaneous assertion
(eq:cov).
@@ -1155,10 +1155,10 @@ target and base are fixed, which proves the simultaneous assertion
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 $b\ll d$ in (eq:exponents) is exactly what makes
+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
@@ -1173,10 +1173,10 @@ pass near the boundary.
## Setup and statement
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_{x\in S,\,y\notin S}\pi_G(x)\,c_G(x,y)
-\]
+[
+ 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
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
@@ -1185,9 +1185,9 @@ of the next section uses.
[Balanced-cut flow]
With probability tending to one in the target disorder,
- Q_G^{\rm edge}(S,S^{\rm c})>B_{\min}:=\exp(-n^{1-b/20})
- \quadfor every S with
- \min(\pi_G(S),\pi_G(S^{\rm c}))\ge n^{-d}.
+ Q_G^{rm edge}(S,S^{rm c})>B_{min}:=exp(-n^{1-b/20})
+ quadfor every S with
+ min(pi_G(S),pi_G(S^{rm c}))ge n^{-d}.
@@ -1199,43 +1199,43 @@ 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}Wx/2$ by an $O(\|W\|\sqrt n)$ amount. The
+$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
+[
+ ∂ 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))$.
+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
+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 $\widehat H_G$ along any path of
-$R_n$ flips is at most $C\sqrt n\cdot R_n/\sqrt n\cdot n^{1/2}=O_\beta(n^{1-b/8})$,
+$|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)$ therefore has target Gibbs mass at most
+$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})
+ exp(-tfrac12 n^{1-b/20})
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)$ be its enlarged boundary, and set
-$\mathcal D(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$ be the event that a witness cut exists, the target-norm bound
+$mathcal E$calE$ 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)$.
+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
@@ -1243,17 +1243,17 @@ The fine horizon $l=f$ and the coarse horizon $l=b$ serve distinct
purposes.
[leftmargin=*]
-\item Fine horizon supplies coverage. On $\mathcal E$, the coverage
+item 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})$.
+item 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: $10f\gg d$. The coarse bound
- $\exp(-n^{1-10b})$ is strong enough, since $10b\ll d\ll2d$.
+ $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
@@ -1262,33 +1262,33 @@ 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
+$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
- +\sqrt\delta(\cos\theta\,G'_1+\sin\theta\,G'_2),
- \qquad 0\le\theta\le\tfrac\pi2 .
+ G(theta)=√(1-delta),G^circ
+ +sqrtdelta(costheta,G'_1+sintheta,G'_2),
+ qquad 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
-\[
- V_b=h\lceil b\log n/h\rceil
-\]
+[
+ V_b=hlceil blog n/hrceil
+]
and draw its coarse spin. At each endpoint, also continue the path to
-\[
- V_f=h\lceil f\log n/h\rceil
-\]
+[
+ V_f=hlceil flog n/hrceil
+]
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(\cdot\mid 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,10 +1298,10 @@ 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:
-[label=(\alph*)]
-\item every coarse spin avoids $\mathcal D(G)$;
-\item the sequence consisting of the first fine spin, all coarse spins in
+$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
grid order, and the last fine spin has consecutive Hamming distances at
most $R_n$.
@@ -1311,37 +1311,37 @@ 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 $2\delta$, 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(n\sqrt\delta)$, 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(n\sqrt\delta))$.
+$exp(O_beta(nsqrtdelta))$.
Apply the likelihood estimate (eq:6) with coarse horizon $l=b$. Its
good event depends only on this proposal run. If
-$q_{\rm good}(dx\mid 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}(dx\mid g)\le\exp(n^{1-b/2})\,\pi_g(dx)
- \quadfor almost every g .
+ q_{rm good}(dxmid g)leexp(n^{1-b/2}),pi_g(dx)
+ quadfor almost every g .
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)$ 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.
By (eq:12), the resulting boundary probability on the complement of
the energy-change event is at most
-\[
- \exp(n^{1-b/2}+O_\beta(n\sqrt\delta)-\tfrac12 n^{1-b/20}).
-\]
-Add the proposal exceptional probability $\exp(-n^{1-10b})$ and the
-energy-change exception. Since $\sqrt\delta=n^{-f/8}$ and $f=1/100$, the
-exponent $1-b/20$ dominates both $1-b/2$ and $O_\beta(n\sqrt\delta)$ for
+[
+ 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.
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
@@ -1352,7 +1352,7 @@ at that point.
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|_n\le2$, and each
+$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
@@ -1360,18 +1360,18 @@ 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,
+ |M_theta(V_b)-M_{theta'}(V_b)|_n
+ le(n^{C_1})^{K_b+1},|theta-theta'|,
+ qquad 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$.
Input bounds.: Bound the operator norms of
-$W(G^\circ),W(G'_1),W(G'_2)$ and the normalized norms of all completion
+$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
@@ -1379,25 +1379,25 @@ 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
+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
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
+$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.
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}$.
@@ -1405,43 +1405,43 @@ magnetization difference negligible relative to $n^{-b/3}$.
For either a coarse spin or a fine endpoint spin compared with its own
coarse magnetization, the normalized squared distance has mean
-\[
- 1-\mathbb E 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=b\log n$. For a fine spin this
+[
+ 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
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
+$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}$.
+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
+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
+$b<d$. The total failure probability is at most $exp(-n^{1-d/2})$ for
sufficiently large $n$.
## The crossing contradiction
-On $\mathcal E$, 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)$. This contradicts property (a).
+placing that coarse spin in $mathcal D(G)$.calD(G)$. This contradicts property (a).
Consequently
- \Pr(\mathcal E)\,\exp(-2n^{1-2d})\le\exp(-n^{1-d/2}) .
+ Pr(mathcal E)calE),exp(-2n^{1-2d})leexp(-n^{1-d/2}) .
-Since $d/2<2d$, this implies $\Pr(\mathcal E)=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.
@@ -1449,8 +1449,8 @@ bath.
%----------------------------------------------------------------------
[!htbp]
-\centering
-[x=1cm,y=1cm,font=\small,
+centering
+[x=1cm,y=1cm,font=small,
coarse/.style={circle,draw=blue!55!black,fill=white,line width=.8pt,
minimum size=5.5mm,inner sep=0pt},
fine/.style={rectangle,draw=black!80,fill=black!12,line width=.8pt,
@@ -1458,57 +1458,57 @@ bath.
forced/.style={coarse,draw=red!65!black,fill=red!8,line width=1.2pt},
boundary/.style={circle,draw=red!65!black,fill=red!8,line width=.8pt,
minimum size=3mm,inner sep=0pt}]
- \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}$};
- \node[fine] (leftfine) at (.65,0) {};
- \node[coarse] (coarsezero) at (2.5,0) {};
- \node[coarse] (coarseone) at (4.4,0) {};
- \node[forced] (crossleft) at (6.3,0) {};
- \node[forced] (crossright) at (8.3,0) {};
- \node[coarse] (coarselast) at (10.3,0) {};
- \node[fine] (rightfine) at (12.8,0) {};
- \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 at (6.9,-1.15)
- {Every step has a coarse endpoint; coarse outputs avoid $\mathcal D(G)$.};
- \node at (7.3,-1.9)
- {Expand the crossing step into single-spin flips: length $\ell\le 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) {};
- \node[boundary] (boundaryright) at (8.4,-2.85) {};
- \node[forced] (pathright) at (10.8,-2.85) {};
- \draw[black!65] (pathleft) -- (boundaryleft);
- \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}$};
- \node[red!65!black,align=center] at (7.3,-3.8)
- {$d_H(u,∂ S),\,d_H(v,∂ S)\le\ell\le R_n
- \;⇒\; u,v\in\mathcal D(G)$.};
-
-\caption{The boundary obstruction for the finite sequence of proposals.
+ 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[fine] (leftfine) at (.65,0) {};
+ node[coarse] (coarsezero) at (2.5,0) {};
+ node[coarse] (coarseone) at (4.4,0) {};
+ node[forced] (crossleft) at (6.3,0) {};
+ node[forced] (crossright) at (8.3,0) {};
+ node[coarse] (coarselast) at (10.3,0) {};
+ node[fine] (rightfine) at (12.8,0) {};
+ 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 at (6.9,-1.15)
+ {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$.};
+ 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) {};
+ node[boundary] (boundaryright) at (8.4,-2.85) {};
+ node[forced] (pathright) at (10.8,-2.85) {};
+ draw[black!65] (pathleft) -- (boundaryleft);
+ 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[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)$
+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.}
@@ -1525,13 +1525,13 @@ of a cut have appreciable Gibbs mass. We now convert exactly this
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,
+[label=arabic*.,leftmargin=*]
+item 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
+item 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$,
+item 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.
@@ -1542,126 +1542,126 @@ than obstructing the bound.
## The pruning lemma
[Pruning and averaged mixing]
-Let $Ω$ be a finite set, $\pi$ a strictly positive probability on
+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_{y\ne x}c(x,y)\le R\qquad(x\inΩ).
-\]
+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
-\[
- Q(S,S^{\rm c}):=\sum_{x\in S,\,y\notin S}\pi(x)c(x,y)>B
- \quadwhenever ε\le\pi(S)\le1-ε.
-\]
+[
+ 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$,
- \sum_{x\inΩ}\pi(x)\bigl\|P_T(x,\cdot)-\pi\bigr\|_{\rm TV}
- \le\frac{√(2R\,H(\pi))}{B\sqrt T}+2ε,
- \qquad H(\pi)=-\sum_x\pi(x)\log\pi(x).
+ 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).
Proof.
-Put $q(x,y)=\pi(x)c(x,y)=q(y,x)$, and use the unordered-edge Dirichlet form
-\[
- \mathfrak D(u)=\sum_{\{x,y\}}q(x,y)(u(x)-u(y))^2.
-\]
+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 $U\subset C$ satisfies
-\[
- \pi(U)\le\pi(C)/2,\qquad Q(U,C∖ U)<B\pi(U),
-\]
+$C=Ω$. Whenever a nonempty $Usubset C$ satisfies
+[
+ pi(U)lepi(C)/2,qquad 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 $A\ne∅$,
-\[
- Q(A,Ω∖ A)<B\pi(A).
-\]
+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 $B\pi(A)\le B$. Consequently the terminal
-set satisfies $\pi(C)>1-ε$ and
+balanced-cut hypothesis, since $Bpi(A)le B$. Consequently the terminal
+set satisfies $pi(C)>1-ε$ and
- Q(U,C∖ U)\ge B\pi(U)
- \quadfor every U\subset C with \pi(U)\le\pi(C)/2 .
+ Q(U,C∖ U)ge Bpi(U)
+ quadfor every Usubset C with pi(U)lepi(C)/2 .
-Step 2: a Poincar\'e inequality on the retained set.: Use the
+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
+cite[Theorem~3.5]{LawlerSokal1988}, keeping the original unnormalized
weights on $C$. The resulting estimate is
- \sum_{y\in C}\pi(y)(u(y)-\bar u_C)^2
- \le(2R)/(B^2)\,\mathfrak D(u),
- \qquad \bar u_C=\frac1{\pi(C)}\sum_{y\in C}\pi(y)u(y).
+ 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).
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$.
+$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
-\[
- B\sum_C\pi w^2
- \le\sum_{\{x,y\}\subset C}q(x,y)|w(x)^2-w(y)^2|.
-\]
+[
+ Bsum_Cpi w^2
+ lesum_{{x,y}subset C}q(x,y)|w(x)^2-w(y)^2|.
+]
By Cauchy--Schwarz this is at most
-\[
- (\sum_{\{x,y\}\subset C}q(x,y)(w(x)-w(y))^2)^{1/2}
- (2R\sum_C\pi w^2)^{1/2},
-\]
-since $(w(x)+w(y))^2\le2(w(x)^2+w(y)^2)$ and the total outgoing rate is at
-most $R$. If $\sum_C\pi w^2$ vanishes the estimate is immediate; otherwise
+[
+ (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
divide and square. The sum of the energies of the positive and negative
-parts is at most $\mathfrak D(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^T\sum_x\pi(x)\,\mathfrak D(√(f_t^x))\,dt
- \le\tfrac14 H(\pi).
-
-Indeed, the derivative of $\sum_y\pi(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 $x\sim\pi$ and integrating proves (eq:15).
+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
+[
+ -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).
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 $t\in(0,T]$ with
-\[
- \sum_x\pi(x)r_x^2\le(R\,H(\pi))/(2TB^2),
- \quad
- r_x^2=\sum_C\pi(y)(√(f_t^x(y))-a_x)^2,
- \quad
- a_x=\frac1{\pi(C)}\sum_C\pi(y)√(f_t^x(y)) .
-\]
-Cauchy--Schwarz and $a_x^2\pi(C)\le\sum_C\pi f_t^x\le1$ imply
-\[
- \sum_C\pi|f_t^x-a_x^2|\le2r_x .
-\]
+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
+[
+ sum_Cpi|f_t^x-a_x^2|le2r_x .
+]
Also, total normalization gives
-$|\sum_C\pi(f_t^x-1)|\le\sum_{C^{\rm c}}\pi(f_t^x+1)$.
+$|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+2\sum_{C^{\rm c}}\pi(f_t^x+1).
-\]
-The last sum before its factor two has average $2\pi(C^{\rm c})$ over
-$x\sim\pi$, because stationarity gives $\sum_x\pi(x)f_t^x(y)=1$. Dividing
+[
+ 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).
@@ -1672,25 +1672,25 @@ at the prescribed time $T$, establishing (eq:averaged-mixing).
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},qquad B=exp(-n^{1-b/20}),qquad 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 n\log2$, since the state space has $2^n$ elements. Hence
-\[
- \sum_x\pi_G(x)\bigl\|P_T^G(x,\cdot)-\pi_G\bigr\|_{\rm TV}
- \le\frac{√(2\log2)\;n}{B\sqrt T}+2n^{-d}.
-\]
+$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}.
+]
Take
-\[
- T=\exp(n^{1-b/40}).
-\]
+[
+ T=exp(n^{1-b/40}).
+]
Then the first term tends to zero, because
-\[
- \log(n)/(B\sqrt T)
- =\log n+n^{1-b/20}-\tfrac12 n^{1-b/40}→-∞ .
-\]
+[
+ log(n)/(Bsqrt T)
+ =log n+n^{1-b/20}-tfrac12 n^{1-b/40}→-∞ .
+]
The flow event (eq:11) itself has disorder probability tending to
one. Markov's inequality therefore shows that the Gibbs mass of fixed
@@ -1698,26 +1698,26 @@ 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
(eq:H). This proves Theorem~thm:main with
-\[
- c_\beta=(b)/(40)=\frac1{40000000}.
-\]
-All threshold dimensions may depend on the fixed $\beta>1$.
+[
+ c_beta=(b)/(40)=frac1{40000000}.
+]
+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:
-\[
- 10b\ \ll\ b/4\ \ll\ b/2\ \ll\ b/20\ \ll\ d
- =100b\ \ll\ 2d\ll f\ll 1 .
-\]
+[
+ 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/2\ll d<2d$ gives the gap. The mixing time $T=\exp(n^{1-b/40})$
-sits below both because $b/40\ll b/20$, so the exponential
-$\exp(-n^{1-b/20})$ flow bound has enough time to accumulate. Nothing here
+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,140 +1726,140 @@ were chosen in a strict hierarchy to keep every exponent well separated.
%======================================================================
{99}
-\bibitem{AC2015}
+bibitem{AC2015}
A.~Auffinger and W.-K.~Chen,
-\newblock On properties of Parisi measures,
-\newblock Probab.\ Theory Related Fields 161 (2015),
+newblock On properties of Parisi measures,
+newblock Probab. Theory Related Fields 161 (2015),
817--850.
-\newblock doi:10.1007/s00440-014-0563-y;
+newblock doi:10.1007/s00440-014-0563-y;
arXiv:1303.3573v1.
-\bibitem{BLO2026}
+bibitem{BLO2026}
M.~Boban, A.~Li and S.~Oveis Gharan,
-\newblock Rank-1-perturbed trickledown theorems: mixing time of Glauber
+newblock Rank-1-perturbed trickledown theorems: mixing time of Glauber
dynamics for the Sherrington--Kirkpatrick model up to
-$\beta\le\tfrac12+ε$,
-\newblock preprint (2026),
+$betaletfrac12+ε$,
+newblock preprint (2026),
arXiv:2609.13138v1.
-\bibitem{BKM2005}
+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.
+newblock Triangular transformations of measures,
+newblock Sbornik: Math. 196 (2005), no.~3, 309--335.
+newblock doi:10.1070/SM2005v196n03ABEH000882.
-\bibitem{Bolthausen2014}
+bibitem{Bolthausen2014}
E.~Bolthausen,
-\newblock An iterative construction of solutions of the TAP equations for
+newblock An iterative construction of solutions of the TAP equations for
the Sherrington--Kirkpatrick model,
-\newblock Comm.\ Math.\ Phys. 325 (2014), 333--366.
-\newblock doi:10.1007/s00220-013-1862-3;
+newblock Comm. Math. Phys. 325 (2014), 333--366.
+newblock doi:10.1007/s00220-013-1862-3;
arXiv:1201.2891.
-\bibitem{BLM2013}
+bibitem{BLM2013}
S.~Boucheron, G.~Lugosi and P.~Massart,
-\newblock Concentration Inequalities: A Nonasymptotic Theory of
+newblock Concentration Inequalities: A Nonasymptotic Theory of
Independence, Oxford University Press, 2013.
-\bibitem{Chen2017}
+bibitem{Chen2017}
W.-K.~Chen,
-\newblock Variational representations for the Parisi functional and the
+newblock Variational representations for the Parisi functional and the
two-dimensional Guerra--Talagrand bound,
-\newblock Ann.\ Probab. 45 (2017), no.~6A, 3929--3966.
-\newblock doi:10.1214/16-AOP1154;
+newblock Ann. Probab. 45 (2017), no.~6A, 3929--3966.
+newblock doi:10.1214/16-AOP1154;
arXiv:1501.06635v2.
-\bibitem{DiaconisSaloffCoste1996}
+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.
+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}
+bibitem{EKZ2022}
R.~Eldan, F.~Koehler and O.~Zeitouni,
-\newblock A spectral condition for spectral gap: fast mixing in
+newblock A spectral condition for spectral gap: fast mixing in
high-temperature Ising models,
-\newblock Probab.\ Theory Related Fields 182 (2022),
+newblock Probab. Theory Related Fields 182 (2022),
nos.~3--4, 1035--1051.
-\newblock doi:10.1007/s00440-021-01085-x;
+newblock doi:10.1007/s00440-021-01085-x;
arXiv:2007.08200v1.
-\bibitem{Guerra2003}
+bibitem{Guerra2003}
F.~Guerra,
-\newblock Broken replica symmetry bounds in the mean field spin glass
+newblock Broken replica symmetry bounds in the mean field spin glass
model,
-\newblock Comm.\ Math.\ Phys. 233 (2003), 1--12.
-\newblock doi:10.1007/s00220-002-0773-5;
+newblock Comm. Math. Phys. 233 (2003), 1--12.
+newblock doi:10.1007/s00220-002-0773-5;
arXiv:cond-mat/0205123v1.
-\bibitem{JT2017}
+bibitem{JT2017}
A.~Jagannath and I.~Tobasco,
-\newblock Some properties of the phase diagram for mixed $p$-spin glasses,
-\newblock Probab.\ Theory Related Fields 167 (2017),
+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;
+newblock doi:10.1007/s00440-015-0691-z;
arXiv:1504.02731v2.
-\bibitem{LawlerSokal1988}
+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,
+newblock Trans. Amer. Math. Soc. 309 (1988), no.~2,
557--580.
-\newblock doi:10.1090/S0002-9947-1988-0930082-9.
+newblock doi:10.1090/S0002-9947-1988-0930082-9.
-\bibitem{Lopatto2026}
+bibitem{Lopatto2026}
P.~Lopatto,
-\newblock Full replica symmetry breaking in the Sherrington--Kirkpatrick
+newblock Full replica symmetry breaking in the Sherrington--Kirkpatrick
model,
-\newblock preprint (2026),
+newblock preprint (2026),
arXiv:2607.11756v3.
-\bibitem{LugosiNeu2022}
+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.
+newblock Generalization bounds via convex analysis,
+newblock Proc. Mach. Learn. Res. 178 (2022), 3524--3546.
+newblock Proceedings article.
-\bibitem{Montanari2021}
+bibitem{Montanari2021}
A.~Montanari,
-\newblock Optimization of the Sherrington--Kirkpatrick Hamiltonian,
-\newblock SIAM J.\ Comput. 54 (2025), no.~4,
+newblock Optimization of the Sherrington--Kirkpatrick Hamiltonian,
+newblock SIAM J. Comput. 54 (2025), no.~4,
FOCS19-1--FOCS19-38 (online 2021).
-\newblock doi:10.1137/20M132016X;
+newblock doi:10.1137/20M132016X;
arXiv:1812.10897v2.
-\bibitem{OpenAISKBarriers2026}
+bibitem{OpenAISKBarriers2026}
OpenAI,
-\newblock Stretched-exponential barriers for typical SK initial states,
-\newblock
+newblock Stretched-exponential barriers for typical SK initial states,
+newblock
OpenAI Math Release preprint, 2026.
-\bibitem{Sellke2025}
+bibitem{Sellke2025}
M.~Sellke,
-\newblock Exponentially slow mixing of the low temperature SK model,
-\newblock preprint (2025),
+newblock Exponentially slow mixing of the low temperature SK model,
+newblock preprint (2025),
arXiv:2511.22621v2.
-\bibitem{SK1975}
+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.
+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}
+bibitem{Wang2026}
S.~Wang,
-\newblock Optimal mixing of Glauber dynamics for the
-Sherrington--Kirkpatrick model at $\beta<1/2$,
-\newblock preprint (2026),
+newblock Optimal mixing of Glauber dynamics for the
+Sherrington--Kirkpatrick model at $beta<1/2$,
+newblock preprint (2026),
arXiv:2608.22159v2.
-\bibitem{Zhou2026}
+bibitem{Zhou2026}
Y.~Zhou,
-\newblock Existence of full replica symmetry breaking for the
+newblock Existence of full replica symmetry breaking for the
Sherrington--Kirkpatrick model at low temperature,
-\newblock Comm.\ Pure Appl.\ Math. 79 (2026), 1746--1770.
-\newblock doi:10.1002/cpa.70038.
+newblock Comm. Pure Appl. Math. 79 (2026), 1746--1770.
+newblock doi:10.1002/cpa.70038.