Passeggiate aleatorie - rovina del giocatore, 2-SAT e grafi

Le catene di Markov di Catene di Markov - matrice di transizione, classificazione degli stati e distribuzione stazionariaUna catena di Markov a tempo discreto e stati finiti è descritta da una matrice stocastica P: P(X_{n+1}=j | X_n=i)=P_ij, la legge al tempo n è π_0 P^n. Gli stati si classificano in classi comunicanti (irriducibilità), periodo (aperiodicità) e ricorrenza/transitorietà. Una distribuzione stazionaria soddisfa πP=π; per catene finite irriducibili esiste ed è unica, vale π_i=1/h_ii (h_ii = tempo medio di primo ritorno), e se la catena è anche aperiodica P^n converge a una matrice con tutte le righe uguali a π. Le catene reversibili (π_i P_ij = π_j P_ji) hanno stazionaria immediata.Catene di Markov - matrice di transizione, classificazione degli stati e distribuzione stazionaria → applicate a tre problemi: una passeggiata sulla retta con due barriere assorbenti (rovina del giocatore), un algoritmo randomizzato che è una passeggiata sullo spazio delle assegnazioni (2-SAT), e la passeggiata su un grafo (connettività, copertura, PageRank). Prerequisiti: Valore attesoIl valore atteso E[X] = Σ x p_X(x) è la media dei valori di X pesata con le loro probabilità (esiste se la serie converge assolutamente); per una funzione g vale E[g(X)] = Σ g(x) p_X(x) senza trovare la legge di g(X), ed E è lineare: E[aX + bY + c] = aE[X] + bE[Y] + c.Valore atteso →, Distribuzione geometricaGeo(p) è il numero della prova in cui arriva il primo successo in prove indipendenti: P(X = n) = (1−p)^(n−1) p per n ≥ 1, P(X > n) = (1−p)^n (lunga attesa), media 1/p, varianza (1−p)/p², ed è senza memoria.Distribuzione geometrica →, Disuguaglianze di Markov, Chebyshev e JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen →, 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à →. Per la nozione di algoritmo Monte Carlo a errore unilaterale: Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazioneUn algoritmo randomizzato usa bit casuali indipendenti; la probabilità è sulle scelte dell'algoritmo, mai sull'input (garanzia per ogni input). Las Vegas: sempre corretto, tempo aleatorio (conta il tempo atteso). Monte Carlo: tempo fisso, risposta sbagliata con probabilità limitata; errore unilaterale (RP: accetta solo se x sta nel linguaggio, accetta con prob almeno 1/2) o bilaterale (BPP: giusto con prob almeno 2/3). ZPP = RP ∩ co-RP = Las Vegas con tempo atteso polinomiale. Amplificazione: unilaterale, k ripetizioni indipendenti, errore (1-p)^k ≤ e^(-pk), serve k ≥ ln(1/ε)/p; bilaterale, voto di maggioranza su k esecuzioni, errore binomiale esatto, esponenziale in k (Chernoff, e^(-k/18) per p=2/3) mentre Chebyshev dà solo 8/k. Las Vegas -> Monte Carlo: interrompere a c volte il tempo atteso (Markov, errore ≤ 1/c). Monte Carlo -> Las Vegas: solo se la risposta si verifica in fretta. Esempio: Miller-Rabin, errore ≤ 1/4 per esecuzione.Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione →.

Rovina del giocatore

Problema. Un giocatore ha $i$ euro e punta $1$ euro a ogni partita: vince con probabilità $p$ (guadagna $1$), perde con $q=1-p$. Si ferma quando raggiunge $N$ (vittoria) o $0$ (rovina). Sia $P_i$ la probabilità di raggiungere $N$ prima di $0$ partendo da $i$, e $D_i$ il numero medio di partite.

Condizionando al primo passo (stati $1,\dots,N-1$ transitori, $0$ e $N$ assorbenti): $$P_i=pP_{i+1}+qP_{i-1},\quad P_0=0,\ P_N=1;\qquad D_i=1+pD_{i+1}+qD_{i-1},\quad D_0=D_N=0.$$

