FormularioProbability and Computing: definizioni, teoremi e formule delle note, in ordine di capitolo

I. Probabilità discreta e algoritmi randomizzati

Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione

Definizione. Un algoritmo è Las Vegas se la risposta è sempre corretta e il tempo di esecuzione $T$ è una variabile aleatoria: si studia $E[T]$. È Monte Carlo se il tempo è limitato (deterministico) ma la risposta può essere sbagliata con una probabilità limitata.

Definizione (errore unilaterale). Un algoritmo è RP (randomized polynomial time) se lavora in tempo polinomiale e

• $x\in L\ \Rightarrow\ \Pr[\text{SI}]\ge 1/2$;
• $x\notin L\ \Rightarrow\ \Pr[\text{SI}]=0$.

Un SI è quindi certo, un NO può essere un errore. La classe co-RP è speculare: un NO è certo, un SI può essere un errore.

Definizione (errore bilaterale). Un algoritmo è BPP (bounded-error probabilistic polynomial time) se, in tempo polinomiale, risponde correttamente con probabilità almeno $2/3$ per ogni $x$, sia in $L$ sia fuori.

Definizione. ZPP (zero-error) è la classe dei linguaggi decisi da un algoritmo Las Vegas con tempo atteso polinomiale.

Teorema. $\text{ZPP}=\text{RP}\cap\text{co-RP}$.

Dimostrazione. ($\supseteq$) Siano $A$ un algoritmo RP e $B$ un co-RP per $L$. A turno: si esegue $A$ e, se dice SI, si risponde SI (certo); si esegue $B$ e, se dice NO, si risponde NO (certo); altrimenti si ricomincia. Se $x\in L$, $A$ dice SI con probabilità $\ge 1/2$ (e $B$ non dice mai NO); se $x\notin L$, $B$ dice NO con probabilità $\ge 1/2$. Ogni giro termina quindi con probabilità $\ge 1/2$: i giri sono geometrici, in media $\le 2$, e la risposta è sempre corretta. ($\subseteq$) Sia $V$ un Las Vegas con $E[T]\le q(n)$ polinomiale. Lo si interrompe a $2q(n)$ passi: per Markov $\Pr[T>2q(n)]\le 1/2$. Se si risponde NO allo scadere del tempo si ottiene un algoritmo RP (un SI è sempre certo, perché prodotto da $V$ concluso, e se $x\in L$ si risponde SI con probabilità $\ge1/2$); se si risponde SI si ottiene un co-RP. $\square$

Union bound e verifica randomizzata - identità polinomiali e prodotti di matrici

Teorema (union bound). Per eventi $A_1,A_2,\dots$ qualunque (finiti o numerabili) $$\Pr\Big(\bigcup_i A_i\Big)\le\sum_i\Pr(A_i).$$

Dimostrazione. Si pone $B_i=A_i\setminus\bigcup_{j<i}A_j$. Gli $B_i$ sono disgiunti, $B_i\subseteq A_i$ e $\bigcup B_i=\bigcup A_i$. Quindi $\Pr(\bigcup A_i)=\sum\Pr(B_i)\le\sum\Pr(A_i)$ per monotonia. $\square$

Teorema (Schwartz-Zippel). Sia $P(x_1,\dots,x_n)$ un polinomio non nullo di grado totale $d$ su un campo $\mathbb F$ (CampiUn campo è un insieme di numeri con somma e prodotto che rispettano le regole usuali (associativa, commutativa, neutri, opposti, inversi, distributiva): è ciò che serve per risolvere le equazioni di primo grado. Esempi: Q, R, C e i campi finiti.Campi →) e sia $S\subseteq\mathbb F$ finito. Se $r_1,\dots,r_n$ sono scelti uniformemente e indipendentemente in $S$, allora $$\Pr[P(r_1,\dots,r_n)=0]\le\frac d{|S|}.$$

Dimostrazione. Per induzione sul numero $n$ di variabili.

