Esercizio - Passeggiata aleatoria su un grafo con triangolo e coda - stazionaria, raggiungimento e copertura

Teoria: Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafiPasseggiata sulla retta con barriere (rovina del giocatore): da i con N come traguardo, P(vittoria)=i/N e durata attesa i(N-i) se il gioco è equo; con p diverso da 1/2, P=(1-r^i)/(1-r^N), r=q/p. Il 2-SAT si risolve con una passeggiata randomizzata (flip di una variabile di una clausola violata): E[T] ≤ n^2 passi, quindi 2n^2 passi bastano con errore ≤ 1/2 (3-SAT: deriva contraria, esponenziale). Sul grafo la passeggiata ha π_v=d(v)/2m, tempo di ritorno 2m/d(v), tempo di copertura < 4m(n-1), da cui la connettività s-t in spazio logaritmico; PageRank è la stazionaria di una passeggiata con teletrasporto.Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafi →; grafi in Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →.

Testo. Il grafo $G$ ha vertici $1,\dots,5$ e archi $\{1,2\},\{1,3\},\{2,3\},\{3,4\},\{4,5\}$ (un triangolo con una coda di due archi attaccata al vertice $3$). Una passeggiata aleatoria sta in un vertice e passa a un vicino scelto uniformemente.

1. Calcolare la distribuzione stazionaria e i tempi medi di ritorno. La passeggiata converge a $\pi$ da qualunque vertice?
2. Calcolare i tempi medi $H_{i5}$ di raggiungimento di $5$ da $i=1,2,3,4$ e i tempi $H_{i1}$ per raggiungere $1$.
3. Verificare l'identità del tempo di pendolarismo $H_{15}+H_{51}=2m\,R_{15}$ ($R$ resistenza efficace con archi da $1\,\Omega$).
4. Calcolare il tempo di copertura da ciascun vertice e confrontarlo con il limite $4m(n-1)$ della teoria.
5. Per un grafo con $n=1000$ vertici, quanti passi e quanti bit usa l'algoritmo di connettività s-t?

Soluzione

1. I gradi sono $d=(2,2,3,2,1)$ e $m=5$ ($\sum d=10=2m$). Quindi $\pi_v=d(v)/10$: $$\pi=(0{,}2;\ 0{,}2;\ 0{,}3;\ 0{,}2;\ 0{,}1),\qquad h_{vv}=\frac{10}{d(v)}=(5,\ 5,\ \tfrac{10}3,\ 5,\ 10).$$ Il grafo contiene il triangolo (ciclo di lunghezza $3$, dispari), quindi non è bipartito e la passeggiata è aperiodica: converge a $\pi$ da qualunque vertice. Se invece si togliesse l'arco $\{1,2\}$ il grafo diventerebbe un albero, che è bipartito (periodo $2$): $P^n$ non convergerebbe, mentre $\pi$ resterebbe valida come media nel tempo.

2. Sia $H_i=H_{i5}$ con $H_5=0$. Condizionando al primo passo: $$H_4=1+\tfrac12H_3,\quad H_3=1+\tfrac13(H_1+H_2+H_4),\quad H_1=1+\tfrac12(H_2+H_3),\quad H_2=1+\tfrac12(H_1+H_3).$$ Sottraendo le ultime due si ottiene $H_1-H_2=\tfrac12(H_2-H_1)$, cioè $H_1=H_2$ (simmetria); allora $H_1=1+\tfrac12H_1+\tfrac12H_3$, $H_1=2+H_3$. Nella seconda: $H_3=1+\tfrac13(2(2+H_3)+H_4)=1+\tfrac43+\tfrac23H_3+\tfrac13H_4$, quindi $\tfrac13H_3=\tfrac73+\tfrac13H_4$, $H_3=7+H_4$. Nella prima: $H_4=1+\tfrac12(7+H_4)$, $\tfrac12H_4=\tfrac92$, $H_4=9$. Dunque $$H_{45}=9,\quad H_{35}=16,\quad H_{15}=H_{25}=18.$$ Verso $1$ (con $H_1=0$): $H_2=1+\tfrac12H_3$, $H_3=1+\tfrac13(H_2+H_4)$, $H_4=1+\tfrac12(H_3+H_5)$, $H_5=1+H_4$. Da $H_4=1+\tfrac12H_3+\tfrac12(1+H_4)$ si ha $H_4=3+H_3$; poi $H_3=1+\tfrac13(1+\tfrac12H_3+3+H_3)=\tfrac73+\tfrac12H_3$, $H_3=\tfrac{14}3$. Quindi $$H_{21}=\tfrac{10}3,\quad H_{31}=\tfrac{14}3,\quad H_{41}=\tfrac{23}3,\quad H_{51}=\tfrac{26}3.$$ Il percorso verso la foglia $5$ è molto più lungo di quello inverso ($18$ contro $\tfrac{26}3\approx8{,}7$): arrivare in fondo a un vicolo cieco costa molto, uscirne è facile. Controllo con il lemma $\sum_{w\sim5}H_{w5}=2m-d(5)=9$: l'unico vicino di $5$ è $4$ e $H_{45}=9$ ✓.

