Probabilitas adalah bahasa untuk berbicara tentang ketidakpastian — termasuk ketidakpastian dalam algoritma yang menggunakan random (randomized algorithms). Analisis expected time randomized quicksort, hashing universal, dan sampling semuanya bergantung pada konsep dasar: sample space, event, conditional probability, dan expected value. Pada Chapter ini kita mendefinisikan fondasi probabilitas diskrit dan memverifikasinya lewat simulasi Monte Carlo di C++.

Sample Space dan Event #

Aturan #

  • Sample space Ω: himpunan semua hasil mungkin suatu eksperimen. Contoh: lempar dadu 6-sisi → Ω = {1, 2, 3, 4, 5, 6}.
  • Event A ⊆ Ω: subset hasil yang kita minati. Contoh: “muncul angka ganjil” → A = {1, 3, 5}.
  • Probabilitas P(A) = |A| / |Ω| bila semua outcome equally likely. Untuk dadu: P(ganjil) = 3/6 = 0.5.

Mekanisme: Aksioma Kolmogorov #

Tiga aksioma yang harus dipenuhi setiap fungsi probabilitas:

  1. P(A) ≥ 0 untuk semua event A.
  2. P(Ω) = 1.
  3. Bila A₁, A₂, ... saling mutually exclusive (Aᵢ ∩ Aⱼ = ∅ untuk i ≠ j), maka P(A₁ ∪ A₂ ∪ ...) = Σ P(Aᵢ).

Dari tiga aksioma ini, semua aturan probabilitas lain (penjumlahan, conditional, Bayes) dapat diturunkan.

Operasi Probabilitas #

Aturan #

text 
Komplement  : P(A^c) = 1 - P(A)                              (A^c = bukan A)
Union        : P(A ∪ B) = P(A) + P(B) - P(A ∩ B)
Intersection (independent): P(A ∩ B) = P(A) · P(B)

Mekanisme: Mengapa Union Dikurangi Irisan #

Bila kita jumlahkan P(A) + P(B), bagian A ∩ B dihitung dua kali (sekali sebagai bagian A, sekali sebagai bagian B). Untuk koreksi, kurangi sekali P(A ∩ B). Inilah formula inclusion-exclusion yang sudah diperkenalkan di Chapter Combinatorics , sekarang diterapkan pada probabilitas.

Probabilitas Kondisional #

Aturan #

Probabilitas A terjadi dengan syarat B sudah terjadi:

text 
P(A | B) = P(A ∩ B) / P(B)         (asumsi P(B) > 0)

Contoh dadu: P(sisi > 3 | genap). Irisan A ∩ B = {4, 6} (sisi yang genap dan > 3). P(A ∩ B) = 2/6. P(B) = 3/6 (genap = {2, 4, 6}). Maka P(A | B) = (2/6) / (3/6) = 2/3 ≈ 0.667.

Mekanisme: Bayes’ Theorem #

Rumus Bayes membalik arah conditional:

text 
P(B | A) = P(A | B) · P(B) / P(A)

Aplikasi: diagnosis medis (peluang penyakit diberikan tes positif), spam filter (peluang spam diberikan kata-kata tertentu), machine learning naive Bayes.

Independensi #

Aturan #

Dua event A, B independen bila P(A ∩ B) = P(A) · P(B), equivalently P(A | B) = P(A). Pengetahuan bahwa B terjadi tidak mengubah peluang A.

Contoh: lempar dua dadu, hasil dadu pertama independen terhadap hasil dadu kedua.

Expected Value #

Aturan #

Expected value (nilai harapan) variabel acak X:

text 
E[X] = Σ_x x · P(X = x)

Untuk dadu 6-sisi seragam: E[X] = (1+2+3+4+5+6)/6 = 3.5.

Mekanisme: Linearitas Ekspektasi #

Sifat penting: E[X + Y] = E[X] + E[Y] bahkan bila X, Y tidak independen. Ini sering menjadi trik elegan dalam analisis algoritma — kita tidak perlu tahu distribusi gabungan.

Implementasi: Simulasi Monte Carlo #

Kode: Lempar Dadu dan Verifikasi Teori #

cpp 
#include <iostream>
#include <random>
#include <vector>

// Demo probabilitas diskrit
// Simulasi: lempar dadu 6-sisi N kali, hitung frekuensi tiap sisi
int main() {
    const int N = 1'000'000;
    std::mt19937 rng(12345);
    std::uniform_int_distribution<int> dice(1, 6);

    std::vector<int> count(7, 0);
    for (int i = 0; i < N; ++i) {
        count[dice(rng)]++;
    }

    std::cout << "Simulasi lempar dadu " << N << " kali:\n";
    for (int s = 1; s <= 6; ++s) {
        double emp = (double)count[s] / N;
        std::cout << "  Sisi " << s << ": count=" << count[s]
                  << "  empirical=" << emp
                  << "  expected=0.16667\n";
    }

    // Probability: P(ganjil) = P(1)+P(3)+P(5) = 3/6 = 0.5
    int odd_count = count[1] + count[3] + count[5];
    std::cout << "\nP(ganjil) empirical = " << (double)odd_count / N
              << " (expected 0.5)\n";

    // Conditional: P(sisi > 3 | sisi genap)
    // = P(sisi > 3 ∩ sisi genap) / P(sisi genap)
    // = P(4 atau 6) / P(2 atau 4 atau 6) = (1/3) / (1/2) = 2/3
    int even_count = count[2] + count[4] + count[6];
    int even_gt3 = count[4] + count[6];
    std::cout << "P(sisi>3 | genap) empirical = "
              << (double)even_gt3 / even_count << " (expected 0.66667)\n";

    // Expected value: E[X] untuk dadu = (1+2+3+4+5+6)/6 = 3.5
    double sum = 0;
    for (int s = 1; s <= 6; ++s) sum += (double)s * count[s];
    std::cout << "E[X] empirical = " << sum / N << " (expected 3.5)\n";

    return 0;
}