• $n=1$. Un polinomio non nullo di grado $d$ in un campo ha al più $d$ radici, quindi si annulla in al più $d$ punti di $S$: probabilità $\le d/|S|$.
• Passo. Si scrive $P=\sum_{i=0}^{k}x_1^{\,i}P_i(x_2,\dots,x_n)$, con $k$ la massima potenza di $x_1$ presente, cioè $P_k\not\equiv0$. Il grado totale di $P_k$ è $\le d-k$. Sia $E_1$ l'evento $P_k(r_2,\dots,r_n)=0$: per ipotesi induttiva $\Pr[E_1]\le(d-k)/|S|$. Se $E_1$ non accade, il polinomio in una variabile $Q(x_1)=P(x_1,r_2,\dots,r_n)$ ha coefficiente direttivo $P_k(r_2,\dots,r_n)\ne0$: è non nullo di grado $k$. Per decisioni differite, $r_1$ è indipendente da $r_2,\dots,r_n$, quindi $\Pr[Q(r_1)=0\mid\overline{E_1}]\le k/|S|$. Allora $$\Pr[P(r)=0]\le\Pr[E_1]+\Pr[P(r)=0\mid\overline{E_1}]\le\frac{d-k}{|S|}+\frac k{|S|}=\frac d{|S|}.\ \square$$ (Se $k=0$ la variabile $x_1$ non compare e basta l'ipotesi induttiva.)

Teorema. Se $AB=C$ risponde sempre giusto. Se $AB\ne C$ risponde $AB=C$ (errore) con probabilità $\le1/2$.

Dimostrazione. Se $AB=C$ allora $A(Br)=(AB)r=Cr$ per ogni $r$. Se $AB\ne C$ la matrice $D=AB-C$ ha un elemento $D_{ij}\ne0$. L'algoritmo sbaglia solo se $Dr=0$, e in particolare solo se $(Dr)_i=\sum_lD_{il}r_l=0$. Per decisioni differite si fissano tutte le componenti $r_l$ con $l\ne j$: la somma diventa $D_{ij}r_j+c$ con $c$ numero fisso. Poiché $r_j\in\{0,1\}$, i due valori $c$ e $c+D_{ij}$ sono diversi, quindi al più uno annulla la somma: $\Pr[(Dr)_i=0\mid r_{-j}]\le1/2$ per ogni $r_{-j}$, e perciò $\Pr[Dr=0]\le1/2$. $\square$

Teorema. Se $a=b$ l'esito è sempre giusto. Se $a\ne b$ l'errore ha probabilità $\le n/\pi(M)$, dove $\pi(M)\approx M/\ln M$ è il numero di primi $\le M$.

Dimostrazione. L'errore avviene se $p$ divide $d=|a-b|$, con $1\le d<2^n$. Ogni primo divisore è $\ge2$, quindi $d$ ha al più $n$ divisori primi distinti (il loro prodotto è $\le d<2^n$). Scegliendo $p$ uniforme tra i $\pi(M)$ primi, la probabilità di cadere in uno di quegli $\le n$ è $\le n/\pi(M)$. $\square$

Taglio minimo randomizzato - algoritmo di Karger

Definizione. Contrarre un arco $e=\{u,v\}$ significa fondere $u$ e $v$ in un unico supervertice: gli archi paralleli a $e$ diventano cappi e si eliminano, gli altri archi restano (anche se diventano paralleli tra loro). Il numero di vertici scende di $1$.

Teorema. Sia $C$ un taglio minimo di $G$ e $k=|C|$. L'algoritmo restituisce proprio $C$ con probabilità $$\Pr[\text{output}=C]\ \ge\ \frac2{n(n-1)}=\frac1{\binom n2}.$$

Dimostrazione. (1) Quando $C$ sopravvive. Gli archi tra le due parti di $C$ sono esattamente gli archi di $C$. Se nessun arco di $C$ viene mai contratto, ogni contrazione fonde due vertici della stessa parte, quindi ogni supervertice sta tutto in una parte; alla fine i due supervertici coprono $V$ e le due parti sono non vuote, dunque sono proprio le due parti di $C$ e l'output è $C$. Viceversa, se si contrae un arco di $C$ l'output non può essere $C$. Quindi basta stimare la probabilità che ai passi $i=1,\dots,n-2$ si scelga un arco fuori da $C$: sia $E_i$ l'evento «al passo $i$ non si sceglie un arco di $C$».

(2) Un passo. Si supponga che $E_1,\dots,E_{i-1}$ siano accaduti. Il multigrafo corrente $G_i$ ha $n_i=n-i+1$ vertici e $C$ è ancora un taglio di $G_i$ (con $k$ archi). Ogni taglio di $G_i$ è anche un taglio di $G$ con lo stesso numero di archi, quindi il taglio minimo di $G_i$ è ancora $k$. Il grado di ogni supervertice è $\ge k$ (gli archi uscenti da un supervertice formano un taglio), perciò $$|E_i|=\tfrac12\sum_v\deg(v)\ \ge\ \frac{n_ik}2 .$$ Si sceglie un arco di $C$ con probabilità $k/|E_i|\le2/n_i$, quindi $$\Pr[E_i\mid E_1\cap\dots\cap E_{i-1}]\ \ge\ 1-\frac2{n_i}=\frac{n-i-1}{n-i+1}.$$

