AR - 16 - Ricerca Decentralizzata II

Iniziamo calcolando la costante di normalizzazione \(z_u\) nel caso in cui \(q=1\). Dalla definizione sappiamo che

\[z_u = \sum_{v \in V - \{u\}} \frac{1}{d(u, v)}\]

dato che ci troviamo in un anello poi, assumendo di avere un numero pari di nodi \(n\), notiamo che abbiamo \(2\) nodi a distanza \(1\) da \(u\), \(2\) nodi a distanza \(2\), \(2\) nodi a distanza \(3\), e così via, fino a \(n/2\).

\[z_u \leq 2 \cdot \bigg(1 + \frac12 + \frac13 + \frac14 + ... + \frac{1}{n/2}\bigg)\]

A questo punto utilizziamo una argomentazione molto tipica, che ci dice che

\[1 + \frac12 + \frac13 + \frac14 + ... + \frac1k \leq 1 + \int_1^k \frac1x dx = 1 + \ln{k}\]

Utilizzando il bound appena descritto e notando che \(\ln x \leq \log_2 x\), otteniamo la seguente relazione

\[\begin{split} z_u &\leq 2 \cdot \sum_{i = 1}^{n/2} \frac1i \\ &\leq 2 \cdot \int_1^{n/2} \frac1x dx \\ &\leq 2 \cdot (1 + \ln{(n/2)}) \\ &\leq 2 \cdot (1 + \log_2{(n/2)}) \\ &= 2 + 2 \cdot \log_2(n) - 2 \cdot log_2(2) \\ &= 2 \cdot log_2(n) \end{split}\]

Trovata la costante \(z_u\), siamo adesso in grado di dare il seguente lower bound alla probabilità che ci sia un arco debole tra \(u\) e \(v\)

\[P[(u, v) \in E] \geq \frac{1}{2 \log_2(n)} \cdot \frac{1}{d(u, v)}\]

---

A questo punto definiamo la seguente v.a.

\[X := \text{ lunghezza del percorso da } s \text{ a } t \text{ trovato dalla ricerca miope}\]

Vale quindi il seguente teorema

Teorema: \(\mathbb{E}[X] \leq 3 \cdot \log^2{n}\)

Dimostrazione: Per formalizzare il concetto di scala di risoluzione discusso nella lezione precedente, dividiamo il processo in fasi. In particolare diciamo che il processo si trova nella fase \(j\) quando il nodo corrente che ha il messaggio è il nodo \(v \in V\) la cui distanza dal destinatario \(t\) è compresa tra \(2^j\) e \(2^{j+1}\).

Notiamo inoltre che se il processo entra nella fase \(j\), non potrà più ritornare alla fase \(i\), con \(j < i\). Questo segue dal fatto che la ricerca miope che stiamo effettuando è una ricerca greedy, nel senso che non ci fa mai allontanare dalla destinazione \(t \in V\). Inoltre, dato che da una fase alla successiva dimezziamo la distanza dal target, possiamo limitare il numero delle fasi nel seguente modo

\[\text{numero fasi ricerca miope} \leq \log\Big(\frac{n}2\Big) \leq \log n\]

Al fine di calcolare il numero di steps totali un possibile approccio è considerare considerare il numero di steps effettuati in ogni fase e poi sommare tutto assieme. A tale fine definiamo le seguenti v.a.

\[X_j := \text{numero di passi percorsi nella fase } j = \text{numero di nodi raggiunti nella fase } j\]

e notiamo che

\[X = \sum\limits_{j = 0}^{\log{n}} X_j\]

dunque, dalla linearità della media, segue che

\[\mathbb{E}[X] = \sum\limits_{j = 0}^{\log{n}} \mathbb{E}[X_j]\]

Andiamo adesso a dimostrare che in media ciascuna fase dura approssimatamente \(\log n\) passi. In formula,

\[\mathbb{E}[X_j] = O(\log n)\]

---

