Logarithmische Skala von Fakultäten
Stirlings Approximation wandelt ein Produkt in eine Summe um, was der grundlegende Schritt ist, der die Mathematik mit großem n handhabbar macht:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Diese Formel ergibt sich aus der Annäherung der Summe Σ ln(k) für k=1..n durch das Integral von ln(x), gefolgt von der Anwendung der Trapezregel zur Begrenzung des Fehlers.
Warum es geometrisch wichtig ist
Die Volumenformel der n-dimensionalen Sphäre beinhaltet Γ(n/2 + 1), die für ganzzahliges n gleich (n/2)! oder Produkte von Halbzahlen ist. Stirling ermöglicht es uns, diese für großes n zu schätzen, ohne jeden Wert direkt zu berechnen.
Stirlings Approximation ergibt log(n!) ≈ n·log(n) − n·log(e) in der Basis-10-Notation, nützlich für Größenordnungsschätzungen.
Für n = 10: ln(10!) ≈ 10·2.303 − 10 + 0.5·ln(62.83) ≈ 23.03 − 10 + 2.08 = 15.10 (wahr: 15.104).
Für n = 100: ln(100!) ≈ 100·4.605 − 100 + 0.5·ln(628.3) ≈ 460.5 − 100 + 3.24 = 363.7 (wahr: 363.74).
Stirling bei n=20
Eine direkte Berechnung: ln(20) ≈ 2.996. ln(2π·20) = ln(125.66) ≈ 4.833.
Die Volumenformel
Das Volumen einer n-dimensionalen Sphäre mit Radius r:
V_n(r) = C_n · r^n where C_n = π^(n/2) / Γ(n/2 + 1)
Die C_n Werte für kleines n folgen einem Muster mit Γ(1/2) = √π und der Reduktionsformel:
- 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
Beachte: C_n erreicht sein Maximum nahe n=5 (≈ 5.264), dann sinkt es. Für großes n, C_n → 0.
Maximum bei n=5
C_5 = 8π²/15. Mit π² ≈ 9.870:
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
Um zu überprüfen, dass dies ein Maximum ist: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Also C_6 < C_5 — das Maximum tritt bei n=5 auf.
Volumenanteil in den Ecken
Das Eckparadoxon quantifiziert: Welcher Anteil eines n-dimensionalen Einheitshyperwürfels [−1,1]^n liegt außerhalb der einbeschriebenen Sphäre mit Radius 1?
Eckenanteil = 1 − C_n / 2^n
| n | C_n | 2^n | Kugelanteil | Eckenanteil | |---|---|---|---|---| | 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% |
Auswirkungen auf Optimierung
Das Eckparadoxon hat direkte Auswirkungen auf die Optimierung in hochdimensionalen Räumen:
Zufallssuche schlägt fehl. Ein Zufallspunkt im n-dimensionalen Parameterraum landet fast sicher in einer Ecke — weit weg vom Ursprung, mit extremen Parameterwerten. Wenn gute Lösungen in der Nähe moderater Parameterwerte konzentriert sind, wird die Zufallssuche sie fast nie finden.
Gradientenabstieg erfolgreich. Durch das Folgen des lokalen Gradienten navigierst du die Geometrie systematisch, anstatt sie blind zu samplen. Der Fluch der Dimensionalität trifft Zufallsmethoden; strukturierte Methoden passen sich an.
Distanz konzentriert sich. In hohen Dimensionen konzentrieren sich alle paarweisen Abstände zwischen Zufallspunkten um denselben Wert: sie werden alle ungefähr √(2n/3) für gleichmäßig verteilte Punkte in [0,1]^n. Nearest-Neighbor-Methoden brechen zusammen, weil 'nächster' und 'fernster' ununterscheidbar werden.
Hammings Rezept: Verstehe die Geometrie, bevor du deiner Intuition vertraust. In hochdimensionalen Räumen ist die Geometrie kontraintuitiv, und die Mathematik ist die einzige zuverlässige Anleitung.