(3) Prodotto. Per la regola del prodotto (Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →) $$\Pr\Big[\bigcap_{i=1}^{n-2}E_i\Big]\ge\prod_{i=1}^{n-2}\frac{n-i-1}{n-i+1}=\frac{n-2}{n}\cdot\frac{n-3}{n-1}\cdot\frac{n-4}{n-2}\cdots\frac24\cdot\frac13=\frac{2}{n(n-1)} ,$$ perché è un prodotto telescopico: restano a numeratore $2\cdot1$ e a denominatore $n(n-1)$. $\square$

Corollario. Un grafo con $n$ vertici ha al più $\binom n2$ tagli minimi.

Dimostrazione. Gli eventi «l'output è $C$» per tagli minimi distinti sono disgiunti, ciascuno ha probabilità $\ge1/\binom n2$ e la somma non supera $1$. $\square$

II. Variabili aleatorie e valore atteso

Linearità del valore atteso e variabili indicatrici

Teorema (linearità). Per ogni coppia di variabili aleatorie $X,Y$ sullo stesso spazio di probabilità e ogni $a,b\in\mathbb R$ (con attese finite) $$E[aX+bY]=aE[X]+bE[Y].$$ Non serve nessuna ipotesi di indipendenza.

Proprietà. $\ln(n+1)\le H_n\le 1+\ln n$; più finemente $H_n=\ln n+\gamma+\tfrac1{2n}-\tfrac1{12n^2}+\dots$, con $\gamma\approx0{,}5772$.

Teorema. $E[T]=nH_n\approx n\ln n+\gamma n$.

Definizione. Se $P(A)>0$, $E[X\mid A]=\frac{E[X\,I_A]}{P(A)}=\sum_x x\,P(X=x\mid A)$ (Probabilità condizionataLa probabilità di A sapendo che si è verificato B è P(A ∣ B) = P(A ∩ B) / P(B), con P(B) > 0; è una nuova misura di probabilità, e da essa seguono la regola del prodotto e la regola della catena.Probabilità condizionata →).

Teorema (probabilità totale per l'attesa). Se $A_1,\dots,A_m$ è una partizione dello spazio con $P(A_i)>0$, $$E[X]=\sum_i E[X\mid A_i]\,P(A_i).$$

Teorema (identità di Wald). Siano $X_1,X_2,\dots$ con la stessa media $\mu$ e $N$ un numero aleatorio di termini a valori interi non negativi, con $E[N]<\infty$. Se per ogni $i$ l'evento $\{N\ge i\}$ è indipendente da $X_i$ (vale se $N$ è indipendente dagli $X_i$, oppure se $N$ è un tempo d'arresto: la decisione di fermarsi dopo $i-1$ termini dipende solo da $X_1..X_{i-1}$), allora per $S_N=X_1+\dots+X_N$ $$E[S_N]=\mu\,E[N].$$

Analisi probabilistica di quicksort e quickselect

Lemma. Per $i<j$, $z_i$ e $z_j$ sono confrontati (al più una volta) con probabilità $$P(z_i\text{ e }z_j\text{ confrontati})=\frac{2}{j-i+1}.$$

Teorema. $E[C_n]=2(n+1)H_n-4n=2n\ln n-(4-2\gamma)\,n+2\ln n+O(1)$, con $4-2\gamma\approx2{,}846$. In particolare $E[C_n]\sim 2n\ln n\approx1{,}386\,n\log_2n$.

Proprietà. Il caso pessimo $\binom n2$ è raggiunto solo se ogni pivot è il minimo o il massimo del suo sottoproblema. Un sottoproblema di taglia $m\ge2$ lo permette con probabilità $\frac2m$, quindi $P(C_n=\binom n2)=\prod_{m=2}^n\frac2m=\frac{2^{n-1}}{n!}$.

Teorema. Il numero atteso di confronti di quickselect su $n$ elementi è al più $4n$, per ogni $k$.

III. Momenti e concentrazione

Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata

Teorema. Se $X$ è a valori interi non negativi con $E[X] > 0$: $$P(X = 0) \le \frac{\mathrm{Var}(X)}{E[X]^2}, \qquad P(X > 0) \ge \frac{E[X]^2}{E[X^2]}.$$