3. $H_{15}+H_{51}=18+\tfrac{26}3=\tfrac{80}3$. La resistenza efficace tra $1$ e $5$: tra $1$ e $3$ ci sono due percorsi in parallelo, l'arco diretto ($1\,\Omega$) e il percorso $1\text{-}2\text{-}3$ ($2\,\Omega$), che danno $\tfrac{1\cdot2}{1+2}=\tfrac23\,\Omega$; poi si sommano in serie gli archi $\{3,4\}$ e $\{4,5\}$: $R_{15}=\tfrac23+1+1=\tfrac83$. Quindi $2m\,R_{15}=10\cdot\tfrac83=\tfrac{80}3$ ✓.

4. Il tempo di copertura da un vertice $s$ si calcola con una catena sugli stati (insieme dei vertici visitati, vertice corrente): $5\cdot16=80$ stati al massimo; la soluzione del sistema lineare (frazioni esatte) è:

Quindi $C(G)=\tfrac{229}{12}\approx19{,}08$, molto sotto il limite $4m(n-1)=4\cdot5\cdot4=80$ (e sotto $2m(n-1)=40$ di quello raffinato). Una simulazione di $40\,000$ prove da $1$ dà $19{,}07$.

5. Con $n=1000$ il numero di passi è $4n^3=4\cdot10^9$. Serve il vertice corrente ($\lceil\log_2 1000\rceil=10$ bit) e un contatore fino a $4\cdot10^9$ ($\lceil\log_2(4\cdot10^9)\rceil=32$ bit): $42$ bit in tutto, contro almeno $n=1000$ bit (un bit per vertice) di una visita in ampiezza o in profondità (Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →). La probabilità di non raggiungere $t$ se è connesso è $<\tfrac12$ (e si può abbassare con ripetizioni).

Codice di verifica

import random
import numpy as np

adj = {1: [2, 3], 2: [1, 3], 3: [1, 2, 4], 4: [3, 5], 5: [4]}
V = sorted(adj); n = len(V); m = sum(map(len, adj.values())) // 2
print("pi:", [len(adj[v]) / (2 * m) for v in V])

def raggiungimento(t):
    idx = [v for v in V if v != t]
    A = np.eye(len(idx))
    for i, v in enumerate(idx):
        for w in adj[v]:
            if w != t: A[i, idx.index(w)] -= 1 / len(adj[v])
    return dict(zip(idx, np.linalg.solve(A, np.ones(len(idx)))))

print("verso 5:", raggiungimento(5)); print("verso 1:", raggiungimento(1))
print("pendolarismo 1-5:", raggiungimento(5)[1] + raggiungimento(1)[5], " 80/3 =", 80 / 3)

# tempo di copertura esatto: stati (insieme visitato come bitmask, vertice corrente)
stati = [(vis, p) for vis in range(1, 2**n) for p in V if vis >> (p - 1) & 1]
ix = {s: i for i, s in enumerate(stati)}
A = np.eye(len(stati)); b = np.ones(len(stati))
for (vis, p), i in ix.items():
    if vis == 2**n - 1:
        b[i] = 0; continue
    for w in adj[p]:
        A[i, ix[(vis | 1 << (w - 1), w)]] -= 1 / len(adj[p])
sol = np.linalg.solve(A, b)
print("copertura da v:", [round(sol[ix[(1 << (v - 1), v)]], 4) for v in V])

rng = random.Random(1); tot = 0
for _ in range(40000):
    x, vis, t = 1, {1}, 0
    while len(vis) < n:
        x = rng.choice(adj[x]); vis.add(x); t += 1
    tot += t
print("simulazione da 1:", tot / 40000)

Output (estratto): copertura da v: [19.0833, 19.0833, 18.9333, 15.6333, 10.3333], pendolarismo 1-5: 26.666..., simulazione intorno a $19{,}07$.