Elementary tail bounds #
Probability facts that several model packages used to prove locally, stated once for the
shared finite layer (monotonicity of probability in the event is Distribution.prob_mono).
avg_lt_one: an observable bounded by1that is strictly below1somewhere has average strictly below1(the uniform case ofDistribution.expect_lt_one, which is inDistribution).avg_markov: Markov's inequalityP(X ā„ c) ⤠š¼X / cfor uniform averages (for any distribution it isDistribution.prob_le_expect_div), andavg_markov_one: its formP(X ā„ 1) ⤠š¼Xfor a sum of independent nonnegative coordinates.Kernel.one_sub_avg_le_prob_ofStep: one uniformly random round lands in an event with probability at least1 - š¼[bad], whenbad ā„ 0charges every miss at least1.Kernel.iterate_monotone: a subharmonic observable (f ⤠K f) has nondecreasing finite-time expectations, andKernel.event_monotone: the occupation probability of an absorbing event is nondecreasing in time.exp_neg_two_log,exp_neg_three_log,one_le_of_log_pos: the scalar conversions used to state high-probability bounds in regimesC ⤠log n.
As everywhere in this library, the source has no paper numbering; each docstring names the package lemmas that the statement replaces.
Uniform averages: strict bound and Markov's inequality #
The uniform case of Distribution.expect_lt_one: on a nonempty type, an observable
bounded by 1 and strictly below 1 somewhere has average strictly below 1.
(The statement of Undecided.avg_lt_one.)
Markov's inequality for a sum of independent nonnegative coordinates:
P(X ā„ 1) ⤠š¼X for X = āįµ¢ Yįµ¢(Ļįµ¢), Ļ : Fin n ā γ uniform. Replaces
Plurality.markov_one (plurality blueprint lem:tails) and the Markov steps proved inline
in Median.falses_tail_markov and ThreeMajority.saturation_stage2c.
One random round, and absorbing events #
One round lands in an event with probability at least 1 - š¼[bad], whenever the
nonnegative charge bad is at least 1 on every round that misses the event (Markov's
inequality for the complement). Replaces Median.prob_step_ge and
Plurality.le_prob_step.
An observable with f ⤠K f (subharmonic) has nondecreasing finite-time expectations:
the counterpart of iterate_antitone. It is the induction behind Voter.colorProbability_mono
and the former Median.event_absorb_mono.
The occupation probability of an absorbing event is nondecreasing in time: if every
state of P stays in P with probability one, then n ⦠P(Xā ā P) is monotone.
Replaces Median.event_absorb_mono.
Scalar facts for high-probability statements #
exp (-2 log n) = 1/n², the conversion of a tail bound exp (-c) with c ℠2 log n
into a failure probability 1/n². Replaces Plurality.exp_neg_two_log and
Median.exp_neg_two_log.
A hypothesis 0 < log n, as implied by the regimes C ⤠log n with C > 0, forces
1 ⤠n. Replaces Plurality.one_le_of_log_pos and Median.one_le_of_log_pos.