Esercizio - esistenza di triangoli con il secondo momento in G(n,p)

Teoria: Momenti e deviazioni - Markov, Chebyshev e mediana randomizzataVar(ΣX_i) = ΣVar + 2ΣCov, e basta l'indipendenza a coppie perché la varianza si sommi. Chebyshev dà code polinomiali (collezionista: P(T ≥ nH_n + cn) ≤ π²/(6c²)); il metodo del secondo momento dà P(X=0) ≤ Var(X)/E[X]². Algoritmo della mediana: campione di n^(3/4) elementi, due estremi d e u a ±√n, ordinamento dei soli elementi tra d e u; fallisce con probabilità ≤ n^(-1/4) ed è Las Vegas con 2n + o(n) confronti.Momenti e deviazioni - Markov, Chebyshev e mediana randomizzata → (metodo del secondo momento). Il valore atteso dei sottografi nel grafo casuale è trattato in Esercizio - triangoli, vertici isolati e cricche in un grafo casuale.

Testo. Nel grafo casuale $G(n,p)$ ogni coppia di vertici è collegata con probabilità $p$, indipendentemente. $X$ è il numero di triangoli.

1. Calcolare $E[X]$ e, con la formula della varianza di una somma, $\mathrm{Var}(X)$.
2. Per $n=50$ e $p=0{,}01$ limitare $P(X\ge1)$ con Markov.
3. Per $n=50$ e $p=0{,}05$, poi $p=0{,}2$, limitare dal basso $P(X>0)$ con il secondo momento.
4. Perché la soglia è $p\approx1/n$?

Soluzione

1. Media e varianza. $X=\sum_TI_T$ sui $\binom n3$ triangoli $T$ possibili; $I_T=1$ se i $3$ archi sono presenti: $E[I_T]=p^3$, $\mathrm{Var}(I_T)=p^3-p^6$ e $E[X]=\binom n3p^3$. Covarianze: due triangoli distinti hanno in comune al più due vertici, quindi al più un arco.

• Nessun arco in comune: $I_T,I_{T'}$ dipendono da archi diversi, quindi sono indipendenti, covarianza $0$.
• Un arco in comune: gli archi distinti sono $3+3-1=5$, $E[I_TI_{T'}]=p^5$ e $\mathrm{Cov}=p^5-p^6$. Le coppie ordinate $(T,T')$ di questo tipo sono $\binom n2(n-2)(n-3)$: l'arco comune, poi il terzo vertice di $T$ ($n-2$ scelte) e quello di $T'$ (diverso dal primo, $n-3$ scelte).

$$\mathrm{Var}(X)=\binom n3(p^3-p^6)+\binom n2(n-2)(n-3)(p^5-p^6).$$ (Verificata per enumerazione di tutti i grafi: per $n=5$, $p=\frac12$: $E[X]=\frac54$, $\mathrm{Var}(X)=\frac{65}{32}$; $n=5$, $p=\frac15$: $\frac2{25}$ e $\frac{296}{3125}$; $n=6$, $p=\frac13$: $\frac{20}{27}$ e $\frac{880}{729}$.)

2. Markov, $n=50$, $p=0{,}01$. $E[X]=\binom{50}3\cdot10^{-6}=19600\cdot10^{-6}=0{,}0196$. Poiché $X$ è intero, $P(X\ge1)\le E[X]=0{,}0196$ (simulazione: $0{,}017$). Triangoli praticamente assenti. Il secondo momento qui non serve: $\mathrm{Var}(X)/E[X]^2=51{,}7$.

3. Secondo momento.

• $p=0{,}05$: $E[X]=19600\cdot1{,}25\times10^{-4}=2{,}45$. Secondo termine: $\binom{50}2(48)(47)=1225\cdot2256=2\,763\,600$ coppie, per $p^5-p^6=3{,}125\times10^{-7}-1{,}5625\times10^{-8}=2{,}969\times10^{-7}$: $0{,}8205$. Primo termine: $2{,}45(1-1{,}25\times10^{-4})=2{,}4497$. $\mathrm{Var}(X)=3{,}2701$. Allora $E[X^2]=3{,}2701+2{,}45^2=9{,}2726$ e $$P(X>0)\ge\frac{E[X]^2}{E[X^2]}=\frac{6{,}0025}{9{,}2726}=0.647.$$ La simulazione (4000 grafi) dà $P(X>0)=0{,}873$.
• $p=0{,}2$: $E[X]=156{,}8$, $\mathrm{Var}(X)=863{,}0$, rapporto $\mathrm{Var}/E^2=0{,}0351$: $P(X=0)\le0{,}0351$ (Chebyshev) e $P(X>0)\ge0{,}966$. In simulazione non si osserva nessun grafo senza triangoli.

4. Soglia. Per $n$ grande, $\binom n3p^3\approx\frac{n^3p^3}6$ e $\binom n2(n-2)(n-3)\approx\frac{n^4}2$, quindi $$\frac{\mathrm{Var}(X)}{E[X]^2}\approx\frac{6}{n^3p^3}+\frac{n^4p^5/2}{n^6p^6/36}=\frac{6}{(np)^3}+\frac{18}{n^2p}.$$ Se $np\to\infty$ entrambi i termini tendono a $0$ e $P(X=0)\to0$: i triangoli ci sono con probabilità $\to1$. Se $np\to0$ è $E[X]\to0$ e per Markov $P(X\ge1)\to0$. La transizione sta a $p\approx1/n$.

Risultato. $E[X]=\binom n3p^3$; $\mathrm{Var}(X)=\binom n3(p^3-p^6)+\binom n2(n-2)(n-3)(p^5-p^6)$; $n=50$: $p=0{,}01\Rightarrow P(X\ge1)\le0{,}0196$; $p=0{,}05\Rightarrow P(X>0)\ge0{,}647$; $p=0{,}2\Rightarrow P(X>0)\ge0{,}966$.

Verifica.

import math, itertools
from fractions import Fraction as F

def stat(n, p):
    E = math.comb(n, 3) * p**3
    V = E * (1 - p**3) + math.comb(n, 2) * (n - 2) * (n - 3) * (p**5 - p**6)
    return E, V

for p in (0.01, 0.05, 0.2):
    E, V = stat(50, p)
    print(p, E, V, V / E**2, E * E / (V + E * E))

# controllo per enumerazione di tutti i grafi su 5 vertici
n, p = 5, F(1, 2)
edges = list(itertools.combinations(range(n), 2)); idx = {e: i for i, e in enumerate(edges)}
tris = list(itertools.combinations(range(n), 3))
EX = EX2 = F(0)
for mask in range(1 << len(edges)):
    k = bin(mask).count("1"); w = p**k * (1 - p)**(len(edges) - k)
    x = sum(all(mask >> idx[e] & 1 for e in itertools.combinations(t, 2)) for t in tris)
    EX += w * x; EX2 += w * x * x
print(EX, EX2 - EX**2, stat(n, p))                          # 5/4 65/32