4 Doğum Günü Problemi ve Olasılığın Özellikleri

23 kişide %50,7 — hash collision, içerme-dışarma, 1/e

Bölüm bilgisi

Blitzstein’in videosu: YouTube — Lecture 3: Birthday Problem, Properties of Probability (≈49 dk)
Okuma süresi: ≈25 dk

4.1 Bu Derste Ne Var?

Ders 2’de olasılığın iki aksiyomunu kurduk. Burada üç şey:

Doğum günü problemi — sadece 23 kişide iki kişinin aynı gün doğma olasılığı neden %50’yi geçer.
Aksiyomlardan özellikler — tümleyen $P(A^c) = 1 - P(A)$ ve tekdüzelik $A \subseteq B \Rightarrow P(A) \le P(B)$.
İçerme-dışarma — ayrık olmayan olayların birleşim olasılığı; ve ünlü $1/e$ sonucuyla biten matching problemi.

“very surprising to most people the first time that they see this result.” — Blitzstein, 0:29

Builder Notu — ML Köprüleri

Doğum günü problemi = hash collision. Kriptografide birthday attack ($2^{n/2}$ denemede bir hash’i kırmak) ve ML’de feature hashing aynı matematiğe dayanır.
$\binom{K}{2}$ çiftler = çoklu karşılaştırma. Çok hipotez/çift test edince bazıları şans eseri anlamlı çıkar — p-hacking ve Bonferroni düzeltmesinin kökü.
İçerme-dışarma → union bound $P(\cup A_i) \le \sum P(A_i)$ — PAC öğrenmenin iş atı.
$1/e$ rastgele permütasyonlarda, secretary problem’in optimal durmasında, bootstrap OOB’de karşına çıkar.

4.2 Doğum Günü Problemi: Kurulum

Problem basit: bir partide $K$ kişi var; en az iki kişinin aynı gün doğmuş olma olasılığı nedir? (Belirli iki kişi değil — herhangi bir çift.)

Varsayımlar:

Yılda 365 gün (29 Şubat dışlandı).
365 gün eşit olası.
Doğum günleri bağımsız.

Kolay durum: $K > 365$ ise olasılık tam $1$. Çünkü 365 kutu (gün) ve 365’ten fazla kişi varsa, en az bir kutuda mutlaka birden çok kişi olur — güvercin yuvası ilkesi (pigeonhole).

Asıl ilginç durum $K \le 365$. Sezgi ne diyor? Blitzstein yıllarca insanlara sormuş: “50/50 şans için kaç kişi gerekir?” Tipik tahmin 150–180. Gerçek cevap: 23.

Builder Notu — Hash Collision

Bu problem doğrudan hash tablosu collision’ıdır. Kriptografideki birthday attack de buradan gelir — $m$ bit’lik bir hash’te çakışma bulmak $\approx 2^{m/2}$ deneme sürer (kaba kuvvetin $2^m$’inden çok daha az), bu yüzden güvenli hash’ler uzun olmalı. Aynı sezgi, ML’de feature hashing kullanırken çakışma sıklığını tahmin eder.

4.3 Doğum Günü: Tümleyenle Hesap

Doğrudan “en az bir eşleşme” olasılığını saymak zor; tümleyenle (hiç eşleşme yok) çalışmak çok daha kolay.

“it’s a little bit easier to work with the complement first.” — Blitzstein, 9:06

Naif tanım. Payda çarpma kuralından: her kişinin 365 olası günü → $365^K$. Pay için kişileri ID sırasıyla düşün: birincinin 365, ikincinin (birinciyle çakışmayan) 364, $\ldots$, $k$. kişinin $365 - k + 1$ seçeneği:

\[ P(\text{hiç eşleşme yok}) = \frac{365 \cdot 364 \cdots (365 - K + 1)}{365^K} \]

(Tam $K$ terim olmalı; son terimde $+1$’i unutmak en sık off-by-one hatasıdır.) Eşleşme olasılığı:

\[ P(\text{en az bir eşleşme}) = 1 - \frac{365 \cdot 364 \cdots (365 - K + 1)}{365^K} \]

import math
import numpy as np
import matplotlib.pyplot as plt

def p_eslesme(K, gun=365):
    if K > gun:
        return 1.0
    p = 1.0
    for i in range(K):
        p *= (gun - i) / gun
    return 1 - p

Ks = np.arange(1, 81)
ps = [p_eslesme(int(K)) for K in Ks]

fig, ax = plt.subplots(figsize=(10, 5.5))
ax.plot(Ks, ps, color='#A51C30', linewidth=2.5, marker='o', markersize=4)
ax.axhline(0.5, color='#6B7280', linestyle='--', linewidth=1, alpha=0.7)
ax.axvline(23, color='#DD6B20', linestyle='--', linewidth=2)

# Eşik etiketi
ax.annotate(f'K = 23 → 0,507\n(eşik %50)', xy=(23, 0.507),
            xytext=(35, 0.35),
            arrowprops=dict(arrowstyle='->', color='#DD6B20', linewidth=1.5),
            fontsize=11, color='#6B0E1B', weight='bold')

# Belirgin noktalar
for K_isaret in [23, 50, 75]:
    p_isaret = p_eslesme(K_isaret)
    ax.plot(K_isaret, p_isaret, 'o', markersize=10,
            markerfacecolor='#DD6B20', markeredgecolor='#6B0E1B')
    ax.annotate(f'{p_isaret:.3f}', xy=(K_isaret, p_isaret),
                xytext=(K_isaret + 1, p_isaret - 0.04),
                fontsize=10, color='#6B0E1B')

ax.set_xlabel('Kişi sayısı $K$', fontsize=12)
ax.set_ylabel('$P(\\text{en az iki kişi aynı gün})$', fontsize=12)
ax.set_title('Doğum günü problemi — %50 eşiği $K = 23$\'te aşılır', fontsize=12)
ax.grid(True, alpha=0.3)
ax.set_xlim(0, 80); ax.set_ylim(0, 1.05)
plt.tight_layout()
plt.show()

Şekil 4.1

Builder Notu — ‘En Az Bir’ Refleksi

“$P(\text{en az bir}) = 1 - P(\text{hiç})$” kalıbı ML’de her yerde: dropout’ta bir nöronun en az bir adımda aktif kalma olasılığı, $n$ denemede en az bir başarı ($1 - (1-p)^n$), bir veri artırma zincirinde en az bir dönüşümün uygulanması. Zor olan “en az bir”i, kolay olan “hiç”in tümleyeniyle hesaplamak temel bir reflekstir.

4.4 Neden 23? Sezgi: $\binom{K}{2}$ Çiftler

23 sayısı neden bu kadar küçük? Çünkü sezgimiz yanlış niceliğe bakıyor. Önemli olan kaç kişi ($K$) değil, kaç çift ($\binom{K}{2}$).

\[ \binom{K}{2} = \frac{K(K-1)}{2}, \qquad \binom{23}{2} = \frac{23 \cdot 22}{2} = 253 \]

“The more relevant quantity is not K, but K choose 2.” — Blitzstein, 13:43

