Counting, Sets & Axioms of Probability

Fondasi Formal Teori Probabilitas

Why This Matters for Your Work

Probabilitas adalah bahasa uncertainty dalam statistik dan ML. Sebelum bisa bicara tentang distribusi, estimator, atau inference, kita perlu fondasi formal yang rigorous.

Kolmogorov’s axioms memberikan fondasi itu — tiga aturan sederhana yang dari sana kita bisa menurunkan semua hasil dalam teori probabilitas, dari basic rules sampai convergence theorems dan asymptotic theory.

Lebih konkret: - Counting methods adalah basis untuk menghitung probabilitas di ruang sampel diskrit — penting untuk kombinatorik dalam uji statistik - Inclusion-exclusion principle muncul langsung di Bonferroni correction untuk multiple testing — sesuatu yang sangat relevan saat kamu jalankan banyak hipotesis sekaligus - Set theory notation adalah bahasa yang dipakai di seluruh literatur statistik dan ML

1 1. Set Theory Review

1.1 Sample Space dan Events

Dalam teori probabilitas formal, kita mulai dari:

Sample space $\Omega$: himpunan semua outcome yang mungkin dari suatu eksperimen
Event $A$: subset dari $\Omega$, yaitu $A \subseteq \Omega$
Elementary outcome $\omega \in \Omega$: satu outcome spesifik

Contoh: - Lempar koin sekali: $\Omega = \{H, T\}$ - Lempar dua koin: $\Omega = \{HH, HT, TH, TT\}$ - Nilai saham besok: $\Omega = \mathbb{R}_{>0}$ (continuous!) - Jumlah pengangguran: $\Omega = \{0, 1, 2, \ldots\}$

Event $A$ = “dapat kepala di lemparan pertama” = $\{HH, HT\}$.

1.2 Operasi pada Himpunan

Misalkan $A, B \subseteq \Omega$. Kita punya operasi:

Operasi	Notasi	Makna
Union	$A \cup B$	$A$ atau $B$ (atau keduanya) terjadi
Intersection	$A \cap B$	$A$ dan $B$ keduanya terjadi
Complement	$A^c$	$A$ tidak terjadi
Difference	$A \setminus B$	$A$ terjadi tapi $B$ tidak
Subset	$A \subseteq B$	Semua outcome di $A$ juga ada di $B$
Empty set	$\emptyset$	Event yang tidak mungkin terjadi

Disjoint events: $A$ dan $B$ dikatakan disjoint (atau mutually exclusive) jika: \[A \cap B = \emptyset\]

Artinya, keduanya tidak bisa terjadi bersamaan.

1.3 De Morgan’s Laws

Dua identitas penting yang sering muncul:

\[\boxed{(A \cup B)^c = A^c \cap B^c}\] \[\boxed{(A \cap B)^c = A^c \cup B^c}\]

Intuisi: “Tidak (A atau B)” = “Tidak A, dan tidak B”. “Tidak (A dan B)” = “Tidak A, atau tidak B.”

Ini valid untuk union/intersection dari $n$ himpunan: \[\left(\bigcup_{i=1}^n A_i\right)^c = \bigcap_{i=1}^n A_i^c \qquad \left(\bigcap_{i=1}^n A_i\right)^c = \bigcup_{i=1}^n A_i^c\]

Definisi: Partisi

Koleksi events $B_1, B_2, \ldots, B_n$ membentuk partisi dari $\Omega$ jika:

$B_i \cap B_j = \emptyset$ untuk semua $i \neq j$ (pairwise disjoint)
$\bigcup_{i=1}^n B_i = \Omega$ (exhaustive)

Partisi membagi $\Omega$ menjadi irisan yang tidak overlap dan menutup seluruh ruang. Konsep ini fundamental untuk Law of Total Probability (Topik 4.2).

2 2. Kolmogorov’s Axioms

Dengan sample space $\Omega$ dan koleksi events yang valid (disebut $\sigma$-algebra, kita skip formalitas ini), probability measure $P$ adalah fungsi yang memetakan setiap event ke bilangan real, memenuhi:

Definisi: Kolmogorov’s Axioms (1933)

Axiom 1 (Non-negativity): \[P(A) \geq 0 \quad \text{untuk semua event } A\]

Axiom 2 (Normalization): \[P(\Omega) = 1\]

Axiom 3 (Countable Additivity): Jika $A_1, A_2, \ldots$ adalah events yang pairwise disjoint ($A_i \cap A_j = \emptyset$ untuk $i \neq j$): \[P\left(\bigcup_{i=1}^{\infty} A_i\right) = \sum_{i=1}^{\infty} P(A_i)\]

