Lemma 4.20: concentration of the pinned log-likelihood
OpenZeroFreeRRG.Hardcore.lemma_4_20_pinned_concentrationFor every reveal rate s in [0,1] and b>0, the planted probability that the pinned log-likelihood exceeds its mean by bn is exponentially small in n along admissible indices.
Preamble
import Mathlib import Definitions.Def_ZeroFreeRRG_Hardcore_BetheFunctional import Definitions.Def_ZeroFreeRRG_Hardcore_Moments open scoped Classical open Filter MeasureTheory AFIsingKS ZeroFreeRRG.Hardcore
Formal statement
theorem ZeroFreeRRG.Hardcore.lemma_4_20_pinned_concentration (m : Model) (hm : m.Valid) (d : ℕ) (hd : 3 ≤ d) (t : ℝ) (ht : m.PosParam t) :
∀ s : ℝ, 0 ≤ s → s ≤ 1 → ∀ b : ℝ, 0 < b → ∃ c : ℝ, 0 < c ∧ ∃ N : ℕ, ∀ n ≥ N, Even (n * d) →
plantedPinnedE m t s d n (fun M σ U =>
if pinnedLL m t M σ U - plantedPinnedE m t s d n (fun M' σ' U' => pinnedLL m t M' σ' U')
> b * n then 1 else 0) ≤ Real.exp (-c * n) := by sorrySource
Chen–Wang–Zhang, Zero-Freeness for Random Regular Graphs up to the Replica Symmetry Breaking Threshold, https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/1461.pdf, p. 31, Lemma 4.20 and equation (29).