Soluzione, gioco equo $p=q=\tfrac12$. La prima equazione dice $P_{i+1}-P_i=P_i-P_{i-1}$: gli incrementi sono costanti, quindi $P_i$ è lineare, e con $P_0=0$, $P_N=1$ si ha $\boxed{P_i=i/N}$. Per la durata si verifica che $D_i=i(N-i)$ soddisfa la ricorrenza: $\tfrac12\bigl[(i-1)(N-i+1)+(i+1)(N-i-1)\bigr]=i(N-i)-1$, quindi $1+(i(N-i)-1)=i(N-i)$ ✓, con $D_0=D_N=0$; la soluzione è unica (sistema lineare con matrice $I-Q$ invertibile, $Q$ transitoria). Dunque $\boxed{D_i=i(N-i)}$.

Esempio. $N=5$, $i=3$: $P_3=\tfrac35$, $D_3=3\cdot2=6$ partite. Con $N=20$, $i=10$: $P=\tfrac12$ e $D=100$ partite.

Soluzione, $p\ne\tfrac12$. L'equazione $P_i=pP_{i+1}+qP_{i-1}$ ha equazione caratteristica $pt^2-t+q=0$ con radici $1$ e $r=q/p$ (perché $p+q=1$). Quindi $P_i=A+Br^i$, e con $P_0=0$, $P_N=1$: $$P_i=\frac{1-r^i}{1-r^N},\qquad r=\frac qp.$$ Per la durata, una soluzione particolare di $D_i=1+pD_{i+1}+qD_{i-1}$ è $i/(q-p)$ (sostituendo: $\tfrac{i}{q-p}=1+\tfrac{p(i+1)+q(i-1)}{q-p}=1+\tfrac{i+p-q}{q-p}=\tfrac{i}{q-p}$ ✓); sommando la soluzione generale dell'omogenea e imponendo $D_0=D_N=0$: $$D_i=\frac{i}{q-p}-\frac N{q-p}\cdot\frac{1-r^i}{1-r^N}=\frac{i-N\,P_i}{q-p}.$$

Esempio. $p=0{,}45$, $N=20$, $i=10$: $r=\tfrac{0{,}55}{0{,}45}=\tfrac{11}9$, $P_{10}=\tfrac{1-r^{10}}{1-r^{20}}=\tfrac1{1+r^{10}}=0{,}1185$ e $D_{10}=\tfrac{10-20\cdot0{,}1185}{0{,}1}=76{,}30$ partite. Un piccolo vantaggio della banca ($0{,}55$ contro $0{,}45$) abbatte la probabilità di vincere da $50\%$ a $11{,}85\%$. Alla roulette (puntando sul rosso $p=\tfrac{18}{38}$) partendo da $90$ per arrivare a $100$ la probabilità è $0{,}3487$ con $1047{,}5$ partite in media, ma da $10$ a $100$ è $4{,}96\cdot10^{-5}$.

Contro una banca infinita ($N\to\infty$, gioco equo): $P_i=i/N\to0$, cioè la rovina è certa, ma la durata $i(N-i)\to\infty$: la rovina arriva quasi certamente, in tempo medio infinito. Questo è il comportamento della passeggiata simmetrica, che è ricorrente ma con tempo medio di ritorno infinito.

2-SAT con una passeggiata aleatoria

Problema. Una formula 2-CNF su $n$ variabili è un AND di clausole di due letterali (per esempio $(x_1\vee\neg x_2)\wedge(\neg x_1\vee x_3)$). Si cerca un'assegnazione che le soddisfi tutte. Esiste un algoritmo deterministico lineare (componenti fortemente connesse), ma quello randomizzato è semplicissimo.

Algoritmo (passeggiata per 2-SAT).

