Pourquoi les factorielles sont importantes
Hamming commence le chapitre 9 en notant que tous les problèmes de conception en ingénierie vivent dans un espace n-dimensionnel, où n compte les paramètres indépendants. Comprendre cet espace exige de comprendre les factorielles — elles apparaissent dans la formule du volume de chaque sphère n-dimensionnelle.
L'approximation de Stirling
Calculer n! directement devient impossible pour les grands n. La formule de Stirling donne une approximation précise :
n! ≈ √(2πn) · (n/e)^n
En prenant les logarithmes (ce que Hamming fait pour convertir le produit en une somme) :
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
L'approximation s'améliore à mesure que n augmente : le rapport Stirling(n)/n! → 1 quand n → ∞. Pourtant, la différence absolue augmente sans limite. Les deux faits sont simultanément vrais.
Chemin de dérivation de Hamming : approximer la somme Σ ln(k) pour k=1..n par l'intégrale ∫ ln(x) dx de 1 à n via la règle du trapèze, puis prendre l'exponentielle. La constante √(2π) apparaît du comportement limite de l'erreur du trapèze.
| n | Stirling | n! réel | Rapport | |---|---|---|---| | 5 | 118,02 | 120 | 0,9835 | | 10 | 3 598 696 | 3 628 800 | 0,9917 | | 20 | ~2,423×10^18 | ~2,432×10^18 | 0,9958 |
Utiliser la formule de Stirling
La forme logarithmique de Stirling s'avère très utile pour les calculs de rapports où l'échelle absolue s'annule :
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
La fonction Gamma
La factorielle n! n'a de sens que pour les entiers non négatifs. Hamming a besoin de la formule du volume de la sphère pour tous les n réels positifs, il introduit donc la fonction Gamma :
Γ(n) = ∫₀^∞ x^(n−1) · e^(−x) dx (converge pour n > 0)
L'intégration par parties donne la formule de réduction : Γ(n) = (n−1) · Γ(n−1).
Aux entiers positifs : Γ(n) = (n−1)! donc Γ(5) = 4! = 24.
Aux demi-entiers : Γ(1/2) = √π ≈ 1,772. Cela découle de l'intégrale gaussienne ∫₋∞^∞ e^(−x²) dx = √π.
Les valeurs dont nous avons besoin pour les volumes de sphères : Γ(n/2 + 1) aux arguments demi-entiers.
| n | n/2 + 1 | Γ(n/2 + 1) | |---|---|---| | 1 | 3/2 | √π/2 ≈ 0,886 | | 2 | 2 | 1! = 1 | | 3 | 5/2 | 3√π/4 ≈ 1,329 | | 4 | 3 | 2! = 2 | | 5 | 7/2 | 15√π/8 ≈ 3,323 |
La Formule & le Paradoxe
Avec Stirling et Gamma en main, Hamming dérive le volume d'une sphère n-dimensionnelle de rayon r :
V_n(r) = C_n · r^n où C_n = π^(n/2) / Γ(n/2 + 1)
La constante C_n dépend seulement de n, non de r. Les premières valeurs :
| n | C_n | |---|---| | 1 | 2 | | 2 | π ≈ 3,142 | | 3 | 4π/3 ≈ 4,189 | | 4 | π²/2 ≈ 4,935 | | 5 | 8π²/15 ≈ 5,264 | | 6 | π³/6 ≈ 5,168 | | 8 | π⁴/24 ≈ 4,059 | | 10 | π⁵/120 ≈ 2,550 |
Le paradoxe : C_n atteint un maximum près de n=5 (C_5 ≈ 5,264), puis diminue vers zéro. La sphère unité en très haute dimension a essentiellement aucun volume — même si intuitivement ajouter plus de dimensions devrait ajouter plus d'espace.
Pourquoi le Volume s'Effondre-t-il ?
La clé : volume = C_n · r^n. Quand r < 1, r^n → 0 exponentiellement. La contrainte de rayon tue le volume plus vite que la dimensionnalité augmente. Presque tout le volume de l'hypercube unité n-dimensionnel vit dans ses coins, en dehors de la sphère inscrite.
Le Paradoxe des Coins
En 2D : un carré unité [−1,1]^2 a une aire de 4. Le cercle inscrit a une aire de π ≈ 3,14. Le cercle remplit 78% du carré.
En 3D : le cube unité [−1,1]^3 a un volume de 8. La sphère inscrite a un volume de 4π/3 ≈ 4,19. La sphère remplit 52%.
En n dimensions : l'hypercube unité [−1,1]^n a un volume de 2^n. La sphère inscrite a un volume de C_n. La fraction à l'intérieur de la sphère :
f(n) = C_n / 2^n
À mesure que n augmente : C_n → 0 tandis que 2^n → ∞. Donc f(n) → 0 rapidement. En 10D, la sphère remplit moins de 0,3% du cube.
Implication en ingénierie : en espace de conception haute-dimensionnel, vous ne pouvez pas explorer en échantillonnant des points aléatoires. Presque tous les points aléatoires atterriront dans des coins, loin du centre. Votre intuition construite en 3D échoue complètement.
Pourquoi l'Intuition 3D Échoue
Le message fondamental de Hamming au chapitre 9 : chaque système d'ingénierie avec n paramètres indépendants vit dans un espace n-dimensionnel. L'aérodynamique, les systèmes de contrôle, la conception de puces, les molécules de médicaments — tous impliquent des espaces de paramètres avec n >> 3.
Trois défaillances spécifiques de l'intuition 3D en haute dimension :
1. Distances diagonales. En 3D, la diagonale d'un cube unité a une longueur √3 ≈ 1,73. En hypercube unité n-dimensionnel, la diagonale a une longueur √n. Pour n=100, la longueur de la diagonale est 10 — pourtant chaque coordonnée va toujours de 0 à 1. Les points qui semblent « proches » dans n'importe quelle dimension unique sont loin les uns des autres dans l'espace n-dimensionnel.
2. Concentration du volume. Comme montré ci-dessus : le volume se concentre dans les coins, non dans la sphère centrale. Votre intuition selon laquelle le centre d'un espace est typique s'effondre.
3. Comptage des voisins. En 2D, un point a environ πr² voisins à l'intérieur du rayon r. En nD, le compte de voisins évolue comme C_n·r^n, qui pour grand n est effectivement zéro pour petit r. Les voisinages s'effondrent.
Conclusion de Hamming : « Vous ne pouvez simplement pas visualiser ce qui se passe dans un espace n. » Vous devez vous fier à la mathématique — aux formules pour le volume, la distance, et la probabilité — non à l'imagination.
Appliquer la Géométrie
L'effondrement du volume de la sphère a des conséquences concrètes pour la pratique moderne :
Optimisation : la descente de gradient en espaces de paramètres haute-dimensionnels fonctionne mieux que la recherche aléatoire précisément parce qu'elle exploite les informations de gradient local pour naviguer dans la structure coins-et-vides.
Apprentissage automatique : les espaces de poids des réseaux de neurones ont des millions de dimensions. La géométrie prédit que l'initialisation aléatoire atterrit rarement près d'une bonne solution — pourtant le processus d'entraînement navigue vers l'une via des étapes de gradient structurées.
Conception d'expériences : couvrir un espace de paramètres haute-dimensionnel avec des échantillons exige exponentiellement de nombreux points. Cela motive les conceptions expérimentales structurées (hypercubes latins, conceptions remplissant l'espace) plutôt que l'échantillonnage aléatoire.