Warum Fakultäten wichtig sind
Hamming beginnt Kapitel 9, indem er bemerkt, dass alle technischen Designprobleme im n-dimensionalen Raum leben, wobei n die unabhängigen Parameter zählt. Um diesen Raum zu verstehen, benötigt man Verständnis von Fakultäten — sie treten in der Volumenformel für jede n-dimensionale Sphäre auf.
Stirling-Approximation
Die direkte Berechnung von n! wird für große n unmöglich. Stirlings Formel gibt eine genaue Approximation:
n! ≈ √(2πn) · (n/e)^n
Logarithmen nehmen (was Hamming tut, um das Produkt in eine Summe umzuwandeln):
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Die Approximation verbessert sich mit wachsendem n: Das Verhältnis Stirling(n)/n! → 1 wenn n → ∞. Doch die absolute Differenz wächst ohne Grenzen. Beide Fakten gelten gleichzeitig.
Hammings Ableitungsweg: approximiere die Summe Σ ln(k) für k=1..n durch das Integral ∫ ln(x) dx von 1 bis n mittels der Trapezregel, dann exponentiiere. Die Konstante √(2π) ergibt sich aus dem Grenzverhalten des Trapezfehlers.
| n | Stirling | Echtes n! | Verhältnis | |---|---|---|---| | 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 |
Stirlings Formel verwenden
Stirlings Logarithmusform erweist sich als besonders nützlich für Verhältnisberechnungen, wobei sich die absolute Größe aufhebt:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Die Gammafunktion
Die Fakultät n! ist nur für nicht-negative ganze Zahlen definiert. Hamming benötigt die Sphärenvolumenformel für alle positiven reellen n, daher führt er die Gammafunktion ein:
Γ(n) = ∫₀^∞ x^(n−1) · e^(−x) dx (konvergent für n > 0)
Partielle Integration ergibt die Reduktionsformel: Γ(n) = (n−1) · Γ(n−1).
Bei positiven ganzen Zahlen: Γ(n) = (n−1)! also Γ(5) = 4! = 24.
Bei den Halbzahlen: Γ(1/2) = √π ≈ 1.772. Dies ergibt sich aus dem Gausschen Integral ∫₋∞^∞ e^(−x²) dx = √π.
Die Werte, die wir für Sphärenvolumina benötigen: Γ(n/2 + 1) bei halbzahligen Argumenten.
| 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 & das Paradoxon
Mit Stirling & Gamma zur Hand leitet Hamming das Volumen einer n-dimensionalen Sphäre mit Radius r her:
V_n(r) = C_n · r^n wobei C_n = π^(n/2) / Γ(n/2 + 1)
Die Konstante C_n hängt nur von n ab, nicht von r. 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 zu einem Maximum nahe n=5 (C_5 ≈ 5.264), fällt dann zurück gegen null. Die Einheitssphäre in sehr hohen Dimensionen hat praktisch kein Volumen — obwohl intuitive Erwartung sagt, dass mehr Dimensionen mehr Platz bedeuten sollte.
Warum zusammenbrechen Volumina?
Der Schlüssel: Volumen = C_n · r^n. Wenn r < 1, dann r^n → 0 exponentiell. Die Radiuseinschränkung tötet das Volumen schneller als die Dimensionalität wächst. Fast das gesamte Volumen des n-dimensionalen Einheitshyperwürfels liegt in seinen Ecken, außerhalb der eingeschriebenen Sphäre.
Das Eckenparadoxon
In 2D: ein Einheitsquadrat [−1,1]^2 hat Fläche 4. Der eingeschriebene Kreis hat Fläche π ≈ 3.14. Der Kreis füllt 78% des Quadrats.
In 3D: der Einheitswürfel [−1,1]^3 hat Volumen 8. Die eingeschriebene Sphäre hat Volumen 4π/3 ≈ 4.19. Die Sphäre füllt 52%.
In n Dimensionen: der Einheitshyperwürfel [−1,1]^n hat Volumen 2^n. Die eingeschriebene Sphäre hat Volumen C_n. Der Bruchteil innerhalb der Sphäre:
f(n) = C_n / 2^n
Mit wachsendem n: C_n → 0 während 2^n → ∞. So f(n) → 0 schnell. In 10D füllt die Sphäre weniger als 0.3% des Würfels.
Technische Konsequenz: in hochdimensionalem Designraum können Sie nicht durch Auswahl zufälliger Punkte Stichproben nehmen. Fast alle zufälligen Punkte landen in Ecken, weit vom Zentrum entfernt. Ihre in 3D gebildete Intuition versagt völlig.
Warum 3D-Intuition versagt
Hammings Kernbotschaft in Kapitel 9: jedes technische System mit n unabhängigen Parametern lebt im n-dimensionalen Raum. Aerodynamik, Steuersysteme, Chip-Design, Arzneimoleküle — alle beinhalten Parameterräume mit n >> 3.
Drei spezifische Versäumnisse der 3D-Intuition in hohen Dimensionen:
1. Diagonalabstände. In 3D hat die Diagonale eines Einheitswürfels Länge √3 ≈ 1.73. In einem n-dimensionalen Einheitshyperwürfel hat die Diagonale Länge √n. Für n=100 beträgt die Diagonallänge 10 — doch jede Koordinate läuft immer noch von 0 bis 1. Punkte, die in einer einzelnen Dimension 'nah beieinander' aussehen, sind im n-dimensionalen Raum weit auseinander.
2. Volumenkonzentration. Wie oben gezeigt: Volumen konzentriert sich in Ecken, nicht in der zentralen Sphäre. Ihre Intuition, dass das Zentrum eines Raums typisch ist, bricht zusammen.
3. Nachbarschaftszählung. In 2D hat ein Punkt ungefähr πr² Nachbarn innerhalb des Radius r. Im nD skaliert die Nachbarschaftszählung wie C_n·r^n, was für großes n effektiv null für kleine r ist. Nachbarschaften zusammenbrechen.
Hammings Fazit: 'Sie können einfach nicht visualisieren, was im n-Raum vor sich geht.' Sie müssen sich auf Mathematik verlassen — auf die Formeln für Volumen, Entfernung & Wahrscheinlichkeit — nicht auf Vorstellungskraft.
Die Geometrie anwenden
Das Zusammenbrechen der Sphärenvolumina hat konkrete Konsequenzen für die moderne Praxis:
Optimierung: Gradientenabstieg in hochdimensionalen Parameterräumen funktioniert besser als Zufallssuche, genau weil er lokale Gradienteninformation nutzt, um durch die Ecken-und-Leere-Struktur zu navigieren.
Machine Learning: Neuronale Netzwerk-Gewichtsräume haben Millionen von Dimensionen. Die Geometrie sagt voraus, dass zufällige Initialisierung selten nahe einer guten Lösung landet — doch der Trainingsprozess navigiert durch strukturierte Gradientenschritte zu einer.
Design von Experimenten: Das Abdecken eines hochdimensionalen Parameterraums mit Stichproben erfordert exponentiell viele Punkte. Dies motiviert strukturierte Experimentdesigns (Latin Hypercubes, raumfüllende Designs) über Zufallsstichproben.