Esercizio - Cammini hamiltoniani in un torneo casuale (lezioni MIT)

Teoria: Metodo probabilistico - valore atteso, alterazioni e derandomizzazioneMetodo probabilistico: se un oggetto casuale ha una proprietà con probabilità positiva (o una variabile ha media mu, quindi qualche esito la raggiunge) allora l'oggetto esiste; taglio di almeno |E|/2, MAX-SAT con 7/8, limite inferiore di Ramsey R(k,k) > 2^(k/2), alterazioni (insiemi indipendenti, Ramsey), derandomizzazione con le aspettative condizionate, lemma locale di Lovász solo enunciato.Metodo probabilistico - valore atteso, alterazioni e derandomizzazione → (principio del valore atteso); indicatori in Linearità del valore atteso e variabili indicatriciLa linearità $E[X+Y]=E[X]+E[Y]$ vale sempre, anche senza indipendenza; con le variabili indicatrici ($E[I_A]=P(A)$) trasforma un conteggio in una somma di probabilità. Applicazioni: attesa del primo successo $1/p$, collezionista di figurine $nH_n$, punti fissi di una permutazione (media $1$), record (media $H_n$), inversioni ($n(n-1)/4$), attesa condizionata, identità di Wald $E[S_N]=E[N]E[X]$.Linearità del valore atteso e variabili indicatrici →. Esempio tratto dalle videolezioni di Probabilistic Methods in Combinatorics, MIT OpenCourseWare.

Testo. Un torneo su $n$ vertici (giocatori) è un grafo in cui ogni coppia di vertici è collegata da un solo arco orientato ($u\to v$: $u$ batte $v$). Un cammino hamiltoniano è una sequenza $v_1\to v_2\to\dots\to v_n$ che tocca ogni vertice una volta, seguendo il verso degli archi.

1. Dimostrare che esiste un torneo su $n$ vertici con almeno $\frac{n!}{2^{n-1}}$ cammini hamiltoniani.
2. Calcolare il valore per $n=3,4,5,10$ e confrontarlo con il torneo transitivo ($i\to j$ se $i<j$).
3. Per $n=3,4,5$ contare i cammini in tutti i tornei e verificare media e massimo.

Soluzione

1. Torneo casuale. Si orienta ogni arco con una moneta equa, indipendentemente: tutti i $2^{\binom n2}$ tornei sono equiprobabili. Ogni permutazione $\sigma=(v_1,\dots,v_n)$ dei vertici è un possibile cammino; sia $I_\sigma=1$ se tutti gli archi $v_1\to v_2,\dots,v_{n-1}\to v_n$ hanno il verso giusto. Le $n-1$ coppie consecutive sono coppie distinte di vertici, quindi i loro archi sono orientati da monete indipendenti: $$P(I_\sigma=1)=\Big(\frac12\Big)^{n-1}.$$ Il numero di cammini hamiltoniani è $H=\sum_\sigma I_\sigma$ sulle $n!$ permutazioni e, per la linearità (non serve l'indipendenza tra le $I_\sigma$, che non c'è: permutazioni diverse condividono archi), $$E[H]=n!\cdot2^{-(n-1)}.$$ Per il principio del valore atteso esiste un torneo con $H\ge\frac{n!}{2^{n-1}}$. $\blacksquare$ La dimostrazione non dice quale torneo: è un risultato di esistenza.

2. Numeri. $\frac{n!}{2^{n-1}}$ vale $\frac64=1{,}5$, $\frac{24}8=3$, $\frac{120}{16}=7{,}5$ per $n=3,4,5$, e per $n=10$: $\frac{3\,628\,800}{512}=\mathbf{7087{,}5}$. Essendo $H$ intero, esiste un torneo con almeno $2$, $3$, $8$ e $7088$ cammini. Il torneo transitivo ne ha uno solo: ogni cammino deve scendere sempre verso indici più grandi, quindi è $1\to2\to\dots\to n$. Un torneo "ordinato" è il peggiore possibile, uno casuale ne ha in media un numero che cresce come $n!/2^{n}$.

3. Enumerazione completa. Per $n=3$ ci sono $2^3=8$ tornei: $6$ transitivi (un cammino) e $2$ cicli $a\to b\to c\to a$ (tre cammini, uno per ogni punto di partenza). Media $\frac{6\cdot1+2\cdot3}{8}=\frac{12}8=1{,}5$ ✓. Per $n=4$ ($64$ tornei) e $n=5$ ($1024$ tornei) la distribuzione di $H$ è:

Le medie coincidono con $\frac{n!}{2^{n-1}}$, e il massimo ($3$, $5$, $15$) è circa il doppio. Due fatti si leggono dalla tabella: ogni torneo ha almeno un cammino hamiltoniano, e il numero di cammini è sempre dispari (teorema di Rédei).

Risultato. $E[H]=\frac{n!}{2^{n-1}}$, quindi esiste un torneo con almeno tanti cammini hamiltoniani ($7088$ per $n=10$, contro $1$ del torneo transitivo).

Verifica.

import itertools, math
from collections import Counter
from fractions import Fraction as F

for n in (3, 4, 5):
    coppie = list(itertools.combinations(range(n), 2)); dist = Counter()
    for m in range(1 << len(coppie)):                       # tutti i tornei
        vince = set((i, j) if m >> k & 1 else (j, i) for k, (i, j) in enumerate(coppie))
        dist[sum(all((p[i], p[i + 1]) in vince for i in range(n - 1)) for p in itertools.permutations(range(n)))] += 1
    media = F(sum(h * c for h, c in dist.items()), 1 << len(coppie))
    print(n, sorted(dist.items()), media, F(math.factorial(n), 2 ** (n - 1)))
print(math.factorial(10) / 2 ** 9)

Risultato: 3 [(1, 6), (3, 2)] 3/2 3/2, 4 [(1, 24), (3, 16), (5, 24)] 3 3, 5 [(1, 120), (3, 120), (5, 240), (9, 240), (11, 120), (13, 120), (15, 64)] 15/2 15/2 e 7087.5.