Esercizio - Chernoff e i mutui del 2008, perché serve l'indipendenza (lezioni MIT)

Teoria: Limiti di Chernoff e di HoeffdingMarkov applicato a e^(tX) dà code esponenziali. Per somme di Bernoulli indipendenti con media μ: P(X ≥ (1+δ)μ) ≤ [e^δ/(1+δ)^(1+δ)]^μ ≤ e^(-δ²μ/3) per 0<δ≤1, P(X ≤ (1-δ)μ) ≤ e^(-δ²μ/2), P(X ≥ R) ≤ 2^(-R) se R ≥ 6μ. Hoeffding per X_i in [a_i,b_i]: P(|S-E[S]| ≥ t) ≤ 2exp(-2t²/Σ(b_i-a_i)²). Applicazioni: n ≥ ln(2/δ)/(2ε²) campioni per stimare una probabilità, amplificazione BPP con k = O(log 1/ε) ripetizioni, bilanciamento di insiemi con scarto √(4m ln n).Limiti di Chernoff e di Hoeffding → (forma esatta della coda superiore e ipotesi di indipendenza); la varianza di una somma di variabili correlate è in 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 →. Esempio tratto dalle videolezioni di Principles of Discrete Applied Mathematics, MIT OpenCourseWare.

Testo. Un titolo raccoglie $n=1000$ mutui; ogni mutuo va in default con probabilità $p=0{,}1$. La parte più protetta del titolo (la tranche senior) perde denaro solo se vanno in default almeno $400$ mutui. Sia $X$ il numero di default.

1. Supponendo i default indipendenti, limitare $P(X\ge400)$ con la forma esatta di Chernoff. Si può usare la forma $e^{-\delta^2\mu/3}$?
2. Dimostrare che per ogni $\delta>0$ vale anche $P(X\ge(1+\delta)\mu)\le e^{-\mu\delta^2/(2+\delta)}$, usando $\ln(1+x)\ge\frac{2x}{2+x}$ per $x>0$, e calcolare questo limite per $X\ge400$.
3. Modello con un fattore comune: con probabilità $q=0{,}05$ arriva una crisi e ogni mutuo va in default con probabilità $0{,}5$; altrimenti con probabilità $p'$, scelta in modo che la probabilità di default di ogni mutuo resti $0{,}1$. Dati la crisi o la sua assenza, i default sono indipendenti. Calcolare $p'$, la correlazione tra due default e $P(X\ge400)$.
4. Che cosa non va nel calcolo del punto 1?

Soluzione

1. Chernoff sotto indipendenza. $X$ è somma di $1000$ Bernoulli indipendenti con $\mu=E[X]=1000\cdot0{,}1=100$. La soglia $400$ è $(1+\delta)\mu$ con $1+\delta=4$, cioè $\delta=3$. Forma esatta: $$P(X\ge400)\le\Big[\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\Big]^{\mu}=\Big[\frac{e^3}{4^4}\Big]^{100}=\Big[\frac{20{,}086}{256}\Big]^{100}=0{,}07846^{100}.$$ Con i logaritmi: $100\log_{10}0{,}07846=100\cdot(-1{,}1054)=-110{,}5$, quindi il limite vale $\approx\mathbf{3\times10^{-111}}$. La forma $e^{-\delta^2\mu/3}$ non si può usare: è dimostrata solo per $0<\delta\le1$, e qui $\delta=3$. Per confronto, la somma esatta della binomiale $\mathrm{Bin}(1000,0{,}1)$ dà $P(X\ge400)=2{,}1\times10^{-137}$: la soglia è $\frac{400-100}{\sqrt{90}}=31{,}6$ deviazioni standard sopra la media.

2. La forma con $2+\delta$. Prima il lemma: $g(x)=\ln(1+x)-\frac{2x}{2+x}$ ha $g(0)=0$ e $$g'(x)=\frac1{1+x}-\frac{4}{(2+x)^2}=\frac{(2+x)^2-4(1+x)}{(1+x)(2+x)^2}=\frac{x^2}{(1+x)(2+x)^2}\ge0,$$ quindi $g$ cresce e $g(x)\ge0$ per $x>0$. Ora il logaritmo della forma esatta è $\mu\big[\delta-(1+\delta)\ln(1+\delta)\big]$. Con il lemma, $-(1+\delta)\ln(1+\delta)\le-(1+\delta)\frac{2\delta}{2+\delta}$, e $$\delta-\frac{2\delta(1+\delta)}{2+\delta}=\frac{2\delta+\delta^2-2\delta-2\delta^2}{2+\delta}=-\frac{\delta^2}{2+\delta}.$$ Dunque $P(X\ge(1+\delta)\mu)\le e^{-\mu\delta^2/(2+\delta)}$ per ogni $\delta>0$. Per $\delta\le1$ si ha $2+\delta\le3$ e si ritrova $e^{-\delta^2\mu/3}$ (con uguaglianza a $\delta=1$). Per $X\ge400$: $e^{-100\cdot9/5}=e^{-180}=\mathbf{6{,}7\times10^{-79}}$, più debole della forma esatta ($10^{-111}$) ma comunque minuscolo.