Output yang Dihasilkan:

text 
Simulasi lempar dadu 1000000 kali:
  Sisi 1: count=167056  empirical=0.167056  expected=0.16667
  Sisi 2: count=166576  empirical=0.166576  expected=0.16667
  Sisi 3: count=166490  empirical=0.16649  expected=0.16667
  Sisi 4: count=166838  empirical=0.166838  expected=0.16667
  Sisi 5: count=167023  empirical=0.167023  expected=0.16667
  Sisi 6: count=166017  empirical=0.166017  expected=0.16667

P(ganjil) empirical = 0.500569 (expected 0.5)
P(sisi>3 | genap) empirical = 0.666468 (expected 0.66667)
E[X] empirical = 3.49825 (expected 3.5)
  1. Baris std::mt19937 rng(12345);: Mersenne Twister PRNG dengan seed deterministik — output reproducible antar run.
  2. Baris std::uniform_int_distribution<int> dice(1, 6);: distribusi seragam di [1, 6]. Setiap sisi memiliki peluang teoretis 1/6 ≈ 0.16667.
  3. Baris count[dice(rng)]++;: lempar dadu sekali, inkrementasi counter sisi yang muncul.
  4. Hasil empirical ≈ 0.1666 per sisi: dengan N = 1.000.000 lemparan, hukum bilangan besar menyatakan frekuensi empiris konvergen ke probabilitas teoretis 1/6. Penyimpangan ~0.001 normal.
  5. Baris int odd_count = count[1] + count[3] + count[5];: hitung frekuensi event “ganjil” dengan menjumlahkan count untuk sisi 1, 3, 5. Event ganjil adalah union dari tiga outcome mutually exclusive — P(ganjil) = P(1) + P(3) + P(5) sesuai aksioma Kolmogorov.
  6. Hasil P(ganjil) empirical = 0.5006: konvergen ke 3/6 = 0.5. Sesuai teori.
  7. Baris even_gt3 / even_count: implementasi langsung dari P(A | B) = P(A ∩ B) / P(B). even_gt3 = count[4] + count[6] (sisi yang genap DAN > 3), even_count = count[2] + count[4] + count[6] (semua sisi genap).
  8. Hasil P(sisi>3 | genap) ≈ 0.6665: konvergen ke 2/3 ≈ 0.6667. Sesuai.
  9. Baris sum += (double)s * count[s];: implementasi E[X] = Σ x · P(X = x). Dengan P(X = s) ≈ count[s] / N, sum menjadi Σ s · count[s] / N.
  10. Hasil E[X] empirical = 3.498: konvergen ke 3.5. Sesuai.

Aplikasi: Analisis Randomized Quicksort #

Aturan #

Randomized quicksort memilih pivot secara acak dari subarray. Waktu rata-rata O(n log n) walaupun worst case O(n²) bila selalu pivot jelek.

Mekanisme: Ekspektasi via Linearitas #

Misalkan T(n) adalah ekspektasi banyak perbandingan. Dengan probabilitas 1/n bahwa pivot adalah elemen ke-i terkecil, kita dapat relasi rekurens:

text 
T(n) = (n - 1) + (1/n) Σ_{k=0}^{n-1} [T(k) + T(n-1-k)]

Bisa dibuktikan via induksi bahwa T(n) ≤ 2(n+1) H_n ≈ 2n ln n — yaitu O(n log n). Trik kuncinya: E[Σ] = Σ E, tidak peduli ketergantungan antar iterasi.

Ringkasan #

  • Sample space Ω, event A ⊆ Ω, P(A) = |A|/|Ω| bila seragam.
  • Aksioma Kolmogorov: non-negatif, P(Ω) = 1, aditif untuk event mutually exclusive.
  • Union: P(A ∪ B) = P(A) + P(B) - P(A ∩ B) (koreksi over-counting).
  • Conditional: P(A | B) = P(A ∩ B) / P(B). Bayes membalik arah.
  • Independensi: P(A ∩ B) = P(A) · P(B).
  • Expected value: E[X] = Σ x · P(X = x). Linearitas E[X + Y] = E[X] + E[Y] berlaku tanpa syarat independensi.
  • Simulasi Monte Carlo: konvergensi O(1/√N) — verifikasi teori secara empiris.