Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.3, p. 749 — P(S_n ≥ x) ≤ ΣP(X_i > y_i) + P₆ under (1.4); < … + P₄ under (1.6); < … + P₅ if also β ≥ tα/2 or βx ≥ μ(−∞, Y)

Proved
NagaevLD.FukNagaev.theorem_1_3

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

fuk-nagaev-inequalitylarge-deviationsp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1sums-of-independent-random-variables

The Fuk–Nagaev inequality. Let X1,…,XnX_1,\dots,X_nX1​,…,Xn​ be independent random variables with Fi(u)=P(Xi<u)F_i(u)=P(X_i<u)Fi​(u)=P(Xi​<u) and Sn=X1+⋯+XnS_n=X_1+\dots+X_nSn​=X1​+⋯+Xn​. Let x>0x>0x>0, let y1,…,yny_1,\dots,y_ny1​,…,yn​ be positive numbers and y≥max⁡iyiy\ge\max_iy_iy≥maxi​yi​. Write

μ(−∞,Y)=∑i=1n∫u≤yiu dFi(u),B2(−∞,Y)=∑i=1n∫u≤yiu2 dFi(u),A(t;0,Y)=∑i=1n∫0≤u≤yi∣u∣t dFi(u),\mu(-\infty,Y)=\sum_{i=1}^n\int_{u\le y_i}u\,dF_i(u),\quad B^2(-\infty,Y)=\sum_{i=1}^n\int_{u\le y_i}u^2\,dF_i(u),\quad A(t;0,Y)=\sum_{i=1}^n\int_{0\le u\le y_i}|u|^t\,dF_i(u),μ(−∞,Y)=i=1∑n​∫u≤yi​​udFi​(u),B2(−∞,Y)=i=1∑n​∫u≤yi​​u2dFi​(u),A(t;0,Y)=i=1∑n​∫0≤u≤yi​​∣u∣tdFi​(u),

and assume B2(−∞,Y)<∞B^2(-\infty,Y)<\inftyB2(−∞,Y)<∞. Suppose t≥2t\ge2t≥2, 0<α<10<\alpha<10<α<1 and β=1−α\beta=1-\alphaβ=1−α.

  1. If (1.4)  max⁡[t,log⁡(βxyt−1A(t;0,Y)+1)]≥αxyetB2(−∞,Y)\ \max\big[t,\log\big(\frac{\beta xy^{t-1}}{A(t;0,Y)}+1\big)\big]\ge\frac{\alpha xy}{e^tB^2(-\infty,Y)} max[t,log(A(t;0,Y)βxyt−1​+1)]≥etB2(−∞,Y)αxy​, then
P(Sn≥x)≤∑i=1nP(Xi>yi)+P6.P(S_n\ge x)\le\sum_{i=1}^nP(X_i>y_i)+P_6.P(Sn​≥x)≤i=1∑n​P(Xi​>yi​)+P6​.
  1. If (1.6)  max⁡[t,log⁡(βxyt−1A(t;0,Y)+1)]<αxyetB2(−∞,Y)\ \max\big[t,\log\big(\frac{\beta xy^{t-1}}{A(t;0,Y)}+1\big)\big]<\frac{\alpha xy}{e^tB^2(-\infty,Y)} max[t,log(A(t;0,Y)βxyt−1​+1)]<etB2(−∞,Y)αxy​, then
P(Sn≥x)<∑i=1nP(Xi>yi)+P4.P(S_n\ge x)<\sum_{i=1}^nP(X_i>y_i)+P_4.P(Sn​≥x)<i=1∑n​P(Xi​>yi​)+P4​.
  1. If (1.6) holds and at least one of β≥tα/2\beta\ge t\alpha/2β≥tα/2, βx≥μ(−∞,Y)\beta x\ge\mu(-\infty,Y)βx≥μ(−∞,Y) holds, then
P(Sn≥x)<∑i=1nP(Xi>yi)+P5.P(S_n\ge x)<\sum_{i=1}^nP(X_i>y_i)+P_5.P(Sn​≥x)<i=1∑n​P(Xi​>yi​)+P5​.

Here

P4=exp⁡{βxy−((1−α2)xy−μ(−∞,Y)y)log⁡(βxyt−1A(t;0,Y)+1)},P_4=\exp\Big\{\beta\frac xy-\Big(\big(1-\tfrac\alpha2\big)\frac xy-\frac{\mu(-\infty,Y)}y\Big)\log\Big(\frac{\beta xy^{t-1}}{A(t;0,Y)}+1\Big)\Big\},P4​=exp{βyx​−((1−2α​)yx​−yμ(−∞,Y)​)log(A(t;0,Y)βxyt−1​+1)}, P5=exp⁡{(β−tα2)xy−(βxy−μ(−∞,Y)y)log⁡(βxyt−1A(t;0,Y)+1)},P6=exp⁡{−αx(αx/2−μ(−∞,Y))etB2(−∞,Y)}.P_5=\exp\Big\{\Big(\beta-\frac{t\alpha}2\Big)\frac xy-\Big(\beta\frac xy-\frac{\mu(-\infty,Y)}y\Big)\log\Big(\frac{\beta xy^{t-1}}{A(t;0,Y)}+1\Big)\Big\},\quad P_6=\exp\Big\{-\frac{\alpha x(\alpha x/2-\mu(-\infty,Y))}{e^tB^2(-\infty,Y)}\Big\}.P5​=exp{(β−2tα​)yx​−(βyx​−yμ(−∞,Y)​)log(A(t;0,Y)βxyt−1​+1)},P6​=exp{−etB2(−∞,Y)αx(αx/2−μ(−∞,Y))​}.

