Warum sind Fakultäten wichtig?
Hamming beginnt im Kapitel 9 mit der Bemerkung, dass alle Ingenieurdesignprobleme im n-dimensionalen Raum leben, wo n die unabhängigen Parameter zählt. Das Verständnis dieses Raums erfordert das Verständnis von Fakultäten - sie erscheinen in der Volumenformel für jede n-dimensionale Kugel.
Stirlingsche Näherung
Die direkte Berechnung von n! wird für große n unmöglich. Stirlingsche Formel gibt eine genaue Näherung:
n! ≈ √(2πn) · (n/e)^n
Indem man die Logarithmen nimmt (was Hamming tut, um das Produkt in eine Summe umzuwandeln):
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Die Näherung verbessert sich mit wachsendem n: das Verhältnis Stirling(n)/n! → 1 als n → ∞. Gleichzeitig wächst jedoch der absolute Unterschied ohne Grenze.
Hamming's Abfolge: approximierte die Summe Σ ln(k) für k=1..n durch die Integral ∫ ln(x) dx von 1 bis n mittels der Trapezzregel, dann die Exponentialfunktion. Die konstante √(2π) entsteht aus der Grenzverhaltens des Trapezzfehlers.
| n | Stirling | True n! | Ratio | |---|---|---|---| | 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 |
Verwendung von Stirlingscher Formel
Stirlingsche Log-Form ist am nützlichsten für Verhältnisberechnungen, bei denen die absolute Skala ausgeglichen wird:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Die Gammafunktion
Das Fakultätszeichen n! hat nur für nichtnegative Ganzzahlen Sinn. Hamming benötigt die Formel für den Kugelvolumen für alle positiven reellen n, daher führt er die Gammafunktion ein:
Γ(n) = ∫₀^∞ x^(n−1) · e^(−x) dx (konvergiert für n > 0)
Die Integration durch Teilung ergibt die Reduktionformel: Γ(n) = (n−1) · Γ(n−1).
Bei positiven Integer: Γ(n) = (n−1)! also Γ(5) = 4! = 24.
Bei den Halbganzzahlen: Γ(1/2) = √π ≈ 1.772. Dies ergibt sich aus der Gauss'schen Integral ∫₋∞^∞ e^(−x²) dx = √π.
Die für Kugelvolumina benötigten Werte: Γ(n/2 + 1) bei Halbganzzahlaragen.
| 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 |
Die Formel und das Paradoxon
Mit Stirlingscher Fakultät und Gammafunktion ableitet Hamming das Volumen einer n-dimensionalen Kugel mit dem Radius r:
V_n(r) = C_n · r^n wobei C_n = π^(n/2) / Γ(n/2 + 1)
Der Konstanten C_n hängt nur von n, nicht von r ab. Die ersten Werte:
| 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 |
Das Paradoxon: C_n steigt bis etwa n=5 (C_5 ≈ 5.264) an, dann fällt es wieder zurück zum Nullwert. Die Einheitskugel in sehr hohen Dimensionen hat praktisch kein Volumen - obwohl man intuitiv mehr Raum hinzufügen sollte, indem man mehr Dimensionen hinzufügt.
Warum kollabiert das Volumen?
Der Schlüssel: Volumen = C_n · r^n. Wenn r < 1, dann r^n → 0 exponentiell. Der Radius-Bedingung schrumpft das Volumen schneller als die Dimensionalität zunimmt. Fast das gesamte Volumen des n-dimensionalen Einheitswürfels liegt in seinen Ecken, außerhalb der einbeschriebenen Kugel.
Das Paradoxon der Ecken
In 2D: Ein Einheitsquadrat [−1,1]^2 hat den Flächeninhalt 4. Der eingeschriebene Kreis hat den Flächeninhalt π ≈ 3,14. Der Kreis füllt 78% des Quadrats.
In 3D: Das Einheitscub [−1,1]^3 hat den Rauminhalt 8. Der eingeschriebene Kugel hat den Rauminhalt 4π/3 ≈ 4,19. Die Kugel füllt 52%.
In n Dimensionen: Das Einheitshypercube [−1,1]^n hat den Rauminhalt 2^n. Die eingeschriebene Kugel hat den Rauminhalt C_n. Der Anteil innerhalb der Kugel:
f(n) = C_n / 2^n
Mit wachsendem n: C_n → 0, während 2^n → ∞. Daher f(n) → 0 schnell. In 10D füllt die Kugel weniger als 0,3% des Cubes.
Folgerung für den Ingenieur: in hochdimensionalen Designschaften kann man nicht willkürlich Punkte auswählen. Fast alle zufällig gewählten Punkte werden in Ecken landen, weit entfernt vom Zentrum. Die Intuition, die man sich in 3D zurechnet, funktioniert nicht mehr.
Warum die 3D-Intuition versagt
Hamming's Kernbotschaft im Kapitel 9: Jedes Ingenieursystem mit n unabhängigen Parametern existiert in n-dimensionalen Raum. Aerodynamik, Steuerungssysteme, Chipdesign, Arzneimoleküle - all das betrifft Parameter-Räume mit n >> 3.
Drei spezifische Versager der 3D-Intuition in hoher Dimension:
1. Diagonale Entfernung. In 3D hat die Diagonale eines Einheitscubes eine Länge von √3 ≈ 1,73. In einem Einheitshypercube in n Dimensionen hat die Diagonale eine Länge von √n. Für n=100 beträgt die Diagonallänge 10 - und trotzdem verlaufen alle Koordinaten zwischen 0 und 1. Punkte, die in einer einzelnen Dimension 'in der Nähe' erscheinen, sind in n-dimensionalen Raum weit entfernt.
2. Volumen-Konzentration. Wie oben gezeigt: das Volumen konzentriert sich in Ecken, nicht im zentralen Kugelbereich. Die Intuition, dass das Zentrum eines Raums typisch ist, stürzt ein.
3. Nachbarn zählen. In 2D hat ein Punkt ungefähr πr² Nachbarn innerhalb des Radius r. In nD steigt die Anzahl der Nachbarn als C_n·r^n, was für große n für kleinen r effektiv null ist. Nachbarschaften kollabieren.
Hamming's Schlussfolgerung: 'Sie können einfach nicht vorstellen, was in n-Raum vorgeht.' Sie müssen auf Mathematik vertrauen - auf die Formeln für Volumen, Distanz und Wahrscheinlichkeit - nicht auf die Vorstellungskraft.
Anwendung der Geometrie
Der Kollaps des Kugelvolumens hat konkrete Folgen für die moderne Praxis:
Optimierung: Gradientenabstiege in hochdimensionalen Parameterspaces funktionieren besser als zufällige Suche, genau weil sie lokale Gradienteninformationen nutzen, um die Ecken-und-Löcher-Struktur zu durchqueren.
Maschinelles Lernen: Gewichtsräume von Neuronalen Netzwerken haben Millionen von Dimensionen. Die Geometrie sagt voraus, dass eine zufällige Initialisierung selten in der Nähe einer guten Lösung landet - aber der Trainingsprozess navigiert durch strukturierte Gradientenschritte hin zu einer.
Experimentenentwurf: Das Abdecken eines hochdimensionalen Parameterspaces mit Proben erfordert exponentiell viele Punkte. Dies motiviert strukturierte experimentelle Designs (lateinische Hyperkuben, räumfüllende Designs) vor zufällige Probenahme.