Documentation

RumorSpread.Bounds

Elementary inequalities for the rumor-spreading proof #

Deterministic real-arithmetic facts (Section 3 of latex/rumor_push.tex):

The point of this toolkit is that the whole O(log n) rumor-spreading proof never needs the exponential function.

theorem RumorPush.one_sub_mul_le_pow {x : ℝ} (hx : x ≤ 2) (m : ℕ) :
1 - ↑m * x ≤ (1 - x) ^ m

Bernoulli's inequality in the form 1 - m·x ≤ (1 - x) ^ m.

theorem RumorPush.mul_sub_sq_le_one_sub_pow {x : ℝ} (hx0 : 0 ≤ x) (hx1 : x ≤ 1) (m : ℕ) :
↑m * x - ↑m ^ 2 * x ^ 2 / 2 ≤ 1 - (1 - x) ^ m

Second-order (Bonferroni-type) lower bound: m·x - m²·x²/2 ≤ 1 - (1-x)^m for 0 ≤ x ≤ 1.

theorem RumorPush.half_mul_le_one_sub_pow {x : ℝ} (hx0 : 0 ≤ x) (hx1 : x ≤ 1) {m : ℕ} (hmx : ↑m * x ≤ 1) :
↑m * x / 2 ≤ 1 - (1 - x) ^ m

If m·x ≤ 1 (and 0 ≤ x ≤ 1) then m·x/2 ≤ 1 - (1-x)^m.

theorem RumorPush.pow_one_sub_le_one_div {x : ℝ} (hx0 : 0 ≤ x) (hx1 : x ≤ 1) (m : ℕ) :
(1 - x) ^ m ≤ 1 / (1 + ↑m * x)

(1-x)^m ≤ 1/(1 + m·x) for 0 ≤ x ≤ 1 (an e-free upper bound).

theorem RumorPush.one_sub_inv_le_log {x : ℝ} (hx : 0 < x) :
1 - 1 / x ≤ Real.log x

Lower bound on the logarithm: 1 - 1/x ≤ log x for 0 < x.