23 kişi az gibi ama aralarında 253 çift var ve bu çiftlerin herhangi biri eşleşebilir. 253, 365’in mertebesine yakın — işte o zaman %50 makul görünüyor.

“the biggest coincidence of all would be if there were no coincidences.” — Blitzstein, 16:19

K = np.arange(1, 71)
ciftler = K * (K - 1) // 2

fig, ax1 = plt.subplots(figsize=(10, 4.5))
ax1.bar(K, ciftler, color='#DD6B20', alpha=0.7, label='$\\binom{K}{2}$ çift sayısı', edgecolor='#9a3412')
ax1.plot(K, K, color='#2C5282', linewidth=2.5, label='$K$ kişi sayısı (lineer)')
ax1.axhline(365, color='#A51C30', linestyle='--', linewidth=2,
            label='365 gün eşiği')
ax1.axvline(23, color='#6B0E1B', linestyle=':', linewidth=1.5)
ax1.text(23.3, 1200, 'K=23\n253 çift', fontsize=10, color='#6B0E1B', weight='bold')

ax1.set_xlabel('K (kişi)', fontsize=12)
ax1.set_ylabel('sayı', fontsize=12)
ax1.set_title('$K$ lineer, $\\binom{K}{2}$ kuadratik — eşleşme \"çift sayısıyla\" yarışır',
              fontsize=12)
ax1.legend(loc='upper left', fontsize=11)
ax1.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()

Şekil 4.2

Builder Notu — Çoklu Karşılaştırma ve P-Hacking

Bu, çoklu karşılaştırma (multiple comparisons) probleminin ta kendisi. Çok sayıda hipotez veya çift test edersen, bir kısmı saf şans eseri “anlamlı” çıkar — çünkü önemli olan tekil testlerin değil karşılaştırma sayısının büyüklüğüdür. P-hacking tam budur. Bonferroni düzeltmesi anlamlılık eşiğini test sayısına bölerek bunu telafi eder — doğum günü sezgisinin istatistiksel karşılığı.

4.5 Olasılığı Alan Gibi Düşün + Tümleyen Kuralı

Aksiyomları hatırla: $P(\varnothing) = 0$, $P(S) = 1$ ve ayrık olaylar için toplanabilirlik. Bu iki kuralı yazıya dökmek, büyük ölçüde Kolmogorov’un eseri.

Sezgi için olasılığı alan gibi düşün: Venn diyagramında tüm $S$’nin alanı $1$’dir; bir olayın olasılığı, kapladığı alandır.

Özellik 1 (tümleyen kuralı):

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

İspat (3 satır): Aksiyom 1’den $1 = P(S)$. $S = A \cup A^c$ ayrık. Aksiyom 2 → $P(S) = P(A) + P(A^c)$. Yani $P(A^c) = 1 - P(A)$. ∎

Builder Notu — Ölçü ve Normalizasyon

“Olasılık = alan” sezgisi, olasılığın bir ölçü (measure) olmasının habercisi (Ders 12+). İspattaki kalıp — “$S$’yi ayrık parçalara böl, toplamları $1$” — normalizasyonun kendisidir. Pratikte: $P(\text{hata}) = 1 - P(\text{doğru})$ kalıbı her yerde.

4.6 Tekdüzelik: $A \subseteq B \Rightarrow P(A) \le P(B)$

Özellik 2 (tekdüzelik / monotonluk): $A$ olayı $B$’nin içindeyse ($A$ gerçekleşince $B$ de gerçekleşiyor), $A$’nın olasılığı $B$’ninkinden büyük olamaz.

\[ A \subseteq B \;\Rightarrow\; P(A) \le P(B) \]

İspat: $B = A \cup (B \cap A^c)$, ayrık. Aksiyom 2: $P(B) = P(A) + P(B \cap A^c)$. Olasılıklar negatif olamayacağından $P(B) \ge P(A)$. ∎

Builder Notu — CDF Monotonluğu

Tekdüzelik bir ölçünün temel özelliğidir. Birikimli dağılım fonksiyonunun (CDF) artan olmasının nedeni budur. Sınır kurarken de kritik: bir hata olayını, onu içeren daha büyük bir olayla üstten sınırlayabilirsin — union bound’un mantığı.

4.7 İçerme-Dışarma (Inclusion-Exclusion)

Ayrık olaylarda $P(A \cup B) = P(A) + P(B)$. Peki ayrık değillerse? Venn diyagramında $A$ ile $B$’nin alanlarını toplarsan, kesişimi iki kez sayarsın; bir kez geri çıkarırsın:

\[ P(A \cup B) = P(A) + P(B) - P(A \cap B) \]

İspat (disjointification). Aksiyom 2 yalnızca ayrık olaylara uygulanır. $A \cup B = A \cup (B \cap A^c)$, ayrık. $P(A \cup B) = P(A) + P(B \cap A^c)$. Ayrıca $B = (A \cap B) \cup (A^c \cap B)$ ayrık, $P(B \cap A^c) = P(B) - P(A \cap B)$. Birleştir, sonuç çıkar. ∎

“disjointification” — Blitzstein, 30:11

Üç olaya genelleme (işaretler dönüşümlü):

\[ 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) \]

from matplotlib.patches import Circle, Wedge

fig, axes = plt.subplots(1, 2, figsize=(10, 4.5))

# Sol: iki olay
ax = axes[0]
ax.add_patch(Circle((-0.5, 0), 1.2, facecolor='#DD6B20', alpha=0.45, edgecolor='#9a3412', linewidth=2))
ax.add_patch(Circle((0.5, 0), 1.2, facecolor='#2C5282', alpha=0.45, edgecolor='#1e3a5f', linewidth=2))
ax.text(-1.2, 0, '$A$', fontsize=20, color='#6B0E1B', weight='bold', ha='center', va='center')
ax.text(1.2, 0, '$B$', fontsize=20, color='#1e3a5f', weight='bold', ha='center', va='center')
ax.text(0, 0, '$A \\cap B$\n(iki kez sayıldı)', fontsize=10, ha='center', va='center',
        color='white', weight='bold')
ax.set_xlim(-2.5, 2.5); ax.set_ylim(-1.7, 1.7); ax.set_aspect('equal')
ax.set_title('$P(A \\cup B) = P(A) + P(B) - P(A \\cap B)$', fontsize=12)
ax.set_xticks([]); ax.set_yticks([])
for sp in ax.spines.values(): sp.set_visible(False)

# Sağ: üç olay
ax = axes[1]
r = 1.0
merkezler = [(-0.6, 0.4), (0.6, 0.4), (0, -0.6)]
renkler = ['#DD6B20', '#2C5282', '#6B46C1']
etiketler = ['$A$', '$B$', '$C$']
for (cx, cy), c, e in zip(merkezler, renkler, etiketler):
    ax.add_patch(Circle((cx, cy), r, facecolor=c, alpha=0.40, edgecolor=c, linewidth=2))
    ax.text(cx + 1.05*(cx/abs(cx) if cx else 0),
            cy + (0.5 if cy > 0 else -0.5),
            e, fontsize=20, color=c, weight='bold', ha='center', va='center')

