Matdis — Bab 6
Peluang Diskrit
Fondasi matematis untuk menganalisis keamanan probabilistik — dari ruang sampel diskrit hingga distribusi yang memodelkan adversary dalam game-based security proofs.
Ref: Rinaldi Munir, Matematika Diskrit, Edisi 7 (2020), Bab 6. — Rosen, Discrete Mathematics, 8th ed., Ch. 7.
Mengapa Peluang Diskrit?
Peluang diskrit menjawab pertanyaan yang muncul terus-menerus di komputasi: berapa peluang dua berkas menghasilkan nilai hash yang sama? Berapa rata-rata percobaan sampai sebuah paket jaringan terkirim? Berapa peluang tabel hash mengalami tabrakan?
Yang membedakannya dari statistik adalah ruang sampelnya berhingga atau terhitung — sisi dadu, bit, simpul graf. Distribusi Bernoulli, Binomial, Geometrik, dan Poisson yang dipelajari di sini adalah alat baku analisis algoritma acak dan sistem antrean.
Analogi: Adversary sebagai Pemain Judi
Dalam keamanan kriptografi, adversary adalah "pemain judi" yang mencoba menebak. Sistem aman jika peluang menangnya tidak jauh dari 1/2 (menebak acak). Distribusi Bernoulli memodelkan setiap "tebakan" — ini tepatnya yang dianalisis dalam game-based security proofs.
1. Ruang Sampel, Kejadian & Peluang
Definisi Dasar
Ruang Sampel (Ω)
Himpunan semua kemungkinan hasil eksperimen.
Lempar dadu: Ω = {1,2,3,4,5,6}
Kejadian (Event)
Subset dari Ω.
A = {2,4,6} (genap)
Peluang
P(A) = |A| / |Ω| untuk ruang sampel uniform.
P(genap) = 3/6 = 1/2
Sifat-Sifat Peluang (Aksioma Kolmogorov)
0 ≤ P(A) ≤ 1 (non-negatif)
P(Ω) = 1 (normalitas)
P(A ∪ B) = P(A) + P(B) jika A ∩ B = ∅
P(Ā) = 1 − P(A)
P(A ∪ B) = P(A)+P(B)−P(A∩B)
P(∅) = 0
Jika A ⊆ B, maka P(A) ≤ P(B)
2. Peluang Kondisional & Kemerdekaan
Definisi & Formula
Peluang Kondisional
P(B|A) = P(A∩B) / P(A)
"Peluang B terjadi, diketahui A sudah terjadi." P(A) > 0.
Kemerdekaan
A dan B merdeka jika:
P(A∩B) = P(A)·P(B)
Ekivalen: P(B|A) = P(B).
Demo Interaktif: Peluang Kondisional
P(A)
0.50
P(A ∩ B)
0.30
P(B | A) = P(A∩B)/P(A)
0.60
3. Teorema Bayes
Teorema Bayes
P(A|B) = P(B|A) · P(A) / P(B)
Di mana P(B) = P(B|A)·P(A) + P(B|Ā)·P(Ā) — Total Probability.
Posterior P(A|B) = memperbarui prior P(A) berdasarkan bukti B. Fondasi Bayesian inference dan Bayesian cryptanalysis.
Demo Bayes: Tes Diagnostik
P(Penyakit | Tes Positif) =
16.67%
Hasil sering mengejutkan! Penyakit langka → tes positif bisa misleading.
Visualisasi SMIL: Update Bayesian
4. Variabel Acak Diskrit
Definisi & Momen
Variabel acak diskrit X adalah fungsi X: Ω → ℝ yang nilainya countable. Probability Mass Function (PMF): p(x) = P(X=x).
Nilai Ekspektasi (Mean)
E[X] = Σ x · P(X=x)
Rata-rata jangka panjang.
Varians
Var(X) = E[X²] - (E[X])²
Ukuran penyebaran dari mean.
Linearitas Ekspektasi
E[aX+b] = aE[X]+b
E[X+Y] = E[X]+E[Y]
5. Distribusi Diskrit
Eksplorasi Interaktif: Distribusi Diskrit
E[X] (Mean)
4.000
Var(X) (Varians)
2.400
Ringkasan Distribusi Diskrit
| Distribusi | PMF | E[X] | Var(X) | Aplikasi |
|---|---|---|---|---|
| Bernoulli(p) | pˣ(1-p)¹⁻ˣ | p | p(1-p) | Satu percobaan berhasil/gagal; lempar koin |
| Binomial(n,p) | C(n,k)pᵏ(1-p)ⁿ⁻ᵏ | np | np(1-p) | Jumlah bit errors; flipping attacks |
| Geometrik(p) | (1-p)ᵏ⁻¹p | 1/p | (1-p)/p² | Percobaan hingga sukses; time to collision |
| Poisson(λ) | e⁻ᵏλᵏ/k! | λ | λ | Arrival rate; network attacks per hour |
6. Kovarians & Korelasi
Definisi Kovarians
Cov(X,Y) = E[XY] − E[X]E[Y]
Interpretasi
- Cov > 0: X dan Y cenderung meningkat bersama
- Cov < 0: X naik ketika Y turun
- Cov = 0: tidak berkorelasi (perlu merdeka untuk lebih kuat)
Properti
Var(X+Y) = Var(X)+Var(Y)+2Cov(X,Y)
Jika X⊥Y: Cov=0, Var(X+Y)=Var(X)+Var(Y)
Dipakai saat menganalisis beberapa percobaan yang saling bebas, misalnya paket jaringan yang hilang secara independen.
7. Aplikasi: Peluang dalam Sistem Komputer
Peluang dalam Analisis Algoritma
Teorema Bayes dalam Kriptoanalisis: Distinguisher statistik menggunakan Bayes untuk membedakan distribusi kunci. Differential cryptanalysis dan correlation attacks pada cipher bergantung pada Bayesian inference.
Peluang pada Hash Collision: Approximasi Poisson untuk birthday attacks: Pr[collision setelah k queries] ≈ 1 - e^(-k²/2N) di mana N = ukuran output space.
8. Contoh Soal & Pembahasan
Soal 1: Ruang Sampel
Dua dadu dilempar. Berapa P(jumlah = 7)?
Soal 2: Peluang Kondisional
P(A)=0.4, P(B)=0.3, P(A∩B)=0.12. Apakah A dan B merdeka?
Soal 3: Teorema Bayes
Penyakit rare dengan P(D)=0.001. Tes punya P(+|D)=0.99, P(+|¬D)=0.05. Jika tes positif, berapa P(D|+)?
Soal 4: Distribusi Binomial
Sebuah bit channel punya error probability p=0.1. Dalam 5 bit, berapa P(tepat 2 error)?
Soal 5: Nilai Ekspektasi
X memodelkan nilai dadu adil {1,...,6}. Hitung E[X] dan Var(X).
Soal 6: Selisih dari Tebakan Acak
Sebuah detektor menebak label biner. Penebak acak murni benar dengan peluang 1/2. Jika sebuah detektor benar dengan peluang 3/4, berapa keunggulannya (advantage) di atas tebakan acak?
Bank Soal Multi-Kompleksitas & Kasus Terintegrasi
Referensi: Munir, R. (2020). Matematika Diskrit, Edisi 7, Bab 6 — Peluang Diskrit.
MUDAH Soal Dasar Probabilitas
P-M1: Ruang Sampel & Peluang Klasik
Sebuah dadu adil dilempar sekali. Tentukan ruang sampel S, peluang muncul bilangan genap, dan peluang muncul bilangan > 4.
P-M2: Distribusi Binomial
Sebuah koin adil dilempar 5 kali. Berapa P(tepat 3 kali Heads)?
P-M3: Peluang Komplemen
P(A) = 0.3, P(B) = 0.5, A dan B mutually exclusive. Hitung P(A∪B) dan P((A∪B)').
P-M4: Nilai Ekspektasi
Sebuah permainan: menang Rp10.000 dengan p=0.4, kalah Rp5.000 dengan p=0.6. Hitung E[X] (expected value).
SEDANG Probabilitas Bersyarat & Teorema Bayes
P-S1: Peluang Bersyarat
Sebuah kotak berisi 3 merah dan 2 biru. Dua bola diambil tanpa pengembalian. Hitung P(kedua merah) dan P(bola ke-2 merah | bola ke-1 merah).
P-S2: Teorema Bayes — Tes Medis
Prevalensi penyakit 1%. Tes positif jika sakit: 95%. Tes positif jika sehat (false positive): 5%. Seseorang tes positif — berapa P(sakit|positif)?
P-S3: Distribusi Geometrik
Seorang hacker mencoba password brute force. Tiap percobaan berhasil dengan p=0.001. Berapa probabilitas berhasil pada percobaan ke-1000? Berapa E[X] percobaan?
P-S4: Independensi & Variabel Acak
X dan Y independen. X ~ Bernoulli(0.6), Y ~ Bernoulli(0.4). Hitung P(X=1, Y=1), E[X+Y], dan Var(X+Y).
SULIT Probabilitas Lanjut
P-H1: Birthday Problem (Hash Collision)
Berapa banyak orang minimal dalam sebuah ruangan agar P(setidaknya 2 orang ulang tahun sama) > 50%? Gunakan approximasi eksponensial.
P-H2: Markov Inequality & Chebyshev
Variabel acak X memiliki E[X]=10 dan Var(X)=4. Gunakan (a) Markov untuk bound P(X≥30), dan (b) Chebyshev untuk bound P(|X-10|≥6).
P-H3: Generating Function Sederhana
X ~ Binomial(n=3, p=0.5). Hitung probability generating function G_X(z) = E[z^X]. Gunakan G_X untuk verifikasi E[X] dan Var(X).
TERINTEGRASI Peluang + Kombinatorika & Graf
P-T1: Bayes + Kombinatorika — Random Key Selection
Kotak A berisi 3 kunci valid dan 2 tidak valid. Kotak B berisi 1 valid dan 4 tidak valid. Dipilih kotak secara acak (50-50), lalu diambil 1 kunci. Kunci ternyata valid. Berapa P(dari kotak A)?
P-T2: Peluang + Graf — Random Walk
Random walk pada graf path P₃ = (v1−v2−v3). Mulai di v2. Tiap langkah: pindah ke tetangga secara seragam. Berapa P(di v1 setelah 2 langkah)?
P-T3: Peluang + Jarak Statistik antar Distribusi
Distribusi P = {1/4, 1/4, 1/4, 1/4} (uniform) dan Q = {1/2, 1/4, 1/8, 1/8}. Hitung statistical distance (total variation distance) SD(P,Q). Jika SD > negl(λ), apakah skema crypto aman secara statistik?