Mengapa Faktorial Penting
Hamming memulai Bab 9 dengan mengatakan bahwa semua masalah desain teknik hidup di ruang n-dimensional, di mana n menghitung parameter independen. Memahami ruang tersebut membutuhkan pemahaman tentang faktorial — mereka muncul di dalam rumus volume setiap bola n-dimensional.
Persamaan Stirling
Menghitung n! secara langsung menjadi mustahil untuk n besar. Persamaan Stirling memberikan pendekatan yang akurat:
n! ≈ √(2πn) · (n/e)^n
Mengambil logaritma (yang Hamming lakukan untuk mengonversi produk menjadi jumlah):
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Pendekatan ini semakin baik seiring pertumbuhan n: rasio Stirling(n)/n! → 1 sebagai n → ∞. Namun, perbedaan absolut tumbuh tanpa batas. Fakta-fakta ini berlaku secara bersamaan.
Rute derivasi Hamming: mengaproximasi jumlah Σ ln(k) untuk k=1..n dengan integral ∫ ln(x) dx dari 1 ke n melalui aturan trapesium, lalu mengambil eksponen. Konstanta √(2π) berasal dari perilaku batas trapezoid error.
| n | Stirling | True n! | Ratio | |---|---|---|---| | 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 Persamaan Stirling
Bentuk log Stirling terbukti paling berguna untuk penghitungan rasio di mana skala absolut dibatalkan:
ln(n!) ≈ n·ln(n) − n + 0.5·ln(2πn)
Fungsi Gamma
Faktorial n! hanya bermakna untuk bilangan bulat non-negatif. Hamming membutuhkan rumus volume bola untuk semua n positif real, jadi dia memperkenalkan fungsi Gamma:
Γ(n) = ∫₀^∞ x^(n−1) · e^(−x) dx (konvergen untuk n > 0)
Integrasi sebagian memberikan rumus reduksi: Γ(n) = (n−1) · Γ(n−1).
Pada bilangan bulat positif: Γ(n) = (n−1)! jadi Γ(5) = 4! = 24.
Pada setengah-bilangan: Γ(1/2) = √π ≈ 1.772. Ini muncul dari integral Gaussian ∫₋∞^∞ e^(−x²) dx = √π.
Nilai yang kita butuhkan untuk volume bola: Γ(n/2 + 1) pada argumen setengah-bilangan.
| 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 |
Formula & Paradox
Dengan Stirling dan Gamma di tangan, Hamming mendapatkan volume bola n-dimensional dengan jari-jari r:
V_n(r) = C_n · r^n di mana C_n = π^(n/2) / Γ(n/2 + 1)
Konstanta C_n hanya tergantung 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 |
Paradox: C_n naik ke puncak sekitar n=5 (C_5 ≈ 5.264), kemudian kembali ke nol. Bola satuan dalam dimensi tinggi sangat memiliki hampir volume - meskipun secara intuitif menambahkan lebih banyak dimensi harus menambah lebih banyak ruang.
Mengapa Volume Menurun?
Kunci: volume = C_n · r^n. Ketika r < 1, r^n → 0 eksponensial. Konstrain radius membunuh volume lebih cepat daripada pertumbuhan dimensi. Hampir semua volume kubus n-dimensional terletak di sudut-sudutnya, di luar bola yang disisipkan.
Paradox Sudut
Dalam 2D: persegi satuan [−1,1]^2 memiliki luas 4. Lingkaran tersemat memiliki luas π ≈ 3.14. Lingkaran tersebut mengisi 78% dari persegi.
Dalam 3D: kubus satuan [−1,1]^3 memiliki volume 8. Bola tersemat memiliki volume 4π/3 ≈ 4.19. Bola tersebut mengisi 52%.
Dalam n dimensi: hyperkubus satuan [−1,1]^n memiliki volume 2^n. Bola tersemat memiliki volume C_n. Fraksi di dalam bola:
f(n) = C_n / 2^n
Saat n tumbuh: C_n → 0 sementara 2^n → ∞. Jadi f(n) → 0 dengan cepat. Dalam 10D, bola tersebut mengisi kurang dari 0,3% dari kubus.
Implikasi teknik: dalam ruang desain berdimensi tinggi, Anda tidak bisa mengambil sampel secara acak dengan memilih titik-titik acak. Hampir semua titik acak akan mendarat di sudut-sudut, jauh dari pusat. Intuisi Anda yang dibangun dalam 3D gagal sepenuhnya.
Mengapa Intuisi 3D Gagal
Pesan inti Hamming di Bab 9: setiap sistem teknik dengan n parameter independen hidup dalam ruang n-dimensional. Aerodinamika, sistem kendali, desain chip, molekul obat - semua melibatkan ruang parameter dengan n >> 3.
Tiga kegagalan khusus dari intuisi 3D dalam dimensi tinggi:
1. Jarak Diagonal. Dalam 3D, diagonal dari kubus satuan memiliki panjang √3 ≈ 1.73. Dalam hyperkubus satuan unit, diagonal memiliki panjang √n. Untuk n=100, panjang diagonal adalah 10 - namun setiap koordinat masih berjalan dari 0 hingga 1. Titik-titik yang terlihat 'dekat' dalam setiap dimensi jauh di ruang n-dimensional.
2. Konsentrasi Volume. Sebagaimana ditunjukkan di atas: volume berkonsentrasi di sudut, bukan di bola tengah. Intuisi Anda bahwa pusat ruang adalah titik yang umum gagal.
3. Penghitungan Tetangga. Dalam 2D, sebuah titik memiliki sekitar πr² tetangga dalam jari-jari r. Dalam nD, jumlah tetangga berkisar pada C_n·r^n, yang untuk n besar hampir nol untuk r kecil. Daerah tetangga mengalami penggabungan.
Kesimpulan Hamming: 'Anda sederhana tidak dapat menggambarkan apa yang sedang terjadi dalam n-space.' Anda harus mengandalkan matematika — pada rumus volume, jarak, dan kejadian — bukan pada imajinasi.
Aplikasi Geometri
Penggabungan volume bola memiliki konsekuensi konkrit untuk praktek modern:
Optimalisasi: turunan gradien dalam ruang parameter n-dimensional bekerja lebih baik dari pencarian acak tepat karena mengambil keuntungan dari informasi gradien lokal untuk menavigasi struktur sudut-dan-ruang-hampa.
Pembelajaran Mesin: ruang bobot jaringan syaraf memiliki jutaan dimensi. Geometri memprediksi bahwa inisialisasi acak jarang menempatkan solusi yang baik — namun proses pelatihan menavigasi ke satu melalui langkah gradien terstruktur.
Desain eksperimen: menutupi ruang parameter n-dimensional dengan sampel membutuhkan banyak titik yang eksponensial. Ini memicu desain eksperimen yang terstruktur (kubus hipersatelit, desain ruang penuh) daripada pencarian acak.