Logarithmische Skala von Fakultäten
Stirlingsche Näherung wandelt ein Produkt in eine Summe um, was der grundlegende Schritt ist, die großen-n-Mathematik beherrschbar zu machen:
ln(n!) ≈ n·ln(n) − n + 0,5·ln(2πn)
Diese Formel entsteht durch das Näherungsverfahren der Summe Σ ln(k) für k=1..n durch die Integralbildung von ln(x), dann die Trapezzregel zur Fehlerabschätzung anwenden.
Warum ist es geometrisch wichtig?
Die Formel für den Volumen der n-dimensionalen Kugel beinhaltet Γ(n/2 + 1), was für ganze Zahlen n gleich (n/2)! oder Produkte von Halbzahlen ist. Stirling ermöglicht uns diese für große n zu schätzen, ohne jede Wert direkt zu berechnen.
Stirlingsche Näherung gibt log(n!) ≈ n·log(n) − n·log(e) in der Dezimalnotation, nützlich für grob geschätzte Werte.
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 Kugel mit Radius r:
V_n(r) = C_n · r^n wo C_n = π^(n/2) / Γ(n/2 + 1)
Die C_n Werte für kleine n folgen einer Musterbildung mit Γ(1/2) = √π und der Reduktion Formel:
- 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
Achtung: C_n erreicht ein Maximum bei n=5 (≈ 5.264) und nimmt dann ab. Für große n geht C_n zur Null.
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 es sich um ein Maximum handelt: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Also C_6 < C_5 — das Maximum von C_n tritt bei n=5 auf.
Anteil des Volumens in den Ecken
Das Eckenparadox quantifiziert: Was ist der Anteil eines n-dimensionalen Einheitswürfels [−1,1]^n, der außerhalb der einbeschriebenen Kugel mit dem Radius 1 liegt?
Eckenanteil = 1 − C_n / 2^n
| n | C_n | 2^n | Kugelvolumen | Eckenvolumen | |---|---|---|---|---| | 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 für Optimierung
Das Eckenparadoxon hat direkte Folgen für die Optimierung in hochdimensionalen Räumen:
Zufällige Suche schlägt fehl. Ein zufälliger Punkt im n-dimensionalen Parameterspace landet fast sicher in einer Ecke - weit vom Ursprung entfernt, mit extremen Parameterwerten. Wenn gute Lösungen in der Nähe mittlerer Parameterwerte cluster, wird zufällige Suche sie fast nie finden.
Gradientenabstieg gelingt. Indem Sie die lokale Gradientenfolge verfolgen, navigieren Sie die Geometrie systematisch anstelle von blinden Probenahmen. Die Fluch des Dimensionswachstums trifft zufällige Methoden; strukturierte Methoden anpassen sich.
Entfernung konzentriert sich. In hohen Dimensionen konzentriert sich alle paarweisen Entfernungen zwischen zufälligen Punkten um den gleichen Wert: Sie alle werden ungefähr √(2n/3) für Punkte gleichverteilt in [0,1]^n. Näherungsmethoden brechen auf, weil 'nächster' und 'weitester' ununterscheidbar werden.
Hamming's Empfehlung: Verstehen Sie die Geometrie, bevor Sie auf Ihre Intuition vertrauen. In hochdimensionalen Räumen ist die Geometrie widersprüchlich und die Mathematik ist die einzige zuverlässige Richtschnur.