ADRC - 11 - Majority Consensus II

Notiamo che la funzione \(f(a) = a^2 \cdot (3n - 2a)\) è una funzione crescente per ogni \(0 < a < n\). Da questo segue che, per \(a \leq n/2 - s\) otteniamo

\[\begin{split} \mathbb{E}[X_{t+1} \,\,|\,\, X_t = a] &= \Big(\frac{a}{n}\Big)^2 \cdot (3n - 2a) \\ &\leq a^2 \cdot (3n - 2a) \\ &\leq \Big(\frac{n}{2} - s\Big)^2 \cdot \Big(3n - 2 \cdot \Big(\frac{n}{2} - s\Big)\Big) \\ &= \Big(\frac{n^2}{4} - ns + s^2\Big) \cdot (2n + 2s) \\ &= \frac{n^3}{2} - \frac32 n^2 s + 2 s^3 \\ &= \frac{n}{2} - \frac32 s + s \cdot \Big( 2 \cdot \frac{s^2}{n^2}\Big) \\ &\leq \frac{n}{2} - \frac{5}{4} s \\ \end{split}\]

dove l'ultimo passaggio segue dal fatto che dire \(s \leq n/4\) è equivalente a dire \(2 \cdot s^2/n^2 \leq 1/8\), e dato che \(11/8 > 5/4\) otteniamo

\[\begin{split} \frac{n}{2} - \frac32 s + s \cdot \Big(2 \cdot \frac{s^2}{n^2} \Big) &\leq \frac{n}{2} - \frac32 s + \frac18 s \\ &\leq \frac{n}{2} - \frac{11}{8} s \\ &\leq \frac{n}{2} - \frac{5}{4} s \\ \end{split}\]

Ora, per ottenere un risultato di concentrazione l'idea è quella di utilizzare il seguente chernoff bound.

---

Chernoff Bound: Siano \(X_1, ..., X_n\) v.a. indipendenti e a valori in \(\{0, 1\}\). Consideriamo \(X := \sum_{i = 1}^n X_i\) e \(\mu = \mathbb{E}[X]\). Allora, per ogni \(0 \leq \lambda \leq \mu\), vale

\[Pr[X \geq u + \lambda] \leq e^{\displaystyle{\frac{-2 \lambda^2}{n}}}\]

---

Nel nostro caso particolare possiamo applicare il bound con \(\mu = \mathbb{E}[X_{t+1}] = n/2 - 5/4 s\) e \(\lambda = 1/8 s\) per ottenere

\[\begin{split} Pr[X_{t+1} \geq \Big( \frac{n}{2} - \frac54 s \Big) + \frac18 s \,\,|\,\, X_t = a] &= Pr[X_{t+1} \geq \frac{n}{2} - \frac98 s \,\,|\,\, X_t = a] \\ &\leq e^{-\frac{2 s^2}{64n}} \\ &= e^{-\frac{s^2}{32n}} \\ \end{split}\]

Dato che abbiamo assunto che \(s \geq c \cdot \sqrt{n \log n}\) per qualche costante \(c \in \mathbb{N}\), ne segue che

\[Pr[X_{t+1} \geq \frac{n}{2} - \frac98 s \,\,|\,\, X_t = a] \leq \frac{1}{n^{\theta(1)}}\]

e quindi otteniamo \(X_{t+1} \leq n/2 - 9/8 s\) con alta probabilità.

\[\tag*{$\checkmark$}\]

---

Facendo il punto della situazione, abbiamo appena dimostrato che finchè il bias è conteunto nell'intervallo \(c \cdot \sqrt{n \log n} \leq s \leq n/4\), il bias incrementa in modo esponenziale con alta probabilità. Infatti, se \(a_{t+1} \leq n/2 - 9/8 s_t\), allora

\[s_{t+1} = \frac{n}{2} - a_{t+1} \geq \frac{n}{2} - \frac{n}{2} + \frac98 s_t = \frac98 s_t\]

e quindi

\[s_{t+1} \geq \Big(\frac{9}{8}\Big)^{t+1} \cdot s_0 = \Big(\frac{9}{8}\Big)^{t+1} \cdot c \sqrt{n \log n}\]

Andiamo adesso a dimostrare che questo implica che in \(O(\log n)\) passi la prima fase termina.

Iniziamo definendo il seguente evento

\[\xi_t := X_t \leq \max \Big\{\frac{n}{4} \,\,,\,\, \frac{n}{2} - \Big(\frac{9}{8}\Big)^t \Big\}\]

notiamo che

\[Pr[\xi_{t+1} \,\,|\,\, \bigcap_{i = 1}^t \xi_i] = 1 - n^{-\alpha}\]

