Mengapa Faktorial Penting
Hamming memulai Bab 9 dengan mencatat bahwa semua masalah desain teknik hidup dalam ruang n-dimensi, di mana n menghitung parameter independen. Memahami ruang itu memerlukan pemahaman faktorial — mereka muncul di dalam rumus volume untuk setiap bola n-dimensi.
Aproksimasi Stirling
Menghitung n! secara langsung menjadi mustahil untuk n besar. Rumus Stirling memberikan aproksimasi yang akurat:
n! ≈ √(2πn) · (n/e)^n
Mengambil logaritma (yang Hamming lakukan untuk mengkonversi produk menjadi jumlah):
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Aproksimasi meningkat seiring n berkembang: rasio Stirling(n)/n! → 1 sebagai n → ∞. Namun perbedaan absolut terus tumbuh tanpa batas. Kedua fakta berlaku secara bersamaan.
Rute derivasi Hamming: aproksimasi jumlah Σ ln(k) untuk k=1..n dengan integral ∫ ln(x) dx dari 1 ke n melalui aturan trapesium, kemudian ambil eksponensialnya. Konstanta √(2π) muncul dari perilaku pembatas kesalahan trapesium.
| n | Stirling | n! Sebenarnya | Rasio | |---|---|---|---| | 5 | 118.02 | 120 | 0.9835 | | 10 | 3,598,696 | 3,628,800 | 0.9917 | | 20 | ~2.423×10^18 | ~2.432×10^18 | 0.9958 |
Menggunakan Rumus Stirling
Bentuk logaritma Stirling terbukti paling berguna untuk perhitungan rasio di mana skala absolut hilang:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Fungsi Gamma
Faktorial n! hanya masuk akal untuk bilangan bulat non-negatif. Hamming memerlukan rumus volume bola untuk semua n positif nyata, jadi dia memperkenalkan fungsi Gamma:
Γ(n) = ∫₀^∞ x^(n−1) · e^(−x) dx (konvergen untuk n > 0)
Integrasi per bagian menghasilkan rumus reduksi: Γ(n) = (n−1) · Γ(n−1).
Pada bilangan bulat positif: Γ(n) = (n−1)! jadi Γ(5) = 4! = 24.
Pada setengah-bilangan bulat: Γ(1/2) = √π ≈ 1.772. Ini muncul dari integral Gaussian ∫₋∞^∞ e^(−x²) dx = √π.
Nilai yang kami butuhkan untuk volume bola: Γ(n/2 + 1) pada argumen setengah-bilangan bulat.
| n | n/2 + 1 | Γ(n/2 + 1) | |---|---|---| | 1 | 3/2 | √π/2 ≈ 0.886 | | 2 | 2 | 1! = 1 | | 3 | 5/2 | 3√π/4 ≈ 1.329 | | 4 | 3 | 2! = 2 | | 5 | 7/2 | 15√π/8 ≈ 3.323 |
Rumus & Paradoksnya
Dengan Stirling dan Gamma di tangan, Hamming menurunkan volume bola n-dimensi dengan jari-jari r:
V_n(r) = C_n · r^n di mana C_n = π^(n/2) / Γ(n/2 + 1)
Konstanta C_n hanya bergantung pada n, bukan r. Nilai pertama:
| n | C_n | |---|---| | 1 | 2 | | 2 | π ≈ 3.142 | | 3 | 4π/3 ≈ 4.189 | | 4 | π²/2 ≈ 4.935 | | 5 | 8π²/15 ≈ 5.264 | | 6 | π³/6 ≈ 5.168 | | 8 | π⁴/24 ≈ 4.059 | | 10 | π⁵/120 ≈ 2.550 |
Paradoksnya: C_n naik ke maksimum dekat n=5 (C_5 ≈ 5.264), kemudian turun kembali menuju nol. Bola unit dalam dimensi sangat tinggi pada dasarnya tidak memiliki volume — meskipun secara intuitif menambah lebih banyak dimensi seharusnya menambah lebih banyak ruang.
Mengapa Volume Runtuh?
Kuncinya: volume = C_n · r^n. Ketika r < 1, r^n → 0 secara eksponensial. Batasan jari-jari membunuh volume lebih cepat daripada dimensionalitas berkembang. Hampir semua volume hyperkubus unit n-dimensi terletak di sudut-sudutnya, di luar bola yang tertulis.
Paradoks Sudut
Dalam 2D: persegi unit [−1,1]^2 memiliki luas 4. Lingkaran yang tertulis memiliki luas π ≈ 3.14. Lingkaran mengisi 78% persegi.
Dalam 3D: kubus unit [−1,1]^3 memiliki volume 8. Bola yang tertulis memiliki volume 4π/3 ≈ 4.19. Bola mengisi 52%.
Dalam n dimensi: hyperkubus unit [−1,1]^n memiliki volume 2^n. Bola yang tertulis memiliki volume C_n. Fraksi di dalam bola:
f(n) = C_n / 2^n
Seiring n tumbuh: C_n → 0 sementara 2^n → ∞. Jadi f(n) → 0 dengan cepat. Dalam 10D, bola mengisi kurang dari 0,3% kubus.
Implikasi teknik: dalam ruang desain berdimensi tinggi, Anda tidak dapat mengambil sampel dengan memilih titik acak. Hampir semua titik acak akan mendarat di sudut, jauh dari pusat. Intuisi Anda yang dibangun dalam 3D gagal total.
Mengapa Intuisi 3D Gagal
Pesan inti Hamming dalam Bab 9: setiap sistem teknik dengan n parameter independen hidup dalam ruang n-dimensi. Aerodinamika, sistem kontrol, desain chip, molekul obat — semuanya melibatkan ruang parameter dengan n >> 3.
Tiga kegagalan spesifik intuisi 3D dalam dimensi tinggi:
1. Jarak diagonal. Dalam 3D, diagonal kubus unit memiliki panjang √3 ≈ 1.73. Dalam hyperkubus unit n-dimensi, diagonal memiliki panjang √n. Untuk n=100, panjang diagonal adalah 10 — namun setiap koordinat masih berjalan dari 0 hingga 1. Titik yang terlihat 'dekat' dalam dimensi tunggal apa pun sebenarnya jauh terpisah dalam ruang n-dimensi.
2. Konsentrasi volume. Seperti ditunjukkan di atas: volume berkonsentrasi di sudut, bukan di bola pusat. Intuisi Anda bahwa pusat ruang adalah tipikal runtuh.
3. Perhitungan tetangga. Dalam 2D, titik memiliki kira-kira πr² tetangga dalam jari-jari r. Dalam nD, perhitungan tetangga berskala sebagai C_n·r^n, yang untuk n besar secara efektif nol untuk r kecil. Lingkungan runtuh.
Kesimpulan Hamming: 'Anda tidak dapat memvisualisasikan apa yang terjadi dalam n-space.' Anda harus mengandalkan matematika — pada rumus untuk volume, jarak, dan probabilitas — bukan imajinasi.
Menerapkan Geometri
Kolaps volume bola memiliki konsekuensi konkret untuk praktik modern:
Optimasi: penurunan gradien dalam ruang parameter berdimensi tinggi bekerja lebih baik daripada pencarian acak tepatnya karena memanfaatkan informasi gradien lokal untuk menavigasi struktur sudut-dan-void.
Machine learning: ruang bobot jaringan saraf memiliki jutaan dimensi. Geometri memprediksi bahwa inisialisasi acak jarang mendarat dekat solusi yang baik — namun proses pelatihan menavigasi menuju satu melalui langkah gradien terstruktur.
Desain eksperimen: meliput ruang parameter berdimensi tinggi dengan sampel memerlukan poin yang banyak secara eksponensial. Ini memotivasi desain eksperimental terstruktur (Latin hypercubes, desain space-filling) daripada pengambilan sampel acak.