Logaritmische schaal van faculteiten
Stirlings benadering converteert een product naar een som, wat de fundamentele stap is die grote-n wiskunde hanteerbaar maakt:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Deze formule ontstaat door de som Σ ln(k) voor k=1..n te benaderen door de integraal van ln(x), vervolgens de trapeziumregel toe te passen om de fout te begrenzen.
Waarom het geometrisch uitmaakt
De volumeformule van de n-dimensionale bol betreft Γ(n/2 + 1), wat voor geheel getal n gelijk is aan (n/2)! of producten van half-gehele getallen. Stirlings benadering laat ons deze voor grote n schatten zonder elke waarde direct te berekenen.
Stirlings benadering geeft log(n!) ≈ n·log(n) − n·log(e) in grondtal-10 notatie, nuttig voor orde-van-grootte schattingen.
Voor n = 10: ln(10!) ≈ 10·2.303 − 10 + 0.5·ln(62.83) ≈ 23.03 − 10 + 2.08 = 15.10 (juist: 15.104).
Voor n = 100: ln(100!) ≈ 100·4.605 − 100 + 0.5·ln(628.3) ≈ 460.5 − 100 + 3.24 = 363.7 (juist: 363.74).
Stirling bij n=20
Een directe berekening: ln(20) ≈ 2.996. ln(2π·20) = ln(125.66) ≈ 4.833.
De volumeformule
Het volume van een n-dimensionale bol met straal r:
V_n(r) = C_n · r^n where C_n = π^(n/2) / Γ(n/2 + 1)
De C_n waarden voor kleine n volgen een patroon met Γ(1/2) = √π en de reductieformule:
- 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
Opmerking: C_n bereikt een maximum dicht bij n=5 (≈ 5.264) en daalt daarna. Voor grote n, C_n → 0.
Maximum bij n=5
C_5 = 8π²/15. Met π² ≈ 9.870:
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
Om te verifiëren dat dit een maximum is: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Dus C_6 < C_5 — het maximum trad op bij n=5.
Fractie van het volume in de hoeken
Het hoekparadox gekwantificeerd: welk deel van een n-dimensionale eenheidshyperkubus [−1,1]^n ligt buiten de ingeschreven bol met straal 1?
Corner fraction = 1 − C_n / 2^n
| n | C_n | 2^n | Bolfractie | Hoekfractie | |---|---|---|---|---| | 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% |
Implicaties voor optimalisering
Het hoekparadox heeft directe gevolgen voor optimalisering in hoog-dimensionale ruimten:
Willekeurig zoeken faalt. Een willekeurig punt in n-dimensionale parameterruimte landet vrijwel zeker in een hoek — ver van de oorsprong, met extreme parameterwaarden. Als goede oplossingen zich dicht bij gematigde parameterwaarden bevinden, zal willekeurig zoeken ze bijna nooit vinden.
Gradiëntdaling slaagt. Door de lokale gradiënt te volgen, navigeer je de meetkunde systematisch in plaats van het blindelings te bemonsteren. De vloek van dimensionaliteit treft willekeurige methoden; gestructureerde methoden passen zich aan.
Afstand concentreert. In hoge dimensies concentreren alle paarsgewijze afstanden tussen willekeurige punten zich rond dezelfde waarde: ze worden allemaal ongeveer √(2n/3) voor punten uniform in [0,1]^n. Nearest-neighbor methoden falen omdat 'dichtstbijzijnd' en 'verst verwijderd' ononderscheidbaar worden.
Hammings advies: begrip de meetkunde voordat je je intuïtie vertrouwt. In hoog-dimensionale ruimten is de meetkunde fundamenteel contra-intuïtief, en wiskunde is de enige betrouwbare gids.