Hanya tiga axiom. Dari sini, semua hasil lain bisa diturunkan.

2.1 Hasil yang Diturunkan dari Axioms

Komplemen: \[P(A^c) = 1 - P(A)\]

Bukti: $A$ dan $A^c$ disjoint, dan $A \cup A^c = \Omega$. Dari Axiom 3: $P(A) + P(A^c) = P(\Omega) = 1$. $\square$

Empty set: \[P(\emptyset) = 0\]

Bukti: $P(\emptyset) = P(\Omega^c) = 1 - P(\Omega) = 1 - 1 = 0$. $\square$

Monotonicity: Jika $A \subseteq B$, maka $P(A) \leq P(B)$.

Bukti: $B = A \cup (B \setminus A)$ dan ini disjoint. Maka $P(B) = P(A) + P(B \setminus A) \geq P(A)$. $\square$

Addition rule (general): \[\boxed{P(A \cup B) = P(A) + P(B) - P(A \cap B)}\]

Bukti: $A \cup B = A \cup (B \setminus A)$ dimana keduanya disjoint. Dan $B = (A \cap B) \cup (B \setminus A)$, disjoint. Maka: \[P(A \cup B) = P(A) + P(B \setminus A) = P(A) + P(B) - P(A \cap B) \quad \square\]

Boole’s inequality (union bound): \[P\left(\bigcup_{i=1}^n A_i\right) \leq \sum_{i=1}^n P(A_i)\]

Ini adalah upper bound yang sangat berguna dalam probabilitas.

3 3. Counting Methods untuk Ruang Sampel Finite

Kalau sample space $\Omega$ adalah finite dan setiap elementary outcome sama-sama mungkin (equally likely), maka: \[P(A) = \frac{|A|}{|\Omega|} = \frac{\text{jumlah outcome yang favorable}}{\text{total outcome}}\]

Masalahnya sekarang jadi masalah counting: hitung $|A|$ dan $|\Omega|$.

3.1 Multiplication Principle (Aturan Perkalian)

Jika ada $k$ tahap berurutan, di mana tahap $i$ punya $n_i$ pilihan, total cara melakukannya adalah: \[n_1 \times n_2 \times \cdots \times n_k\]

Contoh: PIN 4 digit (0–9) → $10^4 = 10000$ kemungkinan.

3.2 Permutasi: Ordered Selection

Permutasi adalah pengambilan berurutan dari $n$ objek, ambil $k$.

\[P(n, k) = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdots (n-k+1)\]

Catatan notasi: $P(n,k)$ untuk permutation, bukan probability di sini.

Intuisi: Slot pertama punya $n$ pilihan, slot kedua $n-1$, …, slot ke-$k$ punya $n-k+1$ pilihan.

Contoh: Dalam lomba dengan 10 peserta, berapa cara memilih juara 1, 2, 3? \[P(10, 3) = \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720\]

3.3 Kombinasi: Unordered Selection

Kombinasi adalah pengambilan tidak berurutan — kita tidak peduli urutannya.

\[\binom{n}{k} = \frac{n!}{k!(n-k)!}\]

Dibaca: “$n$ choose $k$”.

Intuisi: Dari $P(n,k)$ permutations, setiap set $k$ objek muncul $k!$ kali (semua urutannya). Maka: \[\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{k!(n-k)!}\]

Identitas penting: - $\binom{n}{0} = \binom{n}{n} = 1$ - $\binom{n}{k} = \binom{n}{n-k}$ (simetri) - Pascal’s identity: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Pascal’s identity intuisi: Dari $n$ objek, pilih $k$. Fix satu objek spesifik, sebut $x$. Baik kita include $x$ (pilih $k-1$ dari sisa $n-1$) atau tidak (pilih $k$ dari sisa $n-1$).

# Kombinasi: n choose k
choose(52, 5)   # Jumlah kombinasi 5-card dari 52 kartu

[1] 2598960

choose(10, 3)   # 10 choose 3

[1] 120

# Permutasi: P(n,k) = n! / (n-k)!
perm <- function(n, k) factorial(n) / factorial(n - k)
perm(10, 3)     # Permutasi 3 dari 10

[1] 720

# Factorial
factorial(5)    # 5! = 120

[1] 120

factorial(52)   # Sangat besar!

[1] 8.065818e+67

# Pascal's identity check
choose(10, 4) == choose(9, 3) + choose(9, 4)  # TRUE

[1] TRUE

