Kan du bevisa att något existerar utan att faktiskt konstruera det? Kan slumpen hjälpa till att lösa helt deterministiska problem? Probabilistiska metoder använder sannolikhet för att bevisa existens av matematiska objekt eller för att hitta approximativa lösningar. Som att bevisa att det måste finnas en nål i höstacken genom att visa att chansen att inte hitta en är noll.

Fördjupning

Probabilistiska metoder använder sannolikhetsargument för icke-probabilistiska problem. Första momentmetoden visar existens: om E[X] > 0 finns objekt med önskad egenskap. Andra momentmetoden ger koncentration: om Var(X) är liten är X nära sitt väntevärde. Lovász Local Lemma hanterar beroende händelser. Randomiserade algoritmer använder slump för effektiv problemlösning.

Första momentmetoden

Första momentmetoden: Om X är icke-negativ slumpvariabel och E[X] > 0, då P(X > 0) > 0, så det finns instanser där X > 0. Grundläggande probabilistiskt existensbevis. Ofta tillämpad på indikatorvariabler där X räknar objekt med önskad egenskap.

Ramsey-tal nedre gräns

Ramsey-tal R(k,k) = minsta n så att varje 2-färgning av Kₙ innehåller monokromatisk Kₖ.

Bevis att R(k,k) > ⌊2^(k/2)⌋:

1. Färga varje kant i Kₙ röd/blå med sannolikhet 1/2

2. För varje k-delmängd S, låt X_S = 1 om S är monokromatisk

P(X_S = 1) = 2 · (1/2)^(k choose 2) = 2^(1-(k choose 2))

3. X = Σ X_S räknar monokromatiska k-klickar

E[X] = (n choose k) · 2^(1-(k choose 2))

4. För n = ⌊2^(k/2)⌋:

E[X] < (n^k/k!) · 2^(1-(k choose 2))

< (2^(k²/2)/k!) · 2^(1-k(k-1)/2)

= 2^(1-k(k-1)/4) / k!

< 1 för stora k

5. Så P(X = 0) > 0, det finns färgning utan monokromatisk Kₖ

⟹ R(k,k) > n = ⌊2^(k/2)⌋

Andra momentmetoden

Andra momentmetoden använder Chebyshevs olikhet för koncentration: P(|X - E[X]| ≥ t) ≤ Var(X)/t². Om variansen är liten relative till väntevärdet är X koncentrerat kring E[X]. Särskilt användbar när första momentmetoden visar E[X] > 0 men vi vill visa P(X > 0) nära 1.

Antal trianglar i slumpgraf

G(n,p) = slumpgraf på n noder, varje kant med sannolikhet p

Antal trianglar X = Σ_{i<j<k} X_{ijk} där X_{ijk} = 1 om {i,j,k} bildar triangel

Första moment:

E[X_{ijk}] = p³ (tre kanter oberoende)

E[X] = (n choose 3) · p³

Andra moment:

E[X²] = E[(Σ X_{ijk})²] = Σ_{i<j<k} Σ_{i'<j'<k'} E[X_{ijk} X_{i'j'k'}]

Fall:

· Disjunkta trianglar: E[X_{ijk} X_{i'j'k'}] = p⁶

· Delar en kant: E[X_{ijk} X_{i'j'k'}] = p⁵

· Delar två kanter: E[X_{ijk} X_{i'j'k'}] = p⁴

Var(X) = E[X²] - E[X]²

= O(n³p³) + O(n⁴p⁵) + O(n³p⁴) - O(n⁶p⁶)

För p = ω(n^(-1/2)): Var(X)/E[X]² → 0

⟹ P(X = 0) → 0, nästan alla grafer har trianglar

Lovász Local Lemma

Lovász Local Lemma hanterar 'dåliga' händelser som inte är oberoende. Om varje händelse Aᵢ har sannolikhet ≤ p och är oberoende av alla utom ≤ d andra händelser, och ep(d+1) ≤ 1, då P(⋂Āᵢ) > 0. Kraftfull när 'lokala' konflikter existerar men global lösning finns.

Satisfierbarhet med begränsat beroende

SAT-instans där varje klausul har ≥ k literals och varje variabel förekommer i ≤ 2^(k-2) klausuler.

Bevis att formeln är satisfierbar:

1. Tilldela varje variabel värde TRUE/FALSE med sannolikhet 1/2

2. För klausul C med k literals:

P(C osatisfied) = (1/2)^k

3. Klausul C delar variabler med ≤ k · 2^(k-2) andra klausuler

d = k · 2^(k-2)

4. Kontrollera Local Lemma villkor:

ep(d+1) = e · (1/2)^k · (k · 2^(k-2) + 1)

≤ e · (1/2)^k · 2k · 2^(k-2)

= ek · 2^(-2)

≤ 1 för k ≥ 5

5. Så P(alla klausuler satisfied) > 0

⟹ satisfierbar tilldelning existerar

Konstruktiv version (Moser-Tardos):

Algoritm som faktiskt hittar tilldelning i förväntad polynomtid

Randomiserade algoritmer

Randomiserade algoritmer använder slump för att uppnå bättre prestanda än deterministiska motsvarigheter. Monte Carlo algoritmer kan ge fel svar men med liten sannolikhet. Las Vegas algoritmer ger alltid rätt svar men slumpmässig körtid. Derandomisering konverterar randomiserade algoritmer till deterministiska.

Randomiserad QuickSort analys

QuickSort med slumpmässigt vald pivot:

Antal jämförelser C(n) för att sortera n element:

C(n) = Σᵢ₌₁ⁿ Σⱼ₌ᵢ₊₁ⁿ Xᵢⱼ

där Xᵢⱼ = 1 om element i och j jämförs

Sannolikhet att jämföra eᵢ och eⱼ:

P(Xᵢⱼ = 1) = 2/(j-i+1)

Motivering: eᵢ och eⱼ jämförs ⟺ en av dem väljs som pivot

före något element mellan dem

E[C(n)] = Σᵢ₌₁ⁿ Σⱼ₌ᵢ₊₁ⁿ 2/(j-i+1)

= 2 Σₖ₌₂ⁿ Σᵢ₌₁ⁿ⁻ᵏ⁺¹ 1/k

= 2 Σₖ₌₂ⁿ (n-k+1)/k

= 2n Σₖ₌₂ⁿ 1/k - 2 Σₖ₌₂ⁿ 1

= 2n(Hₙ - 1) - 2(n-1)

= 2nHₙ - 4n + 2

≈ 2n ln n

Genomsnittlig komplexitet O(n log n), mycket bättre än worst-case O(n²)

Chernoff bounds och koncentration

Chernoff bounds ger exponentiell koncentration för summor av oberoende slumpvariabler. Starkare än Chebyshev när oberoende finns. Hoeffdings olikhet för begränsade variabler. McDiarmids olikhet för funktioner med begränsad variation. Azuma-Hoeffding för martingaler.

Kugel-och-bin modell

Kasta m bollar i n bins slumpmässigt. Vad är max antal bollar i någon bin?

Xᵢ = antal bollar i bin i

E[Xᵢ] = m/n

Chernoff bound för Xᵢ ≥ (1+δ)m/n:

P(Xᵢ ≥ (1+δ)m/n) ≤ e^(-δ²m/(3n))

Union bound över alla bins:

P(∃i: Xᵢ ≥ (1+δ)m/n) ≤ n · e^(-δ²m/(3n))

För m = n (lika många bollar som bins):

P(max load ≥ (1+δ)) ≤ n · e^(-δ²n/3)

Välj δ = √(3 ln n / n):

P(max load ≥ 1 + √(3 ln n / n)) ≤ n · e^(-ln n) = 1/n

Så med hög sannolikhet: max load = 1 + O(√(ln n / n))

För m = n ln n: max load = O(ln n / ln ln n) med hög sannolikhet

Tillämpningar i grafteori

Probabilistiska metoder revolutionerat grafteori. Bevis för existens av grafer med extrema egenskaper. Slumpgrafer G(n,p) som modell. Tröskelfenomen: egenskaper dyker upp plötsligt vid kritiska sannolikheter. Regularity Lemma och Blow-up Lemma för stora grafer.

Kromatiskt tal för slumpgrafer

G(n,1/2): kromatiskt tal χ(G) koncentrerat kring n/(2 ln n)

Övre gräns (girig färgning):

Greedy-algoritm använder ≤ Δ+1 färger där Δ = max grad

I G(n,1/2): E[Δ] ≈ n/2, koncentrerat via Chernoff

Så χ(G) ≤ (1+o(1))n/2

Nedre gräns (klickar och oberoende mängder):

Största oberoende mängd α(G) ≈ 2 ln n

Så χ(G) ≥ n/α(G) ≈ n/(2 ln n)

Största klick ω(G) ≈ 2 ln n, så χ(G) ≥ ω(G) ≈ 2 ln n

Kombinera: χ(G) = (1+o(1)) n/(2 ln n)

Intressant: χ(G) >> ω(G) för slumpgrafer!

Finns grafer med stort kromatiskt tal men små klickar

Explicit konstruktion mycket svårare än probabilistisk existens

Vanliga misstag

❌ Använda första moment när andra moment behövs

E[X] > 0 visar existens, men P(X > 0) kan vara liten

Exempel: För koncentration behövs variansanalys med andra moment

❌ Ignorera beroenden i Local Lemma

Måste räkna beroendegrafen korrekt

Exempel: Underskatta antalet händelser som varje händelse beror på

❌ Felaktig derandomisering

Att en randomiserad algoritm fungerar garanterar inte derandomisering

Exempel: Metod med villkorlig sannolikhet kräver noggrann analys

Tillämpningar

Datorvetenskap

Randomiserade algoritmer för approximation och optimering

Exempel: Randomiserad rounding för LP-relaxation, skip lists, hash tables

Kombinatorisk optimering

Existensbevis för optimala strukturer

Exempel: MAX-SAT approximation, set cover, TSP heuristiker

Nätverksteori

Modellering av stora nätverk och robusthet

Exempel: Internet-topologi, sociala nätverk, biologiska nätverk

Övningar

1 Medel

Använd första momentmetoden för att visa att det finns en graf på n noder med minst n²/8 kanter och ingen triangel.

Tips

Börja med slumpgraf G(n,1/2) och ta bort en kant från varje triangel

Visa facit

Svar: E[antal trianglar] = (n choose 3)/8. Ta bort en kant per triangel: kvar ≥ n²/4 - n³/48 ≥ n²/8

Förklaring: Slumpgraf har förväntade n²/4 kanter och n³/48 trianglar. Första moment visar existens av triangelfri graf med många kanter.

2 Svår

Visa att för SAT med 3-klausuler där varje variabel förekommer i ≤ 3 klausuler finns satisfierbar tilldelning.

Tips

Använd Lovász Local Lemma med p = 1/8, d = 6

Visa facit

Svar: ep(d+1) = e/8 · 7 = 7e/8 < 1 ✓

Förklaring: Varje klausul har sannolikhet 1/8 att vara osatisfied och beror på ≤ 6 andra klausuler via delade variabler.

3 Svår

Beräkna sannolikheten att slumpgraf G(n,1/2) är sammanhängande för stora n.

Tips

Använd att disconnected ⟺ finns cut av storlek k med k(n-k) kanter missing

Visa facit

Svar: P(sammanhängande) = 1 - O(n·2^(-n/4)) → 1

Förklaring: Union bound över alla cuts ger exponentiellt avtagande sannolikhet för disconnected grafer.

Sammanfattning

Probabilistiska metoder använder sannolikhet för deterministiska problem. Första momentmetoden visar existens via väntevärde. Andra momentmetoden ger koncentration via varians. Lovász Local Lemma hanterar lokalt beroende händelser. Chernoff bounds ger exponentiell koncentration. Randomiserade algoritmer uppnår bättre prestanda med slump. Kraftfulla verktyg inom grafteori, kombinatorik och algoritmdesign. Ofta enklare än konstruktiva bevis men ger inte explicit konstruktion.