1. Si parte da un'assegnazione qualunque (per esempio tutte le variabili a $0$).
2. Ripeti al più $2n^2$ volte: se tutte le clausole sono soddisfatte, restituisci l'assegnazione; altrimenti scegli una clausola violata, scegli a caso uno dei suoi due letterali e cambia il valore della sua variabile.
3. Se dopo $2n^2$ passi non si è trovata un'assegnazione, rispondi "non soddisfacibile".

L'errore è unilaterale (Monte Carlo, vedi Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazioneUn algoritmo randomizzato usa bit casuali indipendenti; la probabilità è sulle scelte dell'algoritmo, mai sull'input (garanzia per ogni input). Las Vegas: sempre corretto, tempo aleatorio (conta il tempo atteso). Monte Carlo: tempo fisso, risposta sbagliata con probabilità limitata; errore unilaterale (RP: accetta solo se x sta nel linguaggio, accetta con prob almeno 1/2) o bilaterale (BPP: giusto con prob almeno 2/3). ZPP = RP ∩ co-RP = Las Vegas con tempo atteso polinomiale. Amplificazione: unilaterale, k ripetizioni indipendenti, errore (1-p)^k ≤ e^(-pk), serve k ≥ ln(1/ε)/p; bilaterale, voto di maggioranza su k esecuzioni, errore binomiale esatto, esponenziale in k (Chernoff, e^(-k/18) per p=2/3) mentre Chebyshev dà solo 8/k. Las Vegas -> Monte Carlo: interrompere a c volte il tempo atteso (Markov, errore ≤ 1/c). Monte Carlo -> Las Vegas: solo se la risposta si verifica in fretta. Esempio: Miller-Rabin, errore ≤ 1/4 per esecuzione.Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione →): se la formula non è soddisfacibile non si trova mai nulla e la risposta è corretta; se lo è, si può sbagliare.

Esempio svolto (n = 3). Formula $(x_1\vee x_2)\wedge(\neg x_1\vee x_3)\wedge(\neg x_2\vee\neg x_3)$; soddisfacibile con $(0,1,0)$ e $(1,0,1)$ (si verificano a mano: con $x_1=1$ la seconda clausola impone $x_3=1$ e la terza $x_2=0$; con $x_1=0$ la prima impone $x_2=1$ e la terza $x_3=0$). Partenza $(0,0,0)$: la prima clausola è violata ($x_1=x_2=0$). Si sceglie a caso tra $x_1$ e $x_2$: sia $x_1$, si ottiene $(1,0,0)$. Ora la seconda clausola è violata ($\neg x_1=0$, $x_3=0$): si sceglie tra $x_1$ e $x_3$, sia $x_3$: $(1,0,1)$, e tutte e tre le clausole sono soddisfatte. Trovata in $2$ passi. Con altre scelte il cammino è più lungo (per esempio se al secondo passo si sceglie $x_1$ si torna a $(0,0,0)$).

Analisi

Teorema. Se la formula è soddisfacibile, il numero atteso di passi per trovare un'assegnazione soddisfacente è al più $n^2$, qualunque sia l'assegnazione iniziale. Quindi con $2n^2$ passi la probabilità di errore è al più $\tfrac12$, e ripetendo $k$ blocchi indipendenti di $2n^2$ passi è al più $2^{-k}$.

