Matrix Chernoff scalar transform coefficient and tail functions
DefinitionTroppMatrixConcentration_ch5_chernoff_functionsDefine for , and by continuous extension. Define the lower-tail expression
and the upper-tail expression
when , using real powers. When , define both tail expressions to be . The theorem statements restrict the lower-tail deviation to and the upper-tail deviation to , so their bases are positive. They impose and positive dimension. At all permitted summands vanish, so the relevant non-strict relative tail events occur at zero. These scalar definitions introduce no probabilistic assumptions or conclusions.
import Definitions.Def_TroppMatrixConcentration_probability
import Mathlib.Analysis.SpecialFunctions.Pow.Real
noncomputable section
namespace TroppMatrixConcentration
def chernoffCgfCoefficient (L θ : ℝ) : ℝ :=
if L = 0 then θ else (Real.exp (θ * L) - 1) / L
def chernoffLowerTail (dimension : ℕ) (a L ε : ℝ) : ℝ :=
if L = 0 then (dimension : ℝ)
else (dimension : ℝ) * Real.rpow
(Real.exp (-ε) / Real.rpow (1 - ε) (1 - ε)) (a / L)
def chernoffUpperTail (dimension : ℕ) (a L ε : ℝ) : ℝ :=
if L = 0 then (dimension : ℝ)
else (dimension : ℝ) * Real.rpow
(Real.exp ε / Real.rpow (1 + ε) (1 + ε)) (a / L)
end TroppMatrixConcentration
Read-back
What the Lean code literally says, in plain math · gpt-6
chernoffCgfCoefficient. For arbitrary real numbers and , this defines a real number equal to if , and equal to if . There are no sign restrictions on either argument. In particular, the value is zero whenever , including when .
chernoffLowerTail. For any natural number (including zero) and any real numbers , this defines the real number if , and otherwise defines , with viewed as a real number. Here the total real power function is given by for , , for every nonzero real (including negative ), and for ; division by zero has value zero. No positivity assumptions on or , or interval restrictions on , are imposed. Thus the expression also covers , when the inner real power has a negative base and may have zero or negative value. If its value is zero and , the quotient supplied to the outer power is zero, so the result is when and zero when . At the inner power is , and, when , the result is . The value is zero for , and is whenever or , including in the branch.
chernoffUpperTail. For any natural number (including zero) and any real numbers , this defines the real number if , and otherwise defines , with viewed as a real number. Here the total real power function is given by for , , for every nonzero real (including negative ), and for ; division by zero has value zero. No positivity assumptions on or , or interval restrictions on , are imposed. Thus the expression also covers , when the inner real power has a negative base and may have zero or negative value. If its value is zero and , the quotient supplied to the outer power is zero, so the result is when and zero when . At the inner power is , and, when , the result is . The value is zero for , and is whenever or , including in the branch.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.