ax.set_xlim(-2.5, 2.5); ax.set_ylim(-2, 1.7); ax.set_aspect('equal')
ax.set_title('3 olay: tekleri topla, çiftleri çıkar, üçlüyü ekle',
             fontsize=12)
ax.set_xticks([]); ax.set_yticks([])
for sp in ax.spines.values(): sp.set_visible(False)

plt.tight_layout()
plt.show()

Şekil 4.3

Builder Notu — Union Bound ve PAC

İçerme-dışarmayı ilk terimde keserek union bound (Boole eşitsizliği) elde edilir: \[P\left(\bigcup_i A_i\right) \le \sum_i P(A_i)\] Bu eşitsizlik ML teorisinin iş atıdır: PAC öğrenme ve genelleme sınırları, çok sayıda “kötü olay”ı union bound ile üstten sınırlar; Bonferroni çoklu-test düzeltmesi de aynı sınırdır. İçerme-dışarma kesin değeri verir; union bound her yerde kullanılan ucuz üst sınırdır.

4.8 Matching Problem (de Montmort, 1713) ve $1/e$

İçerme-dışarmanın güzel uygulaması, 1713’ten kalma kumar oyunu. Deste $1\ldots n$ numaralı $n$ kart. Karıştır, sonra teker teker aç ve $1, 2, 3, \ldots$ diye say. Eğer $j$. açılan kartın üzerinde $j$ yazıyorsa “eşleşme” olur. En az bir eşleşme olasılığı?

$A_j$ = “$j$. karttaki sayı $j$” olayı. İstediğimiz $P(A_1 \cup A_2 \cup \ldots \cup A_n)$. Simetri her şeyi kolaylaştırıyor:

$P(A_j) = 1/n$.
$P(A_1 \cap A_2) = (n-2)! / n! = 1/(n(n-1))$.
Genel: $P(A_1 \cap \ldots \cap A_k) = (n-k)!/n!$.

İçerme-dışarma. Her terimde $n$’ler sadeleşir:

\[ P\left(\bigcup_{j=1}^{n} A_j\right) = 1 - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + \cdots \approx 1 - \frac{1}{e} \approx 0{,}632 \]

“This should remind you of the Taylor series for e to the x … this is approximately one minus one over e.” — Blitzstein, 48:43

Şaşırtıcı: en az bir eşleşme olasılığı, $n$’e neredeyse bağımsız olarak $\approx 0{,}632$’ye oturur.

import math
import numpy as np
import matplotlib.pyplot as plt

ns = np.arange(2, 21)
p_match = [sum((-1)**(k+1) / math.factorial(k) for k in range(1, n + 1)) for n in ns]
p_bootstrap_in = [1 - (1 - 1/n)**n for n in ns]
hedef = 1 - 1/math.e

fig, ax = plt.subplots(figsize=(10, 4.5))
ax.plot(ns, p_match, 'o-', color='#A51C30', linewidth=2.2, markersize=7,
        label='matching: $P(\\text{≥ 1 eşleşme})$')
ax.plot(ns, p_bootstrap_in, 's-', color='#2C5282', linewidth=2.2, markersize=7,
        label='bootstrap: $1 - (1 - 1/n)^n = P(\\text{nokta seçildi})$')
ax.axhline(hedef, color='#DD6B20', linestyle='--', linewidth=2,
           label=f'$1 - 1/e = {hedef:.4f}$')

ax.set_xlabel('$n$', fontsize=12)
ax.set_ylabel('olasılık', fontsize=12)
ax.set_title('İki yolla $1 - 1/e$: matching problem ve bootstrap',
             fontsize=12)
ax.legend(loc='lower right', fontsize=10)
ax.grid(True, alpha=0.3)
ax.set_xticks(ns)
ax.set_ylim(0.3, 0.75)
plt.tight_layout()
plt.show()

Şekil 4.4

Builder Notu — Bootstrap OOB ve $1/e$

$1/e$ ML’de doğrudan bootstrap’ta karşına çıkar. $n$ örnekten yerine koyarak $n$ örnek çektiğinde, belirli bir noktanın hiç seçilmeme olasılığı $(1 - 1/n)^n \to 1/e \approx 0{,}368$. Yani her bootstrap örneği verinin $\approx \%63{,}2$’sini kullanır, kalan $\approx \%36{,}8$ out-of-bag (OOB) olur — random forest’ın OOB hata kestiriminin tam temeli. Aynı $1/e$ derangement’larda (hiç sabit noktası olmayan permütasyonlar) ve secretary problem’in $1/e$ durma kuralında da belirir.

4.9 Bu Dersin Özeti

Doğum günü problemi: $K=23$ → %50,7; $K=50$ → %97; $K=100$ → %99,999+.
Tümleyenle hesap: “en az bir” yerine “hiç yok”u say; $P(\text{eşleşme}) = 1 - 365 \cdot 364 \cdots (365-K+1)/365^K$.
Sezgi $\binom{K}{2}$: Önemli olan kişi $K$ değil, çift sayısı; 23 kişi $\to$ 253 çift.
Tümleyen kuralı: $P(A^c) = 1 - P(A)$.
Tekdüzelik: $A \subseteq B \Rightarrow P(A) \le P(B)$.
İçerme-dışarma: $P(A \cup B) = P(A) + P(B) - P(A \cap B)$; genelde dönüşümlü işaretli toplam. İlk terimde kesince union bound $P(\cup A_i) \le \sum P(A_i)$.
Matching problem: En az bir eşleşme $\approx 1 - 1/e \approx 0{,}632$ ($n$’den bağımsız).

Tek bir cümle

İki basit aksiyomdan tümleyen, tekdüzelik ve içerme-dışarma gibi tüm pratik kurallar türer; olasılığın en şaşırtıcı sonuçları (doğum günü, $1/e$) aslında “kaç çift / kaç eşleşme” diye doğru niceliği saymaktan ibarettir.

4.10 Kontrol Soruları

Soru 1: 30 kişilik sınıfta en az iki kişinin aynı gün doğma olasılığı %50’den büyük mü?

Cevap: Büyük. 23 kişide $0{,}507$ ve $K$ arttıkça olasılık tekdüze artar ($A_{23} \subseteq A_{30}$). Gerçekte $\approx \%70$.

Soru 2: Adil zar 4 kez atılıyor. En az bir 6 gelme olasılığı?

Cevap: Tümleyen (“hiç 6 yok”): $(5/6)^4 = 625/1296$. $P(\text{en az bir 6}) = 1 - 625/1296 = 671/1296 \approx 0{,}518$.

Soru 3: 1-100 arası rastgele tam sayı. 2’ye veya 3’e bölünme olasılığı?

Cevap: İçerme-dışarma. $|A| = 50$ (2’nin katları), $|B| = 33$ (3’ün katları), $|A \cap B| = 16$ (6’nın katları). $P = (50 + 33 - 16)/100 = 67/100 = 0{,}67$.