Dimostrazione. Si fissa un'assegnazione soddisfacente $S$. Sia $X_t$ il numero di variabili in cui l'assegnazione corrente $A_t$ differisce da $S$. Se $X_t=0$ si è trovata $S$ (l'algoritmo può fermarsi prima, su un'altra soluzione). Se $X_t>0$ e c'è una clausola $C$ violata da $A_t$: $S$ soddisfa $C$ mentre $A_t$ no, quindi almeno una delle due variabili di $C$ differisce da $S$ (se entrambe coincidessero con $S$, i due letterali avrebbero lo stesso valore che in $S$ e $C$ sarebbe violata anche da $S$). Cambiando una variabile scelta a caso tra le due: $$P(X_{t+1}=X_t-1)\ge\tfrac12,\qquad P(X_{t+1}=X_t+1)\le\tfrac12.$$ Per confronto (si accoppiano i due processi con lo stesso lancio di moneta) il tempo per arrivare a $0$ è al più quello della passeggiata simmetrica $Y_t$ su $\{0,\dots,n\}$ con $Y_0=X_0$, che scende o sale con probabilità $\tfrac12$ e in $n$ è riflessa ($h_n=1+h_{n-1}$). Sia $h_j$ il tempo medio per arrivare a $0$ da $j$: $$h_0=0,\qquad h_j=1+\tfrac12h_{j-1}+\tfrac12h_{j+1}\ (0<j<n),\qquad h_n=1+h_{n-1}.$$ Si verifica che $h_j=2jn-j^2$: per $0<j<n$, $\tfrac12\bigl[2(j-1)n-(j-1)^2+2(j+1)n-(j+1)^2\bigr]=2jn-j^2-1$, quindi $1+(2jn-j^2-1)=2jn-j^2$ ✓; in $n$: $h_n=n^2$ e $1+h_{n-1}=1+2n(n-1)-(n-1)^2=n^2$ ✓. Il massimo di $2jn-j^2$ su $0\le j\le n$ è $n^2$ (in $j=n$). Dunque $E[T]\le n^2$. Per la disuguaglianza di Markov (Disuguaglianze di Markov, Chebyshev e JensenMarkov: per X ≥ 0, P(X ≥ a) ≤ E[X]/a; Chebyshev: P(|X − μ| ≥ ε) ≤ Var(X)/ε²; Jensen: per φ convessa, φ(E[X]) ≤ E[φ(X)]. Stimano probabilità e medie conoscendo solo media e varianza.Disuguaglianze di Markov, Chebyshev e Jensen →), $P(T>2n^2)\le\tfrac{n^2}{2n^2}=\tfrac12$. Dopo ogni blocco di $2n^2$ passi, qualunque sia l'assegnazione a cui si è arrivati, la stessa analisi dà fallimento $\le\tfrac12$; i blocchi sono condizionalmente indipendenti, quindi $k$ blocchi falliscono con probabilità $\le2^{-k}$. $\blacksquare$

Esempio. Formula su $n=4$ variabili $(\neg x_1\vee\neg x_2)\wedge(\neg x_1\vee x_2)\wedge(x_1\vee\neg x_2)\wedge(x_1\vee\neg x_3)\wedge(x_1\vee\neg x_4)$: la soluzione è unica, $(0,0,0,0)$. Il tempo medio esatto per trovarla (prendendo la prima clausola violata) da distanza $j=1,2,3,4$ vale al massimo $5,\ 10,\ 13,\ 14$, sotto i limiti $2jn-j^2=7,12,15,16$. Il dettaglio è in Esercizio - Algoritmo randomizzato per 2-SAT eseguito su un'istanza con quattro variabili.

Il caso 3-SAT

Con clausole di $3$ letterali una clausola violata ha almeno una variabile sbagliata su tre: la probabilità di avvicinarsi a $S$ è solo $\ge\tfrac13$, quella di allontanarsi $\le\tfrac23$. La passeggiata ha deriva verso l'allontanamento e il tempo atteso di arrivo è esponenziale in $n$ (la ricorrenza $h_j=1+\tfrac13h_{j-1}+\tfrac23h_{j+1}$ ha soluzione dell'ordine di $2^n$). L'idea per migliorare è ripartire spesso: si riparte da un'assegnazione casuale uniforme ogni $3n$ passi. La distanza iniziale da una soluzione $S$ è $\text{Bin}(n,\tfrac12)$ (ogni variabile è giusta con probabilità $\tfrac12$). Da distanza $j$ si arriva a $0$ in $3j$ passi se $2j$ passi sono giusti e $j$ sbagliati (differenza $j$): la probabilità è almeno $\binom{3j}{j}\bigl(\tfrac13\bigr)^{2j}\bigl(\tfrac23\bigr)^j$, calcolata per la passeggiata che scende con probabilità esattamente $\tfrac13$ (la vera è più favorevole, per confronto). Sommando su $j$ con peso $\binom nj2^{-n}$, la probabilità di successo di un tentativo vale $q(n)=\sum_j\binom nj2^{-n}\binom{3j}j\frac{2^j}{3^{3j}}$, e numericamente $q(n)\approx(3/4)^n$ a meno di un fattore polinomiale:

