Integer-threshold Markov bound for arbitrary finite nonnegative weights
ProvedNarrowDNF.Weighted.integer_markovcombinatoricsnarrow-dnf-authors-importprobabilitystoc-2027
Let be finite, let , let , and let . Then
The weights need not sum to one. The denominator is , rather than , because an integer strictly exceeding is at least . In the DNF construction this converts an expected active-set size into a tail bound at an integer certificate-width cutoff.
Preamble
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Algebra.Order.BigOperators.Group.Finset
import Mathlib.Data.Real.Basic
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Positivity
import Mathlib.Tactic.Ring
namespace NarrowDNF
end NarrowDNF
namespace NarrowDNF.Weighted
end NarrowDNF.Weighted
open NarrowDNF
open NarrowDNF
open NarrowDNF.Weighted
open scoped BigOperators
variable {α : Type*} [Fintype α]
Formal statement
theorem NarrowDNF.Weighted.integer_markov (weights : α → ℝ) (hw : ∀ x, 0 ≤ weights x)
(size : α → ℕ) (cutoff : ℕ) :
(∑ x, weights x * (if cutoff < size x then 1 else 0)) ≤
(∑ x, weights x * (size x : ℝ)) / (cutoff + 1 : ℝ) := by sorrySource