Soru 4: (Builder) Bootstrap’ta n örnekten n çektiğinde belirli bir noktanın hiç seçilmeme olasılığı? Hangi ders kavramıyla bağlantılı?

Cevap: Bir nokta her çekimde seçilmeme olasılığı $(1 - 1/n)$; $n$ bağımsız çekim → $(1 - 1/n)^n \to 1/e \approx 0{,}368$. Bootstrap verinin $\approx \%63{,}2$’sini kullanır, $\approx \%36{,}8$ OOB. Matching’deki $1 - 1/e$ ile aynı $e$; random forest’ın OOB kestiriminin temeli.

4.11 Egzersizler

Egzersiz 1. “Aynı ay” sürümü: 12 ay, eşit olası, bağımsız. %50’yi geçmek için kaç kişi yeter? Tahmin et, sonra formülü 365 yerine 12 ile kur.

Egzersiz 2. 52 kartlık desteden 5 kart. En az bir as gelme olasılığını tümleyenle yaz. (İpucu: 48 karttan 5 seçmek = “hiç as yok”.)

Egzersiz 3. $P(A) = P(B) = P(C) = 0{,}5$; ikili kesişimler $0{,}3$; üçlü $0{,}1$. İçerme-dışarma ile $P(A \cup B \cup C)$?

Egzersiz 4. (Python — doğum günü simülasyon)

import random
random.seed(0)

def en_az_bir_eslesme(K, gun=365):
    gunler = [random.randint(1, gun) for _ in range(K)]
    return len(set(gunler)) < K

K, N = 23, 100_000
oran = sum(en_az_bir_eslesme(K) for _ in range(N)) / N
print(f"K={K} simülasyon: {oran:.4f}   (formül beklenen: ~0.5073)")

Egzersiz 5. (Sonraki ders) Matching problem sonucundan: $n \to \infty$ iken “hiç eşleşme yok” olasılığı $1/e$’ye yaklaşır. Hiç sabit noktası olmayan permütasyonlara derangement denir; $n=4$ için tüm permütasyonları listeleyip derangement sayısını elle doğrula.

4.12 Sonraki Ders İçin Hazırlık

Ders 4: Koşullu Olasılık

Kursun belki de en önemli kavramı: koşullu olasılık $P(A \mid B)$. Blitzstein bunu “istatistiğin ruhu” sayar; öğrenmek, yeni kanıt geldikçe inançları güncellemektir. Bayes teoreminin ve tüm Bayesian çıkarımın kapısı.

Ders 4 öncesi yapılacak

Egzersizleri çöz — özellikle 4 (simülasyon) ve 5 (derangement / $1/e$).
Python’da “en az bir” olasılığını her zaman tümleyenle hesaplamayı alışkanlık edin.
Ana cümleyi tekrar oku: “İki basit aksiyomdan tüm pratik kurallar türer…”

4.13 Anahtar Kavramlar (Cheat Sheet)

Kavram	Tanım	Blitzstein’de
Doğum günü problemi	$K=23 \to 0{,}507$ eşleşme	8m16
Pigeonhole	$K > 365 \to P = 1$	6m37
Tümleyenle hesap	$P(\text{en az bir}) = 1 - P(\text{hiç})$	9m06
$\binom{K}{2}$ sezgisi	23 kişi = 253 çift	13m43
Tümleyen kuralı	$P(A^c) = 1 - P(A)$	22m50
Tekdüzelik	$A \subseteq B \Rightarrow P(A) \le P(B)$	25m02
İçerme-dışarma	$P(A \cup B) = P(A) + P(B) - P(A \cap B)$	28m08
Disjointification	Birleşimi ayrık yaz, Aksiyom 2 uygula	30m11
Union bound	$P(\cup A_i) \le \sum P(A_i)$	türetme
Matching problem	$P(\text{eşleşme}) = 1 - 1/2! + 1/3! - \ldots$	39m50
$1/e$ sonucu	$\approx 0{,}632$; bootstrap OOB, derangement	48m43

4.14 ML Bağlantıları Özeti

7 köprü

Doğum günü problemi → hash collision, kriptografide birthday attack ($\approx 2^{m/2}$), ML’de feature hashing.
$\binom{K}{2}$ çiftler → çoklu karşılaştırma, p-hacking, Bonferroni düzeltmesi.
Tümleyen kuralı → $P(\text{en az bir}) = 1 - P(\text{hiç})$; dropout, başarı denemeleri.
Tekdüzelik → ölçü; CDF’nin artan olması (Ders 8).
İçerme-dışarma → union bound → PAC öğrenme / genelleme sınırları, Bonferroni.
$1/e$ (matching) → bootstrap OOB ≈ %36,8, derangement, secretary problem.
Olasılık = alan / aksiyomlar → ölçü teorisi, softmax geçerliliği, marjinalleştirme.

Tek bir şey alıp gideceksen

Olasılığın sürprizleri (doğum günü, $1/e$) sezgiyi değil doğru niceliği saymayı test eder — kaç çift, kaç eşleşme. Ve “en az bir” sorusunu her zaman tümleyeniyle (“hiç”) yenmeye bak.

