Scala Logaritmica dei Fattoriali
L'approssimazione di Stirling converte un prodotto in una somma, che è la mossa fondamentale che rende la matematica per grandi n trattabile:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Questa formula nasce dall'approssimazione della somma Σ ln(k) per k=1..n mediante l'integrale di ln(x), quindi applicando la regola del trapezio per limitare l'errore.
Perché Conta Geometricamente
La formula del volume della sfera n-dimensionale coinvolge Γ(n/2 + 1), che per n intero è uguale a (n/2)! o prodotti di semi-interi. Stirling ci permette di stimare questi per n grandi senza calcolare direttamente ogni valore.
L'approssimazione di Stirling fornisce log(n!) ≈ n·log(n) − n·log(e) in notazione in base 10, utile per stime dell'ordine di grandezza.
Per n = 10: ln(10!) ≈ 10·2.303 − 10 + 0.5·ln(62.83) ≈ 23.03 − 10 + 2.08 = 15.10 (vero: 15.104).
Per n = 100: ln(100!) ≈ 100·4.605 − 100 + 0.5·ln(628.3) ≈ 460.5 − 100 + 3.24 = 363.7 (vero: 363.74).
Stirling a n=20
Un calcolo diretto: ln(20) ≈ 2.996. ln(2π·20) = ln(125.66) ≈ 4.833.
La Formula del Volume
Il volume di una sfera n-dimensionale di raggio r:
V_n(r) = C_n · r^n where C_n = π^(n/2) / Γ(n/2 + 1)
I valori di C_n per n piccoli seguono un modello usando Γ(1/2) = √π e la formula di riduzione:
- n=1: C_1 = π^(1/2)/Γ(3/2) = √π/(√π/2) = 2
- n=2: C_2 = π^1/Γ(2) = π/1 = π
- n=3: C_3 = π^(3/2)/Γ(5/2) = π^(3/2)/(3√π/4) = 4π/3
- n=4: C_4 = π²/Γ(3) = π²/2
- n=5: C_5 = π^(5/2)/Γ(7/2) = π^(5/2)/(15√π/8) = 8π²/15
Nota: C_n raggiunge il picco vicino a n=5 (≈ 5.264) poi diminuisce. Per n grandi, C_n → 0.
Massimo a n=5
C_5 = 8π²/15. Con π² ≈ 9.870:
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
Per verificare che questo è un massimo: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Quindi C_6 < C_5 — il picco si è verificato a n=5.
Frazione di Volume negli Angoli
Il paradosso degli angoli quantificato: quale frazione di un ipercubo unitario n-dimensionale [−1,1]^n si trova fuori dalla sfera inscritta di raggio 1?
Corner fraction = 1 − C_n / 2^n
| n | C_n | 2^n | Frazione di sfera | Frazione di angoli | |---|---|---|---|---| | 2 | 3.14 | 4 | 78.5% | 21.5% | | 3 | 4.19 | 8 | 52.4% | 47.6% | | 4 | 4.93 | 16 | 30.8% | 69.2% | | 5 | 5.26 | 32 | 16.4% | 83.6% | | 6 | 5.17 | 64 | 8.1% | 91.9% | | 10 | 2.55 | 1024 | 0.25% | 99.75% |
Implicazioni per l'Ottimizzazione
Il paradosso degli angoli ha conseguenze dirette per l'ottimizzazione negli spazi ad alta dimensione:
La ricerca casuale fallisce. Un punto casuale nello spazio dei parametri n-dimensionale quasi certamente cade in un angolo — lontano dall'origine, con valori di parametri estremi. Se le buone soluzioni si raggruppano vicino ai valori dei parametri moderati, la ricerca casuale raramente le troverà.
La discesa del gradiente ha successo. Seguendo il gradiente locale, navighi la geometria sistematicamente piuttosto che campionarla ciecamente. La maledizione della dimensionalità colpisce i metodi casuali; i metodi strutturati si adattano.
La distanza si concentra. In alte dimensioni, tutte le distanze appaiate tra punti casuali si concentrano attorno allo stesso valore: diventano tutte approssimativamente √(2n/3) per punti uniformi in [0,1]^n. I metodi nearest-neighbor si guastano perché 'più vicino' e 'più lontano' diventano indistinguibili.
La prescrizione di Hamming: comprendi la geometria prima di fidarti della tua intuizione. Negli spazi ad alta dimensione, la geometria è controintuitiva, e la matematica è l'unica guida affidabile.