4 4. Inclusion-Exclusion Principle

Formula addition rule bisa digeneralisasi untuk $n$ events:

\[\boxed{P\left(\bigcup_{i=1}^n A_i\right) = \sum_i P(A_i) - \sum_{i<j} P(A_i \cap A_j) + \sum_{i<j<k} P(A_i \cap A_j \cap A_k) - \cdots + (-1)^{n+1}P(A_1 \cap \cdots \cap A_n)}\]

Pola: tambah individual, kurang pairwise intersections, tambah triple intersections, dst. Tanda bergantian $+, -, +, -$.

Untuk $n = 2$: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ ✓

Untuk $n = 3$: $P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A\cap B) - P(A\cap C) - P(B\cap C) + P(A\cap B\cap C)$

Connection: Bonferroni Correction untuk Multiple Testing

Ini langsung muncul di praktik research kamu!

Misalkan kamu jalankan $m$ hypothesis tests secara simultan, masing-masing dengan significance level $\alpha$. Event $A_i$ = “test ke-$i$ reject $H_0$ secara salah” (Type I error), dengan $P(A_i) = \alpha$.

Family-Wise Error Rate (FWER) = probabilitas at least satu false rejection: \[\text{FWER} = P\left(\bigcup_{i=1}^m A_i\right)\]

Dengan Boole’s inequality (inclusion-exclusion upper bound): \[\text{FWER} \leq \sum_{i=1}^m P(A_i) = m\alpha\]

Maka untuk menjaga $\text{FWER} \leq \alpha$, gunakan threshold per-test: $\alpha_{\text{Bonferroni}} = \alpha/m$.

Ini adalah Bonferroni correction — langsung dari inclusion-exclusion!

5 5. Worked Example 1: Full House dalam Poker

Pertanyaan: Dalam deck 52 kartu standar, berapa probabilitas mendapat full house (3 kartu dari satu rank, 2 kartu dari rank lain) dalam 5 kartu?

Langkah 1: Total outcome \[|\Omega| = \binom{52}{5} = 2{,}598{,}960\]

Langkah 2: Hitung jumlah full house hands - Pilih rank untuk triple: 13 cara - Pilih 3 dari 4 suit untuk triple: $\binom{4}{3} = 4$ cara - Pilih rank untuk pair (harus berbeda): 12 cara - Pilih 2 dari 4 suit untuk pair: $\binom{4}{2} = 6$ cara

\[|\text{Full House}| = 13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2} = 13 \cdot 4 \cdot 12 \cdot 6 = 3{,}744\]

Langkah 3: Probabilitas \[P(\text{Full House}) = \frac{3{,}744}{2{,}598{,}960} \approx 0.00144 \approx 0.144\%\]

total_hands <- choose(52, 5)
full_house_count <- 13 * choose(4, 3) * 12 * choose(4, 2)
p_full_house <- full_house_count / total_hands

cat("Total 5-card hands:", total_hands, "\n")

Total 5-card hands: 2598960

cat("Full house hands:", full_house_count, "\n")

Full house hands: 3744

cat("P(Full House):", round(p_full_house, 6), "\n")

P(Full House): 0.001441

cat("Odds:", round(1/p_full_house, 1), "to 1\n")

Odds: 694.2 to 1

6 6. Worked Example 2: Birthday Problem dan Sampling

Pertanyaan: Jika kita ambil $n$ observasi with replacement dari populasi ukuran $N$, berapa probabilitas semua observasi distinct?

Setup: Sample space untuk $n$ draws adalah semua sequence panjang $n$ dari $\{1, 2, \ldots, N\}$, dengan repetisi allowed. \[|\Omega| = N^n\]

Event $A$ = “semua observasi distinct”: \[|A| = N \cdot (N-1) \cdot (N-2) \cdots (N-n+1) = \frac{N!}{(N-n)!} = P(N, n)\]

Maka: \[P(A) = \frac{N!/(N-n)!}{N^n} = \frac{N \cdot (N-1) \cdots (N-n+1)}{N^n} = \prod_{k=0}^{n-1}\left(1 - \frac{k}{N}\right)\]

Birthday problem adalah kasus khusus: $N = 365$ hari, cari $n$ orang. Probabilitas at least dua orang berbagi birthday: \[P(\text{collision}) = 1 - P(A) = 1 - \prod_{k=0}^{n-1}\left(1 - \frac{k}{365}\right)\]

# Probabilitas semua observasi distinct (no collision)
p_distinct <- function(n, N = 365) {
  if (n > N) return(0)
  prod(1 - (0:(n-1)) / N)
}

