Logaritmisk skala för fakulteter
Stirlings approximation konverterar en produkt till en summa, vilket är det fundamentala steget som gör stora-n matematik lösbar:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Denna formel uppstår från approximationen av summan Σ ln(k) för k=1..n med integralen av ln(x), och sedan tillämpar man trapetsregeln för att begränsa felet.
Varför det är geometriskt viktigt
N-dimensionell sfärvolymformeln involverar Γ(n/2 + 1), vilket för heltal n motsvarar (n/2)! eller produkter av halvtal. Stirling låter oss uppskatta dessa för stora n utan att beräkna varje värde direkt.
Stirlings approximation ger log(n!) ≈ n·log(n) − n·log(e) i bas-10-notation, användbar för storleksordningsuppskattningar.
För n = 10: ln(10!) ≈ 10·2.303 − 10 + 0.5·ln(62.83) ≈ 23.03 − 10 + 2.08 = 15.10 (sant: 15.104).
För n = 100: ln(100!) ≈ 100·4.605 − 100 + 0.5·ln(628.3) ≈ 460.5 − 100 + 3.24 = 363.7 (sant: 363.74).
Stirling vid n=20
En direkt beräkning: ln(20) ≈ 2.996. ln(2π·20) = ln(125.66) ≈ 4.833.
Volymformeln
Volymen av en n-dimensionell sfär med radie r:
V_n(r) = C_n · r^n where C_n = π^(n/2) / Γ(n/2 + 1)
C_n-värdena för små n följer ett mönster med Γ(1/2) = √π och reduktionsformeln:
- 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
Observera: C_n toppar nära n=5 (≈ 5.264) och minskar sedan. För stora n, C_n → 0.
Maximum vid n=5
C_5 = 8π²/15. Med π² ≈ 9.870:
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
För att verifiera att detta är ett maximum: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Så C_6 < C_5 — toppen inträffade vid n=5.
Andel volym i hörn
Hörnparadoxen kvantifierad: vilken andel av en n-dimensionell enhetshyperkub [−1,1]^n ligger utanför den inskrivna sfären med radie 1?
Corner fraction = 1 − C_n / 2^n
| n | C_n | 2^n | Sfärfraktion | Hörnfraktion | |---|---|---|---|---| | 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% |
Implikationer för optimering
Hörnparadoxen har direkta konsekvenser för optimering i högdimensionella rum:
Slumpmässig sökning misslyckas. En slumpmässig punkt i n-dimensionellt parameterrum hamnar nästan säkert i ett hörn — långt från origo, med extrema parametervärden. Om bra lösningar samlas nära måttliga parametervärden kommer slumpmässig sökning nästan aldrig att hitta dem.
Gradientnedstigning lyckas. Genom att följa den lokala gradienten navigerar du geometrin systematiskt istället för att samla den blint. Dimensionalitetens förbannelse träffar slumpmässiga metoder; strukturerade metoder anpassas.
Avstånd koncentreras. I höga dimensioner koncentreras alla parvisa avstånd mellan slumpmässiga punkter omkring samma värde: de blir alla ungefär √(2n/3) för punkter enhetligt fördelade i [0,1]^n. Närmaste-granne-metoder bryter samman eftersom 'närmaste' och 'fjärraste' blir oåtskiljbara.
Hammings förskrivning: förstå geometrin innan du litar på din intuition. I högdimensionella rum är geometrin kontraintuiv, och matematiken är den enda pålitliga vägledningen.