Teorema. Un giro dell'algoritmo fallisce con probabilità al più $n^{-1/4}$ (a meno di arrotondamenti di $\pm1$ nei ranghi). Il costo di un giro è $2n + O(n^{3/4}\log n)$ confronti, quindi il costo atteso totale è $2n + o(n)$.

Limiti di Chernoff e di Hoeffding

Teorema (Chernoff, forma esatta). $$P\big(X\ge(1+\delta)\mu\big)\le\Big[\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\Big]^{\mu}\quad(\delta>0),\qquad P\big(X\le(1-\delta)\mu\big)\le\Big[\frac{e^{-\delta}}{(1-\delta)^{1-\delta}}\Big]^{\mu}\quad(0<\delta<1).$$

Teorema. Con le stesse ipotesi:

1. per $0<\delta\le1$: $P(X\ge(1+\delta)\mu)\le e^{-\delta^2\mu/3}$;
2. per $0<\delta<1$: $P(X\le(1-\delta)\mu)\le e^{-\delta^2\mu/2}$;
3. per $R\ge 6\mu$: $P(X\ge R)\le 2^{-R}$.

Insieme: $P(|X-\mu|\ge\delta\mu)\le 2e^{-\delta^2\mu/3}$ per $0<\delta\le1$.

Lemma di Hoeffding. Se $a\le X\le b$ e $E[X]=0$, per ogni $s\in\mathbb R$: $E[e^{sX}]\le e^{s^2(b-a)^2/8}$.

Teorema (Hoeffding). $X_1,\dots,X_n$ indipendenti con $a_i\le X_i\le b_i$, $S=\sum X_i$, $c=\sum_i(b_i-a_i)^2$. Per ogni $t>0$: $$P(S-E[S]\ge t)\le e^{-2t^2/c},\qquad P(|S-E[S]|\ge t)\le2e^{-2t^2/c}.$$

Teorema. Sia $A$ una matrice $n\times m$ con entrate $0$ o $1$ ($n\ge3$). Esiste $b\in\{-1,+1\}^m$ tale che ogni riga ha $|(Ab)_i|\le\sqrt{4m\ln n}$.

IV. Palline e urne e hashing

Palline e urne - compleanno, carico massimo e approssimazione di Poisson

Definizione (palline e urne). Si lanciano $m$ palline in $n$ urne: ogni pallina sceglie la sua urna uniformemente e indipendentemente dalle altre. Il carico dell'urna $i$ è $L_i$ = numero di palline in $i$. Vale $L_1+\dots+L_n=m$.

Teorema (soglia del compleanno). Per $m\le n/2$ $$\exp\Bigl(-\frac{m(m-1)}{2n}-\frac{m^3}{3n^2}\Bigr)\ \le\ P(\text{nessuna collisione})\ \le\ \exp\Bigl(-\frac{m(m-1)}{2n}\Bigr).$$ Quindi la collisione ha probabilità circa $1/2$ per $m\approx\sqrt{2n\ln 2}\approx 1{,}18\sqrt n$: la soglia è $\Theta(\sqrt n)$, non $\Theta(n)$.

Teorema (urne vuote). Sia $Z$ il numero di urne vuote. Allora $$E[Z]=n\Bigl(1-\frac1n\Bigr)^m\approx n\,e^{-m/n},\qquad \text{Var}(Z)=n(n-1)\Bigl(1-\frac2n\Bigr)^m+n\Bigl(1-\frac1n\Bigr)^m-n^2\Bigl(1-\frac1n\Bigr)^{2m}.$$

Teorema (carico massimo, estremo superiore). Lanciando $n$ palline in $n$ urne, con probabilità almeno $1-\frac1n$ il carico massimo è al più $k=\bigl\lceil\frac{3\ln n}{\ln\ln n}\bigr\rceil$ (per $n\ge16$, così che $\ln\ln n>1$).

Teorema (esatto contro Poisson). Sia $L=(L_1,\dots,L_n)$ il vettore dei carichi esatti e $Y=(Y_1,\dots,Y_n)$ quello Poisson con media $m/n$. Per ogni funzione $f\ge0$ $$E[f(L)]\le e\sqrt m\;E[f(Y)].$$ In particolare, per ogni evento $A$ sui carichi: $P(L\in A)\le e\sqrt m\,P(Y\in A)$.

