Échelle logarithmique des factorielles
L'approximation de Stirling convertit un produit en une somme, qui est le mouvement fondamental qui rend les mathématiques de grand n tractables :
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Cette formule provient de l'approximation de la somme Σ ln(k) pour k=1..n par l'intégrale de ln(x), puis en appliquant la règle du trapèze pour borner l'erreur.
Pourquoi c'est important géométriquement
La formule du volume de la n-sphère implique Γ(n/2 + 1), qui pour n entier égale (n/2)! ou des produits de demi-entiers. Stirling nous permet d'estimer ces valeurs pour un grand n sans calculer chaque valeur directement.
L'approximation de Stirling donne log(n!) ≈ n·log(n) − n·log(e) en notation base-10, utile pour les estimations d'ordre de grandeur.
Pour n = 10 : ln(10!) ≈ 10·2.303 − 10 + 0.5·ln(62.83) ≈ 23.03 − 10 + 2.08 = 15.10 (vrai : 15.104).
Pour n = 100 : ln(100!) ≈ 100·4.605 − 100 + 0.5·ln(628.3) ≈ 460.5 − 100 + 3.24 = 363.7 (vrai : 363.74).
Stirling pour n=20
Un calcul direct : ln(20) ≈ 2.996. ln(2π·20) = ln(125.66) ≈ 4.833.
La formule du volume
Le volume d'une n-sphère de rayon r dans un espace n-dimensionnel :
V_n(r) = C_n · r^n où C_n = π^(n/2) / Γ(n/2 + 1)
Les valeurs C_n pour les petits n suivent un motif utilisant Γ(1/2) = √π et la formule de réduction :
- 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
Notez : C_n atteint un maximum près de n=5 (≈ 5.264) puis décroît. Pour un grand n, C_n → 0.
Maximum pour n=5
C_5 = 8π²/15. Avec π² ≈ 9.870 :
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
Pour vérifier que c'est un maximum : C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Donc C_6 < C_5 — le pic s'est produit pour n=5.
Fraction du volume dans les coins
Le paradoxe des coins quantifié : quelle fraction d'un hypercube unitaire n-dimensionnel [−1,1]^n se situe en dehors de la sphère inscrite de rayon 1 ?
Fraction des coins = 1 − C_n / 2^n
| n | C_n | 2^n | Fraction de sphère | Fraction de coins | |---|---|---|---|---| | 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% |
Implications pour l'optimisation
Le paradoxe des coins a des conséquences directes pour l'optimisation dans les espaces de haute dimension :
La recherche aléatoire échoue. Un point aléatoire dans un espace de paramètres n-dimensionnel atterrit presque certainement dans un coin — loin de l'origine, avec des valeurs de paramètres extrêmes. Si les bonnes solutions se regroupent près de valeurs de paramètres modérés, la recherche aléatoire ne les trouvera presque jamais.
La descente de gradient réussit. En suivant le gradient local, vous naviguez la géométrie de manière systématique plutôt que de la sampler à l'aveugle. La malédiction de la dimensionnalité frappe les méthodes aléatoires ; les méthodes structurées s'adaptent.
La distance se concentre. En haute dimension, toutes les distances pairwise entre points aléatoires se concentrent autour d'une même valeur : elles deviennent toutes approximativement √(2n/3) pour des points uniformes dans [0,1]^n. Les méthodes de plus proches voisins s'effondrent parce que « le plus proche » et « le plus lointain » deviennent indistinguables.
La prescription de Hamming : comprenez la géométrie avant de faire confiance à votre intuition. Dans les espaces de haute dimension, la géométrie est contre-intuitive, et les mathématiques sont le seul guide fiable.