Supponiamo quindi di essere nella fase \(j\) e di aver raggiunto il nodo \(v \in V\). Una condizione sufficiente per la terminazione della \(j\) -esima fase è quella di avere un arco \((v, z)\) tale che

\[d(z, t) \leq \frac{d(v, t)}{2}\]

Infatti, se questo è vero, allora otteniamo

\[d(z, t) \leq \frac{d(v, t)}{2} < d(v, t) \leq 2^j\]

e quindi il nodo \(z\) si trova fuori dalla fase \(j\).

---

Definiamo poi il seguente insieme di nodi

\[I := \Big\{u \in V: \,\,\, d(u, t) \leq \frac{d(v, t)}{2}\Big\}\]

e notiamo che possiamo dare il seguente lower bound al numero di nodi in \(I\)

\[\begin{split} \phantom{} |I| &= \lfloor \frac{d(v, t)}{2} \rfloor + \lfloor \frac{d(v, t)}{2} \rfloor + 1 \\ &\geq 2 \cdot \Big(\frac{d(v, t) - 1}{2}\Big) + 1 \\ &= d(v, t) \end{split}\]

Consideriamo adesso un nodo \(u \in I\). Notiamo che la distanza tra \(u\) e \(v\) può essere limitata da \(3/2 \cdot d(v, t)\). Infatti,

\[\begin{split} d(u, v) &\leq d(u, t) + d(t, v) \\ &\leq \frac{d(v, t)}{2} + d(v, t) \\ &= \frac32 \cdot d(v, t) \end{split}\]

---

Mettendo assieme tutti questi risultati, siamo in grado di dare un lower bound alla probabilità che dato un \(u \in I\), ci sia un weak tie tra \(u\) e \(v\).

\[\begin{split} P(u) := P[(u, v) \in E \,\, \land \,\, (u, v) \text{ è un weak tie} \,\, | \,\, u \in I] &= \frac{1}{z} \cdot \frac{1}{d(u, v)} \\ &\geq \frac{1}{z} \cdot \frac{1}{\frac32 d(v, t)} \\ &\geq \frac{1}{2 \log{n}} \cdot \frac{1}{\frac32 (v, t)} \\ &= \frac{1}{3 \cdot \log{n} \cdot d(v, t)} \\ \end{split}\]

Siamo adesso in grado di dare un lower bound alla probabilità che esiste un \(u \in I\) connesso a \(v\) tramite un weak tie.

\[\begin{split} P(\exists z \in V: (v, z) \in E \text{ è un weak tie } \land z \in I) &= \sum_{u \in I} P(u) \\ &\geq |I| \cdot P(u) \\ &\geq |I| \cdot \frac{1}{3 \log{n} \cdot d(v, t)} \\ &\geq d(v, t) \cdot \frac{1}{3 \log{n} \cdot d(v, t)} \\ &\geq \frac{1}{3\log{n}} \\ \end{split}\]

Notiamo che abbiamo appena fatto vedere come la probabilità di dimezzare la distanza dalla destinazione non dipende da quando distante mi trovo dalla destinazione. È dunque questo il risultato principale, che formalizza la discussione intuitiva nel caso della griglia svolta nella precedente lezione e che ci permette di ottenere una ricerca decentralizzata efficiente.

---

Ma allora, dato che l'evento preso in considerazione è una condizione sufficiente a uscire dalla fase \(j\), abbiamo che ad ogni step della fase \(j\), la probabilità di terminazione in quel particolare step è almeno

\[\begin{split} P(\text{fase } j \text{ termina}) &\geq P(\exists z \in V: (v, z) \in E \text{ è un weak tie } \land z \in I) \\ &\geq \frac{1}{3 \log{n}} \\ \end{split}\]

Dunque, otteniamo il seguente bound probabilistico rispetto alla durata della \(j\) -esima fase

\[P(X_j \geq i) \leq \Big(1 - \frac{1}{3 \log{n}}\Big)^{i-1}\]

