Corollaries 3.10, 3.11 and 3.12 #
Three choices of λ in Theorem 3.8 (theorem_3_8_bigO).
- Corollary 3.10 (
corollary_3_10):λ = min {2k, (n / log n)^{1/3}}. No hypothesis on the plurality size is needed: ifλ = 2kthenc_m ≥ n/kby pigeonhole, and otherwise the bias hypothesis alone forcesc_m ≥ s(c) ≥ n/λ. This is the paper's headline boundO(min {k, (n / log n)^{1/3}} log n). - Corollary 3.11 (
corollary_3_11):λ = log^ℓ nforℓ ≥ 1, givingO(log^{ℓ+1} n)rounds. - Corollary 3.12 (
corollary_3_12): a constantλ = β ≥ 3, givingO(log n)rounds.
Corollary 3.10. Let log n ≥ 40 and k ≥ 2, and write
λ = min {2k, (n / log n)^{1/3}}. If m is the unique plurality color and
s(c) ≥ 22 √(λ n log n), then after at most 130 λ log n rounds all nodes
support m with probability at least 1 - 143 λ log n / n.
Corollary 3.11. Let log n ≥ 40, k ≥ 2 and ℓ ≥ 1. If m is the
unique plurality color, c_m ≥ n / log^ℓ n and s(c) ≥ 22 √(n log^{ℓ+1} n),
then after at most 130 log^{ℓ+1} n rounds all nodes support m with
probability at least 1 - 143 log^{ℓ+1} n / n.
Corollary 3.12. Let log n ≥ 40, k ≥ 2 and β ≥ 3. If m is the
unique plurality color, c_m ≥ n/β and s(c) ≥ 22 √(β n log n), then after at
most 130 β log n rounds all nodes support m with probability at least
1 - 143 β log n / n. For a constant β this is O(log n) rounds.
Two opinions from a vanishing bias #
3-Majority with two opinions from a vanishing bias (the k = 2, λ = 3 case of
theorem_3_8_bigO, transferred to the binary process ThreeMajority.run through
colorSet_run): if the nodes of I₀ outnumber the others by at least 22 √(3 n log n)
(a fraction 1/2 + O(√(log n / n))) and log n ≥ 40, then after O(log n) rounds, at most
390 log n, every node holds the opinion of I₀ with probability at least
1 - 429 log n / n.