Lower bounds for rumor spreading: generic tools (EPI-8, lower bounds) #
Doerr and Kostrygin, Randomized rumor spreading revisited (ICALP 2017; long version
arXiv:2303.11150), lower bounds of Theorems 51, 52 and 53. The paper derives them from its
general lower bounds (Theorems 27, 38 and 48), joined through Lemma 20, which needs a major
correction (see Lemma20). The lower bounds here follow a direct route instead, made of three
generic tools.
reach_le_of_expect_card_le(first moment): if one round multiplies the expected number of informed nodes by at mostμ, then at leastmnodes are informed aftertrounds with probability at mostμ^t |S| / m. This replaces Theorem 27 (lower exponential growth).reach_add_le(Markov property at a fixed time): the probability of having informedmnodes afters + trounds is at most the probability of having informedm'nodes aftersrounds plus a bound on the probability of informingmnodes introunds from any state with fewer thanm'informed nodes. Splitting at a fixed time, not at the hitting time ofm', avoids any overshoot estimate such as Lemma 20.envelope_le(deterministic lower envelope): if in one round an observableVfalls belowf v(from a state withV ≥ v) with probability at mostδ v, then aftertrounds it is belowf^[t] vwith probability at most∑_{i < t} δ (f^[i] v). This is the round-by-round form of the phase arguments of Theorems 38 and 48 (Lemmas 42 and 50).envelope_seq_leis the same with an explicit target sequenceg iin place of the iteratesf^[i] v.
Throughout, 1 - P.notYet m t S is the probability that at least m nodes are informed after
t rounds started from S, that is, P[T(|S|, m) ≤ t].
Deterministic lower envelopes #
Deterministic lower envelope. Suppose that from every state a with v ≤ V a, the
observable V falls below f v in one round with probability at most δ v ≥ 0. Then, started
from a with v ≤ V a, it is below f^[t] v after t rounds with probability at most
∑_{i < t} δ (f^[i] v). (The round-by-round form of the leapfrog arguments of Lemmas 42 and 50
of the paper.)
Lower envelope along a target sequence. Suppose that, for every i, from every state
a with g i ≤ V a the observable V falls below g (i + 1) in one round with probability
at most δ i ≥ 0. Then, started from a with g 0 ≤ V a, it is below g t after t rounds
with probability at most ∑_{i < t} δ i. (The form of envelope_le with explicit targets, as
the phase sequences u_j and ε_j of Lemmas 40 and 49.)
Reaching m informed nodes #
1 - P[T(|S|, m) > t] is the expectation after t rounds of the indicator of having at
least m informed nodes.
Growth lower bound by the first moment (replaces Theorem 27 for the instances): if one
round multiplies the expected number of informed nodes by at most μ, then at least m > 0
nodes are informed after t rounds with probability at most μ^t |S| / m.
If every uninformed node is informed with probability at most c |S| / n, the expected
number of informed nodes after one round is at most (1 + c) |S|.
Markov property at a fixed time, lower-bound form. If from every state with fewer than
m' informed nodes at least m nodes are informed after t rounds with probability at most
B, then from S at least m nodes are informed after s + t rounds with probability at most
P[at least m' informed after s rounds] + B.