Documentation

Epidemics.Revisited.LowerGeneric

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.

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 #

theorem Epidemics.Revisited.envelope_le {α : Type u_1} [Fintype α] (K : Dynamics.Kernel α) (V : α → ℝ) (f δ : ℝ → ℝ) (hδ : ∀ (v : ℝ), 0 ≤ δ v) (h : ∀ (a : α), ∀ v ≤ V a, ((K a).prob fun (b : α) => V b < f v) ≤ δ v) (t : ℕ) (a : α) (v : ℝ) (hv : v ≤ V a) :
K.event (fun (b : α) => V b < f^[t] v) t a ≤ ∑ i ∈ Finset.range t, δ (f^[i] v)

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.)

theorem Epidemics.Revisited.envelope_seq_le {α : Type u_1} [Fintype α] (K : Dynamics.Kernel α) (V : α → ℝ) (g δ : ℕ → ℝ) (hδ : ∀ (i : ℕ), 0 ≤ δ i) (h : ∀ (i : ℕ) (a : α), g i ≤ V a → ((K a).prob fun (b : α) => V b < g (i + 1)) ≤ δ i) (t : ℕ) (a : α) (ha : g 0 ≤ V a) :
K.event (fun (b : α) => V b < g t) t a ≤ ∑ i ∈ Finset.range t, δ i

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 #

theorem Epidemics.Revisited.one_sub_notYet_eq {n : ℕ} (P : RumorProcess n) (m : ℝ) (t : ℕ) (S : Finset (Fin n)) :
1 - P.notYet m t S = P.K.iterate t (fun (T : Finset (Fin n)) => 1 - below m T) S

1 - P[T(|S|, m) > t] is the expectation after t rounds of the indicator of having at least m informed nodes.

theorem Epidemics.Revisited.iterate_card_le {n : ℕ} (P : RumorProcess n) {μ : ℝ} (hμ : 0 ≤ μ) (h : ∀ (S : Finset (Fin n)), ((P.K S).expect fun (T : Finset (Fin n)) => ↑T.card) ≤ μ * ↑S.card) (t : ℕ) (S : Finset (Fin n)) :
P.K.iterate t (fun (T : Finset (Fin n)) => ↑T.card) S ≤ μ ^ t * ↑S.card
theorem Epidemics.Revisited.reach_le_of_expect_card_le {n : ℕ} (P : RumorProcess n) {μ : ℝ} (hμ : 0 ≤ μ) (h : ∀ (S : Finset (Fin n)), ((P.K S).expect fun (T : Finset (Fin n)) => ↑T.card) ≤ μ * ↑S.card) {m : ℝ} (hm : 0 < m) (t : ℕ) (S : Finset (Fin n)) :
1 - P.notYet m t S ≤ μ ^ t * ↑S.card / m

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.

theorem Epidemics.Revisited.expect_card_le_of_informProb_le {n : ℕ} (P : RumorProcess n) (S : Finset (Fin n)) {c : ℝ} (hc : 0 ≤ c) (h : ∀ x ∉ S, P.informProb S x ≤ c * (↑S.card / ↑n)) :
((P.K S).expect fun (T : Finset (Fin n)) => ↑T.card) ≤ (1 + c) * ↑S.card

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|.

theorem Epidemics.Revisited.one_sub_one_sub_inv_pow_le {n : ℕ} (hn : 0 < n) (k : ℕ) :
1 - (1 - 1 / ↑n) ^ k ≤ ↑k / ↑n

Bernoulli's inequality in the form used for push: 1 - (1 - 1/n)^k ≤ k / n.

theorem Epidemics.Revisited.reach_add_le {n : ℕ} (P : RumorProcess n) {m m' B : ℝ} (hB : 0 ≤ B) (s t : ℕ) (hT : ∀ (T : Finset (Fin n)), ↑T.card < m' → 1 - P.notYet m t T ≤ B) (S : Finset (Fin n)) :
1 - P.notYet m (s + t) S ≤ 1 - P.notYet m' s S + B

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.