Servono in media $1/q(n)\approx(4/3)^n\cdot\text{poly}(n)$ tentativi: un algoritmo di tempo $O\bigl((4/3)^n\,\text{poly}(n)\bigr)$ per 3-SAT, molto meglio di $2^n$ (enunciato senza la dimostrazione completa della stima polinomiale; i valori della tabella sono calcolati con la formula esatta).

Passeggiata aleatoria su un grafo

Sia $G=(V,E)$ un grafo non orientato connesso con $n$ vertici e $m$ archi (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à →). La passeggiata aleatoria sta in un vertice $u$ e passa a un vicino scelto uniformemente: $P_{uv}=1/d(u)$ se $\{u,v\}\in E$.

Teorema. La passeggiata su $G$ connesso è una catena irriducibile. Ha come unica distribuzione stazionaria $\pi_v=\dfrac{d(v)}{2m}$ e tempo medio di ritorno $h_{vv}=\dfrac{2m}{d(v)}$. È aperiodica se e solo se $G$ non è bipartito.

Dimostrazione. Si ha $\sum_vd(v)=2m$, quindi $\pi$ è una distribuzione. Per ogni arco $\{u,v\}$: $\pi_uP_{uv}=\tfrac{d(u)}{2m}\cdot\tfrac1{d(u)}=\tfrac1{2m}=\pi_vP_{vu}$: bilancio dettagliato, quindi $\pi$ è stazionaria; l'unicità e $h_{vv}=1/\pi_v$ seguono dal teorema fondamentale. Se $G$ è bipartito i cammini chiusi hanno lunghezza pari (periodo $2$); se contiene un ciclo dispari insieme ai cammini di andata e ritorno su un arco (lunghezza $2$) il $\gcd$ vale $1$. $\blacksquare$

Esempio. Nel grafo del disegno (triangolo $1,2,3$ con coda $3\text{-}4\text{-}5$) $m=5$, $\pi=(0{,}2;0{,}2;0{,}3;0{,}2;0{,}1)$, tempi di ritorno $5,5,\tfrac{10}3,5,10$. Il nodo $5$ (foglia) si rivisita ogni $10$ passi, il nodo $3$ (il più connesso) ogni $3{,}33$.

Tempi di raggiungimento e di copertura

Sia $H_{uv}$ il tempo medio per andare da $u$ a $v$ ($H_{uu}=0$) e $C(G)$ il tempo di copertura: il massimo, sulle partenze, del tempo medio per visitare tutti i vertici.

Lemma. Per ogni arco $\{u,v\}$ vale $H_{vu}<2m$.

Dimostrazione. Il tempo di ritorno in $u$ si scrive condizionando sul primo passo: $\dfrac{2m}{d(u)}=h_{uu}=1+\dfrac1{d(u)}\sum_{w\sim u}H_{wu}$. Moltiplicando per $d(u)$: $\sum_{w\sim u}H_{wu}=2m-d(u)$. Ogni addendo è $\ge0$, quindi $H_{vu}\le2m-d(u)<2m$. $\blacksquare$

Teorema (copertura). $C(G)<4m(n-1)$.