---

Possiamo adesso calcolare il valore \(\mathbb{E}[X_j]\). Infatti, utilizzando la definizione di media, troviamo che

\[\mathbb{E}[X_j] = \sum\limits_{i = 1}^{n/2} i \cdot P(x_j = i)\]

notiamo però che noi sappiamo calcolare solo \(P(X_j \geq i\), e non \(P(X_j = i)\). Dato però che possiamo lavorare con la sommatoria, e non con i singoli termini, possiamo utilizzare il seguente trucchetto

\[\begin{split} \sum\limits_{i = 1}^{n/2} i \cdot P(X_j = i) &= 1 \cdot P(X_j = 1) + 2 \cdot P(X_j = 2) + 3 \cdot P(X_j = 3) + \ldots \\ &= P(X_j \geq 1) + P(X_j = 2) + 2 \cdot P(X_j = 3) + \ldots \\ &= P(X_j \geq 1) + P(X_j \geq 2) + P(X_j = 3) + \ldots \\ &= \ldots \\ &= P(X_j \geq 1) + P(X_j \geq 2) + \ldots + P(X_j \geq \frac{n}{2}) \\ &\leq \sum\limits_{i = 1}^{n/2}\Big(1 - \frac{1}{3\log{n}} \Big)^{i-1} \\ &< \sum\limits_{i = 0}^{+ \infty}\Big(1 - \frac{1}{3\log{n}} \Big)^{i} \\ &= \frac{1}{1 - (1 - \frac{1}{3 \log{n}})} \\ &= 3 \cdot \log{n} \end{split}\]

Per finire quindi, troviamo che la ricerca miope effettua, in media, il seguente numero di steps

\[\mathbb{E}[X] = \sum\limits_{j = 1}^{\log {n}} \mathbb{E}[X_j] \leq 3 \cdot \log^2{n}\]

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

Andiamo adesso a vedere cosa succede alla ricerca miope quando ci troviamo sull'anello e \(q \neq 1\).

• Caso \(q > 1\). In questo caso la probabilità di dimezzare la distanza utilizzando weak ties è molto bassa, in quanto più \(q\) aumenta e più i weak ties sono archi "corti". Infatti, assumendo che \(d(s, t) = n/2\), troviamo che

  \[P[(s, v) \in E \,\, | \,\, d(v, t) \leq \frac12 \cdot d(s, t)] \leq \frac{1}{z} \cdot \frac{1}{\Big(\frac{n}{4}\Big)^2} \approx \frac{1}{n^2}\]

  che è una probabilità molto bassa al crescere di \(n\).

• Caso \(q = 0\). In questo caso il valore atteso dei percorsi è \(O(\sqrt{n})\). Infatti, siano \(s, t\) due nodi, e definiamo il seguente insieme

  \[R := \{u \in V: \,\, d(u, t) \leq \sqrt{n} \}\]

  troviamo che

  \[P(s \in R) = \frac{2 \cdot \sqrt{n}}{n} \iff P(s \not \in R) = \underbrace{1 - \frac{2}{\sqrt{n}}}_{\text{alta probabilità}}\]

  Sia ora \(v \not \in R\). La probabilità di finire in un passo dentro ad \(R\) è data da

  \[P[\exists u \in R: \,\, (u, v) \in E] = \frac{|R|}{n} = \frac{2 \cdot \sqrt{n}}{n} = \frac{2}{\sqrt{n}}\]

  in quanto con \(q = 0\) ho che \(P[(u, v) \in E] = 1/n\). Notiamo che tale probabilità è molto bassa. Questo significa che solo per entrare dentro \(R\) in media dovrò attendere molti steps.

In generale è possibile dimostrare che nell'anello vale il seguente risultato

\[\forall q \neq 1: \,\, \exists C_q > 0: \,\, \mathbb{E}[X] \geq \alpha \cdot n^{C_q}\]