Skala Logaritma Faktorial
Aproksimasi Stirling mengubah produk menjadi penjumlahan, yang merupakan langkah fundamental yang membuat matematika untuk n-besar dapat dikelola:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Rumus ini muncul dari aproksimasi jumlah Σ ln(k) untuk k=1..n dengan integral dari ln(x), kemudian menerapkan aturan trapesium untuk membatasi kesalahan.
Mengapa Ini Penting Secara Geometris
Rumus volume n-sphere dimensi melibatkan Γ(n/2 + 1), yang untuk n bulat sama dengan (n/2)! atau produk setengah-bilangan bulat. Stirling memungkinkan kami memperkirakan ini untuk n-besar tanpa menghitung setiap nilai secara langsung.
Aproksimasi Stirling memberikan log(n!) ≈ n·log(n) − n·log(e) dalam notasi basis-10, berguna untuk perkiraan orde-besaran.
Untuk n = 10: ln(10!) ≈ 10·2.303 − 10 + 0.5·ln(62.83) ≈ 23.03 − 10 + 2.08 = 15.10 (benar: 15.104).
Untuk n = 100: ln(100!) ≈ 100·4.605 − 100 + 0.5·ln(628.3) ≈ 460.5 − 100 + 3.24 = 363.7 (benar: 363.74).
Stirling pada n=20
Perhitungan langsung: ln(20) ≈ 2.996. ln(2π·20) = ln(125.66) ≈ 4.833.
Rumus Volume
Volume n-dimensional sphere dengan jari-jari r:
V_n(r) = C_n · r^n di mana C_n = π^(n/2) / Γ(n/2 + 1)
Nilai C_n untuk n kecil mengikuti pola menggunakan Γ(1/2) = √π & rumus reduksi:
- 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
Perhatian: C_n mencapai puncak di dekat n=5 (≈ 5.264) kemudian menurun. Untuk n besar, C_n → 0.
Maksimum pada n=5
Perhitungan langsung: C_5 = 8π²/15. Dengan π² ≈ 9.870:
C_5 = 8·9.870/15 = 78.96/15 ≈ 5.264
Untuk memverifikasi ini adalah maksimum: C_6 = π³/6 ≈ 31.006/6 ≈ 5.168. Jadi C_6 < C_5 — puncak terjadi pada n=5.
Fraksi Volume di Sudut
Paradoks sudut terkuantifikasi: fraksi berapa dari unit hypercube n-dimensional [−1,1]^n yang terletak di luar sphere tertulis dengan jari-jari 1?
Fraksi sudut = 1 − C_n / 2^n
| n | C_n | 2^n | Fraksi Sphere | Fraksi Sudut | |---|---|---|---|---| | 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% |
Implikasi untuk Optimasi
Paradoks sudut memiliki konsekuensi langsung untuk optimasi dalam ruang dimensi tinggi:
Pencarian acak gagal. Titik acak dalam ruang parameter n-dimensi hampir pasti mendarat di sudut — jauh dari asal, dengan nilai parameter ekstrem. Jika solusi yang baik berkumpul di dekat nilai parameter moderat, pencarian acak hampir tidak akan pernah menemukannya.
Penurunan gradien berhasil. Dengan mengikuti gradien lokal, anda menavigasi geometri secara sistematis daripada mengambilnya sampelnya secara buta. Kutukan dimensionalitas menimpa metode acak; metode terstruktur beradaptasi.
Jarak terkonsentrasi. Dalam dimensi tinggi, semua jarak pasangan antara titik acak berkonsentrasi di sekitar nilai yang sama: semuanya menjadi kira-kira √(2n/3) untuk titik seragam dalam [0,1]^n. Metode nearest-neighbor putus karena 'terdekat' & 'terjauh' menjadi tidak dapat dibedakan.
Resep Hamming: pahami geometri sebelum mempercayai intuisi anda. Dalam ruang dimensi tinggi, geometri adalah tidak intuitif, & matematika adalah satu-satunya panduan yang dapat diandalkan.