# P(at least one collision = at least two people share birthday)
n_vals <- 1:60
p_collision <- 1 - sapply(n_vals, p_distinct)

# Titik di mana P(collision) > 0.5
min_n <- min(which(p_collision > 0.5))
cat("n =", min_n, "orang: P(shared birthday) =",
    round(p_collision[min_n], 4), "\n")

n = 23 orang: P(shared birthday) = 0.5073

cat("Intuisi yang mengejutkan: hanya perlu", min_n, "orang!")

Intuisi yang mengejutkan: hanya perlu 23 orang!

# Relevansi: hash collisions, sampling, data matching
# Dengan N = 1000 categories dan n = 40 samples:
cat("\nP(distinct) dengan N=1000, n=40:",
    round(p_distinct(40, 1000), 4))


P(distinct) dengan N=1000, n=40: 0.4536

Koneksi ke data science: Masalah ini muncul dalam hash collisions, probability of duplicate IDs, dan analisis sampling. Kalau $n \approx \sqrt{N}$, collision menjadi likely — ini adalah birthday bound.

Practice Problems

Soal 1: Di kelas dengan 30 mahasiswa, setiap mahasiswa diberi PIN 4 digit (0000–9999). Berapa probabilitas setidaknya dua mahasiswa punya PIN sama?

Solusi 1: - $N = 10000$, $n = 30$ - $P(\text{all distinct}) = \prod_{k=0}^{29}(1 - k/10000)$ - $P(\text{collision}) = 1 - P(\text{all distinct}) \approx 0.0435 \approx 4.35\%$

Soal 2: Dari dataset 100 observasi, kamu ingin pilih 5 secara acak untuk validasi manual. Berapa cara memilih 5 observasi ini? Berapa kalau urutan penting (misalnya, kamu assign peringkat ke-1, 2, 3, 4, 5)?

Solusi 2: - Tidak berurutan (kombinasi): $\binom{100}{5} = 75{,}287{,}520$ - Berurutan (permutasi): $P(100, 5) = 100 \cdot 99 \cdot 98 \cdot 97 \cdot 96 = 9{,}034{,}502{,}400$

Soal 3: Kamu jalankan 20 t-tests secara simultan dengan $\alpha = 0.05$. Berapa upper bound untuk FWER? Berapa Bonferroni-corrected threshold per test?

Solusi 3: - Boole’s inequality: $\text{FWER} \leq m\alpha = 20 \times 0.05 = 1.0$ (trivial bound!) - Lebih berguna: kalau tests independent, $\text{FWER} = 1 - (1-0.05)^{20} \approx 0.641$ - Bonferroni threshold: $\alpha/m = 0.05/20 = 0.0025$

Soal 4: Dari sebuah committee 10 orang (6 pria, 4 wanita), pilih subcommittee 3 orang. Berapa probabilitas subcommittee punya at least 1 wanita?

Solusi 4: - $P(\text{at least 1 wanita}) = 1 - P(\text{semua pria})$ - $P(\text{semua pria}) = \binom{6}{3}/\binom{10}{3} = 20/120 = 1/6$ - $P(\text{at least 1 wanita}) = 1 - 1/6 = 5/6 \approx 0.833$

7 Ringkasan

Konsep	Formula Kunci
Complement	$P(A^c) = 1 - P(A)$
Addition rule	$P(A \cup B) = P(A) + P(B) - P(A \cap B)$
Equally likely	$P(A) = \|A\|/\|\Omega\|$
Permutasi	$P(n,k) = n!/(n-k)!$
Kombinasi	$\binom{n}{k} = n!/[k!(n-k)!]$
Inclusion-exclusion	$P(\bigcup A_i) = \sum P(A_i) - \sum P(A_i \cap A_j) + \cdots$
Boole’s inequality	$P(\bigcup A_i) \leq \sum P(A_i)$

Next: Conditional Probability & Bayes’ Theorem →

