Elementary inequalities for the rumor-spreading proof #
Deterministic real-arithmetic facts (Section 3 of latex/rumor_push.tex):
one_sub_mul_le_pow: Bernoulli,1 - m·x ≤ (1-x)^m;mul_sub_sq_le_one_sub_pow: second-order lower boundm·x - m²·x²/2 ≤ 1 - (1-x)^m;half_mul_le_one_sub_pow:m·x/2 ≤ 1 - (1-x)^mwhenm·x ≤ 1;pow_one_sub_le_one_div:(1-x)^m ≤ 1/(1 + m·x);one_sub_inv_le_log:1 - 1/x ≤ log x.
The point of this toolkit is that the whole O(log n) rumor-spreading proof
never needs the exponential function.