The inequality bounds the upper tail of a sum of independent summands by a "large single summand" term ∑iP(Xi>yi)\sum_iP(X_i>y_i)∑i​P(Xi​>yi​) plus an exponential term in truncated moments, with no assumption beyond finiteness of the truncated moments. Its corollaries (1.23) and (1.24) are the familiar Fuk–Nagaev bound P(Sn≥x)≤ct(1)At+x−t+exp⁡{−ct(2)x2/Bn2}P(S_n\ge x)\le c_t^{(1)}A_t^+x^{-t}+\exp\{-c_t^{(2)}x^2/B_n^2\}P(Sn​≥x)≤ct(1)​At+​x−t+exp{−ct(2)​x2/Bn2​} for centred summands.

Formalization Note

  1. Part 3 is printed "If, instead of (1.6), at least one of the conditions … is fulfilled"; the proof (p. 752) establishes it "if, in addition" to (1.6), and under (1.4) only gives P6P_6P6​. The statement follows the proof.
  2. On the page A(t;0,Y)=0A(t;0,Y)=0A(t;0,Y)=0 makes the logarithm +∞+\infty+∞, so (1.4) holds. Lean's division by zero would give the logarithm 000; condition (1.4) is therefore cond_1_4, which contains the disjunct A(t;0,Y)=0A(t;0,Y)=0A(t;0,Y)=0, and (1.6) is cond_1_6, which contains A(t;0,Y)>0A(t;0,Y)>0A(t;0,Y)>0. If B2(−∞,Y)=0B^2(-\infty,Y)=0B2(−∞,Y)=0, P6 takes the page's limiting value 000 (exp⁡{−∞}\exp\{-\infty\}exp{−∞}), not Lean's exp⁡(⋅/0)=1\exp(\cdot/0)=1exp(⋅/0)=1.
  3. B2(−∞,Y)<∞B^2(-\infty,Y)<\inftyB2(−∞,Y)<∞ is assumed as integrability of Xi2X_i^2Xi2​ on {Xi≤yi}\{X_i\le y_i\}{Xi​≤yi​} for each iii: on the page an infinite B2(−∞,Y)B^2(-\infty,Y)B2(−∞,Y) makes the bound trivial, while Lean would replace it by 000 and the statement would become false.
  4. y>0y>0y>0 is stated explicitly (it follows from y≥yi>0y\ge y_i>0y≥yi​>0 when n≥1n\ge1n≥1). Indices run over Fin n. Integrals against dFidF_idFi​ are expectations over the corresponding events.
Preamble
import Mathlib
import Definitions.Def_NagaevLD_FukNagaev_Setting
Formal statement
namespace NagaevLD.FukNagaev

open MeasureTheory ProbabilityTheory

theorem theorem_1_3 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) [IsProbabilityMeasure P]
    {n : ℕ} (X : Fin n → Ω → ℝ) (hmeas : ∀ i, Measurable (X i)) (hindep : iIndepFun X P)
    (x : ℝ) (hx : 0 < x) (yv : Fin n → ℝ) (hyv : ∀ i, 0 < yv i)
    (y : ℝ) (hy0 : 0 < y) (hyy : ∀ i, yv i ≤ y)
    (t : ℝ) (ht : 2 ≤ t)
    (α β : ℝ) (hα0 : 0 < α) (hα1 : α < 1) (hβ : β = 1 - α)
    (hL2 : ∀ i, IntegrableOn (fun ω => X i ω ^ 2) {ω | X i ω ≤ yv i} P) :
    (cond_1_4 t α β x y (B2Y P X yv) (AY P X yv t) →
        P.real {ω | x ≤ S n X ω} ≤
          ∑ i, P.real {ω | yv i < X i ω} + P6 t α x (muY P X yv) (B2Y P X yv)) ∧
      (cond_1_6 t α β x y (B2Y P X yv) (AY P X yv t) →
        P.real {ω | x ≤ S n X ω} <
          ∑ i, P.real {ω | yv i < X i ω} + P4 t α β x y (muY P X yv) (AY P X yv t)) ∧
      (cond_1_6 t α β x y (B2Y P X yv) (AY P X yv t) →
        (β ≥ t * α / 2 ∨ β * x ≥ muY P X yv) →
        P.real {ω | x ≤ S n X ω} <
          ∑ i, P.real {ω | yv i < X i ω} + P5 t α β x y (muY P X yv) (AY P X yv t)) := by sorry

end NagaevLD.FukNagaev
Source
Nagaev, Large deviations of sums of independent random variables, Ann. Probab. 7 (1979), p. 749, Theorem 1.3, (1.4)–(1.7a); P₄, P₅, P₆ defined on p. 748
Human review
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me