Hashing randomizzato - famiglie universali, filtri di Bloom e fingerprint

Definizione (famiglia universale). Una famiglia $\mathcal H$ di funzioni $U\to[m]$ è universale se per ogni coppia di chiavi $x\ne y$, scegliendo $h\in\mathcal H$ uniformemente a caso, $$P_h\bigl(h(x)=h(y)\bigr)\le\frac1m.$$

Teorema (catene). Sia $\mathcal H$ universale, $S\subseteq U$ un insieme di $n$ chiavi e $h$ scelta a caso. Per una chiave $x$ il numero atteso di chiavi di $S\setminus\{x\}$ nel suo bucket è al più $\frac{n-1}m$ se $x\in S$ e $\frac nm$ se $x\notin S$. Quindi ricerca, inserimento e cancellazione costano in media $O(1+\alpha)$.

Teorema (costruzione). Siano $p$ un primo con $p\ge|U|$, chiavi $U=\{0,\dots,p-1\}$ e, per $a\in\{1,\dots,p-1\}$, $b\in\{0,\dots,p-1\}$, $$h_{a,b}(x)=\bigl((ax+b)\bmod p\bigr)\bmod m.$$ La famiglia $\mathcal H=\{h_{a,b}\}$, di $p(p-1)$ funzioni, è universale.

Definizione (filtro di Bloom). Un vettore di $m$ bit, inizialmente $0$, e $k$ funzioni hash $h_1,\dots,h_k:U\to[m]$. Inserimento di $x$: si pongono a $1$ i bit $h_1(x),\dots,h_k(x)$. Interrogazione di $x$: si risponde "presente" se tutti i $k$ bit sono $1$, "assente" altrimenti.

Teorema (falsi positivi). Dopo $n$ inserimenti, con $k$ funzioni indipendenti e uniformi,

• un bit specifico è ancora $0$ con probabilità $\bigl(1-\frac1m\bigr)^{kn}\approx e^{-kn/m}$;
• un elemento non inserito è un falso positivo con probabilità $f\approx\Bigl(1-e^{-kn/m}\Bigr)^k$.
• Per $m,n$ fissati $f$ è minima per $k=\frac mn\ln2$, e vale allora $f=2^{-k}=(0{,}6185)^{m/n}$.

Definizione (fingerprint). Una fingerprint di $b$ bit di un oggetto grande $x$ è $\phi(x)=h(x)\in\{0,1\}^b$ con $h$ scelta a caso; si usa $\phi(x)=\phi(y)$ come test (probabilistico) per $x=y$. Se $x=y$ le fingerprint coincidono sempre; se $x\ne y$ possono coincidere per caso (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 →).

Algoritmi di streaming - campionamento di riserva e conteggio degli elementi distinti

Definizione (modello a flusso). Gli elementi $x_1,x_2,\dots,x_N$ arrivano uno alla volta, si leggono una volta sola e non si possono riguardare. La memoria è molto minore di $N$ (spesso polilogaritmica) e $N$ può essere ignoto. Gli algoritmi sono randomizzati e approssimati: si chiede una stima entro $\varepsilon$ con probabilità almeno $1-\delta$.

Teorema. Dopo aver letto $i\ge k$ elementi, ognuno di essi è nel campione con probabilità esattamente $k/i$ (e ogni sottoinsieme di $k$ elementi ha probabilità $1/\binom ik$).

Teorema. Dopo $n$ eventi, $E[2^{X_n}-1]=n$ (stima non distorta) e $\text{Var}(2^{X_n}-1)=\frac{n(n-1)}2$.

Teorema. Per $k\ge3$, $E\bigl[\frac{k-1}{V_k}\bigr]=d$ (stima non distorta) e lo scarto relativo è circa $\frac1{\sqrt{k-2}}$.

Definizione (Count-Min sketch). Una matrice $C$ di $d$ righe e $w$ colonne di contatori, inizialmente $0$, e $d$ funzioni hash indipendenti $h_1,\dots,h_d:U\to[w]$ da una famiglia universale. Arrivo di $x$: $C[j][h_j(x)]\mathrel{+}=1$ per ogni riga $j$. Stima: $\hat f(x)=\min_{j}C[j][h_j(x)]$.

Teorema (garanzia $(\varepsilon,\delta)$). Sia $F=\sum_yf(y)=N$ il numero totale di arrivi. Con $w=\lceil e/\varepsilon\rceil$ e $d=\lceil\ln(1/\delta)\rceil$: $$f(x)\le\hat f(x)\quad\text{sempre},\qquad P\bigl(\hat f(x)\le f(x)+\varepsilon N\bigr)\ge1-\delta.$$

