Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing

# Learning Gaussian Graphical Models from a Glauber Trajectory Without Mixing
Source: [https://arxiv.org/html/2606.31230](https://arxiv.org/html/2606.31230)
Tony Wu11footnotemark:1 tonyyzwu@mit\.edu MITMahbod Majid mahbod@mit\.edu MITAnkur Moitra moitra@mit\.edu MITSupported in part by DARPA expMath, a Microsoft Trustworthy AI Grant, NSF\-CCF 2430381, an ONR grant, and a David and Lucile Packard Fellowship\.

###### Abstract

We study the task of learning the structure of add\-sparse Gaussian graphical model onnnvariables from a single trajectory of Glauber dynamics\. Beyond algorithmic considerations, many applications present temporally correlated observations rather than i\.i\.d\. samples\. In the classical i\.i\.d\. setting, under comparably general sparsity and minimum edge\-strength assumptions, sublinear\-in\-nnsample guarantees are known, but achieving them in polynomial\-time remains open\. Motivated in part by this gap, we give a polynomial\-time algorithm that recovers the conditional\-independence graph from a single Glauber trajectory, with a trajectory\-length guarantee that does not depend on the mixing time\.

Technically, our algorithm has three components\. First, we estimate the conditional variances and rescale the trajectory to reduce to the unit\-diagonal case, without changing the underlying graph\. Second, we design a local edge test that extracts adjacency information from short update windows by isolating pairwise influence\. Third, we aggregate these local statistics using a robust median\-based estimator, and prove accuracy despite temporal dependence arising from a single trajectory\.

###### Contents

1. [1Introduction](https://arxiv.org/html/2606.31230#S1)1. [1\.1Results](https://arxiv.org/html/2606.31230#S1.SS1) 2. [1\.2Related work](https://arxiv.org/html/2606.31230#S1.SS2)
2. [2Technical Overview](https://arxiv.org/html/2606.31230#S2)
3. [3Preliminaries](https://arxiv.org/html/2606.31230#S3)1. [3\.1Continuous\-time Glauber dynamics](https://arxiv.org/html/2606.31230#S3.SS1) 2. [3\.2Observing patterns](https://arxiv.org/html/2606.31230#S3.SS2) 3. [3\.3Corruption and robust estimation](https://arxiv.org/html/2606.31230#S3.SS3) 4. [3\.4Concentration inequalities](https://arxiv.org/html/2606.31230#S3.SS4) 5. [3\.5Mixing and coupling](https://arxiv.org/html/2606.31230#S3.SS5)
4. [4Reduction to Normalized Gaussian Graphical Models](https://arxiv.org/html/2606.31230#S4)1. [4\.1Properties of the statistic](https://arxiv.org/html/2606.31230#S4.SS1) 2. [4\.2Retrieving the estimator](https://arxiv.org/html/2606.31230#S4.SS2) 3. [4\.3Normalizing the Gaussian](https://arxiv.org/html/2606.31230#S4.SS3)
5. [5Main Algorithm](https://arxiv.org/html/2606.31230#S5)1. [5\.1Properties of the statistic](https://arxiv.org/html/2606.31230#S5.SS1) 2. [5\.2Retrieving the estimator](https://arxiv.org/html/2606.31230#S5.SS2)
6. [6Learning With Mixing](https://arxiv.org/html/2606.31230#S6)1. [6\.1Properties of the statistic](https://arxiv.org/html/2606.31230#S6.SS1) 2. [6\.2Edge detection](https://arxiv.org/html/2606.31230#S6.SS2)
7. [7Information\-Theoretic Lower Bound](https://arxiv.org/html/2606.31230#S7)1. [7\.1The class of graphs](https://arxiv.org/html/2606.31230#S7.SS1) 2. [7\.2A bound on KL\-divergence](https://arxiv.org/html/2606.31230#S7.SS2) 3. [7\.3Fano’s method](https://arxiv.org/html/2606.31230#S7.SS3)
8. [References](https://arxiv.org/html/2606.31230#bib)
9. [ARobust Estimators](https://arxiv.org/html/2606.31230#A1)
10. [BContinuous Time Versus Number of Updates](https://arxiv.org/html/2606.31230#A2)
11. [CA Technical Gap in the Analysis of Prior Work](https://arxiv.org/html/2606.31230#A3)
12. [DNon\-Degeneracy Does Not Control Eigenvalues](https://arxiv.org/html/2606.31230#A4)

## 1Introduction

A*Gaussian Graphical Model*\(GGM\) onnnvertices is a mean\-zero Gaussian random variableX∼𝒩​\(0,Σ\)X\\sim\\mathcal\{N\}\(0,\\Sigma\)\. The relevant object for the graph structure is the*precision matrix*Θ:\-Σ−1\\Theta\\coloneq\\Sigma^\{\-1\}\. We associate toΘ\\Thetaan undirected graphG=\(V,E\)G=\(V,E\)by putting an edge\(i,j\)\(i,j\)wheneverΘi​j≠0\\Theta\_\{ij\}\\neq 0\. The key fact is that, for Gaussians, zeros inΘ\\Thetaexactly encode conditional independences: for distincti,j∈Vi,j\\in V,

Xi⟂Xj\|XV∖\{i,j\}⟺Θi​j=0\.X\_\{i\}\\perp X\_\{j\}\\,\|\\,X\_\{V\\setminus\\\{i,j\\\}\}\\quad\\Longleftrightarrow\\quad\\Theta\_\{ij\}=0\.This is known as the Markov property\. An important measure of complexity of GGMs is*sparsity*: we say the GGM isdd\-sparse if every vertex has at mostddneighbors inGG, equivalently each row ofΘ\\Thetahas at mostddnonzero off\-diagonal entries\.

GGMs provide a natural way to represent*conditional dependence structure*among many interacting variables\. The literature on GGM applications is too vast to survey here, but representative examples include neuroscience and brain connectivity\[[DMG\+20](https://arxiv.org/html/2606.31230#bib.bib12),[HLS\+10](https://arxiv.org/html/2606.31230#bib.bib11)\], genomics\[[YZL\+22](https://arxiv.org/html/2606.31230#bib.bib14)\], metabolic pathway reconstruction\[[KSI\+11](https://arxiv.org/html/2606.31230#bib.bib13)\], climate science\[[ZFL\+14](https://arxiv.org/html/2606.31230#bib.bib10)\], financial systemic\-risk modeling\[[CG16](https://arxiv.org/html/2606.31230#bib.bib4)\], and environmental psychology\[[BMS\+19](https://arxiv.org/html/2606.31230#bib.bib3)\]\. A recurring regime in such applications is high dimensionality, where the number of variablesnncan be comparable to or larger than the number of available observations, motivating our focus on sparse GGMs, in which the conditional\-independence graph has maximum degree at mostdd\.

Algorithmically, the main challenge is already present in*structure learning*: recovering the edge setEE\(equivalently, the support ofΘ\\Theta\)\. Indeed, onceGGis known, estimating the coefficients reduces to runningnnlow\-dimensional \(regression\) problems, each involving only theddneighbors of a node\. More precisely, for each nodei∈Vi\\in V, the conditional distribution ofXiX\_\{i\}given the remaining coordinates is

Xi=−∑j∈N​\(i\)Θi​jΘi​i​Xj\+ξi,ξi∼𝒩​\(0,1Θi​i\)\.X\_\{i\}=\-\\sum\_\{j\\in N\(i\)\}\\frac\{\\Theta\_\{ij\}\}\{\\Theta\_\{ii\}\}X\_\{j\}\+\\xi\_\{i\},\\quad\\xi\_\{i\}\\sim\\mathcal\{N\}\\left\(0,\\frac\{1\}\{\\Theta\_\{ii\}\}\\right\)\.Thus, givenGG, estimatingΘ\\Thetareduces tonnregressions ofXiX\_\{i\}onto\{Xj:j∈N​\(i\)\}\\\{X\_\{j\}:j\\in N\(i\)\\\}, which recover the coefficients\{−Θi​j/Θi​i\}j∈N​\(i\)\\\{\-\\Theta\_\{ij\}/\\Theta\_\{ii\}\\\}\_\{j\\in N\(i\)\}and the noise variance1/Θi​i1/\\Theta\_\{ii\}\.

In the classical i\.i\.d\. data model, Misra, Vuffray and Lokhov\[[MVL20](https://arxiv.org/html/2606.31230#bib.bib20)\]studied the information\-theoretic sample complexity of learning sparse GGMs*without*assuming bounded spectrum or incoherence\. The only assumption they make is the following guarantee on the minimum normalized edge strength

\|Θi​j\|Θi​i​Θj​j≥α∀\(i,j\)∈E,\\frac\{\\lvert\\Theta\_\{ij\}\\rvert\}\{\\sqrt\{\\Theta\_\{ii\}\\Theta\_\{jj\}\}\}\\geq\\alpha\\qquad\\forall\(i,j\)\\in E,\(non\-degeneracy\)which is a natural non\-degeneracy condition ensuring that present edges are not arbitrarily weak\. It is important to note that this constraint does*not*impose any assumptions on the minimum eigenvalue of the normalized matrix, and the spectrum may be arbitrarily ill\-conditioned\. For a simple demonstration of this, see appendix[AppendixD](https://arxiv.org/html/2606.31230#A4)\.

They show that information\-theoreticallyO​\(d​log⁡n/α2\)O\(d\\log n/\\alpha^\{2\}\)i\.i\.d samples suffice for learning the graph structure\. Earlier work of Wang, Wainwright, and Ramchandran\[[WWR10](https://arxiv.org/html/2606.31230#bib.bib22)\]shows that at leastΩ​\(log⁡n/α2\)\\Omega\(\\log n/\\alpha^\{2\}\)i\.i\.d samples are necessary for this task, and it is currently unknown which of the upper bound or the lower bound is tight\. However, the price paid is computational: the algorithm of\[[MVL20](https://arxiv.org/html/2606.31230#bib.bib20)\]uses an exhaustive search based on anℓ0\\ell\_\{0\}\-constrained sparse linear regression and runs in timenΩ​\(d\)n^\{\\Omega\(d\)\}\. Whether one can match the information\-theoretic sample complexity with a polynomial\-time algorithm for general GGMs remains open\. More broadly, there is evidence for computational barriers in related sparse linear regression problems\. In particular, in the fixed\-design, worst\-case setting,*proper*sparse linear regression—meaning the algorithm must output akk\-sparse predictor when akk\-sparse solution exists—isNP\-hard\[[NAT95](https://arxiv.org/html/2606.31230#bib.bib8),[ZWJ14](https://arxiv.org/html/2606.31230#bib.bib9)\]\.

In many scientific settings, observations are not i\.i\.d\.; instead we observe a system evolving over time\. A natural stylized model for such temporal dependence is a Markov chain whose stationary distribution is a GGM, for instance single\-site Gibbs sampling \(Glauber dynamics\)\. If the chain mixes rapidly, then by spacing observations by at least the mixing time one can obtain approximately independent draws and reduce to the classical i\.i\.d\. setting\.

However, mixing\-based reductions can be unsatisfactory even for Gaussian targets\. Indeed, for a multivariate normal target, single\-site Gibbs has an explicit linear\-operator description, and its convergence rate is controlled by the spectrum of an associated update matrix\[[AMI91](https://arxiv.org/html/2606.31230#bib.bib7),[RS97](https://arxiv.org/html/2606.31230#bib.bib6)\]\. Moreover, this convergence behavior is invariant under diagonal rescaling of the coordinates, so it is expressed in terms of the normalized precision matrixΘ′=D−1/2​Θ​D−1/2\\Theta^\{\\prime\}=D^\{\-1/2\}\\Theta D^\{\-1/2\}, whereD=diag​\(Θ11,…,Θn​n\)D=\\mathrm\{diag\}\(\\Theta\_\{11\},\\ldots,\\Theta\_\{nn\}\)\. For example, a standard spectral\-gap bound for single\-site Gibbs implies

tmix​\(ε\)≈n​1λmin​\(Θ′\)​log⁡\(1/ε\),t\_\{\\mathrm\{mix\}\}\(\\varepsilon\)\\approx n\\,\\frac\{1\}\{\\lambda\_\{\\min\}\(\\Theta^\{\\prime\}\)\}\\,\\log\(1/\\varepsilon\),\(1\)where the equality is up to absolute constants\[[RS97](https://arxiv.org/html/2606.31230#bib.bib6),[AMI91](https://arxiv.org/html/2606.31230#bib.bib7)\]\. Sinceλmin​\(Θ′\)\\lambda\_\{\\min\}\(\\Theta^\{\\prime\}\)can be arbitrarily small under the[non\-degeneracy](https://arxiv.org/html/2606.31230#S1.Ex3)constraint,111See[AppendixD](https://arxiv.org/html/2606.31230#A4)for a simple demonstration of this\.the mixing time can be arbitrarily large\.

This leads to our main question:

> *Is it possible to learn the structure of a sparse GGM from a single Glauber trajectory*without*waiting for the chain to mix, and without imposing additional assumptions on the precision matrixΘ\\Theta?*

We answer this question in the affirmative by giving an efficient algorithm that recovers the graph from a single trajectory, with no dependence on the mixing time and without imposing additional assumptions on the precision matrix beyond the[non\-degeneracy](https://arxiv.org/html/2606.31230#S1.Ex3)condition\. In the next section we formalize the model and state our main theorem\.

### 1\.1Results

We begin by recalling two definitions that formalize our setting:\(α,d\)\(\\alpha,d\)\-sparse Gaussian graphical models and single\-site Glauber dynamics\.

###### Definition 1\.1\(\(α,d\)\(\\alpha,d\)\-sparse Gaussian graphical model\)\.

LetΣ∈ℝn×n\\Sigma\\in\\mathbb\{R\}^\{n\\times n\}be positive definite and letΘ:\-Σ−1\\Theta\\coloneq\\Sigma^\{\-1\}\. Forα\>0\\alpha\>0and an integerd≥1d\\geq 1, we say thatX∼𝒩​\(0,Σ\)X\\sim\\mathcal\{N\}\(0,\\Sigma\)is an\(α,d\)\(\\alpha,d\)\-sparse GGM if the graphG=\(V,E\)G=\(V,E\)onV=\[n\]V=\[n\]defined by

\(i,j\)∈E⟺Θi​j≠0,\(i,j\)\\in E\\quad\\Longleftrightarrow\\quad\\Theta\_\{ij\}\\neq 0,has maximum degree at mostdd, and moreover every edge has normalized strength at leastα\\alpha, i\.e\.,

\|Θi​jΘi​i​Θj​j\|≥α∀\(i,j\)∈E\.\\left\\lvert\\frac\{\\Theta\_\{ij\}\}\{\\sqrt\{\\Theta\_\{ii\}\\Theta\_\{jj\}\}\}\\right\\rvert\\ \\geq\\ \\alpha\\qquad\\forall\(i,j\)\\in E\.We refer toGGas the \(conditional\-independence\) graph or the sparsity pattern of the model\.

Next we define the Glauber dynamics for a GGM\. We work with the continuous\-time dynamics, where each coordinate has an independent rate\-11Poisson clock, so the chain performsnnupdates per unit time in expectation\.

###### Definition 1\.2\(Continuous\-time Glauber dynamics for a GGM\)\.

The continuous\-time Glauber dynamics for a GGM with precision matrixΘ\\Thetais a random process\{Y\(t\)\}t≥0\\\{Y^\{\(t\)\}\\\}\_\{t\\geq 0\}taking values inℝn\\mathbb\{R\}^\{n\}\. It is initialized at an arbitrary \(possibly random or worst\-case\) vectorY\(0\)Y^\{\(0\)\}, and is updated at random times\{S\(ℓ\)\}ℓ∈ℕ\\\{S^\{\(\\ell\)\}\\\}\_\{\\ell\\in\\mathbb\{N\}\}withS\(0\)=0S^\{\(0\)\}=0, whereS\(ℓ\)S^\{\(\\ell\)\}is the time of theℓ\\ell\-th update\. The inter\-update times\{S\(ℓ\+1\)−S\(ℓ\)\}ℓ≥0\\\{S^\{\(\\ell\+1\)\}\-S^\{\(\\ell\)\}\\\}\_\{\\ell\\geq 0\}are i\.i\.d\. sampled from the exponential distribution with parameternn, namelyExp​\(n\)\\mathrm\{Exp\}\(n\), so the chain performsnnupdates per unit time in expectation\. The process is piecewise constant between updates; define the embedded discrete\-time chainX\(ℓ\):=Y\(t\)X^\{\(\\ell\)\}:=Y^\{\(t\)\}fort∈\[S\(ℓ\),S\(ℓ\+1\)\)t\\in\[S^\{\(\\ell\)\},S^\{\(\\ell\+1\)\}\)\.

At each update timeS\(ℓ\)S^\{\(\\ell\)\}, an indexI\(ℓ\)∈\[n\]I^\{\(\\ell\)\}\\in\[n\]is chosen uniformly at random\. Leti=I\(ℓ\)i=I^\{\(\\ell\)\}\. Then we resample coordinateiifrom its conditional distribution given the others:

Xi\(ℓ\)∼𝒩​\(−∑j∈N​\(i\)Θi​jΘi​i​Xj\(ℓ−1\),1Θi​i\),X\_\{i\}^\{\(\\ell\)\}\\sim\\mathcal\{N\}\\left\(\-\\sum\_\{j\\in N\(i\)\}\\frac\{\\Theta\_\{ij\}\}\{\\Theta\_\{ii\}\}\\,X\_\{j\}^\{\(\\ell\-1\)\},\\ \\frac\{1\}\{\\Theta\_\{ii\}\}\\right\),and setXj\(ℓ\)=Xj\(ℓ−1\)X\_\{j\}^\{\(\\ell\)\}=X\_\{j\}^\{\(\\ell\-1\)\}for allj≠ij\\neq i\. HereN​\(i\)=\{j≠i:Θi​j≠0\}N\(i\)=\\\{j\\neq i:\\Theta\_\{ij\}\\neq 0\\\}denotes the neighborhood ofiiin the sparsity graph ofΘ\\Theta\.

We are now ready to present our main result\.

###### Theorem 1\.3\(Main Theorem \(Structure learning\)\)\.

There exists a polynomial\-time algorithm which, given a Glauber trajectory from an\(α,d\)\(\\alpha,d\)\-sparse Gaussian graphical model onnnvertices, recovers the sparsity pattern \(i\.e\.,supp​\(Θ\)\\mathrm\{supp\}\(\\Theta\)\) with probability at least1−δ1\-\\delta, provided the trajectory length satisfies

T=Ω​\(d3​log⁡\(n/δ\)α5\)\.T=\\Omega\\\!\\left\(\\frac\{d^\{3\}\\log\(n/\\delta\)\}\{\\alpha^\{5\}\}\\right\)\.

A few remarks are in order\. First, the guarantee makes no mixing\-time assumption and does not require any additional regularity conditions onΘ\\Thetabeyond sparsity and the edge\-strength condition in Definition[1\.1](https://arxiv.org/html/2606.31230#S1.SS1)\. Second, in the continuous\-time dynamics of Definition[1\.1](https://arxiv.org/html/2606.31230#S1.SS1), the chain performsnnsingle\-site updates per unit time in expectation; thus, observing the chain up to time horizonTTcorresponds to aboutn​TnTsingle\-site updates on average\. Third \(on optimality\), information\-theoretic lower bounds ofΩ​\(log⁡\(d\)/α2\)\\Omega\(\\log\(d\)/\\alpha^\{2\}\)were previously known \(see Theorem 2 in\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]\)\. Their statement is parameterized byβmin:\-min\(i,j\)∈E⁡\|Θi​j\|/Θi​i\\beta\_\{\\min\}\\coloneq\\min\_\{\(i,j\)\\in E\}\|\\Theta\_\{ij\}\|/\\Theta\_\{ii\}, whereas we work with the symmetric normalizationmin\(i,j\)∈E⁡\|Θi​j\|/Θi​i​Θj​j\\min\_\{\(i,j\)\\in E\}\|\\Theta\_\{ij\}\|/\\sqrt\{\\Theta\_\{ii\}\\Theta\_\{jj\}\}\. Under the condition thatΘ\\Thetahas diagonal11, these parameters are equal\. In[Section7](https://arxiv.org/html/2606.31230#S7)\([Theorem7\.3](https://arxiv.org/html/2606.31230#S7.Thmtheorem3)\) using similar techniques, we show an improved information\-theoretic lower bound thatΩ​\(n​log⁡\(n\)/α2\)\\Omega\(n\\log\(n\)/\\alpha^\{2\}\)single\-site updates are necessary for structure learning from a single trajectory \(for success probability1/21/2\)\. Since the number of single\-site updates and the continuous\-time trajectory length are equivalent up to a factor ofnn, this implies a lower bound ofΩ​\(log⁡\(n\)/α2\)\\Omega\(\\log\(n\)/\\alpha^\{2\}\)on the continuous\-time trajectory length\.222See[AppendixB](https://arxiv.org/html/2606.31230#A2)for a formal statement of this equivalence\.Thus, while our result matches the correct logarithmic dependence, its polynomial dependence onddandα\\alphamay not be optimal\. Closing the remaining gap between the lower bound and the current no\-mixing upper bounds is an interesting open problem\.

[Theorem1\.3](https://arxiv.org/html/2606.31230#S1.Thmtheorem3)follows from the more general parameter\-learning theorem below\. Our parameter\-learning theorem,[Theorem1\.4](https://arxiv.org/html/2606.31230#S1.Thmtheorem4), learns each coordinate up to multiplicative factorε\\varepsilon\. The structure\-learning theorem then follows by choosingε=O​\(1\)\\varepsilon=O\(1\)and outputting an edge if\|Θ^i​j\|\>α2\\lvert\\widehat\{\\Theta\}\_\{ij\}\\rvert\>\\frac\{\\alpha\}\{2\}\.

###### Theorem 1\.4\(Main Theorem \(Parameter learning\)\)\.

Let0<α,δ,ε<10<\\alpha,\\delta,\\varepsilon<1and letn,d∈ℕn,d\\in\\mathbb\{N\}\. Given a Glauber trajectory evolving according to an\(α,d\)\(\\alpha,d\)\-sparse GGM with precision matrixΘ\\Thetaand whose length satisfies

T=Ω​\(d3​log⁡\(n/δ\)α5​ε5\),T=\\Omega\\\!\\left\(\\frac\{d^\{3\}\\log\(n/\\delta\)\}\{\\alpha^\{5\}\\varepsilon^\{5\}\}\\right\),there is a polynomial\-time algorithm that outputs an estimateΘ^\\widehat\{\\Theta\}such that

\|Θ^i​j−Θi​j\|≤ε​\|Θi​j\|∀i,j,\\left\\lvert\\widehat\{\\Theta\}\_\{ij\}\-\\Theta\_\{ij\}\\right\\rvert\\leq\\varepsilon\|\\Theta\_\{ij\}\|\\quad\\forall i,j,with success probability1−δ1\-\\delta\.

We also show the following result when explicit dependence on the mixing time is allowed, without requiring any assumption on the precision matrix beyond the[non\-degeneracy](https://arxiv.org/html/2606.31230#S1.Ex3)condition\.

###### Theorem 1\.5\(Structure Learning with Mixing\)\.

There is a polynomial\-time algorithm with the following guarantee\. For some absolute constantc\>0c\>0, given a length\-TTGlauber trajectory from an\(α,d\)\(\\alpha,d\)\-sparse Gaussian graphical model onnnvertices, the algorithm recovers the sparsity patternsupp​\(Θ\)\\mathrm\{supp\}\(\\Theta\)with probability at least1−δ1\-\\delta, provided the trajectory length satisfies

T=Ω​\(log⁡\(n/δ\)α2​\(tmix​\(c​α\)\+d2α2\)\)\.T=\\Omega\\\!\\left\(\\frac\{\\log\(n/\\delta\)\}\{\\alpha^\{2\}\}\\left\(t\_\{\\mathrm\{mix\}\}\(c\\alpha\)\+\\frac\{d^\{2\}\}\{\\alpha^\{2\}\}\\right\)\\right\)\.

The proof uses the shorter “i​j​iiji” pattern together with mixing gaps between accepted windows\. On a clean nearly stationary window, the edge signal appears as the regression coefficient between thejj\-increment and the laterii\-increment, so after conditioning on a largejj\-increment the resulting ratio statistic is a bounded\-variance estimate ofΘi​j′\\Theta^\{\\prime\}\_\{ij\}\.

In particular, when the mixing time is guaranteed to be small, for exampletmix​\(c​α\)=O​\(log⁡\(1/α\)\)t\_\{\\mathrm\{mix\}\}\(c\\alpha\)=O\(\\log\(1/\\alpha\)\), the bound becomesT=O​\(d2​log⁡\(n/δ\)α4\)T=O\\\!\\left\(\\frac\{d^\{2\}\\log\(n/\\delta\)\}\{\\alpha^\{4\}\}\\right\)\. This improves the bound in[Theorem1\.3](https://arxiv.org/html/2606.31230#S1.Thmtheorem3)by a factor ofd/αd/\\alpha\. Moreover, relative to the i\.i\.d\. setting, the algorithm effectively requireslog⁡\(n/δ\)/α2\\log\(n/\\delta\)/\\alpha^\{2\}nearly independent samples, matching the lower bound for i\.i\.d\. data shown in\[[WWR10](https://arxiv.org/html/2606.31230#bib.bib22)\]\.

Similar results with mixing were obtained previously in\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]\. Compared with that work,[Theorem1\.5](https://arxiv.org/html/2606.31230#S1.Thmtheorem5)gives an improved dependence onlog⁡\(1/δ\)\\log\(1/\\delta\)and does not require any additional assumptions on the precision matrix\. We discuss the extra assumptions in\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]in[Section1\.2](https://arxiv.org/html/2606.31230#S1.SS2)\.

Finally we discuss the practicality of our algorithms\.

To see a full proof of[Theorems1\.3](https://arxiv.org/html/2606.31230#S1.Thmtheorem3)and[1\.4](https://arxiv.org/html/2606.31230#S1.Thmtheorem4)see[Section5](https://arxiv.org/html/2606.31230#S5)\. For a full proof of[Theorem1\.5](https://arxiv.org/html/2606.31230#S1.Thmtheorem5), see[Section6](https://arxiv.org/html/2606.31230#S6)\. For a technical overview of the algorithm see[Section2](https://arxiv.org/html/2606.31230#S2)\.

### 1\.2Related work

#### Gaussian GGMs from Glauber dynamics\.

Most closely related to our work is the recent work of Tirukkonda, Rayas, and Dasarathy\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\], which gives the first algorithmic guarantees for structure learning in Gaussian graphical models from a single Glauber trajectory, along with information\-theoretic lower bounds\. In[AppendixC](https://arxiv.org/html/2606.31230#A3)we discuss a technical issue in the proof of one of their lemmas\. After we notified the authors of this gap and posted a preliminary version of this paper on the MIT SPUR website333[https://math\.mit\.edu/documents/spur/2025Shen\_Wu\.pdf](https://math.mit.edu/documents/spur/2025Shen_Wu.pdf), they addressed the issue caused by looking at “i​j​iiji” updates by adopting an approach similar to ours, based on “i​i​j​iiiji” updates\. However, both the earlier version and the updated version of their manuscript still rely crucially on several regularity assumptions beyond a minimum edge\-strength assumption\.

Concretely, in addition to requiring\|Θi​j\|/Θi​i≥βmin\|\\Theta\_\{ij\}\|/\\Theta\_\{ii\}\\geq\\beta\_\{\\min\}for all\(i,j\)∈E\(i,j\)\\in E, they assume \(i\) an upper bound\|Θi​j\|/Θi​i≤βmax\|\\Theta\_\{ij\}\|/\\Theta\_\{ii\}\\leq\\beta\_\{\\max\}for all\(i,j\)∈E\(i,j\)\\in E\(Assumption A1\), \(ii\) bounded marginalsΣi​i≤σmax2\\Sigma\_\{ii\}\\leq\\sigma\_\{\\max\}^\{2\}and non\-degenerate conditionals1/Θi​i≥σmin21/\\Theta\_\{ii\}\\geq\\sigma\_\{\\min\}^\{2\}\(Assumption A2\), and \(iii\) a sample decay conditiond​βmax<1−Ω​\(1\)d\\,\\beta\_\{\\max\}<1\-\\Omega\(1\)\(Assumption A3\)\.444As stated it is written asd​βmax<1d\\,\\beta\_\{\\max\}<1; however, the proof of Lemma 4 explicitly uses that this gap is at least a constant\.Meanwhile, we make no additional assumptions beyond the minimum edge\-strength assumption\. Most importantly, in the diagonal\-11andd=O​\(1\)d=O\(1\)setting, the last assumption implies very fast mixing via the Gershgorin circle theorem:λmin​\(Θ\)≥1−d​βmax=Ω​\(1\)\\lambda\_\{\\min\}\(\\Theta\)\\geq 1\-d\\beta\_\{\\max\}=\\Omega\(1\)andλmax​\(Θ\)≤1\+d​βmax=O​\(1\)\\lambda\_\{\\max\}\(\\Theta\)\\leq 1\+d\\beta\_\{\\max\}=O\(1\)\(see[Equation1](https://arxiv.org/html/2606.31230#S1.E1)\)\. Therefore, under their assumptions one can essentially simulate approximate i\.i\.d\. samples by observing the Glauber trajectory at constant time intervals\. However, in our setting, the mixing time may be arbitrarily slow\. Under constant mixing\-time bounds and polynomial runtime,[Theorem1\.5](https://arxiv.org/html/2606.31230#S1.Thmtheorem5)improves the dependence onddandα\\alphaby a factor ofd/αd/\\alphacompared with their algorithm\. In addition, our result avoids the extra assumptions A1 and A2 required in their analysis\.

ResultTrajectory lengthPolynomial runtimeNo mixingExtra assumptions\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]Theorem 1O​\(d3⋅\(log6/5⁡\(n/δ\)​σmax2\(1−d​βmax\)2​σmin2​βmin\)5\)O\\left\(d^\{3\}\\cdot\\left\(\\dfrac\{\\log^\{\{\}^\{6/5\}\}\(n/\\delta\)\\sigma^\{2\}\_\{\\max\}\}\{\(1\-d\\beta\_\{\\max\}\)^\{2\}\\sigma^\{2\}\_\{\\min\}\\beta\_\{\\min\}\}\\right\)^\{5\}\\right\)✓×\\times\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]’s A\[1\-3\]\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]Theorem 2O~​\(d​log2⁡\(n/δ\)\(1−d​βmax\)​α2\)\\tilde\{O\}\\left\(\\dfrac\{d\\log^\{2\}\(n/\\delta\)\}\{\(1\-d\\beta\_\{\\max\}\)\\alpha^\{2\}\}\\right\)×\\times×\\times\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]’s A\[1\-3\][Theorem1\.5](https://arxiv.org/html/2606.31230#S1.Thmtheorem5)O​\(log⁡\(n/δ\)α2​\(tmix​\(α\)\+d2α2\)\)O\\left\(\\dfrac\{\\log\(n/\\delta\)\}\{\\alpha^\{2\}\}\\left\(t\_\{\\mathrm\{mix\}\}\(\\alpha\)\+\\dfrac\{d^\{2\}\}\{\\alpha^\{2\}\}\\right\)\\right\)✓×\\timesNone[Theorem1\.3](https://arxiv.org/html/2606.31230#S1.Thmtheorem3)O​\(d3​log⁡\(n/δ\)α5\)O\\left\(\\dfrac\{d^\{3\}\\log\(n/\\delta\)\}\{\\alpha^\{5\}\}\\right\)✓✓NoneTable 1:Comparison of structure learning results\. In the notation of\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\],βmax,βmin\\beta\_\{\\max\},\\beta\_\{\\min\}denote the largest and the smallest off diagonal value in the precision matrix\.σmax2\\sigma^\{2\}\_\{\\max\}is the upper bound on the diagonal entries on the covariance matrix andσmin2\\sigma^\{2\}\_\{\\min\}is the lower bound on1/Θi​i1/\\Theta\_\{ii\}\.O~\\tilde\{O\}hides lower order logarithmic factors in all parameters\.
#### Learning graphical models from Glauber dynamics\.

A growing line of work studies structure learning when observations arise from local Markov dynamics rather than i\.i\.d\. sampling\. Bresler, Gamarnik, and Shah\[[BGS17](https://arxiv.org/html/2606.31230#bib.bib21)\]initiated this direction for discrete graphical models, showing that observing a single\-site Glauber trajectory can make structure learning computationally tractable for Ising models\. More recently, Gaitonde and Mossel\[[GM24](https://arxiv.org/html/2606.31230#bib.bib5)\]gave a unified analysis for learning Ising models from Glauber trajectories, and Gaitonde, Moitra, and Mossel\[[GMM25a](https://arxiv.org/html/2606.31230#bib.bib1)\]gave the first efficient algorithms in the observation model that reveals only actual configuration changes rather than all update attempts, with extensions to reversible single\-site chains such as Metropolis\. In a different direction, Gaitonde, Moitra, and Mossel\[[GMM25b](https://arxiv.org/html/2606.31230#bib.bib18)\]show that for higher\-order Markov random fields, access to Glauber dynamics trajectories can bypass i\.i\.d\. hardness barriers \(e\.g\., noisy parity\), yielding efficient learning\.

Technically, our algorithm is close in spirit to several methods in this line of work: we examine short windows of the trajectory to probe the interaction between a candidate pair\(i,j\)\(i,j\), and we exploit sparsity to ensure that with sufficiently large probability no neighbor ofiiorjjupdates within the window, allowing the local effect of\(i,j\)\(i,j\)to be isolated from confounding updates\. That said, structure learning for GGMs differs in important ways from the Ising setting\. First, the variables are continuous, so one cannot rely on discrete indicator statistics present in previous work whose empirical averages directly estimate event probabilities\. Second, in the Gaussian case a key difficulty is*anti\-concentration*: to detect an edge\(i,j\)\(i,j\)one needs the neighbor’s influence on the conditional mean to be typically non\-negligible\. Unlike the Ising setting—where boundedness and discrete concentration can often be leveraged—Gaussian anti\-concentration depends on the scale of the conditional variance \(equivalently, onΘi​i\\Theta\_\{ii\}\) and can degrade without additional regularity beyond\(α,d\)\(\\alpha,d\)\. As a result, while the high\-level philosophy is shared, the Gaussian case requires new technical ideas\.

## 2Technical Overview

At a high level, our algorithm has three ingredients\. First, we estimate the diagonal entriesΘi​i\\Theta\_\{ii\}from short windows of the trajectory and use them to normalize the model so that the precision matrix has \(approximately\) unit diagonal\. Second, for each candidate edge\(i,j\)\(i,j\), we look for short update patterns that isolate the influence ofjjon a later update ofii\. Third, because we cannot directly tell whether hidden neighbor updates occurred inside a window, we treat such windows as contaminated and aggregate many windows using robust median\-based estimators\.

We begin with diagonal estimation because it already contains the main ideas of the full algorithm: short informative windows, unobserved contamination, and robust aggregation\. We then explain how to estimate off\-diagonal entries, and finally describe a simpler variant that is available when the chain is allowed to mix between samples\.

#### Two nearbyii\-updates revealΘi​i\\Theta\_\{ii\}\.

Suppose that at some point in the trajectory theiith coordinate updates twice, with no update to any neighbor ofiiin between\. Write the corresponding states as

X\(0\)⟶iX\(1\)⟶iX\(2\)\.X^\{\(0\)\}\\stackrel\{\{\\scriptstyle i\}\}\{\{\\longrightarrow\}\}X^\{\(1\)\}\\stackrel\{\{\\scriptstyle i\}\}\{\{\\longrightarrow\}\}X^\{\(2\)\}\.Since no neighbor ofiichanges between the twoii\-updates, both updates use the same conditional mean\. Hence

Xi\(1\)−Xi\(2\)∼𝒩​\(0,2Θi​i\)\.X\_\{i\}^\{\(1\)\}\-X\_\{i\}^\{\(2\)\}\\sim\\mathcal\{N\}\\\!\\left\(0,\\frac\{2\}\{\\Theta\_\{ii\}\}\\right\)\.So every such window gives a sample whose variance is exactly2/Θi​i2/\\Theta\_\{ii\}\. This turns diagonal estimation into a one\-dimensional robust variance\-estimation problem\.

#### The “ii” pattern and hidden contamination\.

Exact consecutive “ii” updates are too rare to be useful on the trajectory lengths we target\. Instead, we divide the trajectory into short windows of lengthTTand keep every window that contains at least two updates to coordinateii\. A window is*clean*if, in addition, no neighbor ofiiupdates inside that window\. On a clean window, the same calculation as above shows that the difference between the two updated values of coordinateiiis distributed as𝒩​\(0,2/Θi​i\)\\mathcal\{N\}\(0,2/\\Theta\_\{ii\}\)\.

The difficulty is that cleanliness depends on the unknown neighborhood ofii, so we cannot test it directly\. We therefore keep all windows with twoii\-updates and view the non\-clean ones as contaminated samples\. Because the window is short and the graph isdd\-sparse, the contamination rate is small\. Taking the median absolute deviation of the resulting samples gives a robust estimate ofΘi​i\\Theta\_\{ii\}\.

#### Normalization\.

Using a small initial portion of the trajectory, we estimate every diagonal entryΘi​i\\Theta\_\{ii\}\. We then rescale coordinateiibyΘi​i\\sqrt\{\\Theta\_\{ii\}\}\(or, in the actual algorithm, by its estimate\), replacing each stateX∈ℝnX\\in\\mathbb\{R\}^\{n\}withX′X^\{\\prime\}defined byXi′=Θi​i​XiX\_\{i\}^\{\\prime\}=\\sqrt\{\\Theta\_\{ii\}\}\\,X\_\{i\}\. Under exact normalization,X′X^\{\\prime\}is again a Glauber trajectory, now for a precision matrix with diagonal entries equal to11\. With estimated diagonals, the normalized trajectory has diagonal entries within1±ε1\\pm\\varepsilon, and the later analysis is stable to this approximation\. For the overview, we therefore assume from this point onward that the diagonal is exactly11\.

#### A naive “iji” test forΘi​j\\Theta\_\{ij\}\.

To estimate an off\-diagonal entryΘi​j\\Theta\_\{ij\}, the most natural idea is to look for a short window of the form

X\(1\)⟶iX\(2\)⟶jX\(3\)⟶iX\(4\),X^\{\(1\)\}\\stackrel\{\{\\scriptstyle i\}\}\{\{\\longrightarrow\}\}X^\{\(2\)\}\\stackrel\{\{\\scriptstyle j\}\}\{\{\\longrightarrow\}\}X^\{\(3\)\}\\stackrel\{\{\\scriptstyle i\}\}\{\{\\longrightarrow\}\}X^\{\(4\)\},again with no neighbor ofiiorjjupdating inside the window\. On such a clean window,

Xi\(2\)\\displaystyle X\_\{i\}^\{\(2\)\}=∑k≠i−Θi​k​Xk\(1\)\+ε\(2\),\\displaystyle=\\sum\_\{k\\neq i\}\-\\Theta\_\{ik\}X\_\{k\}^\{\(1\)\}\+\\varepsilon^\{\(2\)\},Xi\(4\)\\displaystyle X\_\{i\}^\{\(4\)\}=∑k≠i−Θi​k​Xk\(3\)\+ε\(4\),\\displaystyle=\\sum\_\{k\\neq i\}\-\\Theta\_\{ik\}X\_\{k\}^\{\(3\)\}\+\\varepsilon^\{\(4\)\},withε\(2\),ε\(4\)∼𝒩​\(0,1\)\\varepsilon^\{\(2\)\},\\varepsilon^\{\(4\)\}\\sim\\mathcal\{N\}\(0,1\)i\.i\.d\. The only relevant change between the two conditional means is the value of coordinatejj, so

Xi\(4\)−Xi\(2\)=−Θi​j​\(Xj\(3\)−Xj\(1\)\)\+ε\(4\)−ε\(2\)\.X\_\{i\}^\{\(4\)\}\-X\_\{i\}^\{\(2\)\}=\-\\Theta\_\{ij\}\\bigl\(X\_\{j\}^\{\(3\)\}\-X\_\{j\}^\{\(1\)\}\\bigr\)\+\\varepsilon^\{\(4\)\}\-\\varepsilon^\{\(2\)\}\.This suggests estimatingΘi​j\\Theta\_\{ij\}from the ratio

Xi\(4\)−Xi\(2\)Xj\(3\)−Xj\(1\)\.\\frac\{X\_\{i\}^\{\(4\)\}\-X\_\{i\}^\{\(2\)\}\}\{X\_\{j\}^\{\(3\)\}\-X\_\{j\}^\{\(1\)\}\}\.To keep the denominator well behaved, we further condition on\|Xj\(3\)−Xj\(1\)\|\>c\\lvert X\_\{j\}^\{\(3\)\}\-X\_\{j\}^\{\(1\)\}\\rvert\>cfor a fixed constantc\>0c\>0\.

#### Why the “iji” test fails\.

The problem is a subtle dependence issue\. In the “iji” pattern, the middlejj\-update depends on the value produced by the firstii\-update\. As a result, the noise term from the firstii\-update is not independent of the denominatorXj\(3\)−Xj\(1\)X\_\{j\}^\{\(3\)\}\-X\_\{j\}^\{\(1\)\}\. So the ratio above is not centered in the simple way suggested by the heuristic calculation\. This is the main obstacle that forces us away from the naive “iji” statistic\.

#### The “iiji” pattern breaks the dependence\.

To remove this dependence, we prepend one extraii\-update and instead search for windows of the form

X\(0\)⟶iX\(1\)⟶iX\(2\)⟶jX\(3\)⟶iX\(4\),X^\{\(0\)\}\\stackrel\{\{\\scriptstyle i\}\}\{\{\\longrightarrow\}\}X^\{\(1\)\}\\stackrel\{\{\\scriptstyle i\}\}\{\{\\longrightarrow\}\}X^\{\(2\)\}\\stackrel\{\{\\scriptstyle j\}\}\{\{\\longrightarrow\}\}X^\{\(3\)\}\\stackrel\{\{\\scriptstyle i\}\}\{\{\\longrightarrow\}\}X^\{\(4\)\},where the visible event requires thatiiupdates in the first, second, and fourth quarters, and thatjjupdates in the third quarter, with no off\-patterni/ji/jupdates\. A window is clean if, in addition, no coordinate in\(N​\(i\)∪N​\(j\)\)∖\{i,j\}\(N\(i\)\\cup N\(j\)\)\\setminus\\\{i,j\\\}updates in the window\. Conditioned onX\(0\)X^\{\(0\)\}, the extraii\-update acts as a refresh step: the secondii\-update is independent of the first, so the noise introduced atX\(1\)X^\{\(1\)\}is independent of the later state of coordinatejj\. This yields the relation

Xi\(4\)−Xi\(1\)=−Θi​j​\(Xj\(3\)−Xj\(0\)\)\+ε\(4\)−ε\(1\),X\_\{i\}^\{\(4\)\}\-X\_\{i\}^\{\(1\)\}=\-\\Theta\_\{ij\}\\bigl\(X\_\{j\}^\{\(3\)\}\-X\_\{j\}^\{\(0\)\}\\bigr\)\+\\varepsilon^\{\(4\)\}\-\\varepsilon^\{\(1\)\},whereε\(1\),ε\(4\)∼𝒩​\(0,1\)\\varepsilon^\{\(1\)\},\\varepsilon^\{\(4\)\}\\sim\\mathcal\{N\}\(0,1\)are independent\. After conditioning on\|Xj\(3\)−Xj\(0\)\|\>c\\bigl\\lvert X\_\{j\}^\{\(3\)\}\-X\_\{j\}^\{\(0\)\}\\bigr\\rvert\>c, the ratio statistic

Xi\(4\)−Xi\(1\)Xj\(3\)−Xj\(0\)=−Θi​j\+ε\(4\)−ε\(1\)Xj\(3\)−Xj\(0\),\\frac\{X\_\{i\}^\{\(4\)\}\-X\_\{i\}^\{\(1\)\}\}\{X\_\{j\}^\{\(3\)\}\-X\_\{j\}^\{\(0\)\}\}=\-\\Theta\_\{ij\}\+\\frac\{\\varepsilon^\{\(4\)\}\-\\varepsilon^\{\(1\)\}\}\{X\_\{j\}^\{\(3\)\}\-X\_\{j\}^\{\(0\)\}\},is centered at−Θi​j\-\\Theta\_\{ij\}and has variance bounded by a constant\. Thus each clean “iiji” window gives a noisy but informative estimate ofΘi​j\\Theta\_\{ij\}\.

#### Robust aggregation\.

As in the diagonal\-estimation step, we cannot directly verify that a window is clean, because the unknown graph determines which coordinates count as hidden neighbors\. We therefore select windows using only the visible “iiji” pattern and treat windows with hidden neighbor updates as contaminated\. Moreover, the variance of the ratio statistic can vary from one accepted window to another, and successive windows are not independent because they come from a single trajectory\. Nevertheless, the dependence is structured enough that martingale concentration can be used in place of the usual independent\-sample Chernoff argument\. This shows that the sample median remains a robust estimator of the common location parameter−Θi​j\-\\Theta\_\{ij\}\. Estimating everyΘi​j\\Theta\_\{ij\}to additive errorO​\(α\)O\(\\alpha\)is then enough to recover the graph structure\. With tighter parameter settings, the same framework also yields multiplicative estimation of the full precision matrix\.

#### Learning with mixing\.

We also give a simpler and more sample\-efficient algorithm when the mixing time is allowed to enter the bound\. We insert waiting periods of length abouttmixt\_\{\\mathrm\{mix\}\}between accepted windows so that each accepted window begins from an almost stationary state\. In this regime, the shorter “iji” pattern suffices\. On a clean stationary window of the normalized trajectory,

X′⁣\(0\)⟶iX′⁣\(1\)⟶jX′⁣\(2\)⟶iX′⁣\(3\),X^\{\\prime\(0\)\}\\stackrel\{\{\\scriptstyle i\}\}\{\{\\longrightarrow\}\}X^\{\\prime\(1\)\}\\stackrel\{\{\\scriptstyle j\}\}\{\{\\longrightarrow\}\}X^\{\\prime\(2\)\}\\stackrel\{\{\\scriptstyle i\}\}\{\{\\longrightarrow\}\}X^\{\\prime\(3\)\},the pair

\(Xj′⁣\(2\)−Xj′⁣\(0\),Xi′⁣\(3\)−Xi′⁣\(1\)\)\\left\(X^\{\\prime\(2\)\}\_\{j\}\-X^\{\\prime\(0\)\}\_\{j\},\\;X^\{\\prime\(3\)\}\_\{i\}\-X^\{\\prime\(1\)\}\_\{i\}\\right\)is centered Gaussian with covariance matrix

\(2−Θi​j′−Θi​j′2\)\.\\begin\{pmatrix\}2&\-\\Theta^\{\\prime\}\_\{ij\}\\\\ \-\\Theta^\{\\prime\}\_\{ij\}&2\\end\{pmatrix\}\.Thus the edge signal appears in the covariance, equivalently in the regression coefficient of the laterii\-increment on the earlierjj\-increment\. After passing to the observable trajectory and conditioning on a largejj\-increment, the ratio statistic−2​Δ^i/Δ^j\-2\\widehat\{\\Delta\}\_\{i\}/\\widehat\{\\Delta\}\_\{j\}is a bounded\-variance noisy estimate ofΘi​j′\\Theta^\{\\prime\}\_\{ij\}\. A robust median over well\-separated epochs then recovers the edge, improving the dependence onddandα\\alphawhen mixing is available\.

#### Information\-theoretic lower bound\.

Finally, we prove an information\-theoretic lower bound showing that logarithmic trajectory length is unavoidable even without computational constraints\. We construct a family of GGMs on2​n2nvertices whose graphs are disjoint unions of edges, with each candidate obtained by deleting one edge from a perfect matching\. The resulting trajectories are hard to distinguish from one another\. By upper\-bounding the pairwise KL divergence and applying Fano’s inequality, we obtain a lower bound on the number of Glauber updates required for structure learning\.

Our lower bound also differs from\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]in both the hard family and the KL calculation\. Instead of working with a broader graph\-class construction, we use a simple family obtained from a perfect matching by deleting a single edge\. More importantly, we work directly with the exact KL divergence of the Gaussian conditional\-update distributions, rather than conditioning on small updates and comparing truncated Gaussians\. This yields alog⁡n\\log nimprovement in the lower bound\. Closing the remaining gap to our current no\-mixing upper bounds is an interesting open problem\.

## 3Preliminaries

### 3\.1Continuous\-time Glauber dynamics

We consider Glauber dynamics in the continuous\-time setting\. The initial configuration is arbitrary, and each coordinatei=1,…,ni=1,\\ldots,nupdates according to an independent Poisson process of rate 1\. The following lemma records the relevant update probabilities:

###### Lemma 3\.1\(Lemma 3\.1 in\[[GMM25b](https://arxiv.org/html/2606.31230#bib.bib18)\]\)\.

Given an intervalI⊂ℝ≥0I\\subset\\mathbb\{R\}\_\{\\geq 0\}of lengthTT, letUIU\_\{I\}denote the set of coordinates that update inII\. For anyS⊂\[n\]S\\subset\[n\]with\|S\|=ℓ\|S\|=\\ell, we have

ℙ​\[S∩UI=∅\]\\displaystyle\\mathbb\{P\}\[S\\cap U\_\{I\}=\\varnothing\]=exp⁡\(−T​ℓ\),\\displaystyle=\\exp\(\-T\\ell\),andℙ​\[S⊆UI\]\\displaystyle\\text\{and\}\\quad\\mathbb\{P\}\[S\\subseteq U\_\{I\}\]≥1−ℓ​exp⁡\(−T\)\.\\displaystyle\\geq 1\-\\ell\\exp\(\-T\)\.

###### Proof\.

For each Poisson processΠ\\Piof rate 1 and intervalI⊆ℝ≥0I\\subseteq\\mathbb\{R\}\_\{\\geq 0\}, we haveℙ​\[Π∩I=∅\]=exp⁡\(−\|I\|\)\\mathbb\{P\}\[\\Pi\\cap I=\\varnothing\]=\\exp\(\-\|I\|\), and the claimed bounds follow immediately\. ∎

### 3\.2Observing patterns

Throughout the paper, we look for intervals containing a specific “pattern,” which we concretely define below:

###### Definition 3\.2\(Pattern exhibition and strictness\)\.

A*pattern*of lengthkkis a sequence of indicesP=\(i1,i2,…,ik\)∈\{1,…,n\}kP=\(i\_\{1\},i\_\{2\},\\ldots,i\_\{k\}\)\\in\\\{1,\\ldots,n\\\}^\{k\}\. Consider a patternPPand an intervalI=\[t,t\+T\)I=\[t,t\+T\)of a continuous\-time single\-site update Glauber trajectory\. LetIj=\[t\+\(j−1\)​T/k,t\+j​T/k\)I\_\{j\}=\[t\+\(j\-1\)T/k,t\+jT/k\)forj=1,…,kj=1,\\ldots,k\. We sayII*exhibits*patternPPif indexiji\_\{j\}updates inIjI\_\{j\}for eachj=1,…,kj=1,\\ldots,k\. We sayIIis*strict*with respect toPPif, for eachj=1,…,kj=1,\\ldots,k, no neighbor of any vertex appearing inPP, other thaniji\_\{j\}, updates inIjI\_\{j\}\.

We next bound the probabilities that a given interval exhibits a pattern and is strict with respect to it\.

###### Lemma 3\.3\.

LetIIbe an interval of lengthTT, and letPPbe a pattern containingℓ\\elldistinct indices\. Then with probability at leastexp⁡\(−T​ℓ​d\)\\exp\(\-T\\ell d\),IIis strict with respect toPP\.

###### Proof\.

Each index inPPhas at mostddneighbors, so we are forbidding at mostℓ​d\\ell dneighbors from updating in eachIjI\_\{j\}\. By[Section3\.1](https://arxiv.org/html/2606.31230#S3.SS1), eachIjI\_\{j\}avoids its respective indices with probability at leastexp⁡\(−T/k⋅ℓ​d\)\\exp\(\-T/k\\cdot\\ell d\)\.

The events in thekksubintervals are independent, so the probability this holds for allkksubintervals is at leastexp⁡\(−T​ℓ​d\)\\exp\(\-T\\ell d\)\. ∎

###### Lemma 3\.4\.

LetIIbe an interval of lengthT≤1/3T\\leq 1/3, and letPPbe a pattern of lengthkk\. Then with probability at leastTk/\(2​kk\)T^\{k\}/\(2k^\{k\}\),IIexhibitsPP\.

###### Proof\.

By[Section3\.1](https://arxiv.org/html/2606.31230#S3.SS1),

ℙ​\[I​exhibits​P\]\\displaystyle\\mathbb\{P\}\[I\\text\{ exhibits \}P\]≥\(1−exp⁡\(−T/k\)\)k\\displaystyle\\geq\(1\-\\exp\(\-T/k\)\)^\{k\}≥Tkkk​exp⁡\(−T\)≥Tk2​kk,\\displaystyle\\geq\\frac\{T^\{k\}\}\{k^\{k\}\}\\exp\(\-T\)\\geq\\frac\{T^\{k\}\}\{2k^\{k\}\},where we use the estimates1−exp⁡\(−x\)≥x​exp⁡\(−x\)1\-\\exp\(\-x\)\\geq x\\exp\(\-x\)andT≤1/3T\\leq 1/3\. ∎

###### Lemma 3\.5\.

For any intervalIIand patternPP, the event thatIIexhibitsPPis independent of the event thatIIis strict with respect toPP\.

###### Proof\.

In each subintervalIjI\_\{j\}, exhibition depends only on the clock ofiji\_\{j\}, while strictness depends only on the clocks of the remaining coordinates\. Thus the two events are independent in eachIjI\_\{j\}, and the claim follows by independence across the disjoint subintervals\. ∎

### 3\.3Corruption and robust estimation

We use several robust estimators in this paper\. We work with the following corruption model\.

###### Definition 3\.6\(η\\eta\-corruption\)\.

Let𝒟\\mathcal\{D\}be a distribution, and letX1,…,Xn∼𝒟X\_\{1\},\\dots,X\_\{n\}\\sim\\mathcal\{D\}be i\.i\.d\. samples\. We say that the observed samplesX~1,…,X~n\\widetilde\{X\}\_\{1\},\\ldots,\\widetilde\{X\}\_\{n\}are*η\\eta\-corrupted*if there exist i\.i\.d\.Bernoulli​\(η\)\\text\{Bernoulli\}\(\\eta\)random variablesξ1,…,ξn\\xi\_\{1\},\\ldots,\\xi\_\{n\}such that for eachi=1,…,ni=1,\\ldots,n,

X~i=\{Xi,if​ξi=0Ai,if​ξi=1,\\widetilde\{X\}\_\{i\}=\\begin\{cases\}X\_\{i\},&\\text\{if \}\\xi\_\{i\}=0\\\\ A\_\{i\},&\\text\{if \}\\xi\_\{i\}=1,\\end\{cases\}where eachAiA\_\{i\}is an arbitrary value\. WheneverX~i=Ai\\widetilde\{X\}\_\{i\}=A\_\{i\}, the corrupted value may be chosen adversarially, may depend on the entire trajectory up to the corrupted sampleX~i\\widetilde\{X\}\_\{i\}, and need not be drawn from any distribution\.555This corruption model is closely related to what some recent work calls*malicious noise*or*strong malicious noise*; see, e\.g\.,\[[BHM\+26](https://arxiv.org/html/2606.31230#bib.bib2)\]\.

Note that our corruption model differs from the Huber contamination model, as corrupted entries may be selected adversarially\. It also differs from the strong contamination model in that each sample is independently corrupted with probabilityη\\eta\. Further, as Glauber trajectories are sampled sequentially, corrupted samples in our corruption model may only depend on prior samples\.

Under this corruption model, we use the following robust estimator for variance\.

###### Lemma 3\.7\(Robust variance estimation\)\.

Let0<η≤1/100<\\eta\\leq 1/10and0<δ<10<\\delta<1\. There is a linear\-time algorithm that takesnnsamples from𝒩​\(0,σ2\)\\mathcal\{N\}\(0,\\sigma^\{2\}\), anη\\eta\-fraction of which are corrupted \(as in[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3)\), and outputsσ^\\widehat\{\\sigma\}such that\|σ^−σ\|<5​η​σ\\lvert\\widehat\{\\sigma\}\-\\sigma\\rvert<5\\eta\\sigmawith probability1−δ1\-\\delta, providedn≥2​log⁡\(4/δ\)η2n\\geq\\frac\{2\\log\(4/\\delta\)\}\{\\eta^\{2\}\}\.

We also use the following mean estimator, which allows for another source of adversarial control in the choice of the variances\.

###### Lemma 3\.8\(Robust mean estimation\)\.

Let0<η≤1/100<\\eta\\leq 1/10and0<δ<10<\\delta<1\. LetΦ\\Phidenote the cdf of a standard Gaussian\. We are given a filtration\(ℱℓ\)ℓ=0n\(\\mathcal\{F\}\_\{\\ell\}\)\_\{\\ell=0\}^\{n\}and samplesx\(1\),…,x\(n\)x^\{\(1\)\},\\ldots,x^\{\(n\)\}\. Suppose there exist indicatorsξ\(ℓ\)∈\{0,1\}\\xi^\{\(\\ell\)\}\\in\\\{0,1\\\}such that

𝔼​\[ξ\(ℓ\)∣ℱℓ−1\]≤ηfor all​ℓ\.\\mathbb\{E\}\[\\xi^\{\(\\ell\)\}\\mid\\mathcal\{F\}\_\{\\ell\-1\}\]\\leq\\eta\\qquad\\text\{for all \}\\ell\.Assume moreover that wheneverξ\(ℓ\)=0\\xi^\{\(\\ell\)\}=0, the clean sample is centered at the same valueμ\\muand has Gaussian tails dominated by unit variance in the sense that, for everyt≥0t\\geq 0,

ℙ\[x\(ℓ\)≥μ\+t\|ℱℓ−1,ξ\(ℓ\)=0\]≤1−Φ\(t\),\\mathbb\{P\}\\\!\\left\[x^\{\(\\ell\)\}\\geq\\mu\+t\\,\\middle\|\\,\\mathcal\{F\}\_\{\\ell\-1\},\\xi^\{\(\\ell\)\}=0\\right\]\\leq 1\-\\Phi\(t\),ℙ\[x\(ℓ\)≤μ−t\|ℱℓ−1,ξ\(ℓ\)=0\]≤1−Φ\(t\)\.\\mathbb\{P\}\\\!\\left\[x^\{\(\\ell\)\}\\leq\\mu\-t\\,\\middle\|\\,\\mathcal\{F\}\_\{\\ell\-1\},\\xi^\{\(\\ell\)\}=0\\right\]\\leq 1\-\\Phi\(t\)\.Then the sample medianμ^\\widehat\{\\mu\}satisfies\|μ^−μ\|<5​η\\lvert\\widehat\{\\mu\}\-\\mu\\rvert<5\\etawith probability1−δ1\-\\delta, providedn≥2​log⁡\(2/δ\)η2n\\geq\\frac\{2\\log\(2/\\delta\)\}\{\\eta^\{2\}\}\.

Note that[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3)remains valid even when the corrupted samples are chosen adversarially with knowledge of the full trajectory of iterates, whereas[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3)does not\. In particular,[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3)applies whenever, conditional onℱℓ−1\\mathcal\{F\}\_\{\\ell\-1\}and on the sample being uncorrupted, the clean law is a Gaussian scale mixtureμ\+σ​ε\\mu\+\\sigma\\varepsilonwith\|σ\|<1\|\\sigma\|<1: averaging overσ\\sigmapreserves the displayed tail bounds\.

The proofs of these estimators are provided in[AppendixA](https://arxiv.org/html/2606.31230#A1)\.

### 3\.4Concentration inequalities

We use the following concentration inequalities in the proofs of[Sections3\.3](https://arxiv.org/html/2606.31230#S3.SS3)and[3\.3](https://arxiv.org/html/2606.31230#S3.SS3)\.

###### Fact 3\.9\(Dvoretzky–Kiefer–Wolfowitz\)\.

LetY1,…,YnY\_\{1\},\\ldots,Y\_\{n\}be i\.i\.d\. real\-valued random variables with cdfFF, and let

Fn​\(t\):=1n​∑i=1n𝟏​\{Yi≤t\},F\_\{n\}\(t\):=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\mathbf\{1\}\\\{Y\_\{i\}\\leq t\\\},be the empirical cdf\. Then for everyε\>0\\varepsilon\>0,

ℙ​\[supt∈ℝ\|Fn​\(t\)−F​\(t\)\|\>ε\]≤2​e−2​n​ε2\.\\mathbb\{P\}\\\!\\left\[\\sup\_\{t\\in\\mathbb\{R\}\}\\bigl\|F\_\{n\}\(t\)\-F\(t\)\\bigr\|\>\\varepsilon\\right\]\\leq 2e^\{\-2n\\varepsilon^\{2\}\}\.

###### Fact 3\.10\(Azuma–Hoeffding\)\.

Let\(Mk,ℱk\)k=0n\(M\_\{k\},\\mathcal\{F\}\_\{k\}\)\_\{k=0\}^\{n\}be a martingale, and suppose that for eachk=1,…,nk=1,\\ldots,n,

Mk−Mk−1∈\[ak,bk\]almost surely\.M\_\{k\}\-M\_\{k\-1\}\\in\[a\_\{k\},b\_\{k\}\]\\qquad\\text\{almost surely\}\.Then for everyt\>0t\>0,

ℙ​\[Mn−M0≥t\]≤exp⁡\(−2​t2∑k=1n\(bk−ak\)2\)\.\\mathbb\{P\}\[M\_\{n\}\-M\_\{0\}\\geq t\]\\leq\\exp\\\!\\left\(\-\\frac\{2t^\{2\}\}\{\\sum\_\{k=1\}^\{n\}\(b\_\{k\}\-a\_\{k\}\)^\{2\}\}\\right\)\.In particular, if each increment lies in an interval of length at most11, then

ℙ​\[Mn−M0≥t\]≤e−2​t2/n\.\\mathbb\{P\}\[M\_\{n\}\-M\_\{0\}\\geq t\]\\leq e^\{\-2t^\{2\}/n\}\.

### 3\.5Mixing and coupling

###### Definition 3\.11\(Mixing and mixed chains\)\.

A positionXiX\_\{i\}of the Markov chainX0X\_\{0\},X1X\_\{1\},…\\ldotsis*ε\\varepsilon\-mixed*ifXiX\_\{i\}has TV\-distance at mostε\\varepsilonfrom its stationary distributionπ\\pi\. We define the*mixing time*by

tmix​\(ε\)\\displaystyle t\_\{\\mathrm\{mix\}\}\(\\varepsilon\)=min⁡\{t≥0:maxx⁡dTV​\(ℒ​\(Xt∣X0=x\),π\)≤ε\},\\displaystyle=\\min\\Big\\\{t\\geq 0:\\max\_\{x\}d\_\{\\mathrm\{TV\}\}\(\\mathcal\{L\}\(X\_\{t\}\\mid X\_\{0\}=x\),\\pi\)\\leq\\varepsilon\\Big\\\},where the maximum is over all starting statesxx\.

The stationary distribution of a Glauber trajectory with covariance matrixΣ\\Sigmais𝒩​\(0,Σ\)\\mathcal\{N\}\(0,\\Sigma\)\. We use the following slightly stronger invariance statement\.

###### Lemma 3\.12\.

Fix a coordinateii\. Ifx∼𝒩​\(0,Σ\)x\\sim\\mathcal\{N\}\(0,\\Sigma\), then after a single Glauber update to theiith coordinate, the resulting positionx′x^\{\\prime\}still satisfiesx′∼𝒩​\(0,Σ\)x^\{\\prime\}\\sim\\mathcal\{N\}\(0,\\Sigma\)\.

###### Proof\.

Without loss of generality, we update the first coordinate\. Write precision and covariance in block matrix form as

Σ\\displaystyle\\Sigma=\(Σ11Σ1,−1Σ−1,1Σ−1,−1\),\\displaystyle=\\begin\{pmatrix\}\\Sigma\_\{11\}&\\Sigma\_\{1,\-1\}\\\\ \\Sigma\_\{\-1,1\}&\\Sigma\_\{\-1,\-1\}\\end\{pmatrix\},Θ\\displaystyle\\Theta=\(Θ11Θ1,−1Θ−1,1Θ−1,−1\)\.\\displaystyle=\\begin\{pmatrix\}\\Theta\_\{11\}&\\Theta\_\{1,\-1\}\\\\ \\Theta\_\{\-1,1\}&\\Theta\_\{\-1,\-1\}\\end\{pmatrix\}\.The update rule is

x−1′=x−1,x1′=−Θ1,−1Θ11​x−1\+𝒩​\(0,1Θ11\)\.x^\{\\prime\}\_\{\-1\}=x\_\{\-1\},\\qquad x\_\{1\}^\{\\prime\}=\-\\frac\{\\Theta\_\{1,\-1\}\}\{\\Theta\_\{11\}\}x\_\{\-1\}\+\\mathcal\{N\}\\left\(0,\\frac\{1\}\{\\Theta\_\{11\}\}\\right\)\.Then\(x1′,x−1′\)\(x\_\{1\}^\{\\prime\},x\_\{\-1\}^\{\\prime\}\)is still Gaussian with mean0\. Moreover,

Cov⁡\(x1′,x−1′\)\\displaystyle\\operatorname\{Cov\}\(x\_\{1\}^\{\\prime\},x\_\{\-1\}^\{\\prime\}\)=−Θ1,−1Θ11​Σ−1,−1=Σ1,−1,\\displaystyle=\-\\frac\{\\Theta\_\{1,\-1\}\}\{\\Theta\_\{11\}\}\\Sigma\_\{\-1,\-1\}=\\Sigma\_\{1,\-1\},Var⁡\(x1′\)\\displaystyle\\operatorname\{Var\}\(x\_\{1\}^\{\\prime\}\)=1Θ11\+Θ1,−1Θ11​Σ−1,−1​Θ−1,1Θ11=Σ11,\\displaystyle=\\frac\{1\}\{\\Theta\_\{11\}\}\+\\frac\{\\Theta\_\{1,\-1\}\}\{\\Theta\_\{11\}\}\\Sigma\_\{\-1,\-1\}\\frac\{\\Theta\_\{\-1,1\}\}\{\\Theta\_\{11\}\}=\\Sigma\_\{11\},by Schur’s complement\. Sincex−1′=x−1x^\{\\prime\}\_\{\-1\}=x\_\{\-1\}, this provesx′∼𝒩​\(0,Σ\)x^\{\\prime\}\\sim\\mathcal\{N\}\(0,\\Sigma\)\. ∎

From here, we may use the coupling lemma to derive a similar statement about mixing\.

###### Fact 3\.13\(Coupling lemma\)\.

Letμ\\muandη\\etabe distributions overℝn\\mathbb\{R\}^\{n\}\. For any couplingω\\omegaofμ\\muandη\\eta, if\(X,Y\)∼ω\(X,Y\)\\sim\\omega, thenℙ​\[X≠Y\]≥dTV​\(μ,η\)\\mathbb\{P\}\[X\\neq Y\]\\geq d\_\{\\mathrm\{TV\}\}\(\\mu,\\eta\)\. Moreover, equality is attained for some coupling\.

###### Corollary 3\.14\.

Letμ\\muandη\\etabe distributions\. Supposef​\(X\)∼ηf\(X\)\\sim\\etawheneverX∼μX\\sim\\mu\. Then, ifYYis sampled from a distribution with TV\-distanceε\\varepsilonfromμ\\mu, thenf​\(Y\)f\(Y\)follows a distribution with TV\-distance at mostε\\varepsilonfromη\\eta\.

###### Proof\.

Letν\\nudenote the distribution ofYY\. By[Section3\.5](https://arxiv.org/html/2606.31230#S3.SS5), there exists a coupling ofX∼μX\\sim\\muandY∼νY\\sim\\nusuch thatℙ​\[X≠Y\]=dTV​\(μ,ν\)≤ε\\mathbb\{P\}\[X\\neq Y\]=d\_\{\\mathrm\{TV\}\}\(\\mu,\\nu\)\\leq\\varepsilon\. Under this coupling,f​\(X\)∼ηf\(X\)\\sim\\etaandℙ​\[f​\(X\)≠f​\(Y\)\]≤ε\\mathbb\{P\}\[f\(X\)\\neq f\(Y\)\]\\leq\\varepsilon\. Another application of[Section3\.5](https://arxiv.org/html/2606.31230#S3.SS5)gives the claim\. ∎

###### Corollary 3\.15\.

Fix a coordinateii\. If a Glauber trajectory isε\\varepsilon\-mixed \(as in[Section3\.5](https://arxiv.org/html/2606.31230#S3.SS5)\), and undergoes a Glauber update to theiith coordinate, it remainsε\\varepsilon\-mixed\.

###### Proof\.

Combine[Section3\.5](https://arxiv.org/html/2606.31230#S3.SS5)and[Section3\.5](https://arxiv.org/html/2606.31230#S3.SS5)\. ∎

## 4Reduction to Normalized Gaussian Graphical Models

In this section we design an algorithm that reduces the problem of learning an arbitrary sparse Gaussian graphical model from a Glauber trajectory to the case where the diagonal entries of the precision matrix are 1\.

To this end, we first estimate the diagonal entries up to a multiplicative factor\(1±O​\(ε\)\)\(1\\pm O\(\\varepsilon\)\)\. We then scale the Glauber trajectoryX\(1\)X^\{\(1\)\},X\(2\)X^\{\(2\)\},…\\ldotsbyXi′⁣\(k\):=Θi​i⋅Xi\(k\)X\_\{i\}^\{\\prime\(k\)\}:=\\sqrt\{\\Theta\_\{ii\}\}\\cdot X\_\{i\}^\{\(k\)\}for alli,ki,k, which we show is itself a Glauber trajectory\. Using our estimates forΘi​i\\Theta\_\{ii\}, we then have a coordinate\-wise\(1±O​\(ε\)\)\(1\\pm O\(\\varepsilon\)\)\-approximation of this scaled trajectory, which also happens to be a Glauber trajectory itself\.

Our main result for this section is as follows:

###### Theorem 4\.1\(Normalization\)\.

Let0<α,δ<10<\\alpha,\\delta<1and0<ε≤1/100<\\varepsilon\\leq 1/10, and letn,d∈ℕn,d\\in\\mathbb\{N\}\. Given a Glauber trajectory evolving according to an\(α,d\)\(\\alpha,d\)\-sparse GGM with precision matrixΘ\\Thetaand having length

T=4000​d​log⁡\(8​n/δ\)ε3\+Trest,T=\\frac\{4000d\\log\(8n/\\delta\)\}\{\\varepsilon^\{3\}\}\+T\_\{\\mathrm\{rest\}\},whereTrest≥0T\_\{\\mathrm\{rest\}\}\\geq 0, there is a polynomial\-time algorithm that outputs an estimateDDfordiag⁡\(Θ\)\\operatorname\{diag\}\(\\Theta\)such that

\|1Di−1Θi​i\|≤εΘi​i∀i,\\left\\lvert\\frac\{1\}\{\\sqrt\{D\_\{i\}\}\}\-\\frac\{1\}\{\\sqrt\{\\Theta\_\{ii\}\}\}\\right\\rvert\\leq\\frac\{\\varepsilon\}\{\\sqrt\{\\Theta\_\{ii\}\}\}\\quad\\forall i,and a trajectory of lengthTrestT\_\{\\mathrm\{rest\}\}evolving according to a GGM with precision matrixΘ^=D−1/2​Θ​D−1/2\\widehat\{\\Theta\}=D^\{\-1/2\}\\Theta D^\{\-1/2\}with probability1−δ1\-\\delta\.

We proceed in three steps\.[Section4\.1](https://arxiv.org/html/2606.31230#S4.SS1)identifies the “i​iii” statistic underlying diagonal estimation\.[Section4\.2](https://arxiv.org/html/2606.31230#S4.SS2)uses this statistic together with robust variance estimation to prove[Section4](https://arxiv.org/html/2606.31230#S4)\.[Section4\.3](https://arxiv.org/html/2606.31230#S4.SS3)shows that the rescaled trajectory is again a Glauber trajectory and then completes the proof of[Theorem4\.1](https://arxiv.org/html/2606.31230#S4.Thmtheorem1)\.

###### Lemma 4\.2\.

For fixedii, given a Glauber trajectory whose length satisfies

T≥4000​d​log⁡\(8/δ\)ε3,T\\geq\\frac\{4000d\\log\(8/\\delta\)\}\{\\varepsilon^\{3\}\},we may retrieve in polynomial time an estimateDiD\_\{i\}forΘi​i\\Theta\_\{ii\}with

\|1Di−1Θi​i\|≤εΘi​i\\left\\lvert\\frac\{1\}\{\\sqrt\{D\_\{i\}\}\}\-\\frac\{1\}\{\\sqrt\{\\Theta\_\{ii\}\}\}\\right\\rvert\\leq\\frac\{\\varepsilon\}\{\\sqrt\{\\Theta\_\{ii\}\}\}with probability1−δ1\-\\delta\.

### 4\.1Properties of the statistic

Fixii\. LetT≤1/3T\\leq 1/3, and letItI\_\{t\}denote the time interval\[t,t\+T\)\[t,t\+T\)\. Let𝒜\(t\)\\mathcal\{A\}^\{\(t\)\}denote the event thatItI\_\{t\}is strict with respect to\(i,i\)\(i,i\), andℬ\(t\)\\mathcal\{B\}^\{\(t\)\}the eventItI\_\{t\}exhibits\(i,i\)\(i,i\)\.

If𝒜\(t\)\\mathcal\{A\}^\{\(t\)\}andℬ\(t\)\\mathcal\{B\}^\{\(t\)\}both hold, letY\(0\)Y^\{\(0\)\},Y\(1\)Y^\{\(1\)\},Y\(2\)Y^\{\(2\)\}denote the position at timestt,t\+T/2t\+T/2,t\+Tt\+Trespectively\.

###### Lemma 4\.3\.

We haveYi\(1\)−Yi\(2\)∣𝒜\(t\),ℬ\(t\)∼𝒩​\(0,2Θi​i\)Y^\{\(1\)\}\_\{i\}\-Y^\{\(2\)\}\_\{i\}\\mid\\mathcal\{A\}^\{\(t\)\},\\mathcal\{B\}^\{\(t\)\}\\sim\\mathcal\{N\}\\left\(0,\\frac\{2\}\{\\Theta\_\{ii\}\}\\right\)\.

###### Proof\.

By[Section1\.1](https://arxiv.org/html/2606.31230#S1.SS1), we have

Yi\(1\)\\displaystyle Y^\{\(1\)\}\_\{i\}=−∑j≠i−Θi​jΘi​i​Yj\(0\)\+ε1,\\displaystyle=\-\\sum\_\{j\\neq i\}\-\\frac\{\\Theta\_\{ij\}\}\{\\Theta\_\{ii\}\}Y^\{\(0\)\}\_\{j\}\+\\varepsilon\_\{1\},andYi\(2\)\\displaystyle\\text\{and\}\\quad Y^\{\(2\)\}\_\{i\}=−∑j≠i−Θi​jΘi​i​Yj\(1\)\+ε2,\\displaystyle=\-\\sum\_\{j\\neq i\}\-\\frac\{\\Theta\_\{ij\}\}\{\\Theta\_\{ii\}\}Y^\{\(1\)\}\_\{j\}\+\\varepsilon\_\{2\},whereε1,ε2∼𝒩​\(0,1Θi​i\)\\varepsilon\_\{1\},\\varepsilon\_\{2\}\\sim\\mathcal\{N\}\(0,\\frac\{1\}\{\\Theta\_\{ii\}\}\)are i\.i\.d\.

If𝒜\(t\)\\mathcal\{A\}^\{\(t\)\}holds,Yj\(1\)=Yj\(2\)Y^\{\(1\)\}\_\{j\}=Y^\{\(2\)\}\_\{j\}for allj≠ij\\neq i, so

Yi\(1\)−Yi\(2\)∣Y\(0\),𝒜\(t\),ℬ\(t\)=ε1−ε2∼𝒩​\(0,2Θi​i\),\\displaystyle Y\_\{i\}^\{\(1\)\}\-Y\_\{i\}^\{\(2\)\}\\mid Y^\{\(0\)\},\\mathcal\{A\}^\{\(t\)\},\\mathcal\{B\}^\{\(t\)\}=\\varepsilon\_\{1\}\-\\varepsilon\_\{2\}\\sim\\mathcal\{N\}\\left\(0,\\frac\{2\}\{\\Theta\_\{ii\}\}\\right\),and the dependence onY\(0\)Y^\{\(0\)\}may be dropped\. ∎

### 4\.2Retrieving the estimator

We divide our sample intoMMintervals of lengthTT, discarding intervals that do not satisfyℬ\(t\)\\mathcal\{B\}^\{\(t\)\}, samplingYi\(1\)−Yi\(2\)Y\_\{i\}^\{\(1\)\}\-Y\_\{i\}^\{\(2\)\}from the rest, and treating intervals that fail to satisfy𝒜\(t\)\\mathcal\{A\}^\{\(t\)\}as corruption in order to predict1/Θi​i1/\\Theta\_\{ii\}with robust one\-dimensional variance estimation\.

By[Sections3\.2](https://arxiv.org/html/2606.31230#S3.SS2)and[3\.2](https://arxiv.org/html/2606.31230#S3.SS2), the corruption rate among the retained intervals is bounded by

qi:=ℙ​\[¬𝒜\(t\)∣ℬ\(t\)\]≤1−e−d​T\.q\_\{i\}:=\\mathbb\{P\}\[\\neg\\mathcal\{A\}^\{\(t\)\}\\mid\\mathcal\{B\}^\{\(t\)\}\]\\leq 1\-e^\{\-dT\}\.
###### Lemma 4\.4\.

In a Glauber dynamic of lengthM​TMT, in at least116​M​T2\\frac\{1\}\{16\}MT^\{2\}intervalsℬ\(t\)\\mathcal\{B\}^\{\(t\)\}holds with probability at least1−exp⁡\(−164​M​T2\)1\-\\exp\(\-\\frac\{1\}\{64\}MT^\{2\}\)\.

###### Proof\.

By[Section3\.2](https://arxiv.org/html/2606.31230#S3.SS2), each interval satisfiesℬ\(t\)\\mathcal\{B\}^\{\(t\)\}with probability at leastT2/8T^\{2\}/8\. These events are independent across disjoint intervals\. A Chernoff lower\-tail bound therefore gives

ℙ​\[∑r=1M𝟏​\{ℬ\(r\)\}≤12​M​T28\]≤exp⁡\(−18​M​T28\),\\mathbb\{P\}\\left\[\\sum\_\{r=1\}^\{M\}\\mathbf\{1\}\\\{\\mathcal\{B\}^\{\(r\)\}\\\}\\leq\\frac\{1\}\{2\}\\frac\{MT^\{2\}\}\{8\}\\right\]\\leq\\exp\\left\(\-\\frac\{1\}\{8\}\\frac\{MT^\{2\}\}\{8\}\\right\),which is exactly the claimed bound\. ∎

###### Proof of[Section4](https://arxiv.org/html/2606.31230#S4)\.

Choose

T=ε5​dandM​T2=800​log⁡\(8/δ\)ε2\.T=\\frac\{\\varepsilon\}\{5d\}\\qquad\\text\{and\}\\qquad MT^\{2\}=\\frac\{800\\log\(8/\\delta\)\}\{\\varepsilon^\{2\}\}\.Then the actual corruption rate satisfies

qi≤1−e−d​T≤1−e−ε/5≤ε5\.q\_\{i\}\\leq 1\-e^\{\-dT\}\\leq 1\-e^\{\-\\varepsilon/5\}\\leq\\frac\{\\varepsilon\}\{5\}\.Since

exp⁡\(−M​T264\)=exp⁡\(−25​log⁡\(8/δ\)2​ε2\)≤δ8,\\exp\\\!\\left\(\-\\frac\{MT^\{2\}\}\{64\}\\right\)=\\exp\\\!\\left\(\-\\frac\{25\\log\(8/\\delta\)\}\{2\\varepsilon^\{2\}\}\\right\)\\leq\\frac\{\\delta\}\{8\},by[Section4\.2](https://arxiv.org/html/2606.31230#S4.SS2), with probability1−δ/21\-\\delta/2we see

M​T216=50​log⁡\(8/δ\)ε2=2​log⁡\(8/δ\)\(ε/5\)2\.\\frac\{MT^\{2\}\}\{16\}=\\frac\{50\\log\(8/\\delta\)\}\{\\varepsilon^\{2\}\}=\\frac\{2\\log\(8/\\delta\)\}\{\(\\varepsilon/5\)^\{2\}\}\.
Then, by[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3)with corruption parameterqi≤ε/5q\_\{i\}\\leq\\varepsilon/5and failure probabilityδ/2\\delta/2, we can estimate2/Θi​i\\sqrt\{2/\\Theta\_\{ii\}\}within additive error

5⋅ε5​2Θi​i=ε​2Θi​i,5\\cdot\\frac\{\\varepsilon\}\{5\}\\sqrt\{\\frac\{2\}\{\\Theta\_\{ii\}\}\}=\\varepsilon\\sqrt\{\\frac\{2\}\{\\Theta\_\{ii\}\}\},and hence within a factor1±ε1\\pm\\varepsilon, with success probability1−δ/21\-\\delta/2\. Taking a union bound gives the desired success rate\.

Finally, the required length of the trajectory is

M​T=4000​d​log⁡\(8/δ\)ε3\.∎MT=\\frac\{4000d\\log\(8/\\delta\)\}\{\\varepsilon^\{3\}\}\.\\qed

Finally, we derive estimates for allnndiagonal entriesΘi​i\\Theta\_\{ii\}\.

###### Corollary 4\.5\.

Given a Glauber dynamic of length

T=4000​d​log⁡\(8​n/δ\)ε3,T=\\frac\{4000d\\log\(8n/\\delta\)\}\{\\varepsilon^\{3\}\},we may retrieve in polynomial time estimatesDiD\_\{i\}for eachiisuch that, with probability at least1−δ1\-\\delta,

\|1Di−1Θi​i\|≤εΘi​i\\left\\lvert\\frac\{1\}\{\\sqrt\{D\_\{i\}\}\}\-\\frac\{1\}\{\\sqrt\{\\Theta\_\{ii\}\}\}\\right\\rvert\\leq\\frac\{\\varepsilon\}\{\\sqrt\{\\Theta\_\{ii\}\}\}for alli=1,…,ni=1,\\ldots,n\.

###### Proof\.

Apply[Section4](https://arxiv.org/html/2606.31230#S4)with errorδ/n\\delta/n\. Then, the probability of any error among thennestimates isδ\\deltaby union bound\. ∎

Algorithm 1D=EstimateDiagonal​\(n,d,α,ε,δ\)D=\\text\{EstimateDiagonal\}\(n,d,\\alpha,\\varepsilon,\\delta\)1:Set

T=ε5​dT=\\frac\{\\varepsilon\}\{5d\}and

M=20000​d2​log⁡\(8​n/δ\)ε4M=\\frac\{20000d^\{2\}\\log\(8n/\\delta\)\}\{\\varepsilon^\{4\}\}\.

2:Observe Glauber trajectory of length

M​TMT, split into

MMintervals

I1I\_\{1\},

…\\ldots,

IMI\_\{M\}of length

TT\.

3:for

i=1,…,ni=1,\\ldots,ndo

4:Let

S=\{1≤t≤M:ℬ\(t\)\}S=\\\{1\\leq t\\leq M:\\mathcal\{B\}^\{\(t\)\}\\\}, where

ℬ\(t\)\\mathcal\{B\}^\{\(t\)\}is defined in[Section4\.1](https://arxiv.org/html/2606.31230#S4.SS1)\.

5:if

\|S\|<116​M​T2\|S\|<\\frac\{1\}\{16\}\{MT^\{2\}\}then

6:Return

⊥\\bot\.

7:else

8:By[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3), estimate

σ^2\\widehat\{\\sigma\}^\{2\}from

\{Yi\(1\)−Yi\(2\):t∈S\}\\\{Y^\{\(1\)\}\_\{i\}\-Y^\{\(2\)\}\_\{i\}:t\\in S\\\}, where

Yi\(1\)Y\_\{i\}^\{\(1\)\}and

Yi\(2\)Y\_\{i\}^\{\(2\)\}are defined in[Section4\.1](https://arxiv.org/html/2606.31230#S4.SS1)\.

9:Set

Di=2/σ^2D\_\{i\}=2/\\widehat\{\\sigma\}^\{2\}\.

10:endif

11:endfor

12:Return

DD\.

### 4\.3Normalizing the Gaussian

LetX\(1\)X^\{\(1\)\},X\(2\)X^\{\(2\)\},…\\ldotsdenote the updates from the Glauber dynamic\. As earlier, defineX′⁣\(1\)X^\{\\prime\(1\)\},X′⁣\(2\)X^\{\\prime\(2\)\},…\\ldotsso thatXi′⁣\(k\):=Θi​i⋅Xi\(k\)X\_\{i\}^\{\\prime\(k\)\}:=\\sqrt\{\\Theta\_\{ii\}\}\\cdot X\_\{i\}^\{\(k\)\}for alli,ki,k\.

###### Lemma 4\.6\.

The aboveX′⁣\(1\)X^\{\\prime\(1\)\},X′⁣\(2\)X^\{\\prime\(2\)\},…\\ldotsis a Glauber trajectory with precision matrixΘ′=Θdiag−1/2​Θ​Θdiag−1/2\\Theta^\{\\prime\}=\\Theta\_\{\\mathrm\{diag\}\}^\{\-1/2\}\\Theta\\Theta\_\{\\mathrm\{diag\}\}^\{\-1/2\}\.

###### Proof\.

Note thatΘi​j′=Θi​jΘi​i​Θj​j\\Theta^\{\\prime\}\_\{ij\}=\\frac\{\\Theta\_\{ij\}\}\{\\sqrt\{\\Theta\_\{ii\}\\Theta\_\{jj\}\}\}\.

We may directly check that[Section1\.1](https://arxiv.org/html/2606.31230#S1.SS1)is preserved\. We have

xi′\\displaystyle x^\{\\prime\}\_\{i\}↦Θi​i​\(−∑j=1nΘi​jΘi​i​xj′Θj​j\+𝒩​\(0,1Θi​i\)\)\\displaystyle\\mapsto\\sqrt\{\\Theta\_\{ii\}\}\\left\(\-\\sum\_\{j=1\}^\{n\}\\frac\{\\Theta\_\{ij\}\}\{\\Theta\_\{ii\}\}\\frac\{x^\{\\prime\}\_\{j\}\}\{\\sqrt\{\\Theta\_\{jj\}\}\}\+\\mathcal\{N\}\\left\(0,\\frac\{1\}\{\\Theta\_\{ii\}\}\\right\)\\right\)=−∑j=1nΘi​jΘi​i​Θj​j​xj′\+𝒩​\(0,1\)\.∎\\displaystyle=\-\\sum\_\{j=1\}^\{n\}\\frac\{\\Theta\_\{ij\}\}\{\\sqrt\{\\Theta\_\{ii\}\\Theta\_\{jj\}\}\}x\_\{j\}^\{\\prime\}\+\\mathcal\{N\}\(0,1\)\.\\qed

To prove our main theorem, we consider the trajectoryX^\(1\)\\widehat\{X\}^\{\(1\)\},X^\(2\)\\widehat\{X\}^\{\(2\)\},…\\ldotsdefined byX^i\(k\)=Di⋅Xi\(k\)\\widehat\{X\}^\{\(k\)\}\_\{i\}=\\sqrt\{D\_\{i\}\}\\cdot X\_\{i\}^\{\(k\)\}for alli,ki,k\.

#### Putting the normalization together\.

###### Proof of[Theorem4\.1](https://arxiv.org/html/2606.31230#S4.Thmtheorem1)\.

It suffices to showX^\\widehat\{X\}is a Glauber dynamic with precision matrixΘ^=D−1/2​Θ​D−1/2\\widehat\{\\Theta\}=D^\{\-1/2\}\\Theta D^\{\-1/2\}, i\.e\.Θ^i​j=Θi​jDi​Dj\\widehat\{\\Theta\}\_\{ij\}=\\frac\{\\Theta\_\{ij\}\}\{\\sqrt\{D\_\{i\}D\_\{j\}\}\}\. Again, we check[Section1\.1](https://arxiv.org/html/2606.31230#S1.SS1)is preserved\. We have

x^i\\displaystyle\\widehat\{x\}\_\{i\}↦Di​\(−∑j=1nΘi​jΘi​i​x^jDj\+𝒩​\(0,1Θi​i\)\)\\displaystyle\\mapsto\\sqrt\{D\_\{i\}\}\\left\(\-\\sum\_\{j=1\}^\{n\}\\frac\{\\Theta\_\{ij\}\}\{\\Theta\_\{ii\}\}\\frac\{\\widehat\{x\}\_\{j\}\}\{\\sqrt\{D\_\{j\}\}\}\+\\mathcal\{N\}\\left\(0,\\frac\{1\}\{\\Theta\_\{ii\}\}\\right\)\\right\)=−∑j=1nΘ^i​jΘ^i​i​x^j\+𝒩​\(0,1Θ^i​i\)\.\\displaystyle=\-\\sum\_\{j=1\}^\{n\}\\frac\{\\widehat\{\\Theta\}\_\{ij\}\}\{\\widehat\{\\Theta\}\_\{ii\}\}\\widehat\{x\}\_\{j\}\+\\mathcal\{N\}\\left\(0,\\frac\{1\}\{\\widehat\{\\Theta\}\_\{ii\}\}\\right\)\.Finally, for independence reasons, we use only the first

Tdiag:=4000​d​log⁡\(8​n/δ\)ε3T\_\{\\mathrm\{diag\}\}:=\\frac\{4000d\\log\(8n/\\delta\)\}\{\\varepsilon^\{3\}\}updates of the trajectory to estimateDD, discard that initial segment, and keep the remaining trajectory of lengthTrestT\_\{\\mathrm\{rest\}\}to produce the trajectory with the desired properties\. ∎

In particular, note that by construction,Θ^\\widehat\{\\Theta\}is coordinate\-wise a\(1±O​\(ε\)\)\(1\\pm O\(\\varepsilon\)\)\-approximation forΘ′\\Theta^\{\\prime\}\(defined in[Section4\.3](https://arxiv.org/html/2606.31230#S4.SS3)\)\.

Concretely,

###### Corollary 4\.7\.

There existc1,…,cn∈1±εc\_\{1\},\\ldots,c\_\{n\}\\in 1\\pm\\varepsilonso that for eachiiandkk, we haveX^i\(k\)=1ci​Xi′⁣\(k\)\\widehat\{X\}\_\{i\}^\{\(k\)\}=\\frac\{1\}\{c\_\{i\}\}X\_\{i\}^\{\\prime\(k\)\}; moreoverΘ^i​j=ci​cj​Θi​j′\\widehat\{\\Theta\}\_\{ij\}=c\_\{i\}c\_\{j\}\\Theta\_\{ij\}^\{\\prime\}for eachiiandjj\.

###### Proof\.

Indeed,

Xi′⁣\(k\)X^i\(k\)=Θi​iDi=:ci∈1±ε,\\frac\{X\_\{i\}^\{\\prime\(k\)\}\}\{\\widehat\{X\}\_\{i\}^\{\(k\)\}\}=\\sqrt\{\\frac\{\\Theta\_\{ii\}\}\{D\_\{i\}\}\}=:c\_\{i\}\\in 1\\pm\\varepsilon,and further

Θ^i​jΘi​j′=Θi​i​Θj​jDi​Dj=ci​cj\.∎\\frac\{\\widehat\{\\Theta\}\_\{ij\}\}\{\\Theta\_\{ij\}^\{\\prime\}\}=\\frac\{\\sqrt\{\\Theta\_\{ii\}\\Theta\_\{jj\}\}\}\{\\sqrt\{D\_\{i\}D\_\{j\}\}\}=c\_\{i\}c\_\{j\}\.\\qed

Thus, the trajectoryX^\\widehat\{X\}we constructed has two properties:

- •it is itself a Glauber trajectory with diagonal entries1±O​\(ε\)1\\pm O\(\\varepsilon\)\(and precision matrixΘ^\\widehat\{\\Theta\}\);
- •it is coordinate\-wise a\(1±ε\)\(1\\pm\\varepsilon\)\-approximation for a Glauber trajectory with diagonal entries 1 \(and precision matrixΘ′\\Theta^\{\\prime\}\)\.

## 5Main Algorithm

We now move to structure\-learning\. Our main result is as follows:

###### Theorem 5\.1\([Theorem1\.3](https://arxiv.org/html/2606.31230#S1.Thmtheorem3)\)\.

Let0<α,δ<10<\\alpha,\\delta<1andn,d∈ℕn,d\\in\\mathbb\{N\}\. Given a Glauber trajectory evolving according to an\(α,d\)\(\\alpha,d\)\-sparse GGM with precision matrixΘ\\Thetaand whose length satisfies

T≥256⋅2575​d3​log⁡\(4​n/δ\)α5,T\\geq\\frac\{256\\cdot 257^\{5\}\\,d^\{3\}\\log\(4n/\\delta\)\}\{\\alpha^\{5\}\},there is a polynomial\-time algorithm that correctly outputs whetheri∼ji\\sim jfor eachiiandjjwith probability1−δ1\-\\delta\.

We also derive the following parameter\-learning guarantees:

###### Corollary 5\.2\([Theorem1\.4](https://arxiv.org/html/2606.31230#S1.Thmtheorem4)\)\.

Let0<α,δ,ε<10<\\alpha,\\delta,\\varepsilon<1, and letn,d∈ℕn,d\\in\\mathbb\{N\}\. Given a Glauber trajectory evolving according to an\(α,d\)\(\\alpha,d\)\-sparse GGM with precision matrixΘ\\Thetaand whose length satisfies

T≥256⋅2575​d3​log⁡\(4​n/δ\)α5​ε5,T\\geq\\frac\{256\\cdot 257^\{5\}\\,d^\{3\}\\log\(4n/\\delta\)\}\{\\alpha^\{5\}\\varepsilon^\{5\}\},there is a polynomial\-time algorithm that outputs an estimateΘ^\\widehat\{\\Theta\}forΘ\\Thetasuch that\|Θ^i​j−Θi​j\|≤ε​\|Θi​j\|\\left\\lvert\\widehat\{\\Theta\}\_\{ij\}\-\\Theta\_\{ij\}\\right\\rvert\\leq\\varepsilon\\left\\lvert\\Theta\_\{ij\}\\right\\rvertfor eachiiandjj\.

To this end, we fixiiandjj, and evaluate the existence of each edgei∼ji\\sim jindividually\.

###### Lemma 5\.3\.

For fixediiandjj, given a Glauber trajectory whose length satisfies

T≥128⋅2575​d3​log⁡\(16/δ\)α5,T\\geq\\frac\{128\\cdot 257^\{5\}\\,d^\{3\}\\log\(16/\\delta\)\}\{\\alpha^\{5\}\},we may determine whetheri∼ji\\sim jin polynomial time with probability1−δ1\-\\delta\.

[Section5\.1](https://arxiv.org/html/2606.31230#S5.SS1)analyzes the statistic used to test whetheri∼ji\\sim j: first in the ideal normalized trajectory, then for the observable approximate trajectory, and finally after conditioning on a large denominator\.[Section5\.2](https://arxiv.org/html/2606.31230#S5.SS2)uses these ingredients to build the estimator and complete the proofs of[Section5](https://arxiv.org/html/2606.31230#S5),[Theorem5\.1](https://arxiv.org/html/2606.31230#S5.Thmtheorem1), and[Section5](https://arxiv.org/html/2606.31230#S5)\.

A naive analysis based on the shorter “i​j​iiji” pattern fails because the middlejj\-update depends on the earlierii\-update, creating a dependence in the resulting ratio statistic\. For this reason we instead study the “i​i​j​iiiji” pattern, whose extraii\-update breaks this dependence and leads to the statistic analyzed below\. The observations remain dependent and can be corrupted by hidden neighbor updates, so after conditioning on\|Δj\|\>c\|\\Delta\_\{j\}\|\>cwe estimate the resulting location parameter using[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3)\.

### 5\.1Properties of the statistic

Fixiiandjj\. LetT≤1/3T\\leq 1/3, letItI\_\{t\}denote the time interval\[t,t\+T\)\[t,t\+T\), and letPi​i​j​i:=\(i,i,j,i\)P\_\{iiji\}:=\(i,i,j,i\)\. Let𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}denote the observable event thatItI\_\{t\}exhibitsPi​i​j​iP\_\{iiji\}, and let𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}denote the event thatItI\_\{t\}is strict with respect toPi​i​j​iP\_\{iiji\}\. By[Section3\.2](https://arxiv.org/html/2606.31230#S3.SS2),𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}and𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}are independent\.

Normalize the Glauber trajectory by[Theorem4\.1](https://arxiv.org/html/2606.31230#S4.Thmtheorem1), and letX^\\widehat\{X\}consist of\(1±1/10\)\(1\\pm 1/10\)coordinate\-wise approximations ofX′X^\{\\prime\}\. We first analyze the normalized Glauber dynamicX′X^\{\\prime\}\.

#### The ideal normalized statistic\.

Conditioned on𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}and𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}, letY′⁣\(k\)Y^\{\\prime\(k\)\}denote the value ofX′X^\{\\prime\}at timet\+T​k/4t\+Tk/4, fork=0,1,2,3,4k=0,1,2,3,4\. Denote

Δj′⁣\(t\):=Yj′⁣\(3\)−Yj′⁣\(0\)andΔi′⁣\(t\):=Yi′⁣\(4\)−Yi′⁣\(1\)\.\\Delta^\{\\prime\(t\)\}\_\{j\}:=Y^\{\\prime\(3\)\}\_\{j\}\-Y^\{\\prime\(0\)\}\_\{j\}\\quad\\text\{and\}\\quad\\Delta^\{\\prime\(t\)\}\_\{i\}:=Y^\{\\prime\(4\)\}\_\{i\}\-Y^\{\\prime\(1\)\}\_\{i\}\.
###### Lemma 5\.4\.

We haveΔi′⁣\(t\)∣𝒞\(t\),𝒟\(t\),Y′⁣\(0\),Y′⁣\(3\)∼−Θi​j′​Δj′⁣\(t\)\+𝒩​\(0,2\)\\Delta^\{\\prime\(t\)\}\_\{i\}\\mid\\mathcal\{C\}^\{\(t\)\},\\mathcal\{D\}^\{\(t\)\},Y^\{\\prime\(0\)\},Y^\{\\prime\(3\)\}\\sim\-\\Theta\_\{ij\}^\{\\prime\}\\Delta^\{\\prime\(t\)\}\_\{j\}\+\\mathcal\{N\}\(0,2\)\.

###### Proof\.

Throughout this proof we condition on𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}and𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}\. Letε1,ε2,ε3,ε4∼𝒩​\(0,1\)\\varepsilon\_\{1\},\\varepsilon\_\{2\},\\varepsilon\_\{3\},\\varepsilon\_\{4\}\\sim\\mathcal\{N\}\(0,1\)denote the fresh noises coming from the last designated updates ofiiin the first, second, and fourth quarters, and ofjjin the third quarter, respectively\. By the definition of𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}and𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}, the interval exhibitsPi​i​j​iP\_\{iiji\}and is strict with respect to it\.

First,

Yi′⁣\(1\)=−∑k≠iΘi​k′​Yk′⁣\(0\)\+ε1,Y\_\{i\}^\{\\prime\(1\)\}=\-\\sum\_\{k\\neq i\}\\Theta\_\{ik\}^\{\\prime\}Y\_\{k\}^\{\\prime\(0\)\}\+\\varepsilon\_\{1\},because no neighbor ofiichanges during the first quarter\. Likewise,

Yi′⁣\(2\)=−∑k≠iΘi​k′​Yk′⁣\(0\)\+ε2,Y\_\{i\}^\{\\prime\(2\)\}=\-\\sum\_\{k\\neq i\}\\Theta\_\{ik\}^\{\\prime\}Y\_\{k\}^\{\\prime\(0\)\}\+\\varepsilon\_\{2\},because the second quarter again contains anii\-update and no neighbor ofiiupdates\.

Before the designatedjj\-update in the third quarter, the only neighbor ofjjthat may have changed isii, so

Yj′⁣\(3\)=−∑k≠jΘj​k′​Yk′⁣\(2\)\+ε3\.Y\_\{j\}^\{\\prime\(3\)\}=\-\\sum\_\{k\\neq j\}\\Theta\_\{jk\}^\{\\prime\}Y\_\{k\}^\{\\prime\(2\)\}\+\\varepsilon\_\{3\}\.ThusY′⁣\(3\)Y^\{\\prime\(3\)\}depends onε2\\varepsilon\_\{2\}andε3\\varepsilon\_\{3\}, but not onε1\\varepsilon\_\{1\}\.

Finally, before the designatedii\-update in the fourth quarter, the only neighbor ofiithat may have changed isjj, so

Yi′⁣\(4\)=−∑k≠i,jΘi​k′​Yk′⁣\(0\)−Θi​j′​Yj′⁣\(3\)\+ε4\.Y\_\{i\}^\{\\prime\(4\)\}=\-\\sum\_\{k\\neq i,j\}\\Theta\_\{ik\}^\{\\prime\}Y\_\{k\}^\{\\prime\(0\)\}\-\\Theta\_\{ij\}^\{\\prime\}Y\_\{j\}^\{\\prime\(3\)\}\+\\varepsilon\_\{4\}\.Subtracting the expression forYi′⁣\(1\)Y\_\{i\}^\{\\prime\(1\)\}gives

Yi′⁣\(4\)−Yi′⁣\(1\)=−Θi​j′​\(Yj′⁣\(3\)−Yj′⁣\(0\)\)\+ε4−ε1\.Y\_\{i\}^\{\\prime\(4\)\}\-Y\_\{i\}^\{\\prime\(1\)\}=\-\\Theta\_\{ij\}^\{\\prime\}\\bigl\(Y\_\{j\}^\{\\prime\(3\)\}\-Y\_\{j\}^\{\\prime\(0\)\}\\bigr\)\+\\varepsilon\_\{4\}\-\\varepsilon\_\{1\}\.Thenε4−ε1∼𝒩​\(0,2\)\\varepsilon\_\{4\}\-\\varepsilon\_\{1\}\\sim\\mathcal\{N\}\(0,2\)is independent ofY′⁣\(0\)Y^\{\\prime\(0\)\}andY′⁣\(3\)Y^\{\\prime\(3\)\}\. This proves the claim\. ∎

#### Passing to the observable statistic\.

We now turn to the observable data fromX^\\widehat\{X\}\. LetY^\(k\)\\widehat\{Y\}^\{\(k\)\}denote the value ofX^\\widehat\{X\}at timet\+T​k/4t\+Tk/4, fork=0,1,2,3,4k=0,1,2,3,4\. Denote

Δ^j\(t\)=Y^j\(3\)−Y^j\(0\)andΔ^i\(t\)=Y^i\(4\)−Y^i\(1\)\.\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}=\\widehat\{Y\}^\{\(3\)\}\_\{j\}\-\\widehat\{Y\}^\{\(0\)\}\_\{j\}\\quad\\text\{and\}\\quad\\widehat\{\\Delta\}\_\{i\}^\{\(t\)\}=\\widehat\{Y\}^\{\(4\)\}\_\{i\}\-\\widehat\{Y\}^\{\(1\)\}\_\{i\}\.
###### Lemma 5\.5\.

For constantsci,cj∈1±1/10c\_\{i\},c\_\{j\}\\in 1\\pm 1/10as in Corollary[4\.3](https://arxiv.org/html/2606.31230#S4.SS3.SSS0.Px1), we have for allttwith𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}and𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}that

Δ^i\(t\)∣𝒞\(t\),𝒟\(t\),Y^\(0\),Y^\(3\)∼−cjci​Θi​j′​Δ^j\(t\)\+𝒩​\(0,2ci2\)\.\\displaystyle\\widehat\{\\Delta\}\_\{i\}^\{\(t\)\}\\mid\\mathcal\{C\}^\{\(t\)\},\\mathcal\{D\}^\{\(t\)\},\\widehat\{Y\}^\{\(0\)\},\\widehat\{Y\}^\{\(3\)\}\\sim\-\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta\_\{ij\}^\{\\prime\}\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}\+\\mathcal\{N\}\\left\(0,\\frac\{2\}\{c\_\{i\}^\{2\}\}\\right\)\.

###### Proof\.

By Corollary[4\.3](https://arxiv.org/html/2606.31230#S4.SS3.SSS0.Px1), we haveΔ^i\(t\)=1ci​Δi′⁣\(t\)\\widehat\{\\Delta\}\_\{i\}^\{\(t\)\}=\\frac\{1\}\{c\_\{i\}\}\\Delta^\{\\prime\(t\)\}\_\{i\}andΔ^j\(t\)=1cj​Δj′⁣\(t\)\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}=\\frac\{1\}\{c\_\{j\}\}\\Delta^\{\\prime\(t\)\}\_\{j\}, from which the claim follows\. ∎

#### Conditioning on a large denominator\.

Letℰ\(t\)\\mathcal\{E\}^\{\(t\)\}denote the condition that\|Δ^j\(t\)\|≥0\.6\\lvert\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}\\rvert\\geq 0\.6\. We will restrict our attention to samples whereℰ\(t\)\\mathcal\{E\}^\{\(t\)\}holds\.

###### Lemma 5\.6\.

We haveℙ​\[ℰ\(t\)∣𝒟\(t\),Y^\(0\)\]\>1/4\\mathbb\{P\}\[\\mathcal\{E\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\},\\widehat\{Y\}^\{\(0\)\}\]\>1/4\.

###### Proof\.

Ascj<1\.1c\_\{j\}<1\.1, we have that\|Δ^j\(t\)\|≥0\.6\\lvert\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}\\rvert\\geq 0\.6is implied by\|Δj′⁣\(t\)\|≥0\.66\\lvert\\Delta^\{\\prime\(t\)\}\_\{j\}\\rvert\\geq 0\.66, so it suffices to show\|Δj′⁣\(t\)\|≥0\.66\\lvert\\Delta^\{\\prime\(t\)\}\_\{j\}\\rvert\\geq 0\.66with probability more than1/41/4\.

LetZZbe the value ofX′X^\{\\prime\}right before the lastjj\-update in the third quarter\. Then, by[Section1\.1](https://arxiv.org/html/2606.31230#S1.SS1),Yj′⁣\(3\)Y^\{\\prime\(3\)\}\_\{j\}givenZZis a Gaussian with variance 1, i\.e\.Δj′⁣\(t\)∣Z∼𝒩​\(m,1\)\\Delta^\{\\prime\(t\)\}\_\{j\}\\mid Z\\sim\\mathcal\{N\}\(m,1\)for somemmdependent onZZ\.

Therefore, for any fixedZZ, we have

ℙ​\[\|Δj′⁣\(t\)\|\>0\.66∣Z\]\\displaystyle\\mathbb\{P\}\[\\lvert\\Delta\_\{j\}^\{\\prime\(t\)\}\\rvert\>0\.66\\mid Z\]=ℙx∼𝒩​\(m,1\)​\[\|x\|≥0\.66∣Z\]\\displaystyle=\\mathbb\{P\}\_\{x\\sim\\mathcal\{N\}\(m,1\)\}\[\\lvert x\\rvert\\geq 0\.66\\mid Z\]≥ℙx∼𝒩​\(\|m\|,1\)​\[x≥0\.66∣Z\]\\displaystyle\\geq\\mathbb\{P\}\_\{x\\sim\\mathcal\{N\}\(\\lvert m\\rvert,1\)\}\[x\\geq 0\.66\\mid Z\]≥ℙx∼𝒩​\(0,1\)​\[x≥0\.66\]\>1/4,\\displaystyle\\geq\\mathbb\{P\}\_\{x\\sim\\mathcal\{N\}\(0,1\)\}\[x\\geq 0\.66\]\>1/4,implying that

ℙ​\[\|Δj′⁣\(t\)\|\>0\.66∣𝒟\(t\),Y^\(0\)\]\>14,\\mathbb\{P\}\[\\lvert\\Delta\_\{j\}^\{\\prime\(t\)\}\\rvert\>0\.66\\mid\\mathcal\{D\}^\{\(t\)\},\\widehat\{Y\}^\{\(0\)\}\]\>\\frac\{1\}\{4\},regardless of the realized value ofZZ\. ∎

###### Lemma 5\.7\.

For someσ<2\.62\\sigma<2\.62, we have

−Δ^i\(t\)Δ^j\(t\)\|Y^\(0\),Y^\(3\),𝒞\(t\),𝒟\(t\),ℰ\(t\)∼cjci​Θi​j′\+𝒩​\(0,σ2\)\.\-\\frac\{\\widehat\{\\Delta\}^\{\(t\)\}\_\{i\}\}\{\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\}\\;\\Bigm\|\\;\\widehat\{Y\}^\{\(0\)\},\\widehat\{Y\}^\{\(3\)\},\\mathcal\{C\}^\{\(t\)\},\\mathcal\{D\}^\{\(t\)\},\\mathcal\{E\}^\{\(t\)\}\\sim\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta\_\{ij\}^\{\\prime\}\+\\mathcal\{N\}\(0,\\sigma^\{2\}\)\.

###### Proof\.

Sinceℰ\(t\)\\mathcal\{E\}^\{\(t\)\}is determined byY^\(0\)\\widehat\{Y\}^\{\(0\)\}andY^\(3\)\\widehat\{Y\}^\{\(3\)\},[Section5\.1](https://arxiv.org/html/2606.31230#S5.SS1.SSS0.Px2)gives

Δ^i\(t\)Δ^j\(t\)\|Y^\(0\),Y^\(3\),𝒞\(t\),𝒟\(t\),ℰ\(t\)∼−cjci​Θi​j′\+𝒩​\(0,2ci2​\(Δ^j\(t\)\)2\),\\displaystyle\\frac\{\\widehat\{\\Delta\}^\{\(t\)\}\_\{i\}\}\{\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\}\\;\\Bigm\|\\;\\widehat\{Y\}^\{\(0\)\},\\widehat\{Y\}^\{\(3\)\},\\mathcal\{C\}^\{\(t\)\},\\mathcal\{D\}^\{\(t\)\},\\mathcal\{E\}^\{\(t\)\}\\sim\-\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta\_\{ij\}^\{\\prime\}\+\\mathcal\{N\}\\left\(0,\\frac\{2\}\{c\_\{i\}^\{2\}\\left\(\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}\\right\)^\{2\}\}\\right\),Sinceci\>0\.9c\_\{i\}\>0\.9and\|Δ^j\(t\)\|\>0\.6\\lvert\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}\\rvert\>0\.6, the upper bound follows from2ci​\|Δ^j\(t\)\|<2\.62\\frac\{\\sqrt\{2\}\}\{c\_\{i\}\\lvert\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}\\rvert\}<2\.62\. ∎

### 5\.2Retrieving the estimator

We divide our Glauber trajectory intoMMintervals of lengthTT, for someMMandTTwe will decide later \(so the trajectory has lengthM​TMT\)\. We discard intervals that do not satisfy𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}andℰ\(t\)\\mathcal\{E\}^\{\(t\)\}, sampling−Δ^i\(t\)/Δ^j\(t\)\-\\widehat\{\\Delta\}\_\{i\}^\{\(t\)\}/\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}from the rest, and treating intervals that fail to satisfy𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}as corruption\.

Algorithm 2Θ~=LearnGGM​\(n,d,α,ε,δ\)\\widetilde\{\\Theta\}=\\text\{LearnGGM\}\(n,d,\\alpha,\\varepsilon,\\delta\)1:Set

ϕ=α/257\\phi=\\alpha/257,

T=ϕ/dT=\\phi/d, and

M=256​d4​log⁡\(4​n/δ\)/ϕ6M=256d^\{4\}\\log\(4n/\\delta\)/\\phi^\{6\}\.

2:Let

diag⁡\(Θ~\)=EstimateDiagonal​\(n,d,α,1/10,δ/2\)\\operatorname\{diag\}\(\\widetilde\{\\Theta\}\)=\\text\{EstimateDiagonal\}\(n,d,\\alpha,1/10,\\delta/2\)from Algorithm[1](https://arxiv.org/html/2606.31230#alg1)\.

3:Use the remaining trajectory\.

4:Let

E=∅E=\\varnothing\.

5:Observe Glauber trajectory of length

M​TMT, split into

MMintervals

I1I\_\{1\},

…\\ldots,

IMI\_\{M\}of length

TT\.

6:for

i=1,…,ni=1,\\ldots,ndo

7:for

j=i\+1,…,nj=i\+1,\\ldots,ndo

8:Let

S=\{1≤t≤M:𝒟\(t\),ℰ\(t\)\}S=\\\{1\\leq t\\leq M:\\mathcal\{D\}^\{\(t\)\},\\mathcal\{E\}^\{\(t\)\}\\\}, where

𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}and

ℰ\(t\)\\mathcal\{E\}^\{\(t\)\}are defined in[Section5\.1](https://arxiv.org/html/2606.31230#S5.SS1)\.

9:if

\|S\|<14096​M​T4\|S\|<\\frac\{1\}\{4096\}\{MT^\{4\}\}then

10:Return

⊥\\bot\.

11:else

12:By[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3), estimate the median

ν^\\widehat\{\\nu\}from

\{−Δ^i\(t\)/\(2\.62​Δ^j\(t\)\):t∈S\}\\\{\-\\widehat\{\\Delta\}^\{\(t\)\}\_\{i\}/\(2\.62\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\):t\\in S\\\}, where

Δ^i\(t\)\\widehat\{\\Delta\}\_\{i\}^\{\(t\)\}and

Δ^j\(t\)\\widehat\{\\Delta\}\_\{j\}^\{\(t\)\}are defined in[Section5\.1](https://arxiv.org/html/2606.31230#S5.SS1), and set

μ^=−2\.62​ν^\\widehat\{\\mu\}=\-2\.62\\widehat\{\\nu\}\.

13:if

\|μ^\|\>9​α/22\|\\widehat\{\\mu\}\|\>9\\alpha/22then

14:Set

E=E⊔\{\(i,j\)\}E=E\\sqcup\\\{\(i,j\)\\\}\.

15:endif

16:endif

17:endfor

18:endfor

19:Return

EE\.

Letη\\etabe an upper bound on the conditional corruption probability of an accepted interval, i\.e\. onℙ​\[¬𝒞\(t\)∣𝒟\(t\),ℰ\(t\),s\]\\mathbb\{P\}\[\\neg\\mathcal\{C\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\},\\mathcal\{E\}^\{\(t\)\},s\]for a realized start statess\. We first boundη\\eta\.

###### Lemma 5\.8\.

We haveη≤4​\(1−exp⁡\(−2​T​d\)\)\\eta\\leq 4\(1\-\\exp\(\-2Td\)\)\.

###### Proof\.

Letssdenote the start state of the interval\. SincePi​i​j​iP\_\{iiji\}contains two distinct indices,[Section3\.2](https://arxiv.org/html/2606.31230#S3.SS2)gives

ℙ​\[¬𝒞\(t\)\]≤1−e−2​T​d\.\\mathbb\{P\}\[\\neg\\mathcal\{C\}^\{\(t\)\}\]\\leq 1\-e^\{\-2Td\}\.Also, by[Section3\.2](https://arxiv.org/html/2606.31230#S3.SS2)and independence of the future clocks from the start state,

ℙ​\[¬𝒞\(t\)∣𝒟\(t\),s\]≤1−e−2​T​d\.\\mathbb\{P\}\[\\neg\\mathcal\{C\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\},s\]\\leq 1\-e^\{\-2Td\}\.Also[Section5\.1](https://arxiv.org/html/2606.31230#S5.SS1.SSS0.Px3)gives

ℙ​\[ℰ\(t\)∣𝒟\(t\),s\]\>1/4\.\\mathbb\{P\}\[\\mathcal\{E\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\},s\]\>1/4\.Therefore, for every start statess,

ℙ​\[¬𝒞\(t\)∣𝒟\(t\),ℰ\(t\),s\]\\displaystyle\\mathbb\{P\}\[\\neg\\mathcal\{C\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\},\\mathcal\{E\}^\{\(t\)\},s\]=ℙ​\[ℰ\(t\)∣¬𝒞\(t\),𝒟\(t\),s\]​ℙ​\[¬𝒞\(t\)∣𝒟\(t\),s\]ℙ​\[ℰ\(t\)∣𝒟\(t\),s\]≤4​\(1−e−2​T​d\)\.\\displaystyle=\\frac\{\\mathbb\{P\}\[\\mathcal\{E\}^\{\(t\)\}\\mid\\neg\\mathcal\{C\}^\{\(t\)\},\\mathcal\{D\}^\{\(t\)\},s\]\\,\\mathbb\{P\}\[\\neg\\mathcal\{C\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\},s\]\}\{\\mathbb\{P\}\[\\mathcal\{E\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\},s\]\}\\leq 4\(1\-e^\{\-2Td\}\)\.Averaging over the start state yields the claim\. ∎

We next show that we can collect sufficiently many samples in which𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}andℰ\(t\)\\mathcal\{E\}^\{\(t\)\}hold\.

###### Lemma 5\.9\.

For a Glauber dynamic of lengthM​TMT\(split intoMMintervals of lengthTTas above\), in at leastM​T4/4096MT^\{4\}/4096intervals do𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}andℰ\(t\)\\mathcal\{E\}^\{\(t\)\}hold with probability at least1−exp⁡\(−M​T4/16384\)1\-\\exp\(\-MT^\{4\}/16384\)\.

###### Proof\.

Let

At:=𝟏​\{𝒟\(t\)∧ℰ\(t\)\},A\_\{t\}:=\\mathbf\{1\}\\\{\\mathcal\{D\}^\{\(t\)\}\\wedge\\mathcal\{E\}^\{\(t\)\}\\\},and letℱt\\mathcal\{F\}\_\{t\}be the sigma\-field generated by the firstttintervals\. By[Section3\.2](https://arxiv.org/html/2606.31230#S3.SS2)applied to the patternPi​i​j​iP\_\{iiji\},

ℙ​\[𝒟\(t\)\]≥T4512\.\\mathbb\{P\}\[\\mathcal\{D\}^\{\(t\)\}\]\\geq\\frac\{T^\{4\}\}\{512\}\.Together with[Section5\.1](https://arxiv.org/html/2606.31230#S5.SS1.SSS0.Px3), this yields

𝔼\[At∣ℱt−1\]≥T42048=:p0\.\\mathbb\{E\}\[A\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\geq\\frac\{T^\{4\}\}\{2048\}=:p\_\{0\}\.Fixs\>0s\>0\. Since0≤At≤10\\leq A\_\{t\}\\leq 1,

𝔼​\[e−s​At∣ℱt−1\]\\displaystyle\\mathbb\{E\}\[e^\{\-sA\_\{t\}\}\\mid\\mathcal\{F\}\_\{t\-1\}\]=1−\(1−e−s\)​𝔼​\[At∣ℱt−1\]≤e−\(1−e−s\)​p0\.\\displaystyle=1\-\(1\-e^\{\-s\}\)\\mathbb\{E\}\[A\_\{t\}\\mid\\mathcal\{F\}\_\{t\-1\}\]\\leq e^\{\-\(1\-e^\{\-s\}\)p\_\{0\}\}\.Therefore

Zr:=exp\(−s∑t=1rAt\+\(1−e−s\)p0r\)Z\_\{r\}:=\\exp\\\!\\left\(\-s\\sum\_\{t=1\}^\{r\}A\_\{t\}\+\(1\-e^\{\-s\}\)p\_\{0\}r\\right\)is a supermartingale\. Using Markov’s inequality withs=log⁡2s=\\log 2,

ℙ​\[∑t=1MAt<M​p02\]\\displaystyle\\mathbb\{P\}\\\!\\left\[\\sum\_\{t=1\}^\{M\}A\_\{t\}<\\frac\{Mp\_\{0\}\}\{2\}\\right\]≤exp⁡\(log⁡22​M​p0−12​M​p0\)<e−M​p0/8\.\\displaystyle\\leq\\exp\\\!\\left\(\\frac\{\\log 2\}\{2\}Mp\_\{0\}\-\\frac\{1\}\{2\}Mp\_\{0\}\\right\)<e^\{\-Mp\_\{0\}/8\}\.SinceM​p0/2=M​T4/4096Mp\_\{0\}/2=MT^\{4\}/4096andM​p0/8=M​T4/16384Mp\_\{0\}/8=MT^\{4\}/16384, the claim follows\. ∎

#### Putting the estimator together\.

###### Proof of[Section5](https://arxiv.org/html/2606.31230#S5)\.

First isolate the first

Tdiag:=4,000,000​d​log⁡\(32/δ\)T\_\{\\mathrm\{diag\}\}:=4\{,\}000\{,\}000d\\log\(32/\\delta\)of the trajectory\. Applying[Section4](https://arxiv.org/html/2606.31230#S4)withε=1/10\\varepsilon=1/10and failure probabilityδ/4\\delta/4to coordinatesiiandjjrecovers approximationsDi​iD\_\{ii\}andDj​jD\_\{jj\}of the diagonal up to multiplicative factor1±1/101\\pm 1/10, and hence all necessary readings ofX^i\\widehat\{X\}\_\{i\}andX^j\\widehat\{X\}\_\{j\}, with probability at least1−δ/21\-\\delta/2\. We then focus on the remainder of the trajectory\.

Set

ϕ:=α257,T:=ϕd,M​T4:=128​log⁡\(8/δ\)ϕ2\.\\phi:=\\frac\{\\alpha\}\{257\},\\qquad T:=\\frac\{\\phi\}\{d\},\\qquad MT^\{4\}:=\\frac\{128\\log\(8/\\delta\)\}\{\\phi^\{2\}\}\.The previous lemma gives the uniform conditional corruption bound

ℙ​\[¬𝒞\(t\)∣𝒟\(t\),ℰ\(t\),s\]\\displaystyle\\mathbb\{P\}\[\\neg\\mathcal\{C\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\},\\mathcal\{E\}^\{\(t\)\},s\]≤4​\(1−e−2​T​d\)=4​\(1−e−2​ϕ\)<8​ϕ\\displaystyle\\leq 4\(1\-e^\{\-2Td\}\)=4\(1\-e^\{\-2\\phi\}\)<8\\phifor every realized start statess\. Setη:=8​ϕ<1/10\\eta:=8\\phi<1/10\.

Since

exp⁡\(−M​T416384\)=exp⁡\(−log⁡\(8/δ\)128​ϕ2\)<δ4,\\exp\\\!\\left\(\-\\frac\{MT^\{4\}\}\{16384\}\\right\)=\\exp\\\!\\left\(\-\\frac\{\\log\(8/\\delta\)\}\{128\\phi^\{2\}\}\\right\)<\\frac\{\\delta\}\{4\},[Section5\.2](https://arxiv.org/html/2606.31230#S5.SS2)implies that with probability1−δ/41\-\\delta/4the number of accepted intervals is at least

M​T44096=log⁡\(8/δ\)32​ϕ2=2​log⁡\(8/δ\)η2\.\\frac\{MT^\{4\}\}\{4096\}=\\frac\{\\log\(8/\\delta\)\}\{32\\phi^\{2\}\}=\\frac\{2\\log\(8/\\delta\)\}\{\\eta^\{2\}\}\.
Condition on this sample\-count event, and enumerate the accepted intervals in chronological order ast1<⋯<tNt\_\{1\}<\\cdots<t\_\{N\}\. Forℓ=1,…,N\\ell=1,\\dots,N, let

Rℓ:=−Δ^i\(tℓ\)Δ^j\(tℓ\)andξ\(ℓ\):=𝟏¬𝒞\(tℓ\)\.R\_\{\\ell\}:=\-\\frac\{\\widehat\{\\Delta\}\_\{i\}^\{\(t\_\{\\ell\}\)\}\}\{\\widehat\{\\Delta\}\_\{j\}^\{\(t\_\{\\ell\}\)\}\}\\qquad\\text\{and\}\\qquad\\xi^\{\(\\ell\)\}:=\\mathbf\{1\}\_\{\\neg\\mathcal\{C\}^\{\(t\_\{\\ell\}\)\}\}\.Letℱℓ\\mathcal\{F\}\_\{\\ell\}be the sigma\-field generated by the diagonal\-estimation phase together with the trajectory up to the end of intervalItℓI\_\{t\_\{\\ell\}\}\. By averaging the uniform bound above over the skipped intervals before the next accepted one, we obtain

𝔼​\[ξ\(ℓ\)∣ℱℓ−1\]≤ηfor all​ℓ\.\\mathbb\{E\}\[\\xi^\{\(\\ell\)\}\\mid\\mathcal\{F\}\_\{\\ell\-1\}\]\\leq\\eta\\qquad\\text\{for all \}\\ell\.Moreover, on the eventξ\(ℓ\)=0\\xi^\{\(\\ell\)\}=0,[Section5\.1](https://arxiv.org/html/2606.31230#S5.SS1.SSS0.Px3)shows that, conditional on the full accepted interval, the clean sampleRℓ/2\.62R\_\{\\ell\}/2\.62has Gaussian tails dominated by

𝒩​\(−12\.62​cjci​Θi​j′,1\)\.\\mathcal\{N\}\\\!\\left\(\-\\frac\{1\}\{2\.62\}\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta\_\{ij\}^\{\\prime\},1\\right\)\.Averaging over the accepted\-interval randomness preserves these one\-sided tail bounds conditional onℱℓ−1\\mathcal\{F\}\_\{\\ell\-1\}\. Therefore[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3)applies to the rescaled samplesRℓ/2\.62R\_\{\\ell\}/2\.62, and with success probability1−δ/41\-\\delta/4their sample medianν^\\widehat\{\\nu\}satisfies

\|ν^\+12\.62​cjci​Θi​j′\|<5​η\.\\left\|\\widehat\{\\nu\}\+\\frac\{1\}\{2\.62\}\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta\_\{ij\}^\{\\prime\}\\right\|<5\\eta\.Setμ′:=−2\.62​ν^\\mu^\{\\prime\}:=\-2\.62\\widehat\{\\nu\}\. Then

\|μ′−cjci​Θi​j′\|<5⋅2\.62⋅η<9​α22\.\\left\|\\mu^\{\\prime\}\-\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta\_\{ij\}^\{\\prime\}\\right\|<5\\cdot 2\.62\\cdot\\eta<\\frac\{9\\alpha\}\{22\}\.
However,

- •Ifi≁ji\\nsim j, thenΘi​j′=0\\Theta\_\{ij\}^\{\\prime\}=0, so\|μ′\|<9​α/22\|\\mu^\{\\prime\}\|<9\\alpha/22\.
- •Ifi∼ji\\sim j, then\|Θi​j′\|≥α\|\\Theta\_\{ij\}^\{\\prime\}\|\\geq\\alpha, so \|cjci​Θi​j′\|≥1−1/101\+1/10​α\>9​α11,\\left\|\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta\_\{ij\}^\{\\prime\}\\right\|\\geq\\frac\{1\-1/10\}\{1\+1/10\}\\,\\alpha\>\\frac\{9\\alpha\}\{11\},and therefore\|μ′\|\>9​α/22\|\\mu^\{\\prime\}\|\>9\\alpha/22\.

Thus thresholding at9​α/229\\alpha/22determines whetheri∼ji\\sim j\. A union bound over the diagonal\-estimation phase, the sample\-count event, and the robust\-median step gives success probability at least1−δ1\-\\delta\.

Finally,

Tdiag\+M​T\\displaystyle T\_\{\\mathrm\{diag\}\}\+MT≤4,000,000​d​log⁡\(32/δ\)\+128​d3​log⁡\(8/δ\)ϕ5<128⋅2575​d3​log⁡\(16/δ\)α5,\\displaystyle\\leq 4\{,\}000\{,\}000d\\log\(32/\\delta\)\+\\frac\{128d^\{3\}\\log\(8/\\delta\)\}\{\\phi^\{5\}\}<\\frac\{128\\cdot 257^\{5\}\\,d^\{3\}\\log\(16/\\delta\)\}\{\\alpha^\{5\}\},where the diagonal\-estimation prefix is absorbed by the second term sinced≥1d\\geq 1andα<1\\alpha<1\. ∎

###### Proof of[Theorem5\.1](https://arxiv.org/html/2606.31230#S5.Thmtheorem1)\.

It suffices to apply[Section5](https://arxiv.org/html/2606.31230#S5)with error2​δ/n22\\delta/n^\{2\}for each pair\(i,j\)\(i,j\)\. Since

log⁡\(162​δ/n2\)=log⁡\(8​n2δ\)≤2​log⁡\(4​nδ\),\\log\\\!\\left\(\\frac\{16\}\{2\\delta/n^\{2\}\}\\right\)=\\log\\\!\\left\(\\frac\{8n^\{2\}\}\{\\delta\}\\right\)\\leq 2\\log\\\!\\left\(\\frac\{4n\}\{\\delta\}\\right\),the required trajectory length is bounded by the display in[Theorem5\.1](https://arxiv.org/html/2606.31230#S5.Thmtheorem1)\. Then, the probability of any error among the\(n2\)\\binom\{n\}\{2\}candidate edges is less thanδ\\deltaby union bound\. ∎

###### Proof of Corollary[5](https://arxiv.org/html/2606.31230#S5)\.

We follow the proof of[Section5](https://arxiv.org/html/2606.31230#S5), but estimate each diagonal entry up to multiplicative factor1±ε/201\\pm\\varepsilon/20and replaceα\\alphabyα​ε\\alpha\\varepsilonin the off\-diagonal estimator\. The resulting trajectory length is exactly the displayed bound\. Report the diagonal estimates asΘ^i​i\\widehat\{\\Theta\}\_\{ii\}, and reportΘ^i​j=0\\widehat\{\\Theta\}\_\{ij\}=0whenever the structure\-learning step outputsi≁ji\\nsim j\.

For each pair\(i,j\)\(i,j\)withi∼ji\\sim j, the proof of[Section5](https://arxiv.org/html/2606.31230#S5)produces an estimateμ^i​j\\widehat\{\\mu\}\_\{ij\}forcjci​Θi​j′\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta\_\{ij\}^\{\\prime\}such that

\|μ^i​j−cjci​Θi​j′\|<9​α​ε22≤922​ε​\|Θi​j′\|,\\left\\lvert\\widehat\{\\mu\}\_\{ij\}\-\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta\_\{ij\}^\{\\prime\}\\right\\rvert<\\frac\{9\\alpha\\varepsilon\}\{22\}\\leq\\frac\{9\}\{22\}\\varepsilon\\lvert\\Theta\_\{ij\}^\{\\prime\}\\rvert,since\|Θi​j′\|≥α\\lvert\\Theta\_\{ij\}^\{\\prime\}\\rvert\\geq\\alphaon edges\. Also, becauseci,cj∈1±ε/20c\_\{i\},c\_\{j\}\\in 1\\pm\\varepsilon/20,

\|cjci−1\|≤2​\(ε/20\)1−ε/20≤219​ε\.\\left\\lvert\\frac\{c\_\{j\}\}\{c\_\{i\}\}\-1\\right\\rvert\\leq\\frac\{2\(\\varepsilon/20\)\}\{1\-\\varepsilon/20\}\\leq\\frac\{2\}\{19\}\\varepsilon\.Therefore

\|μ^i​j−Θi​j′\|≤\(922\+219\)​ε​\|Θi​j′\|=215418​ε​\|Θi​j′\|\.\\left\\lvert\\widehat\{\\mu\}\_\{ij\}\-\\Theta\_\{ij\}^\{\\prime\}\\right\\rvert\\leq\\left\(\\frac\{9\}\{22\}\+\\frac\{2\}\{19\}\\right\)\\varepsilon\\lvert\\Theta\_\{ij\}^\{\\prime\}\\rvert=\\frac\{215\}\{418\}\\varepsilon\\lvert\\Theta\_\{ij\}^\{\\prime\}\\rvert\.
Set

Θ^i​j:=μ^i​j​Θ^i​i​Θ^j​j\.\\widehat\{\\Theta\}\_\{ij\}:=\\widehat\{\\mu\}\_\{ij\}\\sqrt\{\\widehat\{\\Theta\}\_\{ii\}\\widehat\{\\Theta\}\_\{jj\}\}\.Since the diagonal estimates are within a factor1±ε/201\\pm\\varepsilon/20, we have

Θ^i​i​Θ^j​j=\(1±ε/20\)​Θi​i​Θj​j\.\\sqrt\{\\widehat\{\\Theta\}\_\{ii\}\\widehat\{\\Theta\}\_\{jj\}\}=\(1\\pm\\varepsilon/20\)\\sqrt\{\\Theta\_\{ii\}\\Theta\_\{jj\}\}\.Hence

\|Θ^i​j−Θi​j\|\\displaystyle\\left\\lvert\\widehat\{\\Theta\}\_\{ij\}\-\\Theta\_\{ij\}\\right\\rvert≤\(215418​\(1\+120\)\+120\)​ε​\|Θi​j\|<0\.591​ε​\|Θi​j\|<ε​\|Θi​j\|\.\\displaystyle\\leq\\left\(\\frac\{215\}\{418\}\\left\(1\+\\frac\{1\}\{20\}\\right\)\+\\frac\{1\}\{20\}\\right\)\\varepsilon\\lvert\\Theta\_\{ij\}\\rvert<0\.591\\,\\varepsilon\\lvert\\Theta\_\{ij\}\\rvert<\\varepsilon\\lvert\\Theta\_\{ij\}\\rvert\.This proves the claim\. ∎

## 6Learning With Mixing

In this section, we give a more sample\-efficient structure\-learning algorithm when the mixing time is known\. Unlike the mixing\-free algorithm of[Section5](https://arxiv.org/html/2606.31230#S5), we may now work with the shorter “i​j​iiji” pattern\. The key point is that on a clean stationaryi​j​iijiwindow, thejj\-increment and the laterii\-increment form an exact bivariate Gaussian pair whose covariance is−Θi​j′\-\\Theta^\{\\prime\}\_\{ij\}\.

Our main result in this section is as follows\.

###### Theorem 6\.1\.

Let0<α,δ<10<\\alpha,\\delta<1andn,d∈ℕn,d\\in\\mathbb\{N\}\. Suppose we are given a Glauber trajectory evolving according to an\(α,d\)\(\\alpha,d\)\-sparse GGM with precision matrixΘ\\Theta, and thattmix​\(ε\)t\_\{\\mathrm\{mix\}\}\(\\varepsilon\)is known\. If the trajectory length satisfies

T≥80,000​log⁡\(2​n/δ\)α2​\(tmix​\(α4000\)\+8,000,000​d2α2\),T\\geq\\frac\{80\{,\}000\\log\(2n/\\delta\)\}\{\\alpha^\{2\}\}\\left\(t\_\{\\mathrm\{mix\}\}\\\!\\left\(\\frac\{\\alpha\}\{4000\}\\right\)\+\\frac\{8\{,\}000\{,\}000\\,d^\{2\}\}\{\\alpha^\{2\}\}\\right\),then there is a polynomial\-time algorithm that correctly outputs whetheri∼ji\\sim jfor eachiiandjjwith probability1−δ1\-\\delta\.

Again, we fixiiandjj, and evaluate the existence of the edgei∼ji\\sim jindividually\.

###### Theorem 6\.2\.

For fixediiandjj, given a Glauber trajectory whose length satisfies

T≥40,000​log⁡\(8/δ\)α2​\(tmix​\(α4000\)\+8,000,000​d2α2\),T\\geq\\frac\{40\{,\}000\\log\(8/\\delta\)\}\{\\alpha^\{2\}\}\\left\(t\_\{\\mathrm\{mix\}\}\\\!\\left\(\\frac\{\\alpha\}\{4000\}\\right\)\+\\frac\{8\{,\}000\{,\}000\\,d^\{2\}\}\{\\alpha^\{2\}\}\\right\),we may determine whetheri∼ji\\sim jwith probability1−δ1\-\\delta\.

[Section6\.1](https://arxiv.org/html/2606.31230#S6.SS1)analyzes the statistic in the normalized model and then transfers it to the observable trajectory\.[Section6\.2](https://arxiv.org/html/2606.31230#S6.SS2)uses these ingredients together with an epoch decomposition and mixing to build the edge test and complete the proofs of[Theorems6\.2](https://arxiv.org/html/2606.31230#S6.Thmtheorem2)and[6\.1](https://arxiv.org/html/2606.31230#S6.Thmtheorem1)\.

### 6\.1Properties of the statistic

Fixiiandjj\. LetT0≤1/3T\_\{0\}\\leq 1/3, letItI\_\{t\}denote the time interval\[t,t\+T0\)\[t,t\+T\_\{0\}\), and letPi​j​i:=\(i,j,i\)P\_\{iji\}:=\(i,j,i\)\. Let𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}denote the observable event thatItI\_\{t\}exhibitsPi​j​iP\_\{iji\}, and let𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}denote the event thatItI\_\{t\}is strict with respect toPi​j​iP\_\{iji\}\. By[Section3\.2](https://arxiv.org/html/2606.31230#S3.SS2),𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}and𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}are independent\.

Normalize the Glauber trajectory by[Theorem4\.1](https://arxiv.org/html/2606.31230#S4.Thmtheorem1), and letX^\\widehat\{X\}consist of\(1±α/10\)\(1\\pm\\alpha/10\)coordinate\-wise approximations ofX′X^\{\\prime\}\. We first analyze the normalized Glauber dynamicX′X^\{\\prime\}\.

#### The ideal normalized statistic\.

Conditioned on𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}and𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}, letY′⁣\(k\)Y^\{\\prime\(k\)\}denote the value ofX′X^\{\\prime\}at timet\+k​T0/3t\+kT\_\{0\}/3, fork=0,1,2,3k=0,1,2,3\. Denote

Δj′⁣\(t\):=Yj′⁣\(2\)−Yj′⁣\(0\),Δi′⁣\(t\):=Yi′⁣\(3\)−Yi′⁣\(1\)\.\\Delta^\{\\prime\(t\)\}\_\{j\}:=Y^\{\\prime\(2\)\}\_\{j\}\-Y^\{\\prime\(0\)\}\_\{j\},\\qquad\\Delta^\{\\prime\(t\)\}\_\{i\}:=Y^\{\\prime\(3\)\}\_\{i\}\-Y^\{\\prime\(1\)\}\_\{i\}\.
###### Lemma 6\.3\.

Letθ:=Θi​j′\\theta:=\\Theta^\{\\prime\}\_\{ij\}\. If the interval begins from stationarity, so thatY′⁣\(0\)∼𝒩​\(0,Σ′\)Y^\{\\prime\(0\)\}\\sim\\mathcal\{N\}\(0,\\Sigma^\{\\prime\}\), then conditioned on𝒞\(t\)\\mathcal\{C\}^\{\(t\)\}and𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}we have

\(Δj′⁣\(t\)Δi′⁣\(t\)\)∼𝒩​\(0,\(2−θ−θ2\)\)\.\\begin\{pmatrix\}\\Delta^\{\\prime\(t\)\}\_\{j\}\\\\\[2\.84526pt\] \\Delta^\{\\prime\(t\)\}\_\{i\}\\end\{pmatrix\}\\sim\\mathcal\{N\}\\\!\\left\(0,\\;\\begin\{pmatrix\}2&\-\\theta\\\\ \-\\theta&2\\end\{pmatrix\}\\right\)\.

###### Proof\.

LetR:=Θ′​Y′⁣\(0\)R:=\\Theta^\{\\prime\}Y^\{\\prime\(0\)\}\. SinceY′⁣\(0\)∼𝒩​\(0,Σ′\)Y^\{\\prime\(0\)\}\\sim\\mathcal\{N\}\(0,\\Sigma^\{\\prime\}\)andΣ′=\(Θ′\)−1\\Sigma^\{\\prime\}=\(\\Theta^\{\\prime\}\)^\{\-1\}, we haveR∼𝒩​\(0,Θ′\)R\\sim\\mathcal\{N\}\(0,\\Theta^\{\\prime\}\), with

Var⁡\(Ri\)=Var⁡\(Rj\)\\displaystyle\\operatorname\{Var\}\(R\_\{i\}\)=\\operatorname\{Var\}\(R\_\{j\}\)=1\\displaystyle=1andCov⁡\(Ri,Rj\)\\displaystyle\\text\{and\}\\quad\\operatorname\{Cov\}\(R\_\{i\},R\_\{j\}\)=θ\.\\displaystyle=\\theta\.
Letε1,ε2,ε3∼𝒩​\(0,1\)\\varepsilon\_\{1\},\\varepsilon\_\{2\},\\varepsilon\_\{3\}\\sim\\mathcal\{N\}\(0,1\)be the fresh Gaussian noises corresponding to the last update of the designated coordinate in each of the three thirds\. BecauseItI\_\{t\}exhibitsPi​j​iP\_\{iji\}and is strict with respect to it, the endpoint of each prescribed coordinate is the fresh draw from the last update in that third\. Hence

Yi′⁣\(1\)=Yi′⁣\(0\)−Ri\+ε1\.Y^\{\\prime\(1\)\}\_\{i\}=Y^\{\\prime\(0\)\}\_\{i\}\-R\_\{i\}\+\\varepsilon\_\{1\}\.
Before the middlejj\-update, the only neighbor ofjjthat may have changed isii, so

Δj′⁣\(t\)=Yj′⁣\(2\)−Yj′⁣\(0\)=−Rj\+θ​Ri−θ​ε1\+ε2\.\\Delta^\{\\prime\(t\)\}\_\{j\}=Y^\{\\prime\(2\)\}\_\{j\}\-Y^\{\\prime\(0\)\}\_\{j\}=\-R\_\{j\}\+\\theta R\_\{i\}\-\\theta\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\.
Similarly, before the finalii\-update, the only neighbor ofiithat may have changed isjj, so

Yi′⁣\(3\)=Yi′⁣\(0\)−Ri−θ​Δj′⁣\(t\)\+ε3,Y^\{\\prime\(3\)\}\_\{i\}=Y^\{\\prime\(0\)\}\_\{i\}\-R\_\{i\}\-\\theta\\Delta^\{\\prime\(t\)\}\_\{j\}\+\\varepsilon\_\{3\},and therefore

Δi′⁣\(t\)=−θ​Δj′⁣\(t\)\+ε3−ε1\.\\Delta^\{\\prime\(t\)\}\_\{i\}=\-\\theta\\Delta^\{\\prime\(t\)\}\_\{j\}\+\\varepsilon\_\{3\}\-\\varepsilon\_\{1\}\.
Everything is jointly Gaussian, so it remains only to compute the covariance matrix\. First,

Var⁡\(Δj′⁣\(t\)\)\\displaystyle\\operatorname\{Var\}\(\\Delta^\{\\prime\(t\)\}\_\{j\}\)=Var⁡\(−Rj\+θ​Ri\)\+Var⁡\(−θ​ε1\+ε2\)\\displaystyle=\\operatorname\{Var\}\(\-R\_\{j\}\+\\theta R\_\{i\}\)\+\\operatorname\{Var\}\(\-\\theta\\varepsilon\_\{1\}\+\\varepsilon\_\{2\}\)=\(1−θ2\)\+\(1\+θ2\)=2\.\\displaystyle=\(1\-\\theta^\{2\}\)\+\(1\+\\theta^\{2\}\)=2\.Next,

Cov⁡\(Δi′⁣\(t\),Δj′⁣\(t\)\)\\displaystyle\\operatorname\{Cov\}\(\\Delta^\{\\prime\(t\)\}\_\{i\},\\Delta^\{\\prime\(t\)\}\_\{j\}\)=−θ​Var⁡\(Δj′⁣\(t\)\)\+Cov⁡\(ε3−ε1,Δj′⁣\(t\)\)\\displaystyle=\-\\theta\\operatorname\{Var\}\(\\Delta^\{\\prime\(t\)\}\_\{j\}\)\+\\operatorname\{Cov\}\(\\varepsilon\_\{3\}\-\\varepsilon\_\{1\},\\Delta^\{\\prime\(t\)\}\_\{j\}\)=−2​θ\+θ=−θ\.\\displaystyle=\-2\\theta\+\\theta=\-\\theta\.Finally,

Var⁡\(Δi′⁣\(t\)\)\\displaystyle\\operatorname\{Var\}\(\\Delta^\{\\prime\(t\)\}\_\{i\}\)=θ2​Var⁡\(Δj′⁣\(t\)\)\+Var⁡\(ε3−ε1\)\+2​Cov⁡\(−θ​Δj′⁣\(t\),ε3−ε1\)\\displaystyle=\\theta^\{2\}\\operatorname\{Var\}\(\\Delta^\{\\prime\(t\)\}\_\{j\}\)\+\\operatorname\{Var\}\(\\varepsilon\_\{3\}\-\\varepsilon\_\{1\}\)\+2\\operatorname\{Cov\}\(\-\\theta\\Delta^\{\\prime\(t\)\}\_\{j\},\\varepsilon\_\{3\}\-\\varepsilon\_\{1\}\)=−2​θ2\+2\+2​θ2=2\.\\displaystyle=\-2\\theta^\{2\}\+2\+2\\theta^\{2\}=2\.This proves the claim\. ∎

###### Corollary 6\.4\.

On the same clean stationary interval,

Δi′⁣\(t\)=−Θi​j′2​Δj′⁣\(t\)\+ζ\(t\),\\Delta^\{\\prime\(t\)\}\_\{i\}=\-\\frac\{\\Theta^\{\\prime\}\_\{ij\}\}\{2\}\\Delta^\{\\prime\(t\)\}\_\{j\}\+\\zeta^\{\(t\)\},where

ζ\(t\)∼𝒩​\(0,2−\(Θi​j′\)22\)\\zeta^\{\(t\)\}\\sim\\mathcal\{N\}\\\!\\left\(0,\\,2\-\\frac\{\(\\Theta^\{\\prime\}\_\{ij\}\)^\{2\}\}\{2\}\\right\)andζ\(t\)\\zeta^\{\(t\)\}is independent ofΔj′⁣\(t\)\\Delta^\{\\prime\(t\)\}\_\{j\}\.

###### Proof\.

This is the Gaussian regression formula from[Section6\.1](https://arxiv.org/html/2606.31230#S6.SS1.SSS0.Px1), since

Cov⁡\(Δi′⁣\(t\),Δj′⁣\(t\)\)Var⁡\(Δj′⁣\(t\)\)=−Θi​j′2\.∎\\frac\{\\operatorname\{Cov\}\(\\Delta^\{\\prime\(t\)\}\_\{i\},\\Delta^\{\\prime\(t\)\}\_\{j\}\)\}\{\\operatorname\{Var\}\(\\Delta^\{\\prime\(t\)\}\_\{j\}\)\}=\-\\frac\{\\Theta^\{\\prime\}\_\{ij\}\}\{2\}\.\\qed

#### Passing to the observable statistic\.

LetY^\(k\)\\widehat\{Y\}^\{\(k\)\}denote the value ofX^\\widehat\{X\}at timet\+k​T0/3t\+kT\_\{0\}/3, fork=0,1,2,3k=0,1,2,3\. Denote

Δ^j\(t\):=Y^j\(2\)−Y^j\(0\),Δ^i\(t\):=Y^i\(3\)−Y^i\(1\)\.\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}:=\\widehat\{Y\}^\{\(2\)\}\_\{j\}\-\\widehat\{Y\}^\{\(0\)\}\_\{j\},\\qquad\\widehat\{\\Delta\}^\{\(t\)\}\_\{i\}:=\\widehat\{Y\}^\{\(3\)\}\_\{i\}\-\\widehat\{Y\}^\{\(1\)\}\_\{i\}\.
By[Section4\.3](https://arxiv.org/html/2606.31230#S4.SS3.SSS0.Px1), there exist constantsci,cj∈1±α/10c\_\{i\},c\_\{j\}\\in 1\\pm\\alpha/10such that

Δ^j\(t\)=1cj​Δj′⁣\(t\)andΔ^i\(t\)=1ci​Δi′⁣\(t\)\.\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}=\\frac\{1\}\{c\_\{j\}\}\\Delta^\{\\prime\(t\)\}\_\{j\}\\qquad\\text\{and\}\\qquad\\widehat\{\\Delta\}^\{\(t\)\}\_\{i\}=\\frac\{1\}\{c\_\{i\}\}\\Delta^\{\\prime\(t\)\}\_\{i\}\.Hence[Section6\.1](https://arxiv.org/html/2606.31230#S6.SS1.SSS0.Px1)yields

Δ^i\(t\)=−cj2​ci​Θi​j′​Δ^j\(t\)\+1ci​ζ\(t\),\\widehat\{\\Delta\}^\{\(t\)\}\_\{i\}=\-\\frac\{c\_\{j\}\}\{2c\_\{i\}\}\\Theta^\{\\prime\}\_\{ij\}\\,\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\+\\frac\{1\}\{c\_\{i\}\}\\zeta^\{\(t\)\},whereζ\(t\)\\zeta^\{\(t\)\}is independent ofΔ^j\(t\)\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}and

ζ\(t\)∼𝒩​\(0,2−\(Θi​j′\)22\)\.\\zeta^\{\(t\)\}\\sim\\mathcal\{N\}\\\!\\left\(0,\\,2\-\\frac\{\(\\Theta^\{\\prime\}\_\{ij\}\)^\{2\}\}\{2\}\\right\)\.

#### Conditioning on a large denominator\.

Letℰ\(t\)\\mathcal\{E\}^\{\(t\)\}denote the event

ℰ\(t\):=\{\|Δ^j\(t\)\|≥1\.1\}\.\\mathcal\{E\}^\{\(t\)\}:=\\\{\\lvert\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\\rvert\\geq 1\.1\\\}\.
###### Lemma 6\.5\.

We have

ℙ​\[ℰ\(t\)∣𝒟\(t\),Y^\(0\)\]\>29\.\\mathbb\{P\}\[\\mathcal\{E\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\},\\widehat\{Y\}^\{\(0\)\}\]\>\\frac\{2\}\{9\}\.

###### Proof\.

Sincecj<1\.1c\_\{j\}<1\.1, the event\|Δ^j\(t\)\|≥1\.1\\lvert\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\\rvert\\geq 1\.1is implied by\|Δj′⁣\(t\)\|≥1\.21\\lvert\\Delta^\{\\prime\(t\)\}\_\{j\}\\rvert\\geq 1\.21\. LetZZbe the value ofX′X^\{\\prime\}right before the last update ofjjinside the middle third\. Conditioned onZZ, the endpointΔj′⁣\(t\)\\Delta^\{\\prime\(t\)\}\_\{j\}is Gaussian with variance11, sayΔj′⁣\(t\)∣Z∼𝒩​\(m,1\)\\Delta^\{\\prime\(t\)\}\_\{j\}\\mid Z\\sim\\mathcal\{N\}\(m,1\)for somemm\.

Let

f​\(m\):=ℙx∼𝒩​\(m,1\)​\[\|x\|≤1\.21\]\.f\(m\):=\\mathbb\{P\}\_\{x\\sim\\mathcal\{N\}\(m,1\)\}\[\\lvert x\\rvert\\leq 1\.21\]\.Thenffis even, and form≥0m\\geq 0,

f′​\(m\)=φ​\(1\.21\+m\)−φ​\(1\.21−m\)≤0\.f^\{\\prime\}\(m\)=\\varphi\(1\.21\+m\)\-\\varphi\(1\.21\-m\)\\leq 0\.Thereforeffis maximized atm=0m=0, so

ℙ​\[\|Δj′⁣\(t\)\|≥1\.21∣Z\]≥ℙx∼𝒩​\(0,1\)​\[\|x\|≥1\.21\]\>29\.\\mathbb\{P\}\[\\lvert\\Delta^\{\\prime\(t\)\}\_\{j\}\\rvert\\geq 1\.21\\mid Z\]\\geq\\mathbb\{P\}\_\{x\\sim\\mathcal\{N\}\(0,1\)\}\[\\lvert x\\rvert\\geq 1\.21\]\>\\frac\{2\}\{9\}\.Averaging overZZproves the claim\. ∎

###### Lemma 6\.6\.

Condition on a clean stationary interval and onℰ\(t\)\\mathcal\{E\}^\{\(t\)\}\. Then

−2​Δ^i\(t\)Δ^j\(t\)=cjci​Θi​j′\+σ\(t\)​ε\(t\),\-2\\frac\{\\widehat\{\\Delta\}^\{\(t\)\}\_\{i\}\}\{\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\}=\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta^\{\\prime\}\_\{ij\}\+\\sigma^\{\(t\)\}\\varepsilon^\{\(t\)\},whereε\(t\)∼𝒩​\(0,1\)\\varepsilon^\{\(t\)\}\\sim\\mathcal\{N\}\(0,1\),σ\(t\)\\sigma^\{\(t\)\}is measurable with respect toΔ^j\(t\)\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}, and

\|σ\(t\)\|<2\.86\.\\lvert\\sigma^\{\(t\)\}\\rvert<2\.86\.

###### Proof\.

By the regression identity above,

−2​Δ^i\(t\)Δ^j\(t\)=cjci​Θi​j′−2​ζ\(t\)ci​Δ^j\(t\)\.\-2\\frac\{\\widehat\{\\Delta\}^\{\(t\)\}\_\{i\}\}\{\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\}=\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta^\{\\prime\}\_\{ij\}\-2\\frac\{\\zeta^\{\(t\)\}\}\{c\_\{i\}\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\}\.Sinceζ\(t\)\\zeta^\{\(t\)\}is independent ofΔ^j\(t\)\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}and has variance at most22, the second term equalsσ\(t\)​ε\(t\)\\sigma^\{\(t\)\}\\varepsilon^\{\(t\)\}for some standard Gaussianε\(t\)\\varepsilon^\{\(t\)\}and

\|σ\(t\)\|≤2​2\|ci​Δ^j\(t\)\|<2​20\.9⋅1\.1<2\.86,\\lvert\\sigma^\{\(t\)\}\\rvert\\leq\\frac\{2\\sqrt\{2\}\}\{\\lvert c\_\{i\}\\widehat\{\\Delta\}^\{\(t\)\}\_\{j\}\\rvert\}<\\frac\{2\\sqrt\{2\}\}\{0\.9\\cdot 1\.1\}<2\.86,where we useℰ\(t\)\\mathcal\{E\}^\{\(t\)\}\. ∎

### 6\.2Edge detection

We divide the trajectory intoMM*epochs*, each consisting of a mixing period of lengthtmix​\(β\)t\_\{\\mathrm\{mix\}\}\(\\beta\)followed byNNcandidate intervals of lengthT0T\_\{0\}, where

T0=α400​d,β=α4000,N=50T03\.T\_\{0\}=\\frac\{\\alpha\}\{400d\},\\quad\\beta=\\frac\{\\alpha\}\{4000\},\\quad N=\\frac\{50\}\{T\_\{0\}^\{3\}\}\.
In thekkth epoch, letLkL\_\{k\}denote the first candidate interval for which𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}holds\. If no such interval exists, the epoch is discarded\. IfLkL\_\{k\}exists butℰ\(t\)\\mathcal\{E\}^\{\(t\)\}fails on that interval, the epoch is also discarded\. Otherwise we record the sample

Rk:=−2​Δ^i\(k\)Δ^j\(k\),R\_\{k\}:=\-2\\frac\{\\widehat\{\\Delta\}\_\{i\}^\{\(k\)\}\}\{\\widehat\{\\Delta\}\_\{j\}^\{\(k\)\}\},whereΔ^i\(k\)\\widehat\{\\Delta\}\_\{i\}^\{\(k\)\}andΔ^j\(k\)\\widehat\{\\Delta\}\_\{j\}^\{\(k\)\}are computed from the selected intervalLkL\_\{k\}\.

The resulting procedure is given by[Algorithm3](https://arxiv.org/html/2606.31230#alg3)\.

Algorithm 3E=LearnGGMMixed​\(n,d,α,δ,tmix\)E=\\text\{LearnGGMMixed\}\(n,d,\\alpha,\\delta,t\_\{\\mathrm\{mix\}\}\)1:Set

T0=α/\(400​d\)T\_\{0\}=\\alpha/\(400d\),

β=α/4000\\beta=\\alpha/4000,

N=50/T03N=50/T\_\{0\}^\{3\}, and

M=80,000​log⁡\(2​n/δ\)/α2M=80\{,\}000\\log\(2n/\\delta\)/\\alpha^\{2\}\.

2:Let

diag⁡\(Θ~\)=EstimateDiagonal​\(n,d,α,α/10,δ/2\)\\operatorname\{diag\}\(\\widetilde\{\\Theta\}\)=\\text\{EstimateDiagonal\}\(n,d,\\alpha,\\alpha/10,\\delta/2\)from Algorithm[1](https://arxiv.org/html/2606.31230#alg1)\.

3:Keep the unused part of the trajectory\.

4:Let

E=∅E=\\varnothing\.

5:Observe a trajectory of length

M​\(tmix​\(β\)\+N​T0\)M\(t\_\{\\mathrm\{mix\}\}\(\\beta\)\+NT\_\{0\}\), split into

MMepochs\.

6:for

i=1,…,ni=1,\\ldots,ndo

7:for

j=i\+1,…,nj=i\+1,\\ldots,ndo

8:Let

S=∅S=\\varnothing\.

9:for

k=1,…,Mk=1,\\ldots,Mdo

10:After the mixing segment of epoch

kk, split the remainder into candidate intervals

Ik,1,…,Ik,NI\_\{k,1\},\\ldots,I\_\{k,N\}of length

T0T\_\{0\}\.

11:Let

LkL\_\{k\}be the first interval for which

𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}holds\.

12:if

LkL\_\{k\}exists and

ℰ\(t\)\\mathcal\{E\}^\{\(t\)\}holds on

LkL\_\{k\}then

13:Record

Rk=−2​Δ^i\(k\)/Δ^j\(k\)R\_\{k\}=\-2\\widehat\{\\Delta\}\_\{i\}^\{\(k\)\}/\\widehat\{\\Delta\}\_\{j\}^\{\(k\)\}and append it to

SS\.

14:endif

15:endfor

16:if

\|S\|<M/16\|S\|<M/16then

17:Return

⊥\\bot\.

18:else

19:Let

μ^\\widehat\{\\mu\}be the sample median of

SS\.

20:if

\|μ^\|\>9​α/22\|\\widehat\{\\mu\}\|\>9\\alpha/22then

21:Set

E=E⊔\{\(i,j\)\}E=E\\sqcup\\\{\(i,j\)\\\}\.

22:endif

23:endif

24:endfor

25:endfor

26:Return

EE\.

We now analyze the estimator\.

###### Lemma 6\.7\.

LetAkA\_\{k\}denote the indicator that epochkkrecords a sample\. With the choiceN=50/T03N=50/T\_\{0\}^\{3\}, each epoch records a sample with conditional probability at least1/81/8given the past\. Consequently,

ℙ​\[∑k=1MAk<M16\]≤e−M/128\.\\mathbb\{P\}\\\!\\left\[\\sum\_\{k=1\}^\{M\}A\_\{k\}<\\frac\{M\}\{16\}\\right\]\\leq e^\{\-M/128\}\.

###### Proof\.

Fix an epoch and condition on the past\. For a single candidate interval,[Section3\.2](https://arxiv.org/html/2606.31230#S3.SS2)gives

ℙ​\[𝒟\(t\)\]≥T0354\.\\mathbb\{P\}\[\\mathcal\{D\}^\{\(t\)\}\]\\geq\\frac\{T\_\{0\}^\{3\}\}\{54\}\.Therefore the probability that some candidate interval satisfies𝒟\(t\)\\mathcal\{D\}^\{\(t\)\}is at least

1−\(1−T0354\)N≥1−e−50/54\>35\.1\-\\left\(1\-\\frac\{T\_\{0\}^\{3\}\}\{54\}\\right\)^\{N\}\\geq 1\-e^\{\-50/54\}\>\\frac\{3\}\{5\}\.
LetLkL\_\{k\}be the first such interval\. Conditioned onLkL\_\{k\}and on the past,[Section6\.1](https://arxiv.org/html/2606.31230#S6.SS1.SSS0.Px3)gives

ℙ​\[ℰ\(t\)​holds on​Lk∣Lk,past\]\>29\.\\mathbb\{P\}\[\\mathcal\{E\}^\{\(t\)\}\\text\{ holds on \}L\_\{k\}\\mid L\_\{k\},\\text\{ past\}\]\>\\frac\{2\}\{9\}\.Therefore the conditional probability that the epoch records a sample is at least

35⋅29=215\>18\.\\frac\{3\}\{5\}\\cdot\\frac\{2\}\{9\}=\\frac\{2\}\{15\}\>\\frac\{1\}\{8\}\.
Letℱk\\mathcal\{F\}\_\{k\}be the sigma\-field generated by the firstkkepochs, and define

Mr:=∑k=1r\(Ak−𝔼​\[Ak∣ℱk−1\]\)\.M\_\{r\}:=\\sum\_\{k=1\}^\{r\}\\left\(A\_\{k\}\-\\mathbb\{E\}\[A\_\{k\}\\mid\\mathcal\{F\}\_\{k\-1\}\]\\right\)\.Then\(Mr,ℱr\)\(M\_\{r\},\\mathcal\{F\}\_\{r\}\)is a martingale with increments in\[−1,1\]\[\-1,1\], and∑k=1M𝔼​\[Ak∣ℱk−1\]≥M/8\\sum\_\{k=1\}^\{M\}\\mathbb\{E\}\[A\_\{k\}\\mid\\mathcal\{F\}\_\{k\-1\}\]\\geq M/8\. Thus

ℙ​\[∑k=1MAk<M16\]≤ℙ​\[MM<−M16\]≤e−M/128\\mathbb\{P\}\\\!\\left\[\\sum\_\{k=1\}^\{M\}A\_\{k\}<\\frac\{M\}\{16\}\\right\]\\leq\\mathbb\{P\}\\\!\\left\[M\_\{M\}<\-\\frac\{M\}\{16\}\\right\]\\leq e^\{\-M/128\}by Azuma–Hoeffding\. ∎

###### Lemma 6\.8\.

Suppose

T0=α400​dandβ=α4000\.T\_\{0\}=\\frac\{\\alpha\}\{400d\}\\qquad\\text\{and\}\\qquad\\beta=\\frac\{\\alpha\}\{4000\}\.Then, conditional on the past and on the event that an epoch records a sample, that sample is corrupted with probability less thanα/35\\alpha/35\.

###### Proof\.

There are two sources of corruption\.

First, non\-strict pattern intervals\. Since future clocks are independent of the past andPi​j​iP\_\{iji\}contains two distinct indices,[Sections3\.2](https://arxiv.org/html/2606.31230#S3.SS2)and[3\.2](https://arxiv.org/html/2606.31230#S3.SS2)give

ℙ​\[¬𝒞\(t\)∣𝒟\(t\)\]≤1−e−2​d​T0\.\\mathbb\{P\}\[\\neg\\mathcal\{C\}^\{\(t\)\}\\mid\\mathcal\{D\}^\{\(t\)\}\]\\leq 1\-e^\{\-2dT\_\{0\}\}\.By[Section6\.1](https://arxiv.org/html/2606.31230#S6.SS1.SSS0.Px3), conditioning additionally onℰ\(t\)\\mathcal\{E\}^\{\(t\)\}inflates this by at most a factor of9/29/2, so the non\-strictness contribution to the conditional corruption probability is at most

ηstrict≤1−e−2​d​T02/9<9​d​T0=9​α400\.\\eta\_\{\\mathrm\{strict\}\}\\leq\\frac\{1\-e^\{\-2dT\_\{0\}\}\}\{2/9\}<9dT\_\{0\}=\\frac\{9\\alpha\}\{400\}\.
Second, imperfect mixing\. At the start of each epoch, after waitingtmix​\(β\)t\_\{\\mathrm\{mix\}\}\(\\beta\), the epoch\-start distribution is within TV\-distanceβ\\betaof stationarity\. By[Section3\.5](https://arxiv.org/html/2606.31230#S3.SS5), the same is true at the start of any later candidate interval in the epoch\. A maximal coupling with stationarity therefore fails with probability at mostβ\\beta\. Since an epoch records a sample with conditional probability at least1/81/8by[Section6\.2](https://arxiv.org/html/2606.31230#S6.SS2), conditioning on the epoch being recorded inflates this by at most a factor of88\. Thus the mixing contribution to corruption is at most

ηmix≤8​β=α500\.\\eta\_\{\\mathrm\{mix\}\}\\leq 8\\beta=\\frac\{\\alpha\}\{500\}\.
Combining the two bounds gives

η≤ηstrict\+ηmix<9​α400\+α500=49​α2000<α35\.∎\\eta\\leq\\eta\_\{\\mathrm\{strict\}\}\+\\eta\_\{\\mathrm\{mix\}\}<\\frac\{9\\alpha\}\{400\}\+\\frac\{\\alpha\}\{500\}=\\frac\{49\\alpha\}\{2000\}<\\frac\{\\alpha\}\{35\}\.\\qed

#### Putting the edge test together\.

###### Proof of[Theorem6\.2](https://arxiv.org/html/2606.31230#S6.Thmtheorem2)\.

First isolate the initial

Tdiag:=4,000,000​d​log⁡\(32/δ\)α3T\_\{\\mathrm\{diag\}\}:=\\frac\{4\{,\}000\{,\}000d\\log\(32/\\delta\)\}\{\\alpha^\{3\}\}portion of the trajectory, and apply[Section4](https://arxiv.org/html/2606.31230#S4)to retrieve approximations of the diagonal up to multiplicative factor1±α/101\\pm\\alpha/10, and hence all necessary readings ofX^i\\widehat\{X\}\_\{i\}andX^j\\widehat\{X\}\_\{j\}, with probability at least1−δ/21\-\\delta/2\.

Now take

T0=α400​d,β\\displaystyle T\_\{0\}=\\frac\{\\alpha\}\{400d\},\\quad\\beta=α4000,N=50T03,M=40,000​log⁡\(8/δ\)α2\.\\displaystyle=\\frac\{\\alpha\}\{4000\},\\quad N=\\frac\{50\}\{T\_\{0\}^\{3\}\},\\quad M=\\frac\{40\{,\}000\\log\(8/\\delta\)\}\{\\alpha^\{2\}\}\.By[Section6\.2](https://arxiv.org/html/2606.31230#S6.SS2), with probability at least1−δ/41\-\\delta/4, the number of recorded samples is at least

M16=2500​log⁡\(8/δ\)α2\.\\frac\{M\}\{16\}=\\frac\{2500\\log\(8/\\delta\)\}\{\\alpha^\{2\}\}\.Letk1<⋯<kNk\_\{1\}<\\cdots<k\_\{N\}denote the recorded epochs in chronological order, and condition on the sample\-count event from[Section6\.2](https://arxiv.org/html/2606.31230#S6.SS2), so that

N≥M16=2500​log⁡\(8/δ\)α2\.N\\geq\\frac\{M\}\{16\}=\\frac\{2500\\log\(8/\\delta\)\}\{\\alpha^\{2\}\}\.Forℓ=1,…,N\\ell=1,\\dots,N, write

Rℓ:=Rkℓ,ξ\(ℓ\):=𝟏\{epoch​kℓ​is corrupted\}\.R\_\{\\ell\}:=R\_\{k\_\{\\ell\}\},\\qquad\\xi^\{\(\\ell\)\}:=\\mathbf\{1\}\_\{\\\{\\text\{epoch \}k\_\{\\ell\}\\text\{ is corrupted\}\\\}\}\.Letℱℓ\\mathcal\{F\}\_\{\\ell\}be the sigma\-field generated by the trajectory up to the end of epochkℓk\_\{\\ell\}\. By averaging[Section6\.2](https://arxiv.org/html/2606.31230#S6.SS2)over the skipped epochs before the next recorded one, we obtain

𝔼​\[ξ\(ℓ\)∣ℱℓ−1\]≤ηfor all​ℓ,\\mathbb\{E\}\[\\xi^\{\(\\ell\)\}\\mid\\mathcal\{F\}\_\{\\ell\-1\}\]\\leq\\eta\\qquad\\text\{for all \}\\ell,with

η<α35\.\\eta<\\frac\{\\alpha\}\{35\}\.
On the eventξ\(ℓ\)=0\\xi^\{\(\\ell\)\}=0,[Section6\.1](https://arxiv.org/html/2606.31230#S6.SS1.SSS0.Px3)implies that, conditional onℱℓ−1\\mathcal\{F\}\_\{\\ell\-1\}, the clean sampleRℓ/2\.86R\_\{\\ell\}/2\.86has Gaussian tails dominated by

𝒩​\(12\.86​cjci​Θi​j′,1\)\.\\mathcal\{N\}\\\!\\left\(\\frac\{1\}\{2\.86\}\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta^\{\\prime\}\_\{ij\},1\\right\)\.Let

μ:=cjci​Θi​j′\.\\mu:=\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta^\{\\prime\}\_\{ij\}\.Since

M16=2500​log⁡\(8/δ\)α2\>2​log⁡\(8/δ\)\(α/35\)2,\\frac\{M\}\{16\}=\\frac\{2500\\log\(8/\\delta\)\}\{\\alpha^\{2\}\}\>\\frac\{2\\log\(8/\\delta\)\}\{\(\\alpha/35\)^\{2\}\},[Section3\.3](https://arxiv.org/html/2606.31230#S3.SS3)applies to the rescaled samplesRℓ/2\.86R\_\{\\ell\}/2\.86\. Therefore, with probability at least1−δ/41\-\\delta/4, the sample medianμ^\\widehat\{\\mu\}satisfies

\|μ^−μ\|<5⋅2\.86⋅α35<9​α22\.\\lvert\\widehat\{\\mu\}\-\\mu\\rvert<5\\cdot 2\.86\\cdot\\frac\{\\alpha\}\{35\}<\\frac\{9\\alpha\}\{22\}\.
Now:

- •Ifi≁ji\\nsim j, thenΘi​j′=0\\Theta^\{\\prime\}\_\{ij\}=0, soμ=0\\mu=0\.
- •Ifi∼ji\\sim j, then\|Θi​j′\|≥α\\lvert\\Theta^\{\\prime\}\_\{ij\}\\rvert\\geq\\alpha, and sinceci,cj∈1±α/10c\_\{i\},c\_\{j\}\\in 1\\pm\\alpha/10, \|μ\|=\|cjci​Θi​j′\|≥1−α/101\+α/10​α\>9​α11\.\\lvert\\mu\\rvert=\\left\\lvert\\frac\{c\_\{j\}\}\{c\_\{i\}\}\\Theta^\{\\prime\}\_\{ij\}\\right\\rvert\\geq\\frac\{1\-\\alpha/10\}\{1\+\\alpha/10\}\\alpha\>\\frac\{9\\alpha\}\{11\}\.

Hence thresholding at9​α/229\\alpha/22separates the two cases\.

A final union bound over the diagonal\-estimation phase, the sample\-count event, and the robust\-median step gives success probability at least1−δ1\-\\delta, since each individual event has failure probability upper bounded byδ/4\\delta/4\.

The per\-epoch non\-mixing cost is

N​T0=50T02=50​\(400​dα\)2=8,000,000​d2α2\.NT\_\{0\}=\\frac\{50\}\{T\_\{0\}^\{2\}\}=50\\left\(\\frac\{400d\}\{\\alpha\}\\right\)^\{2\}=\\frac\{8\{,\}000\{,\}000\\,d^\{2\}\}\{\\alpha^\{2\}\}\.Therefore the total trajectory length is at most

Tdiag\+M​\(tmix​\(β\)\+N​T0\)≤40,000​log⁡\(8/δ\)α2​\(tmix​\(α4000\)\+8,000,000​d2α2\),\\displaystyle T\_\{\\mathrm\{diag\}\}\+M\\bigl\(t\_\{\\mathrm\{mix\}\}\(\\beta\)\+NT\_\{0\}\\bigr\)\\leq\\frac\{40\{,\}000\\log\(8/\\delta\)\}\{\\alpha^\{2\}\}\\left\(t\_\{\\mathrm\{mix\}\}\\\!\\left\(\\frac\{\\alpha\}\{4000\}\\right\)\+\\frac\{8\{,\}000\{,\}000\\,d^\{2\}\}\{\\alpha^\{2\}\}\\right\),where the diagonal\-estimation prefix is absorbed by thed2/α4d^\{2\}/\\alpha^\{4\}term sinced≥1d\\geq 1andα<1\\alpha<1\. ∎

###### Proof of[Theorem6\.1](https://arxiv.org/html/2606.31230#S6.Thmtheorem1)\.

Apply[Theorem6\.2](https://arxiv.org/html/2606.31230#S6.Thmtheorem2)with error2​δ/n22\\delta/n^\{2\}for each pair\(i,j\)\(i,j\)\. Since

log⁡\(82​δ/n2\)=log⁡\(4​n2δ\)≤2​log⁡\(2​nδ\),\\log\\\!\\left\(\\frac\{8\}\{2\\delta/n^\{2\}\}\\right\)=\\log\\\!\\left\(\\frac\{4n^\{2\}\}\{\\delta\}\\right\)\\leq 2\\log\\\!\\left\(\\frac\{2n\}\{\\delta\}\\right\),the required trajectory length is bounded by the display in[Theorem6\.1](https://arxiv.org/html/2606.31230#S6.Thmtheorem1)\. A union bound over the\(n2\)\\binom\{n\}\{2\}candidate edges now gives success probability at least1−δ1\-\\delta\. ∎

## 7Information\-Theoretic Lower Bound

In this section, we prove the lower bound by constructing a hard family of graphs, upper\-bounding the pairwise KL divergence between the resulting trajectory distributions, and applying Fano’s inequality\. By[AppendixB](https://arxiv.org/html/2606.31230#A2), this yields the corresponding continuous\-time lower bound up to the usual factor ofnn\.

Our strategy is to decompose the KL divergence step\-wise\. And upper bound the expected KL divergence introduced at each update, using the fact that KL divergence between Gaussians with the same variance is proportional to the square of the mean difference\. Our initial decomposition is the same as that of\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\], but instead of upper bounding the KL divergence by the worst case update, our analysis involving the average case mean difference produces alog⁡\(n\)\\log\(n\)improvement over the previous result\.

We formalize recovery through graph\-learning tests:

###### Definition 7\.1\.

A*graph\-learning test*is a function that takes as input a Glauber trajectory𝒯\\mathcal\{T\}generated from an\(α,d\)\(\\alpha,d\)\-GGM with precision matrixΘ\\Thetaand support graphGG, together with the valuesα\\alphaanddd, and outputs an estimateG^\\widehat\{G\}forGG\. Its success event isG^=G\\widehat\{G\}=G\.

From now on, we consider only well\-mixed Glauber trajectories:

###### Definition 7\.2\.

Let𝒯​\(N,Θ\)\\mathcal\{T\}\(N,\\Theta\)denote a Glauber trajectory, withNNupdates, with precision matrixΘ\\Theta, and with starting point sampled from𝒩​\(0,Θ−1\)\\mathcal\{N\}\(0,\\Theta^\{\-1\}\)\.

Our main result in this section is as follows:

###### Theorem 7\.3\.

Letn≥16n\\geq 16andNNbe positive integers, and let0<α<1/40<\\alpha<1/4\. There exists a setSSof2​n2n\-dimensional\(α,1\)\(\\alpha,1\)\-sparse GGMs such that, ifΘ\\Thetais sampled uniformly fromSSand the trajectory𝒯​\(N,Θ\)\\mathcal\{T\}\(N,\\Theta\)is generated therefrom, then the success rate of a graph\-learning test is at most1/21/2wheneverN≤n​log⁡n8​α2N\\leq\\frac\{n\\log n\}\{8\\alpha^\{2\}\}\.

Note that\(α,1\)\(\\alpha,1\)\-sparse GGMs are also\(α,d\)\(\\alpha,d\)\-sparse for every positive integerdd, so this bound holds for alldd\.

### 7\.1The class of graphs

Fixnna positive integer, and consider the graphG0G\_\{0\}of sparsity 1 on vertices labeled 1, 2,…\\ldots,2​n2n, with an edge\(2​k−1\)∼2​k\(2k\-1\)\\sim 2kfor eachk=1,…,nk=1,\\ldots,n, and no other edges\. Further, letGkG\_\{k\}be a copy ofG0G\_\{0\}, but with the edge\(2​k−1\)∼2​k\(2k\-1\)\\sim 2kremoved, fork=1,…,nk=1,\\ldots,n\.

For each graphGkG\_\{k\}, defineΘk\\Theta\_\{k\}as the following\(α,1\)\(\\alpha,1\)\-sparse GGM with underlying graphGkG\_\{k\}:

\(Θk\)i​j=\{1i=jαi∼j​inGk0else\.\.\(\\Theta\_\{k\}\)\_\{ij\}=\\begin\{cases\}1&i=j\\\\ \\alpha&i\\sim j\\text\{ in $G\_\{k\}$\}\\\\ 0&\\text\{else\.\}\\end\{cases\}\.Our set of GGMs isS=\{Θ1,…,Θn\}S=\\\{\\Theta\_\{1\},\\ldots,\\Theta\_\{n\}\\\}\.

Notice that each GGM is the direct sum of2×22\\times 2matrices, among which at least one is the identity matrixI2I\_\{2\}, and the remaining are

Mα=\[1αα1\]\.M\_\{\\alpha\}=\\begin\{bmatrix\}1&\\alpha\\\\ \\alpha&1\\end\{bmatrix\}\.The eigenvalues ofMαM\_\{\\alpha\}are1−α\>01\-\\alpha\>0and1\+α\>01\+\\alpha\>0, so allΘk\\Theta\_\{k\}are positive definite\.

### 7\.2A bound on KL\-divergence

We now upper\-bound the pairwise KL divergence between the candidate trajectory distributions\. For a stateXXbefore theiith update, write𝒯​\(i,Θr\)X\(i\)∣X\(i−1\)=X\\mathcal\{T\}\(i,\\Theta\_\{r\}\)\_\{X^\{\(i\)\}\\mid X^\{\(i\-1\)\}=X\}for the conditional distribution of the post\-update state underΘr\\Theta\_\{r\}, and𝒯​\(i,Θr\)Xℓ\(i\)∣X\(i−1\)=X\\mathcal\{T\}\(i,\\Theta\_\{r\}\)\_\{X^\{\(i\)\}\_\{\\ell\}\\mid X^\{\(i\-1\)\}=X\}for itsℓ\\ellth coordinate, wherer∈\{0,1\}r\\in\\\{0,1\\\}\.

###### Lemma 7\.4\.

For eachk=1,…,nk=1,\\ldots,n, we have

DKL​\(𝒯​\(N,Θk\)∥𝒯​\(N,Θ0\)\)≤\(Nn\+1\)​α2\.D\_\{\\mathrm\{KL\}\}\(\\mathcal\{T\}\(N,\\Theta\_\{k\}\)\\parallel\\mathcal\{T\}\(N,\\Theta\_\{0\}\)\)\\leq\\left\(\\frac\{N\}\{n\}\+1\\right\)\\alpha^\{2\}\.

###### Proof of[Section7\.2](https://arxiv.org/html/2606.31230#S7.SS2)\.

Without loss of generalityk=1k=1\. Recall both trajectories𝒯​\(N,Θ0\)\\mathcal\{T\}\(N,\\Theta\_\{0\}\)and𝒯​\(N,Θk\)\\mathcal\{T\}\(N,\\Theta\_\{k\}\)begin mixed, so we first compute the KL\-divergence of their initial positions, by

DKL​\(𝒯​\(0,Θ1\)X\(0\)∥𝒯​\(0,Θ0\)X\(0\)\)\\displaystyle D\_\{\\mathrm\{KL\}\}\(\\mathcal\{T\}\(0,\\Theta\_\{1\}\)\_\{X^\{\(0\)\}\}\\parallel\\mathcal\{T\}\(0,\\Theta\_\{0\}\)\_\{X^\{\(0\)\}\}\)=DKL​\(𝒩​\(0,Θ1−1\)∥𝒩​\(0,Θ0−1\)\)\\displaystyle=D\_\{\\mathrm\{KL\}\}\(\\mathcal\{N\}\(0,\\Theta\_\{1\}^\{\-1\}\)\\parallel\\mathcal\{N\}\(0,\\Theta\_\{0\}^\{\-1\}\)\)=DKL​\(𝒩​\(0,Mα\)∥𝒩​\(0,I2\)\)\\displaystyle=D\_\{\\mathrm\{KL\}\}\(\\mathcal\{N\}\(0,M\_\{\\alpha\}\)\\parallel\\mathcal\{N\}\(0,I\_\{2\}\)\)=−12​ln⁡\(1−α2\)<α2,\\displaystyle=\-\\frac\{1\}\{2\}\\ln\(1\-\\alpha^\{2\}\)<\\alpha^\{2\},sinceα<1/4\\alpha<1/4\.

Now, by coupling, we may assume the two trajectories share the same sequence of updates\. Suppose both trajectories have reached positionXXbefore theiith update, and on theiith update, both trajectories update theℓ\\ellth coordinate\. We explicitly write down the distribution of theℓ\\ellth coordinate after this Glauber update:

𝒯​\(i,Θ0\)Xℓ\(i\)∣X\(i−1\)=X=−∑j∼ℓ−\(Θ0\)j​ℓ​Xj\+𝒩​\(0,1\),\\displaystyle\\mathcal\{T\}\(i,\\Theta\_\{0\}\)\_\{X^\{\(i\)\}\_\{\\ell\}\\mid X^\{\(i\-1\)\}=X\}=\-\\sum\_\{j\\sim\\ell\}\-\(\\Theta\_\{0\}\)\_\{j\\ell\}X\_\{j\}\+\\mathcal\{N\}\(0,1\),𝒯​\(i,Θ1\)Xℓ\(i\)∣X\(i−1\)=X=−∑j∼ℓ−\(Θ1\)j​ℓ​Xj\+𝒩​\(0,1\)\\displaystyle\\mathcal\{T\}\(i,\\Theta\_\{1\}\)\_\{X^\{\(i\)\}\_\{\\ell\}\\mid X^\{\(i\-1\)\}=X\}=\-\\sum\_\{j\\sim\\ell\}\-\(\\Theta\_\{1\}\)\_\{j\\ell\}X\_\{j\}\+\\mathcal\{N\}\(0,1\)But recall\(Θ0\)j​ℓ=\(Θ1\)j​ℓ\(\\Theta\_\{0\}\)\_\{j\\ell\}=\(\\Theta\_\{1\}\)\_\{j\\ell\}unless\{j,ℓ\}=\{1,2\}\\\{j,\\ell\\\}=\\\{1,2\\\}, in which case\(Θ0\)12−\(Θ1\)12=α\(\\Theta\_\{0\}\)\_\{12\}\-\(\\Theta\_\{1\}\)\_\{12\}=\\alpha\. Hence, the two distributions are normal with the same variance, and the means differ byα​X2\\alpha X\_\{2\}ifℓ=1\\ell=1, byα​X1\\alpha X\_\{1\}ifℓ=2\\ell=2, and by 0 otherwise\.

It follows that the KL\-divergence for theiith update is given by

DKL​\(𝒯​\(i,Θ1\)X\(i\)∣X\(i−1\)=X∥𝒯​\(i,Θ0\)X\(i\)∣X\(i−1\)=X\)\\displaystyle D\_\{\\mathrm\{KL\}\}\\Big\(\\mathcal\{T\}\(i,\\Theta\_\{1\}\)\_\{X^\{\(i\)\}\\mid X^\{\(i\-1\)\}=X\}\\parallel\\mathcal\{T\}\(i,\\Theta\_\{0\}\)\_\{X^\{\(i\)\}\\mid X^\{\(i\-1\)\}=X\}\\Big\)=DKL​\(𝒯​\(i,Θ1\)Xℓ\(i\)∣X\(i−1\)=X∥𝒯​\(i,Θ0\)Xℓ\(i\)∣X\(i−1\)=X\)\\displaystyle=D\_\{\\mathrm\{KL\}\}\\Big\(\\mathcal\{T\}\(i,\\Theta\_\{1\}\)\_\{X^\{\(i\)\}\_\{\\ell\}\\mid X^\{\(i\-1\)\}=X\}\\parallel\\mathcal\{T\}\(i,\\Theta\_\{0\}\)\_\{X^\{\(i\)\}\_\{\\ell\}\\mid X^\{\(i\-1\)\}=X\}\\Big\)=𝔼ℓ\[\{12​α2​X22ℓ=112​α2​X12ℓ=20ℓ≥3\]=α24​n​\(X12\+X22\)\.\\displaystyle=\\mathop\{\\mathbb\{E\}\}\_\{\\ell\}\\left\[\\begin\{cases\}\\frac\{1\}\{2\}\\alpha^\{2\}X\_\{2\}^\{2\}&\\ell=1\\\\ \\frac\{1\}\{2\}\\alpha^\{2\}X\_\{1\}^\{2\}&\\ell=2\\\\ 0&\\ell\\geq 3\\end\{cases\}\\right\]=\\frac\{\\alpha^\{2\}\}\{4n\}\\left\(X\_\{1\}^\{2\}\+X\_\{2\}^\{2\}\\right\)\.
But by[Section3\.5](https://arxiv.org/html/2606.31230#S3.SS5), we always haveX∼𝒩​\(0,Θ1−1\)X\\sim\\mathcal\{N\}\(0,\\Theta\_\{1\}^\{\-1\}\), so𝔼X\[X12\]=\(Θ1−1\)11=11−α2<2\\mathop\{\\mathbb\{E\}\}\_\{X\}\\left\[X\_\{1\}^\{2\}\\right\]=\(\\Theta\_\{1\}^\{\-1\}\)\_\{11\}=\\frac\{1\}\{1\-\\alpha^\{2\}\}<2, and thus

𝔼X\(i−1\)\[DKL​\(𝒯​\(i,Θ1\)X\(i\)∣X\(i−1\)=X∥𝒯​\(i,Θ0\)X\(i\)∣X\(i−1\)=X\)\]=α22​n​\(1−α2\)<α2n\.\\displaystyle\\mathop\{\\mathbb\{E\}\}\_\{X^\{\(i\-1\)\}\}\\Big\[D\_\{\\mathrm\{KL\}\}\\Big\(\\mathcal\{T\}\(i,\\Theta\_\{1\}\)\_\{X^\{\(i\)\}\\mid X^\{\(i\-1\)\}=X\}\\parallel\\mathcal\{T\}\(i,\\Theta\_\{0\}\)\_\{X^\{\(i\)\}\\mid X^\{\(i\-1\)\}=X\}\\Big\)\\Big\]=\\frac\{\\alpha^\{2\}\}\{2n\(1\-\\alpha^\{2\}\)\}<\\frac\{\\alpha^\{2\}\}\{n\}\.We conclude by linearity of expectation,

DKL​\(𝒯​\(N,Θ1\)∥𝒯​\(N,Θ0\)\)\\displaystyle D\_\{\\mathrm\{KL\}\}\(\\mathcal\{T\}\(N,\\Theta\_\{1\}\)\\parallel\\mathcal\{T\}\(N,\\Theta\_\{0\}\)\)=DKL​\(𝒯​\(0,Θ1\)X\(0\)∥𝒯​\(0,Θ0\)X\(0\)\)\\displaystyle=D\_\{\\mathrm\{KL\}\}\\Big\(\\mathcal\{T\}\(0,\\Theta\_\{1\}\)\_\{X^\{\(0\)\}\}\\parallel\\mathcal\{T\}\(0,\\Theta\_\{0\}\)\_\{X^\{\(0\)\}\}\\Big\)\+∑i=1N𝔼X\(i−1\)\[DKL​\(𝒯​\(i,Θ1\)X\(i\)∣X\(i−1\)=X∥𝒯​\(i,Θ0\)X\(i\)∣X\(i−1\)=X\)\]\\displaystyle\\qquad\+\\sum\_\{i=1\}^\{N\}\\mathop\{\\mathbb\{E\}\}\_\{X^\{\(i\-1\)\}\}\\Big\[D\_\{\\mathrm\{KL\}\}\\Big\(\\mathcal\{T\}\(i,\\Theta\_\{1\}\)\_\{X^\{\(i\)\}\\mid X^\{\(i\-1\)\}=X\}\\parallel\\mathcal\{T\}\(i,\\Theta\_\{0\}\)\_\{X^\{\(i\)\}\\mid X^\{\(i\-1\)\}=X\}\\Big\)\\Big\]<α2\+N​α2n\.∎\\displaystyle<\\alpha^\{2\}\+\\frac\{N\\alpha^\{2\}\}\{n\}\.\\qed

### 7\.3Fano’s method

We finish by using Fano’s method to bound the success rate of a graph\-learning test\.

###### Lemma 7\.5\.

The success rate of a graph\-learning test is bounded by

ℙ​\[G^=G\]≤\(N\+n\)​α2n​log⁡n\+log⁡2log⁡n\.\\mathbb\{P\}\\left\[\\widehat\{G\}=G\\right\]\\leq\\frac\{\(N\+n\)\\alpha^\{2\}\}\{n\\log n\}\+\\frac\{\\log 2\}\{\\log n\}\.

###### Proof\.

LetVVbe sampled uniformly from\{1,…,n\}\\\{1,\\ldots,n\\\}\. Let𝒯\\mathcal\{T\}denote the observed trajectory\. We may then bound the mutual information betweenVVand the observed trajectory by

I​\(V;𝒯\)\\displaystyle I\(V;\\mathcal\{T\}\)≤1n​∑i=1nDKL​\(𝒯​\(N,Θi\)∥𝒯​\(N,Θ0\)\)<α2\+N​α2n\.\\displaystyle\\leq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}D\_\{\\mathrm\{KL\}\}\(\\mathcal\{T\}\(N,\\Theta\_\{i\}\)\\parallel\\mathcal\{T\}\(N,\\Theta\_\{0\}\)\)<\\alpha^\{2\}\+\\frac\{N\\alpha^\{2\}\}\{n\}\.By Fano’s inequality, we have

ℙ​\[G^=G\]\\displaystyle\\mathbb\{P\}\\left\[\\widehat\{G\}=G\\right\]≤I​\(V;𝒯\)\+log⁡2log⁡n≤\(N\+n\)​α2n​log⁡n\+log⁡2log⁡n\.∎\\displaystyle\\leq\\frac\{I\(V;\\mathcal\{T\}\)\+\\log 2\}\{\\log n\}\\leq\\frac\{\(N\+n\)\\alpha^\{2\}\}\{n\\log n\}\+\\frac\{\\log 2\}\{\\log n\}\.\\qed

###### Proof of[Theorem7\.3](https://arxiv.org/html/2606.31230#S7.Thmtheorem3)\.

With our given assumptions, we haveN\+n≤n​log⁡n4​α2N\+n\\leq\\frac\{n\\log n\}\{4\\alpha^\{2\}\}, and so by[Section7\.3](https://arxiv.org/html/2606.31230#S7.SS3), we have

ℙ​\[G^=G\]\\displaystyle\\mathbb\{P\}\\left\[\\widehat\{G\}=G\\right\]≤\(N\+n\)​α2n​log⁡n\+log⁡2log⁡n≤14\+14=12\.∎\\displaystyle\\leq\\frac\{\(N\+n\)\\alpha^\{2\}\}\{n\\log n\}\+\\frac\{\\log 2\}\{\\log n\}\\leq\\frac\{1\}\{4\}\+\\frac\{1\}\{4\}=\\frac\{1\}\{2\}\.\\qed

## Acknowledgements

The authors thank Jason Gaitonde for helpful discussions and comments on an earlier version of this manuscript\. They also thank Jonathan Bloom and Roman Bezrukavnikov for organizing the SPUR program at MIT, where this project began\.

## References

- \[AMI91\]Y\. Amit\(1991\)On rates of convergence of stochastic relaxation for gaussian and non\-gaussian distributions\.Journal of Multivariate Analysis38\(1\),pp\. 82–99\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p7.2),[§1](https://arxiv.org/html/2606.31230#S1.p7.3)\.
- \[BMS\+19\]N\. Bhushan, F\. Mohnert, D\. Sloot, L\. Jans, C\. Albers, and L\. Steg\(2019\)Using a gaussian graphical model to explore relationships between items and variables in environmental psychology research\.Frontiers in psychology10,pp\. 1050\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p2.2)\.
- \[BHM\+26\]G\. Blanc, Y\. Huang, T\. Malkin, and R\. A\. Servedio\(2026\)Is nasty noise actually harder than malicious noise?\.InProceedings of the 2026 Annual ACM\-SIAM Symposium on Discrete Algorithms \(SODA\),pp\. 6767–6787\.Cited by:[footnote 5](https://arxiv.org/html/2606.31230#footnote5)\.
- \[BGS17\]G\. Bresler, D\. Gamarnik, and D\. Shah\(2017\)Learning graphical models from the glauber dynamics\.IEEE Transactions on Information Theory64\(6\),pp\. 4072–4080\.Cited by:[§1\.2](https://arxiv.org/html/2606.31230#S1.SS2.SSS0.Px2.p1.1)\.
- \[CG16\]P\. Cerchiello and P\. Giudici\(2016\)Conditional graphical models for systemic risk estimation\.Expert systems with applications43,pp\. 165–174\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p2.2)\.
- \[DMG\+20\]M\. Dyrba, R\. Mohammadi, M\. J\. Grothe, T\. Kirste, and S\. J\. Teipel\(2020\)Gaussian graphical models reveal inter\-modal and inter\-regional conditional dependencies of brain alterations in alzheimer’s disease\.Frontiers in aging neuroscience12,pp\. 99\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p2.2)\.
- \[GMM25a\]J\. Gaitonde, A\. Moitra, and E\. Mossel\(2025\)Better models and algorithms for learning ising models from dynamics\.arXiv preprint arXiv:2507\.15173\.Cited by:[§1\.2](https://arxiv.org/html/2606.31230#S1.SS2.SSS0.Px2.p1.1)\.
- \[GMM25b\]J\. Gaitonde, A\. Moitra, and E\. Mossel\(2025\)Bypassing the noisy parity barrier: learning higher\-order markov random fields from dynamics\.InProceedings of the 57th Annual ACM Symposium on Theory of Computing,pp\. 348–359\.Cited by:[§1\.2](https://arxiv.org/html/2606.31230#S1.SS2.SSS0.Px2.p1.1),[Lemma 3\.1](https://arxiv.org/html/2606.31230#S3.SS1.1)\.
- \[GM24\]J\. Gaitonde and E\. Mossel\(2024\)A unified approach to learning ising models: beyond independence and bounded width\.InProceedings of the 56th Annual ACM Symposium on Theory of Computing,pp\. 503–514\.Cited by:[§1\.2](https://arxiv.org/html/2606.31230#S1.SS2.SSS0.Px2.p1.1)\.
- \[HLS\+10\]S\. Huang, J\. Li, L\. Sun, J\. Ye, A\. Fleisher, T\. Wu, K\. Chen, E\. Reiman, A\. D\. N\. Initiative,et al\.\(2010\)Learning brain connectivity of alzheimer’s disease by sparse inverse covariance estimation\.NeuroImage50\(3\),pp\. 935–949\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p2.2)\.
- \[KSI\+11\]J\. Krumsiek, K\. Suhre, T\. Illig, J\. Adamski, and F\. J\. Theis\(2011\)Gaussian graphical modeling reconstructs pathway reactions from high\-throughput metabolomics data\.BMC systems biology5\(1\),pp\. 21\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p2.2)\.
- \[MVL20\]S\. Misra, M\. Vuffray, and A\. Y\. Lokhov\(2020\)Information theoretic optimal learning of gaussian graphical models\.InConference on Learning Theory,pp\. 2888–2909\.Cited by:[Appendix D](https://arxiv.org/html/2606.31230#A4.p1.7),[§1](https://arxiv.org/html/2606.31230#S1.p4.1),[§1](https://arxiv.org/html/2606.31230#S1.p5.6)\.
- \[NAT95\]B\. K\. Natarajan\(1995\)Sparse approximate solutions to linear systems\.SIAM journal on computing24\(2\),pp\. 227–234\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p5.6)\.
- \[RS97\]G\. O\. Roberts and S\. K\. Sahu\(1997\)Updating schemes, correlation structure, blocking and parameterization for the gibbs sampler\.Journal of the Royal Statistical Society Series B: Statistical Methodology59\(2\),pp\. 291–317\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p7.2),[§1](https://arxiv.org/html/2606.31230#S1.p7.3)\.
- \[TRD25\]V\. Tirukkonda, A\. Rayas, and G\. Dasarathy\(2025\)Structure learning in gaussian graphical models from glauber dynamics\.In2025 IEEE International Symposium on Information Theory \(ISIT\),pp\. 1–6\.Cited by:[Appendix C](https://arxiv.org/html/2606.31230#A3.SS0.SSS0.Px1.p1.13),[Appendix C](https://arxiv.org/html/2606.31230#A3.SS0.SSS0.Px2.p1.3),[Appendix C](https://arxiv.org/html/2606.31230#A3.SS0.SSS0.Px4.p1.3),[Appendix C](https://arxiv.org/html/2606.31230#A3.p1.4),[§1\.1](https://arxiv.org/html/2606.31230#S1.SS1.p4.15),[§1\.1](https://arxiv.org/html/2606.31230#S1.SS1.p9.1),[§1\.2](https://arxiv.org/html/2606.31230#S1.SS2.SSS0.Px1.p1.2),[Table 1](https://arxiv.org/html/2606.31230#S1.T1),[Table 1](https://arxiv.org/html/2606.31230#S1.T1.18.5),[Table 1](https://arxiv.org/html/2606.31230#S1.T1.2.2.3),[Table 1](https://arxiv.org/html/2606.31230#S1.T1.2.2.5),[Table 1](https://arxiv.org/html/2606.31230#S1.T1.5.5.4),[Table 1](https://arxiv.org/html/2606.31230#S1.T1.5.5.5),[§2](https://arxiv.org/html/2606.31230#S2.SS0.SSS0.Px9.p2.1),[§7](https://arxiv.org/html/2606.31230#S7.p2.1)\.
- \[WWR10\]W\. Wang, M\. J\. Wainwright, and K\. Ramchandran\(2010\)Information\-theoretic bounds on model selection for gaussian markov random fields\.In2010 IEEE International Symposium on Information Theory,pp\. 1373–1377\.Cited by:[§1\.1](https://arxiv.org/html/2606.31230#S1.SS1.p8.4),[§1](https://arxiv.org/html/2606.31230#S1.p5.6)\.
- \[YZL\+22\]H\. Yi, Q\. Zhang, C\. Lin, and S\. Ma\(2022\)Information\-incorporated gaussian graphical model for gene expression data\.Biometrics78\(2\),pp\. 512–523\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p2.2)\.
- \[ZFL\+14\]T\. Zerenner, P\. Friederichs, K\. Lehnertz, and A\. Hense\(2014\)A gaussian graphical model approach to climate networks\.Chaos: An Interdisciplinary Journal of Nonlinear Science24\(2\)\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p2.2)\.
- \[ZWJ14\]Y\. Zhang, M\. J\. Wainwright, and M\. I\. Jordan\(2014\)Lower bounds on the performance of polynomial\-time algorithms for sparse linear regression\.InConference on Learning Theory,pp\. 921–948\.Cited by:[§1](https://arxiv.org/html/2606.31230#S1.p5.6)\.

## Appendix ARobust Estimators

In this appendix, we prove the two robust\-estimation lemmas stated in[Section3](https://arxiv.org/html/2606.31230#S3), namely[Sections3\.3](https://arxiv.org/html/2606.31230#S3.SS3)and[3\.3](https://arxiv.org/html/2606.31230#S3.SS3)\. The variance proof is based on controlling the relevant quantile under contamination, while the mean proof uses a martingale argument together with Azuma–Hoeffding\. See[3\.3](https://arxiv.org/html/2606.31230#S3.SS3)

###### Proof\.

LetΦ\\Phiandφ\\varphidenote the cdf and pdf, respectively, of the standard Gaussian, and setq:=Φ−1​\(3/4\)q:=\\Phi^\{\-1\}\(3/4\)\. LetMMbe the sample median of the absolute values of the observed samples, and setσ^:=Mq\\widehat\{\\sigma\}:=\\frac\{M\}\{q\}\. By scaling, it suffices to consider the caseσ=1\\sigma=1\. Then the absolute value of an uncorrupted sample has cdfG​\(t\):=2​Φ​\(t\)−1G\(t\):=2\\Phi\(t\)\-1\. LetGnG\_\{n\}denote the empirical cdf of the clean absolute values, letHnH\_\{n\}denote the empirical cdf of the observed absolute values, and letk:=∑i=1nξik:=\\sum\_\{i=1\}^\{n\}\\xi\_\{i\}be the number of corruptions\.

By Dvoretzky–Kiefer–Wolfowitz with toleranceη/2\\eta/2,

ℙ​\[supx∈ℝ\|Gn​\(x\)−G​\(x\)\|\>η2\]≤2​e−n​η2/2≤δ2\.\\mathbb\{P\}\\\!\\left\[\\sup\_\{x\\in\\mathbb\{R\}\}\\lvert G\_\{n\}\(x\)\-G\(x\)\\rvert\>\\frac\{\\eta\}\{2\}\\right\]\\leq 2e^\{\-n\\eta^\{2\}/2\}\\leq\\frac\{\\delta\}\{2\}\.Also, a multiplicative Chernoff bound with parameter1/31/3gives

ℙ​\[k\>43​η​n\]\\displaystyle\\mathbb\{P\}\\\!\\left\[k\>\\frac\{4\}\{3\}\\eta n\\right\]≤exp⁡\(−\(43​log⁡43−13\)​η​n\)≤e−η​n/20≤δ4,\\displaystyle\\leq\\exp\\\!\\left\(\-\\left\(\\frac\{4\}\{3\}\\log\\frac\{4\}\{3\}\-\\frac\{1\}\{3\}\\right\)\\eta n\\right\)\\leq e^\{\-\\eta n/20\}\\leq\\frac\{\\delta\}\{4\},where the last inequality uses

n≥2​log⁡\(4/δ\)η2andη≤110\.n\\geq\\frac\{2\\log\(4/\\delta\)\}\{\\eta^\{2\}\}\\qquad\\text\{and\}\\qquad\\eta\\leq\\frac\{1\}\{10\}\.Therefore, with probability at least1−3​δ/41\-3\\delta/4,

supx∈ℝ\|Gn​\(x\)−G​\(x\)\|≤η2andk≤43​η​n\.\\sup\_\{x\\in\\mathbb\{R\}\}\\big\\lvert G\_\{n\}\(x\)\-G\(x\)\\big\\rvert\\leq\\frac\{\\eta\}\{2\}\\qquad\\text\{and\}\\qquad k\\leq\\frac\{4\}\{3\}\\eta n\.
Work on this event\. SinceHnH\_\{n\}is obtained fromGnG\_\{n\}by changing at mostkksample points,

supx∈ℝ\|Hn​\(x\)−G​\(x\)\|\\displaystyle\\sup\_\{x\\in\\mathbb\{R\}\}\\big\\lvert H\_\{n\}\(x\)\-G\(x\)\\big\\rvert≤supx∈ℝ\|Hn​\(x\)−Gn​\(x\)\|\+supx∈ℝ\|Gn​\(x\)−G​\(x\)\|\\displaystyle\\leq\\sup\_\{x\\in\\mathbb\{R\}\}\\big\\lvert H\_\{n\}\(x\)\-G\_\{n\}\(x\)\\big\\rvert\+\\sup\_\{x\\in\\mathbb\{R\}\}\\big\\lvert G\_\{n\}\(x\)\-G\(x\)\\big\\rvert≤kn\+η2≤11​η6\.\\displaystyle\\leq\\frac\{k\}\{n\}\+\\frac\{\\eta\}\{2\}\\leq\\frac\{11\\eta\}\{6\}\.
SinceMMis a median of the observed absolute values, we haveHn​\(M−\)≤1/2≤Hn​\(M\)H\_\{n\}\(M^\{\-\}\)\\leq 1/2\\leq H\_\{n\}\(M\)\. BecauseGGis continuous and increasing, it follows that

12−11​η6≤G​\(M\)≤12\+11​η6\.\\frac\{1\}\{2\}\-\\frac\{11\\eta\}\{6\}\\leq G\(M\)\\leq\\frac\{1\}\{2\}\+\\frac\{11\\eta\}\{6\}\.Equivalently,

34−11​η12≤Φ​\(M\)≤34\+11​η12\.\\frac\{3\}\{4\}\-\\frac\{11\\eta\}\{12\}\\leq\\Phi\(M\)\\leq\\frac\{3\}\{4\}\+\\frac\{11\\eta\}\{12\}\.Sinceη≤1/10\\eta\\leq 1/10, this placesMMin the interval

Φ−1​\(79120\)≤M≤Φ−1​\(101120\)\.\\Phi^\{\-1\}\\left\(\\frac\{79\}\{120\}\\right\)\\leq M\\leq\\Phi^\{\-1\}\\left\(\\frac\{101\}\{120\}\\right\)\.
NowΦ−1\\Phi^\{\-1\}is increasing and convex on\(1/2,1\)\(1/2,1\), so its deviation fromq=Φ−1​\(3/4\)q=\\Phi^\{\-1\}\(3/4\)is bounded linearly on this interval\. Because

11​η12≤11120⋅10​η,\\frac\{11\\eta\}\{12\}\\leq\\frac\{11\}\{120\}\\cdot 10\\eta,we obtain

\|M−q\|≤10​η⋅max⁡\{Φ−1​\(101120\)−q,q−Φ−1​\(79120\)\}\.\\displaystyle\\lvert M\-q\\rvert\\leq 10\\eta\\cdot\\max\\\!\\bigg\\\{\\Phi^\{\-1\}\\left\(\\frac\{101\}\{120\}\\right\)\-q,\\;q\-\\Phi^\{\-1\}\\left\(\\frac\{79\}\{120\}\\right\)\\bigg\\\}\.Finally,

\|σ^−1\|\\displaystyle\\lvert\\widehat\{\\sigma\}\-1\\rvert=\|M−q\|q\\displaystyle=\\frac\{\\lvert M\-q\\rvert\}\{q\}≤10​ηΦ−1​\(3/4\)​max⁡\{Φ−1​\(101120\)−Φ−1​\(34\),Φ−1​\(34\)−Φ−1​\(79120\)\}\\displaystyle\\leq\\frac\{10\\eta\}\{\\Phi^\{\-1\}\(3/4\)\}\\max\\\!\\bigg\\\{\\Phi^\{\-1\}\\left\(\\frac\{101\}\{120\}\\right\)\-\\Phi^\{\-1\}\\left\(\\frac\{3\}\{4\}\\right\),\\;\\Phi^\{\-1\}\\left\(\\frac\{3\}\{4\}\\right\)\-\\Phi^\{\-1\}\\left\(\\frac\{79\}\{120\}\\right\)\\bigg\\\}<5​η\.\\displaystyle<5\\eta\.This proves the lemma\. ∎

See[3\.3](https://arxiv.org/html/2606.31230#S3.SS3)

###### Proof\.

Let\(ℱℓ\)ℓ=0n\(\\mathcal\{F\}\_\{\\ell\}\)\_\{\\ell=0\}^\{n\}be the filtration from the statement, and letμ^\\widehat\{\\mu\}denote the sample median\. LetΦ\\Phiandφ\\varphidenote the cdf and pdf, respectively, of a standard Gaussian\. Let𝟙ℓ\\mathds\{1\}\_\{\\ell\}indicate the event that eitherξ\(ℓ\)=1\\xi^\{\(\\ell\)\}=1orx\(ℓ\)\>μ\+5​ηx^\{\(\\ell\)\}\>\\mu\+5\\eta\. Then

𝔼​\[𝟙ℓ∣ℱℓ−1\]\\displaystyle\\mathbb\{E\}\[\\mathds\{1\}\_\{\\ell\}\\mid\\mathcal\{F\}\_\{\\ell\-1\}\]≤𝔼\[ξ\(ℓ\)∣ℱℓ−1\]\+ℙ\[x\(ℓ\)\>μ\+5η,ξ\(ℓ\)=0\|ℱℓ−1\]\\displaystyle\\leq\\mathbb\{E\}\[\\xi^\{\(\\ell\)\}\\mid\\mathcal\{F\}\_\{\\ell\-1\}\]\+\\mathbb\{P\}\\\!\\left\[x^\{\(\\ell\)\}\>\\mu\+5\\eta,\\ \\xi^\{\(\\ell\)\}=0\\,\\middle\|\\,\\mathcal\{F\}\_\{\\ell\-1\}\\right\]≤η\+ℙ\[x\(ℓ\)\>μ\+5η\|ℱℓ−1,ξ\(ℓ\)=0\]\\displaystyle\\leq\\eta\+\\mathbb\{P\}\\\!\\left\[x^\{\(\\ell\)\}\>\\mu\+5\\eta\\,\\middle\|\\,\\mathcal\{F\}\_\{\\ell\-1\},\\xi^\{\(\\ell\)\}=0\\right\]≤1\+η−Φ​\(5​η\)\.\\displaystyle\\leq 1\+\\eta\-\\Phi\(5\\eta\)\.Therefore,

Mk=∑ℓ=1k\(𝟙ℓ−𝔼​\[𝟙ℓ∣ℱℓ−1\]\)M\_\{k\}=\\sum\_\{\\ell=1\}^\{k\}\\left\(\\mathds\{1\}\_\{\\ell\}\-\\mathbb\{E\}\[\\mathds\{1\}\_\{\\ell\}\\mid\\mathcal\{F\}\_\{\\ell\-1\}\]\\right\)is a martingale with bounded increments in\[−1,1\]\[\-1,1\]\.

By Azuma–Hoeffding \([Section3\.4](https://arxiv.org/html/2606.31230#S3.SS4)\),

ℙ​\[μ^≥μ\+5​η\]\\displaystyle\\mathbb\{P\}\[\\widehat\{\\mu\}\\geq\\mu\+5\\eta\]≤ℙ​\[∑ℓ=1n𝟙ℓ≥n2\]\\displaystyle\\leq\\mathbb\{P\}\\left\[\\sum\_\{\\ell=1\}^\{n\}\\mathds\{1\}\_\{\\ell\}\\geq\\frac\{n\}\{2\}\\right\]≤ℙ​\[Mn≥n​\(Φ​\(5​η\)−η−12\)\]\\displaystyle\\leq\\mathbb\{P\}\\left\[M\_\{n\}\\geq n\\left\(\\Phi\(5\\eta\)\-\\eta\-\\frac\{1\}\{2\}\\right\)\\right\]≤exp⁡\(−2​n​\(Φ​\(5​η\)−η−12\)2\)\.\\displaystyle\\leq\\exp\\left\(\-2n\\left\(\\Phi\(5\\eta\)\-\\eta\-\\frac\{1\}\{2\}\\right\)^\{2\}\\right\)\.Forη≤1/10\\eta\\leq 1/10, we haveφ​\(5​η\)\>3/10\\varphi\(5\\eta\)\>3/10, and hence

Φ​\(5​η\)−η−12\\displaystyle\\Phi\(5\\eta\)\-\\eta\-\\frac\{1\}\{2\}=−η\+∫05​ηφ​\(x\)​𝑑x\>−η\+5​η​φ​\(5​η\)\>η/2\.\\displaystyle=\-\\eta\+\\int\_\{0\}^\{5\\eta\}\\varphi\(x\)\\,dx\>\-\\eta\+5\\eta\\varphi\(5\\eta\)\>\\eta/2\.Substituting this bound yields

ℙ​\[μ^≥μ\+5​η\]≤exp⁡\(−n​η2/2\)\.\\mathbb\{P\}\[\\widehat\{\\mu\}\\geq\\mu\+5\\eta\]\\leq\\exp\(\-n\\eta^\{2\}/2\)\.
The lower tail is identical: if𝟙~ℓ\\widetilde\{\\mathds\{1\}\}\_\{\\ell\}denotes the event that eitherξ\(ℓ\)=1\\xi^\{\(\\ell\)\}=1orx\(ℓ\)<μ−5​ηx^\{\(\\ell\)\}<\\mu\-5\\eta, the same argument gives

ℙ​\[μ^≤μ−5​η\]≤exp⁡\(−n​η2/2\)\.\\mathbb\{P\}\[\\widehat\{\\mu\}\\leq\\mu\-5\\eta\]\\leq\\exp\(\-n\\eta^\{2\}/2\)\.
Combining the two one\-sided bounds with a union bound, we obtain

ℙ​\[\|μ^−μ\|≥5​η\]≤2​exp⁡\(−n​η2/2\)≤δ\.\\mathbb\{P\}\[\\lvert\\widehat\{\\mu\}\-\\mu\\rvert\\geq 5\\eta\]\\leq 2\\exp\(\-n\\eta^\{2\}/2\)\\leq\\delta\.This proves the lemma\. ∎

## Appendix BContinuous Time Versus Number of Updates

The upper bounds in[Theorems1\.3](https://arxiv.org/html/2606.31230#S1.Thmtheorem3)and[1\.4](https://arxiv.org/html/2606.31230#S1.Thmtheorem4)are stated in terms of the continuous\-time horizonTT, whereas the lower bound in[Theorem7\.3](https://arxiv.org/html/2606.31230#S7.Thmtheorem3)is stated in terms of the number of single\-site updates\. This appendix records the standard reduction showing that these two formulations are equivalent up to the factornn\.

Recall from[Section1\.1](https://arxiv.org/html/2606.31230#S1.SS1)that the jump times satisfyS\(0\)=0S^\{\(0\)\}=0andS\(ℓ\+1\)−S\(ℓ\)∼Exp​\(n\)S^\{\(\\ell\+1\)\}\-S^\{\(\\ell\)\}\\sim\\mathrm\{Exp\}\(n\)i\.i\.d\. Let

NT:\-max⁡\{ℓ≥0:S\(ℓ\)≤T\}N\_\{T\}\\coloneq\\max\\\{\\ell\\geq 0:S^\{\(\\ell\)\}\\leq T\\\}denote the number of updates by timeTT\. ThenNT∼Poisson​\(n​T\)N\_\{T\}\\sim\\mathrm\{Poisson\}\(nT\)\. Moreover, conditional onNT=mN\_\{T\}=m, the continuous\-time trajectory up to timeTTis exactly the firstmmsteps of the embedded discrete\-time chain, together with the jump timesS\(1\),…,S\(m\)S^\{\(1\)\},\\dots,S^\{\(m\)\}\. Since these jump times are independent ofΘ\\Thetaand of the embedded chain, the only substantive difference between the two models is that in continuous time one observes a*random*numberNTN\_\{T\}of discrete\-time updates\.

###### Proposition B\.1\.

The continuous\-time and discrete\-time formulations are interchangeable up to constant factors\.

1. \(i\)If there is an estimator that, from the firstNNupdates of the embedded discrete\-time chain, succeeds with probability at least1−δ1\-\\delta, then there is an estimator that, from a continuous\-time trajectory of length2​N/n2N/n, succeeds with probability at least1−δ−e−N/41\-\\delta\-e^\{\-N/4\}\.
2. \(ii\)If there is an estimator that, from a continuous\-time trajectory of lengthTT, succeeds with probability at least1−δ1\-\\delta, then there is an estimator that, from the first⌈2​n​T⌉\\lceil 2nT\\rceilupdates of the embedded discrete\-time chain, succeeds with probability at least1−δ−e−n​T/31\-\\delta\-e^\{\-nT/3\}\.

###### Proof\.

For \(i\), observe the continuous\-time trajectory up to time2​N/n2N/n\. IfN2​N/n≥NN\_\{2N/n\}\\geq N, run the discrete\-time estimator on the firstNNupdates of the embedded chain and ignore the rest\. SinceN2​N/n∼Poisson​\(2​N\)N\_\{2N/n\}\\sim\\mathrm\{Poisson\}\(2N\), the bad event is\{N2​N/n<N\}\\\{N\_\{2N/n\}<N\\\}, which has probability at moste−N/4e^\{\-N/4\}by Chernoff\.

For \(ii\), suppose we are given the firstM=⌈2​n​T⌉M=\\lceil 2nT\\rceilupdates of the embedded discrete\-time chain\. Sample i\.i\.d\. waiting timesW1,…,WM∼Exp​\(n\)W\_\{1\},\\dots,W\_\{M\}\\sim\\mathrm\{Exp\}\(n\), setS\(ℓ\)=∑r=1ℓWrS^\{\(\\ell\)\}=\\sum\_\{r=1\}^\{\\ell\}W\_\{r\}, and reconstruct the corresponding continuous\-time path up to timeTT\. IfS\(M\)\>TS^\{\(M\)\}\>T, this reconstruction is exact up to timeTT, so we may run the continuous\-time estimator\. The bad event isS\(M\)≤TS^\{\(M\)\}\\leq T, equivalentlyNT≥MN\_\{T\}\\geq Mfor a rate\-nnPoisson process, and sinceM≥2​n​TM\\geq 2nTthis has probability at moste−n​T/3e^\{\-nT/3\}by Chernoff\. ∎

###### Corollary B\.2\.

Up to absolute constant factors, the deterministic conversion between the two models isN≍n​TN\\asymp nT\. In particular, the lower boundN=Ω​\(n​log⁡n/α2\)N=\\Omega\(n\\log n/\\alpha^\{2\}\)of[Theorem7\.3](https://arxiv.org/html/2606.31230#S7.Thmtheorem3)is equivalent to a continuous\-time lower boundT=Ω​\(log⁡n/α2\)T=\\Omega\(\\log n/\\alpha^\{2\}\)\.

## Appendix CA Technical Gap in the Analysis of Prior Work

We identify a gap in the analysis of\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]\. We notified the authors, who have since posted an updated manuscript on arXiv addressing the issue via an “i​i​j​iiiji”\-based mechanism\. Concretely, in the proof of Lemma 1 \(step \(c\)\), and again in the proof of Lemma 7 \(Appendix B\.5\), the argument asserts that a certain conditional expectation of a ratio vanishes by invoking mean\-zero and \(marginal\) independence of Gaussian noise terms\. As we explain below, this cancellation is not justified when\(i,j\)∈E\(i,j\)\\in E, because the denominator involves a future increment of coordinatejjwhich depends on earlier noise injected at coordinateii\.

From a technical viewpoint, this is one major reason that our mixing\-free analysis relies on update patterns of the form “i​i​j​iiiji” rather than on a direct “i​j​iiji” ratio argument\. The additional update ofiiis used to avoid exactly the type of dependence described above\. In the separate mixing\-based result, we are able to work with “i​j​iiji” patterns because the analysis there is different and does not rely on this cancellation\.

We now explain the gap in detail\.

In Lemma 1, they consider an update patternn1<n2<n3n\_\{1\}<n\_\{2\}<n\_\{3\}in which nodeiiis updated at timesn1n\_\{1\}andn3n\_\{3\}and nodejjis updated at timen2n\_\{2\}, and they define a conditional expectation𝔼x¯,c​\[⋅\]\\mathbb\{E\}\_\{\\bar\{x\},c\}\[\\cdot\]that fixes the values ofXN​\(i\)∖\{j\}X\_\{N\(i\)\\setminus\\\{j\\\}\}at the beginning of the window and conditions on the event\|Xj\(n2\)−Xj\(n1\)\|≥c\\lvert X\_\{j\}^\{\(n\_\{2\}\)\}\-X\_\{j\}^\{\(n\_\{1\}\)\}\\rvert\\geq c\. In the proof, the step labeled \(c\) asserts that

𝔼x¯,c​\[εi\(n3\)−εi\(n1\)Xj\(n2\)−Xj\(n1\)\]=0,\\mathbb\{E\}\_\{\\bar\{x\},c\}\\\!\\left\[\\frac\{\\varepsilon\_\{i\}^\{\(n\_\{3\}\)\}\-\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\}\{X\_\{j\}^\{\(n\_\{2\}\)\}\-X\_\{j\}^\{\(n\_\{1\}\)\}\}\\right\]=0,citing the mean\-zero and \(marginal\) independence of the Gaussian noise variables\{εi\(t\)\}\\\{\\varepsilon\_\{i\}^\{\(t\)\}\\\}\. A formally identical cancellation is used later in Appendix B\.5 \(in the proof of Lemma 7\) when rewriting their test statistic as a signal term plus a ratio involvingΔ​εi/Δ​Xj\\Delta\\varepsilon\_\{i\}/\\Delta X\_\{j\}and dropping the latter in conditional expectation\.

#### Why the denominator depends on earlier noise when\(i,j\)∈E\(i,j\)\\in E\.

Fix the “i​j​iiji” update patternn1<n2<n3n\_\{1\}<n\_\{2\}<n\_\{3\}from Lemma 1 of\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\], whereiiis updated at timesn1n\_\{1\}andn3n\_\{3\}andjjis updated at timen2n\_\{2\}, and enforce their accompanying event that no neighbor ofiiorjj\(other than possibly each other\) updates inside the window\. Assume\(i,j\)∈E\(i,j\)\\in E, soΘj​i≠0\\Theta\_\{ji\}\\neq 0\. Recall the Gaussian single\-site update rule: whenuuis updated at timett,

Xu\(t\)\\displaystyle X\_\{u\}^\{\(t\)\}=−∑k∈N​\(u\)Θu​kΘu​u​Xk\(t−1\)\+εu\(t\),εu\(t\)∼𝒩​\(0,1Θu​u\),\\displaystyle=\-\\\!\\sum\_\{k\\in N\(u\)\}\\frac\{\\Theta\_\{uk\}\}\{\\Theta\_\{uu\}\}\\,X\_\{k\}^\{\(t\-1\)\}\+\\varepsilon\_\{u\}^\{\(t\)\},\\qquad\\varepsilon\_\{u\}^\{\(t\)\}\\sim\\mathcal\{N\}\\\!\\left\(0,\\frac\{1\}\{\\Theta\_\{uu\}\}\\right\),Consider the randomness only through the lens of the single noise termεi\(n1\)\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}by fixing the pre\-n1n\_\{1\}state, the update indices, and all other Gaussian noises\{εu\(t\):\(u,t\)≠\(i,n1\)\}\\\{\\varepsilon\_\{u\}^\{\(t\)\}:\(u,t\)\\neq\(i,n\_\{1\}\)\\\}\. Under this fixing, the update at timen1n\_\{1\}gives an affine representation

Xi\(n1\)=mi\+εi\(n1\)X\_\{i\}^\{\(n\_\{1\}\)\}=m\_\{i\}\+\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}for a constantmim\_\{i\}determined by what has been fixed\. Sinceiiis not updated betweenn1n\_\{1\}andn2n\_\{2\}, the update ofjjat timen2n\_\{2\}usesXi\(n1\)X\_\{i\}^\{\(n\_\{1\}\)\}, and therefore

Xj\(n2\)\\displaystyle X\_\{j\}^\{\(n\_\{2\}\)\}=−Θj​iΘj​j​Xi\(n1\)−∑k∈N​\(j\)∖\{i\}Θj​kΘj​j​Xk\(n2−1\)\+εj\(n2\)\\displaystyle=\-\\frac\{\\Theta\_\{ji\}\}\{\\Theta\_\{jj\}\}\\,X\_\{i\}^\{\(n\_\{1\}\)\}\-\\sum\_\{k\\in N\(j\)\\setminus\\\{i\\\}\}\\frac\{\\Theta\_\{jk\}\}\{\\Theta\_\{jj\}\}\\,X\_\{k\}^\{\(n\_\{2\}\-1\)\}\+\\varepsilon\_\{j\}^\{\(n\_\{2\}\)\}=mj′−Θj​iΘj​j​εi\(n1\)\+εj\(n2\),\\displaystyle=m\_\{j\}^\{\\prime\}\-\\frac\{\\Theta\_\{ji\}\}\{\\Theta\_\{jj\}\}\\,\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\+\\varepsilon\_\{j\}^\{\(n\_\{2\}\)\},for a constantmj′m\_\{j\}^\{\\prime\}determined by the same fixing\. Consequently, the increment appearing in their denominator satisfies

Xj\(n2\)−Xj\(n1\)\\displaystyle X\_\{j\}^\{\(n\_\{2\}\)\}\-X\_\{j\}^\{\(n\_\{1\}\)\}=a\+b​εi\(n1\)\+εj\(n2\),b=−Θj​iΘj​j≠0,\\displaystyle=a\+b\\,\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\+\\varepsilon\_\{j\}^\{\(n\_\{2\}\)\},\\qquad b=\-\\frac\{\\Theta\_\{ji\}\}\{\\Theta\_\{jj\}\}\\neq 0,for a constantaadetermined by the fixed past\. In particular, when\(i,j\)∈E\(i,j\)\\in E, the denominator is a function ofεi\(n1\)\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}, so it is not independent of the numerator noise termεi\(n1\)\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\.

#### The conditioning\|Xj\(n2\)−Xj\(n1\)\|≥c\\lvert X\_\{j\}^\{\(n\_\{2\}\)\}\-X\_\{j\}^\{\(n\_\{1\}\)\}\\rvert\\geq cdoes not repair the issue\.

In Lemma 1 \(and again in Appendix B\.5\),\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]conditions on the event

\|Xj\(n2\)−Xj\(n1\)\|≥c\.\\left\\lvert X\_\{j\}^\{\(n\_\{2\}\)\}\-X\_\{j\}^\{\(n\_\{1\}\)\}\\right\\rvert\\geq c\.Under the affine form above, this event is exactly

\|a\+b​εi\(n1\)\+εj\(n2\)\|≥c,\\left\\lvert a\+b\\,\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\+\\varepsilon\_\{j\}^\{\(n\_\{2\}\)\}\\right\\rvert\\geq c,which depends onεi\(n1\)\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\. Thus, even after imposing the “≥c\\geq c” condition, the ratio term in step \(c\) involves a numerator noise component that is statistically coupled to the denominator\.

#### The ratio noise term need not have zero \(conditional\) expectation\.

As a result, the cancellation invoked in step \(c\) would require showing that an expression of the form

𝔼\[εi\(n1\)a\+b​εi\(n1\)\+εj\(n2\)\|\|a\+bεi\(n1\)\+εj\(n2\)\|≥c\]=0\\mathbb\{E\}\\\!\\left\[\\frac\{\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\}\{a\+b\\,\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\+\\varepsilon\_\{j\}^\{\(n\_\{2\}\)\}\}\\;\\Bigg\|\\;\\left\\lvert a\+b\\,\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\+\\varepsilon\_\{j\}^\{\(n\_\{2\}\)\}\\right\\rvert\\geq c\\right\]=0holds under the relevant conditioning\. There is no general reason for this to be true\.

In fact, fora=0a=0andb=1b=1, we have

𝔼\[εi\(n1\)εi\(n1\)\+εj\(n2\)\|\|εi\(n1\)\+εj\(n2\)\|≥c\]=12\\mathbb\{E\}\\left\[\\frac\{\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\}\{\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\+\\varepsilon\_\{j\}^\{\(n\_\{2\}\)\}\}\\;\\Bigg\|\\;\\left\\lvert\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\+\\varepsilon\_\{j\}^\{\(n\_\{2\}\)\}\\right\\rvert\\geq c\\right\]=\\frac\{1\}\{2\}by symmetry inεi\(n1\)\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}andεj\(n2\)\\varepsilon\_\{j\}^\{\(n\_\{2\}\)\}, as they are i\.i\.d\.

Therefore, the vanishing of the ratio noise term cannot be justified solely from mean\-zero and marginal independence of Gaussian noises\.

#### Implications and connection to our approach\.

The discussion above shows that the specific cancellation used in step \(c\) of Lemma 1 of\[[TRD25](https://arxiv.org/html/2606.31230#bib.bib31)\]is not justified as stated\. The denominator contains the future incrementXj\(n2\)−Xj\(n1\)X\_\{j\}^\{\(n\_\{2\}\)\}\-X\_\{j\}^\{\(n\_\{1\}\)\}, which, when\(i,j\)∈E\(i,j\)\\in E, can depend on the earlier noiseεi\(n1\)\\varepsilon\_\{i\}^\{\(n\_\{1\}\)\}\. Consequently, the relevant ratio term need not have zero conditional expectation\. Since the same cancellation is used again in Appendix B\.5, in the proof of Lemma 7, the same issue propagates to the later separation argument built on that identity\.

For our purposes, this explains why the mixing\-free part of our analysis is based oni​i​j​iiijipatterns rather than on this directi​j​iijiratio argument\. The additional update ofiiremoves the dependence created by the firstii\-update before the later update ofjjenters the statistic, so the conditional\-independence step needed in our proofs becomes valid\. By contrast, when mixing is available, we also give a separate algorithm based oni​j​iijipatterns; that argument uses the mixing assumption and does not rely on the cancellation above\.

## Appendix DNon\-Degeneracy Does Not Control Eigenvalues

In this appendix we demonstrate that the reciprocal of the minimum eigenvalue of the normalized precision matrixΘ′\\Theta^\{\\prime\}can be arbitrarily large even when all nonzero entries are bounded away from0\. Further, we show that this phenomenon is independent of the sparsity constraint: even when the graph ofΘ′\\Theta^\{\\prime\}isdd\-sparse ford\>2d\>2, the edge\-strength parameterα\\alphadoes not control1/λmin​\(Θ′\)1/\\lambda\_\{\\min\}\(\\Theta^\{\\prime\}\)\. Our construction is similar to Example \(5\) in\[[MVL20](https://arxiv.org/html/2606.31230#bib.bib20)\]\.

###### Proposition D\.1\.

Fixn≥2n\\geq 2,α<1\\alpha<1, andd≥2d\\geq 2\. For any large numberN∈ℝ\+N\\in\\mathbb\{R\}^\{\+\}, there exists a matrixΘ′∈ℝn×n\\Theta^\{\\prime\}\\in\\mathbb\{R\}^\{n\\times n\}with minimum edge strengthα\\alphaand sparsitydd, whileλmin−1\>N\\lambda\_\{\\min\}^\{\-1\}\>N\.

###### Proof\.

Consider the matrix

Bε:\-\[11−ε1−ε1\]B\_\{\\varepsilon\}\\coloneq\\begin\{bmatrix\}1&1\-\\varepsilon\\\\ 1\-\\varepsilon&1\\end\{bmatrix\}This matrix has minimum edge strength1−ε1\-\\varepsilon\.

The matrixBεB\_\{\\varepsilon\}has eigenvectorsv1=\[1,1\]v\_\{1\}=\[1,1\]andv2=\[1,−1\]v\_\{2\}=\[1,\-1\], satisfyingBε​v1=\(2−ε\)​v1B\_\{\\varepsilon\}v\_\{1\}=\(2\-\\varepsilon\)v\_\{1\}andBε​v2=ε​v2B\_\{\\varepsilon\}v\_\{2\}=\\varepsilon v\_\{2\}\. Henceλmin−1=1/ε\\lambda\_\{\\min\}^\{\-1\}=1/\\varepsilon\. This means that for allα<1\\alpha<1and any large enough numberM\>NM\>NwithM\>11−αM\>\\frac\{1\}\{1\-\\alpha\}, the matrixB1/MB\_\{1/M\}has entries lower bounded by1−1M\>α1\-\\frac\{1\}\{M\}\>\\alpha, while the reciprocal of the minimum eigenvalue isMM\.

We can further extend the example ofBεB\_\{\\varepsilon\}to higher dimension to demonstrate that the edge\-strength condition, together with sparsity constraints, can still allow largeλmin−1\\lambda\_\{\\min\}^\{\-1\}\. For anyn\>2n\>2, the block matrix

Bn,ε:\-\[Bε00In−2\],B\_\{n,\\varepsilon\}\\coloneq\\begin\{bmatrix\}B\_\{\\varepsilon\}&0\\\\ 0&I\_\{n\-2\}\\end\{bmatrix\},whereIn−2I\_\{n\-2\}denotes the identity matrix inn−2n\-2dimensions, has minimum entry1−ε1\-\\varepsilonand sparsityd=2d=2\. The eigenvalues ofBn,εB\_\{n,\\varepsilon\}are determined by its block components, so its minimum eigenvalue isε\\varepsilonand its maximum eigenvalue is2−ε2\-\\varepsilon; thus it hasλmin−1=1ε\\lambda\_\{\\min\}^\{\-1\}=\\frac\{1\}\{\\varepsilon\}\. By the same argument as above, for anyα<1\\alpha<1andd\>2d\>2, we may chooseM\>11−αM\>\\frac\{1\}\{1\-\\alpha\}andM\>NM\>N, and thenBn,1/MB\_\{n,1/M\}hasλmin−1\\lambda\_\{\\min\}^\{\-1\}at leastMMwhile havingα\\alphaedge strength anddd\-sparsity\. ∎