Dimostrazione. Si prende un albero di copertura $T$ di $G$ (esiste perché $G$ è connesso) e la visita in profondità di $T$ che parte da $s$ e ritorna in $s$: percorre ogni arco dell'albero una volta per verso, cioè $2(n-1)$ passaggi $u_0=s\to u_1\to\dots\to u_{2n-2}=s$ tra vertici adiacenti, e visita tutti i vertici. La passeggiata aleatoria da $s$, per visitare tutti i vertici, ha tempo medio al più $\sum_{k}H_{u_ku_{k+1}}$ (il tempo per toccare in ordine questi vertici), e per il lemma ciascun addendo è $<2m$: totale $<2(n-1)\cdot2m$. $\blacksquare$

(Con l'identità del tempo di pendolarismo $H_{uv}+H_{vu}=2m\,R_{uv}$, dove $R_{uv}$ è la resistenza efficace tra $u$ e $v$ con archi da $1\,\Omega$, si migliora a $2m(n-1)$; qui si è usata solo la dimostrazione elementare.)

Esempio (grafo del disegno). I tempi di raggiungimento di $5$ valgono $H_{15}=H_{25}=18$, $H_{35}=16$, $H_{45}=9$ (a mano, con $H_i=H_{i5}$: $H_4=1+\tfrac12H_3$, $H_3=1+\tfrac13(2H_1+H_4)$, $H_1=1+\tfrac12(H_1+H_3)$ con $H_1=H_2$ per simmetria, quindi $H_1=2+H_3$, $H_3=7+H_4$, $H_4=9$, $H_3=16$, $H_1=18$). Il tempo di pendolarismo tra $1$ e $5$ è $H_{15}+H_{51}=18+\tfrac{26}3=\tfrac{80}3$, uguale a $2m\,R_{15}=10\cdot\tfrac83$ perché $R_{15}=\tfrac23+1+1$. Il tempo di copertura esatto da $1$ è $\tfrac{229}{12}\approx19{,}08$ (sistema lineare sugli stati (insieme visitato, posizione)), molto sotto $4m(n-1)=80$.

Il caso del lollipop è il peggiore: per $n=30,60,90$ i tempi esatti sono $3919$, $31\,639$ e $107\,159$, cioè $0{,}145n^3$, $0{,}146n^3$, $0{,}147n^3$, che tende a $\tfrac4{27}n^3=0{,}148n^3$.

Connettività s-t in spazio logaritmico

Problema (UST-CONN). In un grafo non orientato con $n$ vertici, $s$ e $t$ sono nella stessa componente connessa?

Algoritmo. Fai una passeggiata aleatoria da $s$ di $4n^3$ passi; se incontri $t$ rispondi "sì", altrimenti "no".

Se $s$ e $t$ non sono connessi la risposta è sempre corretta. Se lo sono, il tempo medio per raggiungere $t$ è al più il tempo di copertura della componente di $s$, che ha $n'\le n$ vertici e $m'\le\tfrac{n(n-1)}2$ archi: $C<4m'(n'-1)\le2n(n-1)^2<2n^3$. Per Markov, la probabilità di non vedere $t$ in $4n^3$ passi è $<\tfrac12$. Memoria: servono solo il vertice corrente e un contatore fino a $4n^3$, cioè $O(\log n)$ bit (per $n=100$: $4\cdot10^6$ passi, un contatore di $22$ bit). Un algoritmo deterministico con quella memoria è stato trovato solo molto più tardi; qui la randomizzazione dà uno strumento semplicissimo.

PageRank

Il navigatore casuale su un insieme di $n$ pagine: con probabilità $\alpha$ (tipicamente $0{,}85$) segue un link uscente scelto a caso, con probabilità $1-\alpha$ salta a una pagina uniforme. Se una pagina non ha link, si salta sempre. La matrice è $$G=\alpha P+\frac{1-\alpha}n\mathbf 1\mathbf 1^T,\qquad \text{PR}_j=\frac{1-\alpha}n+\alpha\sum_{i\to j}\frac{\text{PR}_i}{d^+(i)},$$ dove $d^+$ è il numero di link uscenti. Tutte le entrate di $G$ sono $\ge\frac{1-\alpha}n>0$: la catena è irriducibile e aperiodica per costruzione, quindi esiste un'unica distribuzione stazionaria, ottenibile come limite di $x\,G^k$ da qualunque $x$ (iterazione di potenza). Il secondo autovalore di $G$ ha modulo $\le\alpha$, quindi l'errore decade come $\alpha^k$ (con $\alpha=0{,}85$, circa $\ln(10^6)/\ln(1/0{,}85)\approx85$ iterazioni per sei cifre).

