scalar_centered_sampling_markov_tail_from_qmoment_bound
ProvedMarkov's inequality on the finite Bernoulli observation measure. Fix entry dimensions and an inclusion probability , giving the product Bernoulli measure on subsets of the matrix entries (each entry included independently with probability ). Let be any real-valued statistic of the observation set, let be an integer, a threshold, and . If the -th absolute moment is controlled,
then stays within the threshold with high probability:
This is the standard -th moment Markov bound, here proved directly on the explicit powerset-sum Bernoulli measure: the weights are nonnegative and sum to (binomial theorem), and on the bad event one has , so . It is the reusable concentration core for the scalar centered-sampling Bernstein tails (the analogue, for the scalar statistic of a centered sampling fluctuation, of the proved spectral-norm Markov tail).
import Definitions.Def_matrix_completion_neumann open MatrixCompletion open scoped BigOperators Classical
theorem scalar_centered_sampling_markov_tail_from_qmoment_bound {n₁ n₂ : ℕ} (p : ℝ) (hp0 : 0 ≤ p) (hp1 : p ≤ 1) (Z : Finset (Fin n₁ × Fin n₂) → ℝ) (q : ℕ) (hq : 1 ≤ q) (t failProb : ℝ) (ht : 0 < t) (hfail : 0 ≤ failProb) (hmoment : bernoulliExpectation p (fun Omega => |Z Omega| ^ q) ≤ t ^ q * failProb) : bernoulliEventProb p (fun Omega => |Z Omega| ≤ t) ≥ 1 - failProb := by sorry