--- title: "Counting, Sets & Axioms of Probability" subtitle: "Fondasi Formal Teori Probabilitas" format: html: toc: true toc-depth: 3 code-fold: false --- ::: {.callout-note title="Why This Matters for Your Work"} Probabilitas adalah bahasa uncertainty dalam statistik dan ML. Sebelum bisa bicara tentang distribusi, estimator, atau inference, kita perlu fondasi formal yang rigorous. **Kolmogorov's axioms** memberikan fondasi itu — tiga aturan sederhana yang dari sana kita bisa menurunkan *semua* hasil dalam teori probabilitas, dari basic rules sampai convergence theorems dan asymptotic theory. Lebih konkret: - **Counting methods** adalah basis untuk menghitung probabilitas di ruang sampel diskrit — penting untuk kombinatorik dalam uji statistik - **Inclusion-exclusion principle** muncul langsung di **Bonferroni correction** untuk multiple testing — sesuatu yang sangat relevan saat kamu jalankan banyak hipotesis sekaligus - Set theory notation adalah bahasa yang dipakai di seluruh literatur statistik dan ML ::: --- ## 1. Set Theory Review ### Sample Space dan Events Dalam teori probabilitas formal, kita mulai dari: - **Sample space** $\Omega$: himpunan semua outcome yang mungkin dari suatu eksperimen - **Event** $A$: subset dari $\Omega$, yaitu $A \subseteq \Omega$ - **Elementary outcome** $\omega \in \Omega$: satu outcome spesifik **Contoh**: - Lempar koin sekali: $\Omega = \{H, T\}$ - Lempar dua koin: $\Omega = \{HH, HT, TH, TT\}$ - Nilai saham besok: $\Omega = \mathbb{R}_{>0}$ (continuous!) - Jumlah pengangguran: $\Omega = \{0, 1, 2, \ldots\}$ Event $A$ = "dapat kepala di lemparan pertama" = $\{HH, HT\}$. ### Operasi pada Himpunan Misalkan $A, B \subseteq \Omega$. Kita punya operasi: | Operasi | Notasi | Makna | |---------|--------|-------| | Union | $A \cup B$ | $A$ atau $B$ (atau keduanya) terjadi | | Intersection | $A \cap B$ | $A$ dan $B$ keduanya terjadi | | Complement | $A^c$ | $A$ tidak terjadi | | Difference | $A \setminus B$ | $A$ terjadi tapi $B$ tidak | | Subset | $A \subseteq B$ | Semua outcome di $A$ juga ada di $B$ | | Empty set | $\emptyset$ | Event yang tidak mungkin terjadi | **Disjoint events**: $A$ dan $B$ dikatakan *disjoint* (atau *mutually exclusive*) jika: $$A \cap B = \emptyset$$ Artinya, keduanya tidak bisa terjadi bersamaan. ### De Morgan's Laws Dua identitas penting yang sering muncul: $$\boxed{(A \cup B)^c = A^c \cap B^c}$$ $$\boxed{(A \cap B)^c = A^c \cup B^c}$$ **Intuisi**: "Tidak (A atau B)" = "Tidak A, dan tidak B". "Tidak (A dan B)" = "Tidak A, atau tidak B." Ini valid untuk union/intersection dari $n$ himpunan: $$\left(\bigcup_{i=1}^n A_i\right)^c = \bigcap_{i=1}^n A_i^c \qquad \left(\bigcap_{i=1}^n A_i\right)^c = \bigcup_{i=1}^n A_i^c$$ ::: {.callout-important title="Definisi: Partisi"} Koleksi events $B_1, B_2, \ldots, B_n$ membentuk **partisi** dari $\Omega$ jika: 1. $B_i \cap B_j = \emptyset$ untuk semua $i \neq j$ (pairwise disjoint) 2. $\bigcup_{i=1}^n B_i = \Omega$ (exhaustive) Partisi membagi $\Omega$ menjadi irisan yang tidak overlap dan menutup seluruh ruang. Konsep ini fundamental untuk Law of Total Probability (Topik 4.2). ::: --- ## 2. Kolmogorov's Axioms Dengan sample space $\Omega$ dan koleksi events yang valid (disebut $\sigma$-algebra, kita skip formalitas ini), **probability measure** $P$ adalah fungsi yang memetakan setiap event ke bilangan real, memenuhi: ::: {.callout-important title="Definisi: Kolmogorov's Axioms (1933)"} **Axiom 1 (Non-negativity)**: $$P(A) \geq 0 \quad \text{untuk semua event } A$$ **Axiom 2 (Normalization)**: $$P(\Omega) = 1$$ **Axiom 3 (Countable Additivity)**: Jika $A_1, A_2, \ldots$ adalah events yang *pairwise disjoint* ($A_i \cap A_j = \emptyset$ untuk $i \neq j$): $$P\left(\bigcup_{i=1}^{\infty} A_i\right) = \sum_{i=1}^{\infty} P(A_i)$$ ::: Hanya tiga axiom. Dari sini, semua hasil lain bisa diturunkan. ### Hasil yang Diturunkan dari Axioms **Komplemen**: $$P(A^c) = 1 - P(A)$$ *Bukti*: $A$ dan $A^c$ disjoint, dan $A \cup A^c = \Omega$. Dari Axiom 3: $P(A) + P(A^c) = P(\Omega) = 1$. $\square$ **Empty set**: $$P(\emptyset) = 0$$ *Bukti*: $P(\emptyset) = P(\Omega^c) = 1 - P(\Omega) = 1 - 1 = 0$. $\square$ **Monotonicity**: Jika $A \subseteq B$, maka $P(A) \leq P(B)$. *Bukti*: $B = A \cup (B \setminus A)$ dan ini disjoint. Maka $P(B) = P(A) + P(B \setminus A) \geq P(A)$. $\square$ **Addition rule (general)**: $$\boxed{P(A \cup B) = P(A) + P(B) - P(A \cap B)}$$ *Bukti*: $A \cup B = A \cup (B \setminus A)$ dimana keduanya disjoint. Dan $B = (A \cap B) \cup (B \setminus A)$, disjoint. Maka: $$P(A \cup B) = P(A) + P(B \setminus A) = P(A) + P(B) - P(A \cap B) \quad \square$$ **Boole's inequality (union bound)**: $$P\left(\bigcup_{i=1}^n A_i\right) \leq \sum_{i=1}^n P(A_i)$$ Ini adalah upper bound yang sangat berguna dalam probabilitas. --- ## 3. Counting Methods untuk Ruang Sampel Finite Kalau sample space $\Omega$ adalah *finite* dan setiap elementary outcome sama-sama mungkin (*equally likely*), maka: $$P(A) = \frac{|A|}{|\Omega|} = \frac{\text{jumlah outcome yang favorable}}{\text{total outcome}}$$ Masalahnya sekarang jadi **masalah counting**: hitung $|A|$ dan $|\Omega|$. ### Multiplication Principle (Aturan Perkalian) Jika ada $k$ tahap berurutan, di mana tahap $i$ punya $n_i$ pilihan, total cara melakukannya adalah: $$n_1 \times n_2 \times \cdots \times n_k$$ **Contoh**: PIN 4 digit (0–9) → $10^4 = 10000$ kemungkinan. ### Permutasi: Ordered Selection **Permutasi** adalah *pengambilan berurutan* dari $n$ objek, ambil $k$. $$P(n, k) = \frac{n!}{(n-k)!} = n \cdot (n-1) \cdots (n-k+1)$$ **Catatan notasi**: $P(n,k)$ untuk permutation, bukan probability di sini. **Intuisi**: Slot pertama punya $n$ pilihan, slot kedua $n-1$, ..., slot ke-$k$ punya $n-k+1$ pilihan. **Contoh**: Dalam lomba dengan 10 peserta, berapa cara memilih juara 1, 2, 3? $$P(10, 3) = \frac{10!}{7!} = 10 \cdot 9 \cdot 8 = 720$$ ### Kombinasi: Unordered Selection **Kombinasi** adalah *pengambilan tidak berurutan* — kita tidak peduli urutannya. $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$ Dibaca: "$n$ choose $k$". **Intuisi**: Dari $P(n,k)$ permutations, setiap *set* $k$ objek muncul $k!$ kali (semua urutannya). Maka: $$\binom{n}{k} = \frac{P(n,k)}{k!} = \frac{n!}{k!(n-k)!}$$ **Identitas penting**: - $\binom{n}{0} = \binom{n}{n} = 1$ - $\binom{n}{k} = \binom{n}{n-k}$ (simetri) - **Pascal's identity**: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ **Pascal's identity intuisi**: Dari $n$ objek, pilih $k$. Fix satu objek spesifik, sebut $x$. Baik kita include $x$ (pilih $k-1$ dari sisa $n-1$) atau tidak (pilih $k$ dari sisa $n-1$). ```{r} #| label: counting-r #| code-summary: "R: Fungsi kombinasi dan permutasi" # Kombinasi: n choose k choose(52, 5) # Jumlah kombinasi 5-card dari 52 kartu choose(10, 3) # 10 choose 3 # Permutasi: P(n,k) = n! / (n-k)! perm <- function(n, k) factorial(n) / factorial(n - k) perm(10, 3) # Permutasi 3 dari 10 # Factorial factorial(5) # 5! = 120 factorial(52) # Sangat besar! # Pascal's identity check choose(10, 4) == choose(9, 3) + choose(9, 4) # TRUE ``` --- ## 4. Inclusion-Exclusion Principle Formula addition rule bisa digeneralisasi untuk $n$ events: $$\boxed{P\left(\bigcup_{i=1}^n A_i\right) = \sum_i P(A_i) - \sum_{i<j} P(A_i \cap A_j) + \sum_{i<j<k} P(A_i \cap A_j \cap A_k) - \cdots + (-1)^{n+1}P(A_1 \cap \cdots \cap A_n)}$$ **Pola**: tambah individual, kurang pairwise intersections, tambah triple intersections, dst. Tanda bergantian $+, -, +, -$. **Untuk $n = 2$**: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ ✓ **Untuk $n = 3$**: $P(A \cup B \cup C) = P(A) + P(B) + P(C) - P(A\cap B) - P(A\cap C) - P(B\cap C) + P(A\cap B\cap C)$ ::: {.callout-caution title="Connection: Bonferroni Correction untuk Multiple Testing"} Ini langsung muncul di praktik research kamu! Misalkan kamu jalankan $m$ hypothesis tests secara simultan, masing-masing dengan significance level $\alpha$. Event $A_i$ = "test ke-$i$ reject $H_0$ secara salah" (Type I error), dengan $P(A_i) = \alpha$. **Family-Wise Error Rate (FWER)** = probabilitas at least satu false rejection: $$\text{FWER} = P\left(\bigcup_{i=1}^m A_i\right)$$ Dengan Boole's inequality (inclusion-exclusion upper bound): $$\text{FWER} \leq \sum_{i=1}^m P(A_i) = m\alpha$$ Maka untuk menjaga $\text{FWER} \leq \alpha$, gunakan threshold per-test: $\alpha_{\text{Bonferroni}} = \alpha/m$. Ini adalah **Bonferroni correction** — langsung dari inclusion-exclusion! ::: --- ## 5. Worked Example 1: Full House dalam Poker **Pertanyaan**: Dalam deck 52 kartu standar, berapa probabilitas mendapat *full house* (3 kartu dari satu rank, 2 kartu dari rank lain) dalam 5 kartu? **Langkah 1**: Total outcome $$|\Omega| = \binom{52}{5} = 2{,}598{,}960$$ **Langkah 2**: Hitung jumlah full house hands - Pilih rank untuk triple: 13 cara - Pilih 3 dari 4 suit untuk triple: $\binom{4}{3} = 4$ cara - Pilih rank untuk pair (harus berbeda): 12 cara - Pilih 2 dari 4 suit untuk pair: $\binom{4}{2} = 6$ cara $$|\text{Full House}| = 13 \cdot \binom{4}{3} \cdot 12 \cdot \binom{4}{2} = 13 \cdot 4 \cdot 12 \cdot 6 = 3{,}744$$ **Langkah 3**: Probabilitas $$P(\text{Full House}) = \frac{3{,}744}{2{,}598{,}960} \approx 0.00144 \approx 0.144\%$$ ```{r} #| label: full-house #| code-summary: "R: Hitung probabilitas full house" total_hands <- choose(52, 5) full_house_count <- 13 * choose(4, 3) * 12 * choose(4, 2) p_full_house <- full_house_count / total_hands cat("Total 5-card hands:", total_hands, "\n") cat("Full house hands:", full_house_count, "\n") cat("P(Full House):", round(p_full_house, 6), "\n") cat("Odds:", round(1/p_full_house, 1), "to 1\n") ``` --- ## 6. Worked Example 2: Birthday Problem dan Sampling **Pertanyaan**: Jika kita ambil $n$ observasi *with replacement* dari populasi ukuran $N$, berapa probabilitas semua observasi distinct? **Setup**: Sample space untuk $n$ draws adalah semua sequence panjang $n$ dari $\{1, 2, \ldots, N\}$, dengan repetisi allowed. $$|\Omega| = N^n$$ Event $A$ = "semua observasi distinct": $$|A| = N \cdot (N-1) \cdot (N-2) \cdots (N-n+1) = \frac{N!}{(N-n)!} = P(N, n)$$ Maka: $$P(A) = \frac{N!/(N-n)!}{N^n} = \frac{N \cdot (N-1) \cdots (N-n+1)}{N^n} = \prod_{k=0}^{n-1}\left(1 - \frac{k}{N}\right)$$ **Birthday problem** adalah kasus khusus: $N = 365$ hari, cari $n$ orang. Probabilitas *at least* dua orang berbagi birthday: $$P(\text{collision}) = 1 - P(A) = 1 - \prod_{k=0}^{n-1}\left(1 - \frac{k}{365}\right)$$ ```{r} #| label: birthday-problem #| code-summary: "R: Birthday problem" # Probabilitas semua observasi distinct (no collision) p_distinct <- function(n, N = 365) { if (n > N) return(0) prod(1 - (0:(n-1)) / N) } # P(at least one collision = at least two people share birthday) n_vals <- 1:60 p_collision <- 1 - sapply(n_vals, p_distinct) # Titik di mana P(collision) > 0.5 min_n <- min(which(p_collision > 0.5)) cat("n =", min_n, "orang: P(shared birthday) =", round(p_collision[min_n], 4), "\n") cat("Intuisi yang mengejutkan: hanya perlu", min_n, "orang!") # Relevansi: hash collisions, sampling, data matching # Dengan N = 1000 categories dan n = 40 samples: cat("\nP(distinct) dengan N=1000, n=40:", round(p_distinct(40, 1000), 4)) ``` **Koneksi ke data science**: Masalah ini muncul dalam hash collisions, probability of duplicate IDs, dan analisis sampling. Kalau $n \approx \sqrt{N}$, collision menjadi likely — ini adalah **birthday bound**. --- ::: {.callout-warning title="Practice Problems" collapse="true"} **Soal 1**: Di kelas dengan 30 mahasiswa, setiap mahasiswa diberi PIN 4 digit (0000–9999). Berapa probabilitas setidaknya dua mahasiswa punya PIN sama? **Solusi 1**: - $N = 10000$, $n = 30$ - $P(\text{all distinct}) = \prod_{k=0}^{29}(1 - k/10000)$ - $P(\text{collision}) = 1 - P(\text{all distinct}) \approx 0.0435 \approx 4.35\%$ --- **Soal 2**: Dari dataset 100 observasi, kamu ingin pilih 5 secara acak untuk validasi manual. Berapa cara memilih 5 observasi ini? Berapa kalau urutan penting (misalnya, kamu assign peringkat ke-1, 2, 3, 4, 5)? **Solusi 2**: - Tidak berurutan (kombinasi): $\binom{100}{5} = 75{,}287{,}520$ - Berurutan (permutasi): $P(100, 5) = 100 \cdot 99 \cdot 98 \cdot 97 \cdot 96 = 9{,}034{,}502{,}400$ --- **Soal 3**: Kamu jalankan 20 t-tests secara simultan dengan $\alpha = 0.05$. Berapa upper bound untuk FWER? Berapa Bonferroni-corrected threshold per test? **Solusi 3**: - Boole's inequality: $\text{FWER} \leq m\alpha = 20 \times 0.05 = 1.0$ (trivial bound!) - Lebih berguna: kalau tests independent, $\text{FWER} = 1 - (1-0.05)^{20} \approx 0.641$ - Bonferroni threshold: $\alpha/m = 0.05/20 = 0.0025$ --- **Soal 4**: Dari sebuah committee 10 orang (6 pria, 4 wanita), pilih subcommittee 3 orang. Berapa probabilitas subcommittee punya at least 1 wanita? **Solusi 4**: - $P(\text{at least 1 wanita}) = 1 - P(\text{semua pria})$ - $P(\text{semua pria}) = \binom{6}{3}/\binom{10}{3} = 20/120 = 1/6$ - $P(\text{at least 1 wanita}) = 1 - 1/6 = 5/6 \approx 0.833$ ::: --- ## Ringkasan | Konsep | Formula Kunci | |--------|---------------| | Complement | $P(A^c) = 1 - P(A)$ | | Addition rule | $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ | | Equally likely | $P(A) = |A|/|\Omega|$ | | Permutasi | $P(n,k) = n!/(n-k)!$ | | Kombinasi | $\binom{n}{k} = n!/[k!(n-k)!]$ | | Inclusion-exclusion | $P(\bigcup A_i) = \sum P(A_i) - \sum P(A_i \cap A_j) + \cdots$ | | Boole's inequality | $P(\bigcup A_i) \leq \sum P(A_i)$ | **Next**: [Conditional Probability & Bayes' Theorem →](02-conditional-bayes.qmd)

Operasi	Notasi	Makna
Union	\(A \cup B\)	\(A\) atau \(B\) (atau keduanya) terjadi
Intersection	\(A \cap B\)	\(A\) dan \(B\) keduanya terjadi
Complement	\(A^c\)	\(A\) tidak terjadi
Difference	\(A \setminus B\)	\(A\) terjadi tapi \(B\) tidak
Subset	\(A \subseteq B\)	Semua outcome di \(A\) juga ada di \(B\)
Empty set	\(\emptyset\)	Event yang tidak mungkin terjadi