Esempio. Tre pagine, $1\to2,3$; $2\to3$; $3\to1$; $\alpha=0{,}85$. Le equazioni sono $x_1=0{,}05+0{,}85x_3$, $x_2=0{,}05+0{,}425x_1$, $x_3=0{,}05+0{,}425x_1+0{,}85x_2$. Dalla seconda e dalla terza: $x_3=0{,}0925+0{,}78625x_1$; nella prima: $x_1=0{,}05+0{,}85(0{,}0925+0{,}78625x_1)=0{,}128625+0{,}6683x_1$, quindi $x_1=0{,}3878$, $x_2=0{,}2148$, $x_3=0{,}3974$. La pagina $3$ è la più importante perché riceve da $1$ (metà del suo peso) e da $2$ (tutto). Il caso con $4$ pagine è in Esercizio - PageRank di quattro pagine con teletrasporto e iterazione di potenza.

Codice: 2-SAT randomizzato e passeggiata su un grafo

import random

def two_sat(clauses, n, rng, max_steps=None):
    """clauses: lista di coppie di letterali (v, segno) con segno 1 = x_v, 0 = not x_v."""
    x = [0] * n
    max_steps = max_steps or 2 * n * n
    sat = lambda c: any(x[v] == s for v, s in c)
    for t in range(max_steps + 1):
        violate = [c for c in clauses if not sat(c)]
        if not violate:
            return x, t
        v, _ = rng.choice(rng.choice(violate))     # clausola violata, poi letterale a caso
        x[v] ^= 1
    return None, max_steps

def passeggiata(adj, start, passi, rng):
    x, visti = start, {start}
    for _ in range(passi):
        x = rng.choice(adj[x]); visti.add(x)
    return visti

rng = random.Random(1)
# (x0 | x1) & (~x0 | x2) & (~x1 | ~x2): variabili 0,1,2
f = [((0, 1), (1, 1)), ((0, 0), (2, 1)), ((1, 0), (2, 0))]
print(two_sat(f, 3, rng))                           # un'assegnazione soddisfacente
adj = {1: [2, 3], 2: [1, 3], 3: [1, 2, 4], 4: [3, 5], 5: [4]}
tempi = []
for _ in range(20000):
    x, visti, t = 1, {1}, 0
    while len(visti) < 5:
        x = rng.choice(adj[x]); visti.add(x); t += 1
    tempi.append(t)
print(sum(tempi) / len(tempi))                      # circa 229/12 = 19.08

Domande d'esame

1. Giocatore con $3$ euro, traguardo $5$, gioco equo: probabilità di vittoria e partite attese. $P_3=\tfrac35$, $D_3=3\cdot2=6$.
2. Dimostra che l'algoritmo randomizzato per 2-SAT con $2n^2$ passi ha errore $\le\tfrac12$. Distanza $X_t$ da una soluzione $S$ fissata: si avvicina con probabilità $\ge\tfrac12$; $h_j=2jn-j^2\le n^2$; Markov.
3. Dimostra che sulla passeggiata su un grafo $\pi_v=d(v)/2m$ e calcola $h_{vv}$ per il vertice $3$ del grafo con triangolo e coda. Bilancio dettagliato $\pi_uP_{uv}=\tfrac1{2m}$; $h_{33}=\tfrac{10}3$.
4. Perché la connettività s-t si decide in spazio $O(\log n)$? Copertura $<2n^3$ ma si memorizzano solo il vertice corrente e un contatore; Markov dà errore $<\tfrac12$, solo unilaterale.