3. Fattore comune. La probabilità totale di default di un mutuo è $q\cdot0{,}5+(1-q)p'=0{,}1$, quindi $$p'=\frac{0{,}1-0{,}05\cdot0{,}5}{0{,}95}=\frac{0{,}075}{0{,}95}=0.0789.$$ Correlazione. Per due mutui $i\ne j$, condizionando sullo stato dell'economia: $P(X_i=X_j=1)=q\cdot0{,}5^2+(1-q)p'^2=0{,}0125+0{,}95\cdot0{,}006233=0{,}01842$. Quindi $\mathrm{Cov}(X_i,X_j)=0{,}01842-0{,}1^2=0{,}00842$ e, con $\mathrm{Var}(X_i)=0{,}1\cdot0{,}9=0{,}09$, la correlazione è $\frac{0{,}00842}{0{,}09}=\mathbf{0{,}094}$: piccola. Coda. Per la formula delle probabilità totaliSe (A_i) è una partizione di Ω, P(B) = Σ P(B ∣ A_i) P(A_i) (probabilità totali); la formula di Bayes inverte il condizionamento: P(A_k ∣ B) = P(B ∣ A_k) P(A_k) / P(B).Formula delle probabilità totali e formula di Bayes →: $$P(X\ge400)=q\,P(\mathrm{Bin}(1000,0{,}5)\ge400)+(1-q)\,P(\mathrm{Bin}(1000,0{,}0789)\ge400).$$ Il primo termine è $0{,}05\cdot(1-1{,}2\times10^{-10})$, perché con $p=0{,}5$ la media è $500$; il secondo è $\approx10^{-172}$. Quindi $P(X\ge400)\approx\mathbf{0{,}05}$, contro $10^{-137}$ del modello indipendente. Una simulazione di $200\,000$ portafogli dà $0{,}0498$. Varianza. $\mathrm{Var}(X)=1000\cdot0{,}09+1000\cdot999\cdot0{,}00842=90+8412=8503$ (simulazione $8486$): le $999\,000$ covarianze piccole pesano cento volte più delle $1000$ varianze.

4. Che cosa non va. La media è la stessa nei due modelli ($100$ default), ma Chernoff richiede l'indipendenza di tutte le variabili: è lì che $M_X(t)$ si fattorizza in $\prod_iM_{X_i}(t)$. Con un fattore comune la fattorizzazione cade e la coda diventa enorme anche se ogni coppia di mutui è quasi scorrelata. Senza indipendenza resta solo Chebyshev con la varianza vera: $P(X\ge400)\le\frac{8503}{300^2}=0{,}094$, un limite valido (il valore vero è $0{,}05$), mentre sotto l'ipotesi falsa di indipendenza Chebyshev darebbe $\frac{90}{300^2}=0{,}001$.

Risultato. Sotto indipendenza $P(X\ge400)\le3\times10^{-111}$ (forma esatta, $\delta=3$) e $\le e^{-180}$ (forma $2+\delta$); valore vero $2{,}1\times10^{-137}$. Con un fattore comune (correlazione $0{,}094$) $P(X\ge400)\approx0{,}05$.

Verifica.

import math
import numpy as np
from math import lgamma, log, log1p, exp

def coda(n, p, k):                                      # P(Bin(n,p) >= k) con i logaritmi
    lp = [lgamma(n + 1) - lgamma(j + 1) - lgamma(n - j + 1) + j * log(p) + (n - j) * log1p(-p) for j in range(k, n + 1)]
    m = max(lp); return exp(m) * sum(exp(x - m) for x in lp)

mu, d = 100, 3
print(mu * (d - (1 + d) * log(1 + d)) / log(10), -mu * d * d / (2 + d) / log(10), math.log10(coda(1000, 0.1, 400)))
q, pc = 0.05, 0.5; pn = (0.1 - q * pc) / (1 - q)
cov = q * pc**2 + (1 - q) * pn**2 - 0.01
print(pn, cov / 0.09, q * coda(1000, pc, 400) + (1 - q) * coda(1000, pn, 400), 1000 * 0.09 + 1000 * 999 * cov)
rng = np.random.default_rng(1)
X = rng.binomial(1000, np.where(rng.random(200_000) < q, pc, pn))
print((X >= 400).mean(), X.var())

Risultato: -110.5 -78.2 -136.7 (logaritmi in base $10$ della forma esatta, della forma con $2+\delta$ e del valore vero), poi 0.0789 0.0936 0.05 8503, poi circa 0.0498 8486.