Esercizio - Numero di ripetizioni di Karger per un errore prefissato

Testo. Un'esecuzione dell'algoritmo di Karger su un multigrafo con $n$ vertici trova un dato taglio minimo con probabilità almeno $1/\binom n2$ . Si eseguono $t$ esecuzioni indipendenti e si tiene il taglio più piccolo.

Dimostrare che la probabilità di fallimento è $\le e^{-t/\binom n2}$ e ricavare $t$ per un fallimento $\le\delta$ .
Calcolare $t$ per $\delta=0{,}01$ e $n=10,\ 50,\ 100$ ; calcolare anche la probabilità di fallimento con $t=\binom n2$ .
Con una matrice di adiacenza una esecuzione costa circa $n^2$ operazioni. Stimare il costo totale per $n=100$ e $\delta=0{,}01$ .
Per il grafo con due triangoli e un ponte ( $n=6$ ) la probabilità vera di successo è $13/35$ . Quante esecuzioni bastano per $\delta=0{,}01$ , col valore vero e col limite?

Teoria: Taglio minimo randomizzato - algoritmo di Karger (sezione sulle ripetizioni); Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione.

Soluzione

Punto 1. Ogni esecuzione fallisce con probabilità $\le1-\frac1{\binom n2}$ . Per l'indipendenza tutte e $t$ falliscono con probabilità $\Big(1-\frac1{\binom n2}\Big)^t\le e^{-t/\binom n2},$ perché $1-x\le e^{-x}$ . Il secondo membro è $\le\delta$ se $t\ge\binom n2\ln(1/\delta)$ . Quindi $t=\big\lceil\binom n2\ln\frac1\delta\big\rceil$ ripetizioni bastano. Con $t=\binom n2\ln n$ il fallimento è $\le1/n$ .

Punto 2. Con $\ln100=4{,}6052$ :

$n=10$ : $\binom{10}2=45$ , $t=\lceil45\cdot4{,}6052\rceil=\lceil207{,}2\rceil=208$ (fallimento vero $\le0{,}00933$ ).
$n=50$ : $\binom{50}2=1225$ , $t=\lceil5641{,}3\rceil=5642$ .
$n=100$ : $\binom{100}2=4950$ , $t=\lceil22795{,}6\rceil=22796$ .

Con $t=\binom n2$ : fallimento $\le\big(1-\frac1{\binom n2}\big)^{\binom n2}$ , cioè $0{,}3637$ per $n=10$ , $0{,}3677$ per $n=50$ , $0{,}3678$ per $n=100$ , quasi $e^{-1}=0{,}3679$ (il limite per $n\to\infty$ ).

Punto 3. $n=100$ : $22796\cdot n^2=22796\cdot10^4\approx2{,}3\cdot10^8$ operazioni (qualche secondo). Il costo cresce come $n^4\log n$ : a $n=1000$ sarebbe $\approx\binom{1000}2\ln100\cdot10^6\approx2{,}3\cdot10^{12}$ , che motiva Karger-Stein ( $O(n^2\log^3n)$ ).

Punto 4. Valore vero $13/35$ : fallimento per esecuzione $22/35$ . $(22/35)^t\le0{,}01$ dà $t\ge\frac{\ln0{,}01}{\ln(22/35)}=\frac{-4{,}605}{-0{,}4643}=9{,}92$ , quindi $t=10$ ( $(22/35)^{10}=0{,}0096$ ). Col limite $1/15$ : $t=\lceil15\ln100\rceil=\lceil69{,}08\rceil=70$ . Il limite chiede $7$ volte più ripetizioni.

Risultati: $t=\lceil\binom n2\ln(1/\delta)\rceil$ ; $208,\ 5642,\ 22796$ ; costo $\approx2{,}3\cdot10^8$ per $n=100$ ; $10$ contro $70$ ripetizioni per i due triangoli.

python

from math import comb, log, ceil
for n in (10, 50, 100):
    c = comb(n, 2); t = ceil(c * log(100))
    print(n, c, t, (1 - 1 / c)**t, (1 - 1 / c)**c, t * n * n)
print(log(0.01) / log(22 / 35), (22 / 35)**10, ceil(15 * log(100)))

Versione ripasso

Fallimento: $\big(1-1/\binom n2\big)^t\le e^{-t/\binom n2}\le\delta$ se $t\ge\binom n2\ln(1/\delta)$ (Taglio minimo randomizzato - algoritmo di Karger).
$\delta=0{,}01$ : $n=10$ : $t=208$ ; $n=50$ : $5642$ ; $n=100$ : $22796$ . Con $t=\binom n2$ il fallimento è $\approx e^{-1}=0{,}368$ .
Costo: $22796\cdot10^4\approx2{,}3\cdot10^8$ per $n=100$ ; in generale $O(n^4\log n)$ , da cui Karger-Stein.
Due triangoli (vera $13/35$ ): $(22/35)^t\le0{,}01\Rightarrow t=10$ ; col limite $1/15$ : $70$ .
Errori tipici: usare $t=\ln(1/\delta)$ (manca il fattore $\binom n2$ ); dimenticare di arrotondare per eccesso; non rendere indipendenti le esecuzioni.

Esercizio - Numero di ripetizioni di Karger per un errore prefissato

Soluzione

Teoria collegata