per qualche costante \(\alpha\). Infatti, assumendo che \(n/2 - (9/8)^2 \geq n/4\), se vale \(\xi_t\) allora otteniamo con alta probabilità

\[\begin{split} X_{t+1} &\leq \frac{n}{2} - \frac98 s \\ &= \frac{n}{2} - \frac98 \cdot \Big(\frac{n}{2} - X_t \Big) \\ &\leq \frac{n}{2} - \frac98 \cdot \frac{n}{2} + \frac98 X_t \\ &\leq \frac{n}{2} - \frac98 \cdot \frac{n}{2} + \frac98 \cdot \Big(\frac{n}{2} - \Big(\frac{9}{8}\Big)^t \Big) \\ &= \frac{n}{2} - \Big(\frac{9}{8} \Big)^{t+1} \end{split}\]

che è proprio l'evento \(\xi_{t+1}\).

Continuando, siamo adesso in grado di calcolare la probabilità che in \(T = \frac{\log(n/4)}{\log(9/8)}\) passi si ha \(X_t \leq n/4\) in modo da passare alla fase successiva. Tale probabilità è così maggiorata

\[\begin{split} Pr[ \exists t \in [0, T]: \,\, X_t \leq n/4] &\geq Pr\Big[\bigcap_{i = 1}^T \xi_i\Big] \\ &= \prod_{i = 1}^T Pr\Big[\xi_i \,\,|\,\, \bigcap_{j = 1}^{i-1} \xi_j\Big] \\ &\geq (1 - n^{-\alpha})^T \\ &\geq 1 - 2Tn^{-\alpha} \\ &\geq 1 - n^{-\alpha/2} \\ \end{split}\]

quindi con alta probabilità in \(O(\log n)\) passi si supera la prima fase.

\[\tag*{$\checkmark$}\]

Dal comportamento in media della dinamica otteniamo quindi

\[\mathbb{E}[X_{t+1} \,\,|\,\, X_t = a] = \Big(\frac{a}{n}\Big)^2 \cdot (3n - 2a) \leq a \cdot \frac{\frac{n}{4}}{n^2} \cdot 3n \leq \frac34 a\]

per ottenere un risultato di concentrazione, applichiamo il seguente chernoff bound.

---

Chernoff Bound: Siano \(X_1, ..., X_n\) v.a. indipendenti a valori in \(0, 1\) e consideriamo \(X := \sum_i X_i\), e \(\mathbb{E}[X] \leq \mu\). Allora, per ogni \(0 < \delta < 1\), valgono

• \(Pr[X \geq (1 + \delta) \mu] \leq Exp(-\frac{\mu \delta^2}{3})\)

• \(Pr[X \leq (1 - \delta) \mu] \leq Exp(-\frac{\mu \delta^2}{2})\)

---

Nel nostro caso, ponendo \(u = 3/4 a\) e \(\delta = 1/20\), troviamo

\[Pr[X_{t+1} \geq \frac{4}{5} a] \leq Pr[X_{t+1} \geq \Big(1 + \frac{1}{20} \Big) \cdot \frac34 a] \leq Exp\Big(\frac{-\frac34 a (\frac{1}{20})^2}{3}\Big) = Exp(-\alpha \cdot a)\]

Quindi, finché \(a = \Omega(\log n)\) abbiamo che \(X_{t+1} \leq 4/5 a\) con alta probabilità, e quindi che il numero dei rossi decresce in modo esponenziale.

\[\tag*{$\checkmark$}\]

---

Dimostriamo adesso che anche questa seconda fase ha una durata di tempo logaritmica.

Iniziamo notando che se fino al round \(t\) della seconda fase c'è stata una decrescità esponenziale, allora questa decrescita continua con alta probabilità anche al round \(t+1\) in quanto

\[X_{t+1} \leq \frac{4}{5} \cdot X_t \leq \frac{4}{5} \cdot \Big(\frac45 \Big)^t \cdot \frac{n}{4} = \Big(\frac45\Big)^{t+1} \cdot \frac{n}{4}\]

Ma allora la probabilità di terminare la seconda fase è maggiorata dalla probabilità di avere \(T\) round continui di decrescità esponenziale, con \(T\) tale che

\[X_t \leq \Big(\frac{3}{4}\Big)^T \frac{n}{4} \leq c \cdot \log n \implies T = \frac{\log\Big({\frac{4 c \log n}{n}}\Big)}{\log{\frac34}}\]

Dato che questo avviene con alta probabilità, possiamo concludere che con alta probabilità in \(O(\log n)\) passi la seconda fase termina.

\[\tag*{$\checkmark$}\]

---