--- title: "Doğum Günü Problemi ve Olasılığın Özellikleri" subtitle: "23 kişide %50,7 — hash collision, içerme-dışarma, 1/e" --- ::: {.callout-note title="Bölüm bilgisi"} - **Blitzstein'in videosu:** [YouTube — Lecture 3: Birthday Problem, Properties of Probability](https://www.youtube.com/watch?v=LZ5Wergp_PA) (≈49 dk) - **Okuma süresi:** ≈25 dk ::: ## Bu Derste Ne Var? {#sec-bu-derste} [Ders 2](02-story-proof-aksiyomlar.qmd)'de olasılığın iki aksiyomunu kurduk. Burada üç şey: 1. **Doğum günü problemi** — sadece 23 kişide iki kişinin aynı gün doğma olasılığı neden %50'yi geçer. 2. **Aksiyomlardan özellikler** — tümleyen $P(A^c) = 1 - P(A)$ ve tekdüzelik $A \subseteq B \Rightarrow P(A) \le P(B)$. 3. **İçerme-dışarma** — ayrık olmayan olayların birleşim olasılığı; ve ünlü $1/e$ sonucuyla biten matching problemi. > *"very surprising to most people the first time that they see this result."* — Blitzstein, 0:29 ::: {.callout-tip title="Builder Notu — ML Köprüleri"} - **Doğum günü problemi = hash collision.** Kriptografide **birthday attack** ($2^{n/2}$ denemede bir hash'i kırmak) ve ML'de **feature hashing** aynı matematiğe dayanır. - **$\binom{K}{2}$ çiftler = çoklu karşılaştırma.** Çok hipotez/çift test edince bazıları şans eseri anlamlı çıkar — **p-hacking** ve **Bonferroni** düzeltmesinin kökü. - **İçerme-dışarma → union bound** $P(\cup A_i) \le \sum P(A_i)$ — PAC öğrenmenin iş atı. - **$1/e$** rastgele permütasyonlarda, **secretary problem**'in optimal durmasında, **bootstrap OOB**'de karşına çıkar. ::: ## Doğum Günü Problemi: Kurulum {#sec-dogum-kurulum} Problem basit: bir partide $K$ kişi var; **en az iki kişinin aynı gün doğmuş** olma olasılığı nedir? (Belirli iki kişi değil — *herhangi* bir çift.) **Varsayımlar:** - Yılda 365 gün (29 Şubat dışlandı). - 365 gün **eşit olası**. - Doğum günleri **bağımsız**. Kolay durum: $K > 365$ ise olasılık tam $1$. Çünkü 365 kutu (gün) ve 365'ten fazla kişi varsa, en az bir kutuda mutlaka birden çok kişi olur — **güvercin yuvası ilkesi (pigeonhole)**. Asıl ilginç durum $K \le 365$. Sezgi ne diyor? Blitzstein yıllarca insanlara sormuş: "50/50 şans için kaç kişi gerekir?" Tipik tahmin 150–180. **Gerçek cevap: 23.** ::: {.callout-tip title="Builder Notu — Hash Collision"} Bu problem doğrudan **hash tablosu collision**'ıdır. Kriptografideki **birthday attack** de buradan gelir — $m$ bit'lik bir hash'te çakışma bulmak $\approx 2^{m/2}$ deneme sürer (kaba kuvvetin $2^m$'inden çok daha az), bu yüzden güvenli hash'ler uzun olmalı. Aynı sezgi, ML'de **feature hashing** kullanırken çakışma sıklığını tahmin eder. ::: ## Doğum Günü: Tümleyenle Hesap {#sec-tumleyenle-hesap} Doğrudan "en az bir eşleşme" olasılığını saymak zor; **tümleyenle** (hiç eşleşme yok) çalışmak çok daha kolay. > *"it's a little bit easier to work with the complement first."* — Blitzstein, 9:06 Naif tanım. Payda çarpma kuralından: her kişinin 365 olası günü → $365^K$. Pay için kişileri ID sırasıyla düşün: birincinin 365, ikincinin (birinciyle çakışmayan) 364, $\ldots$, $k$. kişinin $365 - k + 1$ seçeneği: $$ P(\text{hiç eşleşme yok}) = \frac{365 \cdot 364 \cdots (365 - K + 1)}{365^K} $$ (Tam **$K$ terim** olmalı; son terimde $+1$'i unutmak en sık off-by-one hatasıdır.) Eşleşme olasılığı: $$ P(\text{en az bir eşleşme}) = 1 - \frac{365 \cdot 364 \cdots (365 - K + 1)}{365^K} $$ ```{python} #| label: fig-dogum-gunu #| fig-cap: "Doğum günü eğrisi. $K=23$ → 0,507 (eşik 50%); $K=50$ → 0,97; $K=100$ → 0,99999+. Lineer büyümeyen, gözden geçirilemeyecek kadar dik bir eğri." #| fig-width: 10 #| fig-height: 5.5 import math import numpy as np import matplotlib.pyplot as plt def p_eslesme(K, gun=365): if K > gun: return 1.0 p = 1.0 for i in range(K): p *= (gun - i) / gun return 1 - p Ks = np.arange(1, 81) ps = [p_eslesme(int(K)) for K in Ks] fig, ax = plt.subplots(figsize=(10, 5.5)) ax.plot(Ks, ps, color='#A51C30', linewidth=2.5, marker='o', markersize=4) ax.axhline(0.5, color='#6B7280', linestyle='--', linewidth=1, alpha=0.7) ax.axvline(23, color='#DD6B20', linestyle='--', linewidth=2) # Eşik etiketi ax.annotate(f'K = 23 → 0,507\n(eşik %50)', xy=(23, 0.507), xytext=(35, 0.35), arrowprops=dict(arrowstyle='->', color='#DD6B20', linewidth=1.5), fontsize=11, color='#6B0E1B', weight='bold') # Belirgin noktalar for K_isaret in [23, 50, 75]: p_isaret = p_eslesme(K_isaret) ax.plot(K_isaret, p_isaret, 'o', markersize=10, markerfacecolor='#DD6B20', markeredgecolor='#6B0E1B') ax.annotate(f'{p_isaret:.3f}', xy=(K_isaret, p_isaret), xytext=(K_isaret + 1, p_isaret - 0.04), fontsize=10, color='#6B0E1B') ax.set_xlabel('Kişi sayısı $K$', fontsize=12) ax.set_ylabel('$P(\\text{en az iki kişi aynı gün})$', fontsize=12) ax.set_title('Doğum günü problemi — %50 eşiği $K = 23$\'te aşılır', fontsize=12) ax.grid(True, alpha=0.3) ax.set_xlim(0, 80); ax.set_ylim(0, 1.05) plt.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — 'En Az Bir' Refleksi"} "$P(\text{en az bir}) = 1 - P(\text{hiç})$" kalıbı ML'de her yerde: **dropout**'ta bir nöronun en az bir adımda aktif kalma olasılığı, $n$ denemede en az bir başarı ($1 - (1-p)^n$), bir veri artırma zincirinde en az bir dönüşümün uygulanması. Zor olan "en az bir"i, kolay olan "hiç"in tümleyeniyle hesaplamak temel bir reflekstir. ::: ## Neden 23? Sezgi: $\binom{K}{2}$ Çiftler {#sec-cift-sezgi} 23 sayısı neden bu kadar küçük? Çünkü sezgimiz yanlış niceliğe bakıyor. Önemli olan **kaç kişi** ($K$) değil, **kaç çift** ($\binom{K}{2}$). $$ \binom{K}{2} = \frac{K(K-1)}{2}, \qquad \binom{23}{2} = \frac{23 \cdot 22}{2} = 253 $$ > *"The more relevant quantity is not K, but K choose 2."* — Blitzstein, 13:43 23 kişi az gibi ama aralarında **253 çift** var ve bu çiftlerin *herhangi* biri eşleşebilir. 253, 365'in mertebesine yakın — işte o zaman %50 makul görünüyor. > *"the biggest coincidence of all would be if there were no coincidences."* — Blitzstein, 16:19 ```{python} #| label: fig-cift-vs-kisi #| fig-cap: "Sezgi-karşıtı eksen: $K$ lineer ama $\\binom{K}{2}$ ikinci dereceden büyür. K=23 = 253 çift, K=50 = 1225 çift. Eşleşme olasılığı çift sayısıyla hizalanır." #| fig-width: 10 #| fig-height: 4.5 K = np.arange(1, 71) ciftler = K * (K - 1) // 2 fig, ax1 = plt.subplots(figsize=(10, 4.5)) ax1.bar(K, ciftler, color='#DD6B20', alpha=0.7, label='$\\binom{K}{2}$ çift sayısı', edgecolor='#9a3412') ax1.plot(K, K, color='#2C5282', linewidth=2.5, label='$K$ kişi sayısı (lineer)') ax1.axhline(365, color='#A51C30', linestyle='--', linewidth=2, label='365 gün eşiği') ax1.axvline(23, color='#6B0E1B', linestyle=':', linewidth=1.5) ax1.text(23.3, 1200, 'K=23\n253 çift', fontsize=10, color='#6B0E1B', weight='bold') ax1.set_xlabel('K (kişi)', fontsize=12) ax1.set_ylabel('sayı', fontsize=12) ax1.set_title('$K$ lineer, $\\binom{K}{2}$ kuadratik — eşleşme \"çift sayısıyla\" yarışır', fontsize=12) ax1.legend(loc='upper left', fontsize=11) ax1.grid(True, alpha=0.3) plt.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — Çoklu Karşılaştırma ve P-Hacking"} Bu, **çoklu karşılaştırma (multiple comparisons)** probleminin ta kendisi. Çok sayıda hipotez veya çift test edersen, bir kısmı saf şans eseri "anlamlı" çıkar — çünkü önemli olan tekil testlerin değil **karşılaştırma sayısının** büyüklüğüdür. **P-hacking** tam budur. **Bonferroni düzeltmesi** anlamlılık eşiğini test sayısına bölerek bunu telafi eder — doğum günü sezgisinin istatistiksel karşılığı. ::: ## Olasılığı Alan Gibi Düşün + Tümleyen Kuralı {#sec-tumleyen} Aksiyomları hatırla: $P(\varnothing) = 0$, $P(S) = 1$ ve ayrık olaylar için toplanabilirlik. Bu iki kuralı yazıya dökmek, büyük ölçüde **Kolmogorov**'un eseri. Sezgi için olasılığı **alan** gibi düşün: Venn diyagramında tüm $S$'nin alanı $1$'dir; bir olayın olasılığı, kapladığı alandır. **Özellik 1 (tümleyen kuralı):** $$ P(A^c) = 1 - P(A) $$ **İspat (3 satır):** Aksiyom 1'den $1 = P(S)$. $S = A \cup A^c$ ayrık. Aksiyom 2 → $P(S) = P(A) + P(A^c)$. Yani $P(A^c) = 1 - P(A)$. ∎ ::: {.callout-tip title="Builder Notu — Ölçü ve Normalizasyon"} "Olasılık = alan" sezgisi, olasılığın bir **ölçü (measure)** olmasının habercisi (Ders 12+). İspattaki kalıp — "$S$'yi ayrık parçalara böl, toplamları $1$" — normalizasyonun kendisidir. Pratikte: $P(\text{hata}) = 1 - P(\text{doğru})$ kalıbı her yerde. ::: ## Tekdüzelik: $A \subseteq B \Rightarrow P(A) \le P(B)$ {#sec-tekduzelik} **Özellik 2 (tekdüzelik / monotonluk):** $A$ olayı $B$'nin içindeyse ($A$ gerçekleşince $B$ de gerçekleşiyor), $A$'nın olasılığı $B$'ninkinden büyük olamaz. $$ A \subseteq B \;\Rightarrow\; P(A) \le P(B) $$ **İspat:** $B = A \cup (B \cap A^c)$, ayrık. Aksiyom 2: $P(B) = P(A) + P(B \cap A^c)$. Olasılıklar negatif olamayacağından $P(B) \ge P(A)$. ∎ ::: {.callout-tip title="Builder Notu — CDF Monotonluğu"} Tekdüzelik bir ölçünün temel özelliğidir. Birikimli dağılım fonksiyonunun ([CDF](08-rd-dagilimlari.qmd)) artan olmasının nedeni budur. Sınır kurarken de kritik: bir hata olayını, onu içeren daha büyük bir olayla üstten sınırlayabilirsin — union bound'un mantığı. ::: ## İçerme-Dışarma (Inclusion-Exclusion) {#sec-icerme-disarma} Ayrık olaylarda $P(A \cup B) = P(A) + P(B)$. Peki ayrık değillerse? Venn diyagramında $A$ ile $B$'nin alanlarını toplarsan, **kesişimi iki kez** sayarsın; bir kez geri çıkarırsın: $$ P(A \cup B) = P(A) + P(B) - P(A \cap B) $$ **İspat (disjointification).** Aksiyom 2 yalnızca ayrık olaylara uygulanır. $A \cup B = A \cup (B \cap A^c)$, ayrık. $P(A \cup B) = P(A) + P(B \cap A^c)$. Ayrıca $B = (A \cap B) \cup (A^c \cap B)$ ayrık, $P(B \cap A^c) = P(B) - P(A \cap B)$. Birleştir, sonuç çıkar. ∎ > *"disjointification"* — Blitzstein, 30:11 Üç olaya genelleme (işaretler dönüşümlü): $$ 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) $$ ```{python} #| label: fig-venn-iep #| fig-cap: "Venn ile içerme-dışarma: $A$ ve $B$ alanlarını toplarsan kesişimi iki kez sayarsın — bir kez çıkar. Üç olay için: tek olayları topla, çiftleri çıkar, üçlüyü ekle (dönüşümlü işaretler)." #| fig-width: 10 #| fig-height: 4.5 from matplotlib.patches import Circle, Wedge fig, axes = plt.subplots(1, 2, figsize=(10, 4.5)) # Sol: iki olay ax = axes[0] ax.add_patch(Circle((-0.5, 0), 1.2, facecolor='#DD6B20', alpha=0.45, edgecolor='#9a3412', linewidth=2)) ax.add_patch(Circle((0.5, 0), 1.2, facecolor='#2C5282', alpha=0.45, edgecolor='#1e3a5f', linewidth=2)) ax.text(-1.2, 0, '$A$', fontsize=20, color='#6B0E1B', weight='bold', ha='center', va='center') ax.text(1.2, 0, '$B$', fontsize=20, color='#1e3a5f', weight='bold', ha='center', va='center') ax.text(0, 0, '$A \\cap B$\n(iki kez sayıldı)', fontsize=10, ha='center', va='center', color='white', weight='bold') ax.set_xlim(-2.5, 2.5); ax.set_ylim(-1.7, 1.7); ax.set_aspect('equal') ax.set_title('$P(A \\cup B) = P(A) + P(B) - P(A \\cap B)$', fontsize=12) ax.set_xticks([]); ax.set_yticks([]) for sp in ax.spines.values(): sp.set_visible(False) # Sağ: üç olay ax = axes[1] r = 1.0 merkezler = [(-0.6, 0.4), (0.6, 0.4), (0, -0.6)] renkler = ['#DD6B20', '#2C5282', '#6B46C1'] etiketler = ['$A$', '$B$', '$C$'] for (cx, cy), c, e in zip(merkezler, renkler, etiketler): ax.add_patch(Circle((cx, cy), r, facecolor=c, alpha=0.40, edgecolor=c, linewidth=2)) ax.text(cx + 1.05*(cx/abs(cx) if cx else 0), cy + (0.5 if cy > 0 else -0.5), e, fontsize=20, color=c, weight='bold', ha='center', va='center') ax.set_xlim(-2.5, 2.5); ax.set_ylim(-2, 1.7); ax.set_aspect('equal') ax.set_title('3 olay: tekleri topla, çiftleri çıkar, üçlüyü ekle', fontsize=12) ax.set_xticks([]); ax.set_yticks([]) for sp in ax.spines.values(): sp.set_visible(False) plt.tight_layout() plt.show() ``` ::: {.callout-tip title="Builder Notu — Union Bound ve PAC"} İçerme-dışarmayı ilk terimde keserek **union bound (Boole eşitsizliği)** elde edilir: $$P\left(\bigcup_i A_i\right) \le \sum_i P(A_i)$$ Bu eşitsizlik ML teorisinin iş atıdır: **PAC öğrenme** ve **genelleme sınırları**, çok sayıda "kötü olay"ı union bound ile üstten sınırlar; **Bonferroni** çoklu-test düzeltmesi de aynı sınırdır. İçerme-dışarma kesin değeri verir; union bound her yerde kullanılan ucuz üst sınırdır. ::: ## Matching Problem (de Montmort, 1713) ve $1/e$ {#sec-matching-1-e} İçerme-dışarmanın güzel uygulaması, 1713'ten kalma kumar oyunu. Deste $1\ldots n$ numaralı $n$ kart. Karıştır, sonra teker teker aç ve $1, 2, 3, \ldots$ diye say. Eğer **$j$. açılan kartın üzerinde $j$ yazıyorsa** "eşleşme" olur. En az bir eşleşme olasılığı? $A_j$ = "$j$. karttaki sayı $j$" olayı. İstediğimiz $P(A_1 \cup A_2 \cup \ldots \cup A_n)$. Simetri her şeyi kolaylaştırıyor: - $P(A_j) = 1/n$. - $P(A_1 \cap A_2) = (n-2)! / n! = 1/(n(n-1))$. - Genel: $P(A_1 \cap \ldots \cap A_k) = (n-k)!/n!$. İçerme-dışarma. Her terimde $n$'ler sadeleşir: $$ P\left(\bigcup_{j=1}^{n} A_j\right) = 1 - \frac{1}{2!} + \frac{1}{3!} - \frac{1}{4!} + \cdots \approx 1 - \frac{1}{e} \approx 0{,}632 $$ > *"This should remind you of the Taylor series for e to the x ... this is approximately one minus one over e."* — Blitzstein, 48:43 Şaşırtıcı: en az bir eşleşme olasılığı, $n$'e neredeyse **bağımsız** olarak $\approx 0{,}632$'ye oturur. ```{python} #| label: fig-matching-1e #| fig-cap: "Matching problem: en az bir eşleşme olasılığı $n$'den hızla bağımsızlaşır ve $1 - 1/e \\approx 0{,}632$'ye oturur. Aynı $1/e$, bootstrap OOB oranında da çıkar." #| fig-width: 10 #| fig-height: 4.5 import math import numpy as np import matplotlib.pyplot as plt ns = np.arange(2, 21) p_match = [sum((-1)**(k+1) / math.factorial(k) for k in range(1, n + 1)) for n in ns] p_bootstrap_in = [1 - (1 - 1/n)**n for n in ns] hedef = 1 - 1/math.e fig, ax = plt.subplots(figsize=(10, 4.5)) ax.plot(ns, p_match, 'o-', color='#A51C30', linewidth=2.2, markersize=7, label='matching: $P(\\text{≥ 1 eşleşme})$') ax.plot(ns, p_bootstrap_in, 's-', color='#2C5282', linewidth=2.2, markersize=7, label='bootstrap: $1 - (1 - 1/n)^n = P(\\text{nokta seçildi})$') ax.axhline(hedef, color='#DD6B20', linestyle='--', linewidth=2, label=f'$1 - 1/e = {hedef:.4f}$') ax.set_xlabel('$n$', fontsize=12) ax.set_ylabel('olasılık', fontsize=12) ax.set_title('İki yolla $1 - 1/e$: matching problem ve bootstrap', fontsize=12) ax.legend(loc='lower right', fontsize=10) ax.grid(True, alpha=0.3) ax.set_xticks(ns) ax.set_ylim(0.3, 0.75) plt.tight_layout() plt.show() ``` ::: {.callout-important title="Builder Notu — Bootstrap OOB ve $1/e$"} $1/e$ ML'de doğrudan **bootstrap**'ta karşına çıkar. $n$ örnekten yerine koyarak $n$ örnek çektiğinde, belirli bir noktanın hiç seçilmeme olasılığı $(1 - 1/n)^n \to 1/e \approx 0{,}368$. Yani her bootstrap örneği verinin $\approx \%63{,}2$'sini kullanır, kalan $\approx \%36{,}8$ **out-of-bag (OOB)** olur — **random forest**'ın OOB hata kestiriminin tam temeli. Aynı $1/e$ **derangement**'larda (hiç sabit noktası olmayan permütasyonlar) ve **secretary problem**'in $1/e$ durma kuralında da belirir. ::: ## Bu Dersin Özeti {#sec-ozet} 1. **Doğum günü problemi:** $K=23$ → %50,7; $K=50$ → %97; $K=100$ → %99,999+. 2. **Tümleyenle hesap:** "en az bir" yerine "hiç yok"u say; $P(\text{eşleşme}) = 1 - 365 \cdot 364 \cdots (365-K+1)/365^K$. 3. **Sezgi $\binom{K}{2}$:** Önemli olan kişi $K$ değil, çift sayısı; 23 kişi $\to$ 253 çift. 4. **Tümleyen kuralı:** $P(A^c) = 1 - P(A)$. 5. **Tekdüzelik:** $A \subseteq B \Rightarrow P(A) \le P(B)$. 6. **İçerme-dışarma:** $P(A \cup B) = P(A) + P(B) - P(A \cap B)$; genelde dönüşümlü işaretli toplam. İlk terimde kesince **union bound** $P(\cup A_i) \le \sum P(A_i)$. 7. **Matching problem:** En az bir eşleşme $\approx 1 - 1/e \approx 0{,}632$ ($n$'den bağımsız). ::: {.callout-important title="Tek bir cümle"} İki basit aksiyomdan tümleyen, tekdüzelik ve içerme-dışarma gibi tüm pratik kurallar türer; olasılığın en şaşırtıcı sonuçları (doğum günü, $1/e$) aslında "**kaç çift / kaç eşleşme**" diye doğru niceliği saymaktan ibarettir. ::: ## Kontrol Soruları {#sec-sorular} ::: {.callout-note collapse="true" title="Soru 1: 30 kişilik sınıfta en az iki kişinin aynı gün doğma olasılığı %50'den büyük mü?"} **Cevap:** Büyük. 23 kişide $0{,}507$ ve $K$ arttıkça olasılık **tekdüze artar** ($A_{23} \subseteq A_{30}$). Gerçekte $\approx \%70$. ::: ::: {.callout-note collapse="true" title="Soru 2: Adil zar 4 kez atılıyor. En az bir 6 gelme olasılığı?"} **Cevap:** Tümleyen ("hiç 6 yok"): $(5/6)^4 = 625/1296$. $P(\text{en az bir 6}) = 1 - 625/1296 = 671/1296 \approx 0{,}518$. ::: ::: {.callout-note collapse="true" title="Soru 3: 1-100 arası rastgele tam sayı. 2'ye veya 3'e bölünme olasılığı?"} **Cevap:** İçerme-dışarma. $|A| = 50$ (2'nin katları), $|B| = 33$ (3'ün katları), $|A \cap B| = 16$ (6'nın katları). $P = (50 + 33 - 16)/100 = 67/100 = 0{,}67$. ::: ::: {.callout-note collapse="true" title="Soru 4: (Builder) Bootstrap'ta n örnekten n çektiğinde belirli bir noktanın hiç seçilmeme olasılığı? Hangi ders kavramıyla bağlantılı?"} **Cevap:** Bir nokta her çekimde seçilmeme olasılığı $(1 - 1/n)$; $n$ bağımsız çekim → $(1 - 1/n)^n \to 1/e \approx 0{,}368$. Bootstrap verinin $\approx \%63{,}2$'sini kullanır, $\approx \%36{,}8$ **OOB**. Matching'deki $1 - 1/e$ ile **aynı $e$**; random forest'ın OOB kestiriminin temeli. ::: ## Egzersizler {#sec-egzersizler} **Egzersiz 1.** "Aynı ay" sürümü: 12 ay, eşit olası, bağımsız. %50'yi geçmek için kaç kişi yeter? Tahmin et, sonra formülü 365 yerine 12 ile kur. **Egzersiz 2.** 52 kartlık desteden 5 kart. En az bir as gelme olasılığını **tümleyenle** yaz. (İpucu: 48 karttan 5 seçmek = "hiç as yok".) **Egzersiz 3.** $P(A) = P(B) = P(C) = 0{,}5$; ikili kesişimler $0{,}3$; üçlü $0{,}1$. İçerme-dışarma ile $P(A \cup B \cup C)$? **Egzersiz 4.** *(Python — doğum günü simülasyon)* ```{python} #| label: ex-dogum-gunu-sim #| code-fold: false import random random.seed(0) def en_az_bir_eslesme(K, gun=365): gunler = [random.randint(1, gun) for _ in range(K)] return len(set(gunler)) < K K, N = 23, 100_000 oran = sum(en_az_bir_eslesme(K) for _ in range(N)) / N print(f"K={K} simülasyon: {oran:.4f} (formül beklenen: ~0.5073)") ``` **Egzersiz 5.** *(Sonraki ders)* Matching problem sonucundan: $n \to \infty$ iken "hiç eşleşme yok" olasılığı $1/e$'ye yaklaşır. Hiç sabit noktası olmayan permütasyonlara **derangement** denir; $n=4$ için tüm permütasyonları listeleyip derangement sayısını elle doğrula. ## Sonraki Ders İçin Hazırlık {#sec-sonraki} **Ders 4: Koşullu Olasılık** Kursun belki de en önemli kavramı: **koşullu olasılık** $P(A \mid B)$. Blitzstein bunu "istatistiğin ruhu" sayar; öğrenmek, yeni kanıt geldikçe inançları güncellemektir. Bayes teoreminin ve tüm Bayesian çıkarımın kapısı. ::: {.callout-warning title="Ders 4 öncesi yapılacak"} - Egzersizleri çöz — özellikle 4 (simülasyon) ve 5 (derangement / $1/e$). - Python'da "en az bir" olasılığını her zaman tümleyenle hesaplamayı alışkanlık edin. - Ana cümleyi tekrar oku: *"İki basit aksiyomdan tüm pratik kurallar türer…"* ::: ## Anahtar Kavramlar (Cheat Sheet) {#sec-cheat-sheet} | Kavram | Tanım | Blitzstein'de | |--------|-------|---------------| | **Doğum günü problemi** | $K=23 \to 0{,}507$ eşleşme | 8m16 | | **Pigeonhole** | $K > 365 \to P = 1$ | 6m37 | | **Tümleyenle hesap** | $P(\text{en az bir}) = 1 - P(\text{hiç})$ | 9m06 | | $\binom{K}{2}$ **sezgisi** | 23 kişi = 253 çift | 13m43 | | **Tümleyen kuralı** | $P(A^c) = 1 - P(A)$ | 22m50 | | **Tekdüzelik** | $A \subseteq B \Rightarrow P(A) \le P(B)$ | 25m02 | | **İçerme-dışarma** | $P(A \cup B) = P(A) + P(B) - P(A \cap B)$ | 28m08 | | **Disjointification** | Birleşimi ayrık yaz, Aksiyom 2 uygula | 30m11 | | **Union bound** | $P(\cup A_i) \le \sum P(A_i)$ | türetme | | **Matching problem** | $P(\text{eşleşme}) = 1 - 1/2! + 1/3! - \ldots$ | 39m50 | | $1/e$ **sonucu** | $\approx 0{,}632$; bootstrap OOB, derangement | 48m43 | ## ML Bağlantıları Özeti {#sec-ml-baglantilar} ::: {.callout-tip title="7 köprü"} 1. **Doğum günü problemi** → hash collision, kriptografide birthday attack ($\approx 2^{m/2}$), ML'de feature hashing. 2. $\binom{K}{2}$ **çiftler** → çoklu karşılaştırma, p-hacking, **Bonferroni** düzeltmesi. 3. **Tümleyen kuralı** → $P(\text{en az bir}) = 1 - P(\text{hiç})$; dropout, başarı denemeleri. 4. **Tekdüzelik** → ölçü; **CDF**'nin artan olması (Ders 8). 5. **İçerme-dışarma → union bound** → **PAC öğrenme** / genelleme sınırları, Bonferroni. 6. $1/e$ **(matching)** → **bootstrap OOB** ≈ %36,8, derangement, secretary problem. 7. **Olasılık = alan / aksiyomlar** → ölçü teorisi, softmax geçerliliği, marjinalleştirme. ::: ::: {.callout-important title="Tek bir şey alıp gideceksen"} Olasılığın sürprizleri (doğum günü, $1/e$) sezgiyi değil **doğru niceliği saymayı** test eder — kaç çift, kaç eşleşme. Ve "**en az bir**" sorusunu her zaman tümleyeniyle ("**hiç**") yenmeye bak. :::

4 Doğum Günü Problemi ve Olasılığın Özellikleri

4.1 Bu Derste Ne Var?

4.2 Doğum Günü Problemi: Kurulum

4.3 Doğum Günü: Tümleyenle Hesap

4.4 Neden 23? Sezgi: \(\binom{K}{2}\) Çiftler

4.5 Olasılığı Alan Gibi Düşün + Tümleyen Kuralı

4.6 Tekdüzelik: \(A \subseteq B \Rightarrow P(A) \le P(B)\)

4.7 İçerme-Dışarma (Inclusion-Exclusion)

4.8 Matching Problem (de Montmort, 1713) ve \(1/e\)

4.9 Bu Dersin Özeti

4.10 Kontrol Soruları

4.11 Egzersizler

4.12 Sonraki Ders İçin Hazırlık

4.13 Anahtar Kavramlar (Cheat Sheet)

4.14 ML Bağlantıları Özeti