V. Metodo probabilistico

Metodo probabilistico - valore atteso, alterazioni e derandomizzazione

Lemma (principio del valore atteso). Se $X$ è una variabile aleatoria discreta con $E[X]=\mu$, allora $P(X\ge\mu)>0$ e $P(X\le\mu)>0$. Esistono quindi un esito con $X\ge\mu$ e uno con $X\le\mu$.

Principio (conteggio). Se in uno spazio finito $P(\text{l'oggetto ha la proprietà }\mathcal P)>0$ allora esiste un oggetto con $\mathcal P$. In particolare, se $X$ conta i "difetti" e $E[X]<1$, per Markov $P(X\ge1)\le E[X]<1$ e quindi esiste un oggetto con zero difetti.

Teorema (taglio). Ogni grafo con $|E|$ archi ha un taglio (partizione dei vertici in due insiemi) con almeno $\lceil|E|/2\rceil$ archi tra le due parti.

Teorema (MAX-SAT). Una clausola con $\ell$ letterali su variabili distinte è soddisfatta con probabilità $1-2^{-\ell}$ (è falsa solo se ogni letterale è falso). Quindi in una formula con $m$ clausole di $3$ letterali esiste un'assegnazione che ne soddisfa almeno $\frac78m$ (arrotondato in su). Se tutte le clausole hanno almeno $k$ letterali e $m<2^k$, la formula è soddisfacibile.

Teorema. Se $\binom nk2^{1-\binom k2}<1$ allora $R(k,k)>n$. In particolare $R(k,k)>\lfloor2^{k/2}\rfloor$ per ogni $k\ge3$.

Teorema (insieme indipendente). Un grafo con $n$ vertici e $m\ge n/2$ archi, grado medio $d=2m/n\ge1$, contiene un insieme indipendente (nessun arco tra i suoi vertici) di almeno $\frac n{2d}=\frac{n^2}{4m}$ vertici.

Lemma locale di Lovász (forma simmetrica). Siano $A_1,\dots,A_N$ eventi "cattivi" con $P(A_i)\le p$ e ognuno indipendente da tutti gli altri tranne al più $d$. Se $e\,p\,(d+1)\le1$ allora $P\bigl(\bigcap_i\overline{A_i}\bigr)>0$: con probabilità positiva nessun evento cattivo accade.

VI. Catene di Markov e passeggiate aleatorie

Catene di Markov - matrice di transizione, classificazione degli stati e distribuzione stazionaria

Definizione (catena di Markov). Una successione di variabili aleatorie $X_0, X_1, X_2, \dots$ a valori in un insieme finito di stati $S=\{1,\dots,k\}$ è una catena di Markov (omogenea) se per ogni $n$ e per ogni scelta di stati vale la proprietà di Markov $$P(X_{n+1}=j\mid X_n=i,\,X_{n-1}=i_{n-1},\dots,X_0=i_0)=P(X_{n+1}=j\mid X_n=i)=P_{ij},$$ con $P_{ij}$ che non dipende da $n$. La matrice $P=(P_{ij})$ è la matrice di transizione: ha entrate $\ge0$ e ogni riga somma a 1 (matrice stocastica), perché dallo stato $i$ si va per forza da qualche parte.

Definizione (irriducibilità). Una catena è irriducibile se ha una sola classe, cioè da ogni stato si può raggiungere ogni altro: il grafo è fortemente connesso.

Definizione (periodo). Il periodo di $i$ è $d(i)=\gcd\{n\ge1:(P^n)_{ii}>0\}$ (massimo comun divisore delle lunghezze dei cammini chiusi per $i$). Se $d(i)=1$ lo stato è aperiodico. Il periodo è uguale per tutti gli stati di una classe. Una catena irriducibile è aperiodica se lo è un suo stato; in particolare basta un cappio $P_{ii}>0$.

Definizione (ricorrenza). Sia $T_i=\min\{n\ge1: X_n=i\}$ il tempo di primo ritorno in $i$ partendo da $i$. Lo stato è ricorrente se $P(T_i<\infty\mid X_0=i)=1$, transitorio altrimenti. Il tempo medio di ritorno è $h_{ii}=E[T_i\mid X_0=i]$; se ricorrente e $h_{ii}<\infty$ è ricorrente positivo.