Elementy rachunku prawdopodobieństwa na poziomie olimpijskim: strategie, sztuczki i rozwiązania

Uważaj na te pułapki, zanim zaczniesz liczyć

Fałszywa niezależność i mylące „intuicje”

Na poziomie olimpijskim rachunek prawdopodobieństwa często rozkłada na łopatki nie trudność obliczeń, ale skrótowe założenia. Najczęściej spotykana pułapka to automatyczne przyjmowanie niezależności. Rzut monetą i wybór karty? Owszem, niezależne – dopóki procedura losowania nie wprowadza ukrytej zależności. Losowania bez zwracania, permutacje, układy bez powtórzeń – to typowe scenariusze, w których zdarzenia „brzmią” niezależnie, a takie nie są. Każde użycie wzoru P(A ∩ B) = P(A)P(B) musi mieć solidną podstawę.

Drugi klasyk: mieszasz warunkowanie z ogólnym prawdopodobieństwem. Jeżeli P(A|B) jest łatwe, nie znaczy, że P(A) też. Często kluczowe jest poprawne rozpisanie na przypadki, a nie „wybieranie” najwygodniejszego warunku.

Trzeci błąd: intuicyjne „uśrednianie” bez sprawdzenia, co średnia reprezentuje. Średnia liczba zdarzeń nie informuje o rozkładzie. Może być 0,9 w średniej, a z prawdopodobieństwem 0,99 nic się nie wydarza, a z 0,01 – dzieje się bardzo dużo. Na olimpiadzie granice z Markowa lub Czebyszewa bywają zbyt grube – warto umieć sięgnąć po ostrzejsze narzędzia albo argument strukturalny.

Rozpoznawanie struktury: bez tego tracisz czas

Przed rachunkami rozkoduj wzorzec zadania. Czy są równoważne pozycje (symetria)? Czy proces kończy się losowo (czas zatrzymania)? Czy zdarzenia powtarzają się wiele razy z podobną strukturą (zmienne wskaźnikowe)? Czy sumujesz małe niezależne wkłady (granice Chernoffa)? Wejście w zły paradygmat (np. liczenie po omacku tam, gdzie działa prosty wskaźnik) potrafi podwoić czas i ryzyko błędów.

Ustal: co jest elementarnym eksperymentem, czy wyników jest skończenie wiele, czy próba jest złożona (proces wieloetapowy), i jakie są „obiekty naturalne” – karty, miejsca, krawędzie grafu, pary elementów, pozycje w permutacji. Właśnie na tych obiektach najczęściej definiuje się zmienne wskaźnikowe, inwarianty lub rekurencje.

Krótki brief: pytania, które chcesz rozstrzygnąć

• Kiedy użyć liniowości wartości oczekiwanej, a kiedy nie zadziała?
• Kiedy unia zdarzeń i proste oszacowania są wystarczające, a kiedy wchodzi zasada inkluzji-wykluczenia lub metoda drugiego momentu?
• Jak rozpoznać zadanie na „pierwszy krok” i rozwiązać je rekurencyjnie lub warunkowaniem?
• W jakich sytuacjach warto użyć symetrii, parowania, sprzężenia (coupling), a kiedy to strata czasu?
• Jak bezpiecznie korzystać z nierówności koncentracyjnych (Markowa, Czebyszewa, Chernoffa, Azumy) na poziomie olimpijskim?
• Kiedy metoda probabilistyczna (dowód istnienia) ma sens, a kiedy potrzebujesz konstrukcji?
• Jak nie wpaść w pułapki: pozorna niezależność, złe warunkowanie, dzielenie przez zero-prawdopodobieństwo, błędna enumeracja?

Trzymaj te pytania z boku kartki – przyspieszają decyzje i pomagają wybrać strategię bez błądzenia. Zaczynaj ostrożnie i testuj metodę na małych parametrach n.

Mapa decyzji: jak wybierać metodę do zadania olimpijskiego

Kluczowe kryteria wyboru techniki

Nie ma jednej „najlepszej” sztuczki – są kryteria, które prowadzą do sensownego wyboru:

• Powtarzalna struktura (wiele „podobnych” zdarzeń) – definiuj wskaźniki i sumuj oczekiwane wartości.
• Silna symetria (rzeczy „nie do odróżnienia”) – użyj argumentu równości szans, inwariancji lub dwusposobowego zliczania.
• Proces krokowy z naturalnym „pierwszym ruchem” – rozbij na przypadki, zbuduj rekurencję lub wykorzystaj łańcuch Markowa.
• Interesuje Cię „co najmniej jedno wystąpienie” – testuj prosty związek unii, potem rozważ inkluzję-wykluczenie i/lub drugi moment.
• Sumujesz niezależne wkłady i szukasz prawdopodobieństw odchyleń – Chernoff. Gdy zależności są „łagodne”, ale kroki ograniczone – Azuma.
• Chcesz udowodnić istnienie obiektu – metoda probabilistyczna, czasem z ponumerowaniem losowego procesu i odrzucaniem złych zdarzeń.

Jeśli zadanie „bije po oczach” sumą wielu małych wkładów, zacznij od liniowości wartości oczekiwanej. Jeśli pytanie dotyczy „czy coś w ogóle istnieje”, a dokładne policzenie jest trudne – kierunek: drugi moment lub metoda probabilistyczna.

Kiedy warto, a kiedy nie – szybkie konteksty

Decyzyjne ścieżki: które narzędzie wybrać teraz

Liniowość wartości oczekiwanej: szybki start czy ślepa uliczka?

Warto, gdy liczysz sumę wielu podobnych wkładów: stałe punkty w permutacji, liczba krawędzi spełniających warunek, liczba kolizji w losowaniu z powtórzeniami. Zdefiniuj wskaźniki, zsumuj E[X_i] bez martwienia się zależnościami.

Uważaj, gdy pytanie dotyczy rzadkości (P(X=0), P(X≥k)) lub precyzyjnych ogonów. Sama E[X] nie powie, czy zdarzenie „w ogóle” zachodzi z dodatnim prawdopodobieństwem – do tego potrzebna jest wariancja lub koncentracja.

Mini przykład: w losowej permutacji liczba stałych punktów ma E[X]=1 (wskaźniki po pozycjach). To szybko daje przybliżenie P(X>0)≈1−1/e, ale do dolnej granicy na P(X>0) bezpośrednio potrzebujesz już drugiego momentu.

Rekomendacja: zacznij od E[X]; jeśli pytanie jest „czy coś istnieje?”, przełącz się natychmiast na Var(X) lub lepszą technikę ogonową.

Działaj: w pierwszej minucie wypisz X=∑X_i i policz E[X] wprost z definicji wskaźników.

Inkluzja–wykluczenie kontra prosta unia: jak nie przedobrzyć

Warto, gdy zdarzenia mają kontrolowane nakładanie (symetrie, równe przecięcia, lokalne zależności). Pierwsze 2–3 składniki często dają ostrą granicę i wyraźną poprawę nad sumą prawdopodobieństw.

Uważaj, gdy przecięcia są licznie i trudno policzalne – pełne PIE bywa pułapką czasową i rachunkową. Gdy nakładanie jest „gęste”, rozważ metodę drugiego momentu lub Lovász Local Lemma (jeśli zależności są lokalne).

Mini przykład: w „co najmniej jedna kolizja” przy losowaniu kuponów, suma unii daje górę, a do dołu wystarczą pierwsze przecięcia par (kolizje parami). Głębsze składniki rzadko zmieniają rząd wielkości.

Rekomendacja: użyj unii jako szybkiej góry; jeśli jest luźna, dołóż 1–2 poziomy PIE, ale tylko wtedy, gdy przecięcia policzysz jednym wzorem.

Działaj: zanim wejdziesz w PIE, naszkicuj, jak wygląda przecięcie k zdarzeń – jeśli nie widzisz prostego wzoru, zmień metodę.

Drugi moment i Paley–Zygmund: kiedy odwaga popłaca

Warto, gdy chcesz pokazać, że X>0 z dodatnim prawdopodobieństwem, a samo E[X] to za mało. Jeśli potrafisz policzyć E[X] i E[X^2], to P(X>0) ≥ E[X]^2/E[X^2] często zamyka temat elegancko.

Uważaj, gdy X ma rozłożone „ciężkie ogony” lub gdy zależności są tak silne, że E[X^2] eksploduje. Wtedy lepsza może być dekompozycja na bloki, ograniczenie zależności lub LLL.

Mini przykład: liczba struktur spełniających lokalne warunki (np. pewne parowania) – wskaźniki po obiektach + kontrola par wskaźników prowadzi do sensownego ilorazu E[X]^2/E[X^2].

Rekomendacja: jeśli celem jest istnienie, a masz policzalne pary „kolidujących” obiektów, włącz drugi moment przed wchodzeniem w głębokie PIE.

Działaj: policz E[X] i szkic E[X^2] na jednej kartce – jeśli iloraz wygląda stabilnie, jedziesz dalej.

Koncentracja: Markow–Czebyszew czy Chernoff–Azuma?

Warto (Markow/Czebyszew), gdy potrzebujesz szybkiej, uniwersalnej bariery bez założeń o niezależności. To tarcza, nie skalpel.

Warto (Chernoff), gdy masz sumę niezależnych/bliźniaczo podobnych zmiennych 0–1 lub ograniczonych i potrzebujesz ostrych ogonów wykładniczych. Idealne w zadaniach „ile razy zajdzie rzadkie zdarzenie”.

Warto (Azuma/martingały), gdy występują zależności, ale każdy krok zmienia X o mało (różnice ograniczone). Działa np. w ekspozycjach krawędzi grafu „po jednej”.

Uważaj: Chernoff wymaga (prawie) niezależności; Azuma wymaga dobrej filtracji i ograniczeń różnic. Bez tego granice będą iluzją.

Mini przykład: liczba trafień w losowych próbach – Chernoff da precyzyjne P(|X−E[X]|>t). Długość prefiksu spełniającego warunek w losowym procesie odsłanianym krok po kroku – Azuma.

Rekomendacja: jeśli widzisz „sumę Bernoullich” – strzel w Chernoffa; jeśli widzisz „odsłanianie po jednym z ograniczonym wpływem” – idź w Azumę.

Działaj: w 30 sekund ustal, czy potrafisz zapisać X jako sumę kroków z ograniczoną zmianą – to przełącza cię na Azumę.

Symetria, parowanie i dwusposobowe liczenie: skrót do sedna

Warto, gdy obiekty są nieodróżnialne z punktu widzenia pytania (pozycje w permutacji, krawędzie w regularnym grafie, miejsca w urnie). Równość szans i argumenty „zlicz to na dwa sposoby” często dają natychmiastowe E[X] lub P(A).

Uważaj, gdy symetria jest pozorna: warunek boczny łamie równoważność klas. Wtedy szybkie „po równo” bywa błędne.

Mini przykład: w permutacji prawdopodobieństwo, że i jest stały, to 1/n niezależnie od i – stąd E[stałych]=1 bez rachunków.

Rekomendacja: najpierw zapytaj „czy pozycje są nieodróżnialne?” – jeśli tak, licz wprost przez symetrię zamiast rozwijać wzory.

Działaj: zanim włączysz algebra, poszukaj jednego zdania o równości rozkładów stanów.

Pierwszy krok, rekurencje i sensowny stan

Warto, gdy naturalnie pojawia się stan i warunek stopu (gry losowe, przejścia po grafie, powtarzane próby). Rozpisz P lub E od stanu do stanu – często dostajesz krótką rekurencję.

Uważaj, gdy stan jest źle dobrany (zbyt ubogi – traci informację, zbyt bogaty – eksploduje wymiar). Zanim piszesz równania, sprawdź, czy proces jest Markowowski w wybranym opisie.

Mini przykład: prawdopodobieństwo ruin w spacerze prostym – równanie z pierwszego kroku prowadzi do zamkniętej formuły bez sum po wszystkich trajektoriach.

Rekomendacja: modeluj tylko to, co wpływa na następny ruch; resztę „zapomnij”. To chroni przed rekurencją potworem.

Działaj: szkicuj graf stanów i strzałki z prawdopodobieństwami zanim cokolwiek liczysz.

Sprzężenia (coupling): kontrolowane porównanie procesów

Warto, gdy chcesz porównać skomplikowany proces z prostym, który dominuje/stłumia. Konstrukcja wspólnej przestrzeni losowej bywa krótsza niż bezpośrednie liczenie.

Uważaj, gdy sprzężenie jest sztuczne i trudne do kontrolowania – łatwo stworzyć piękny opis, który nie daje liczb. Szukaj monotoniczności i naturalnych parowań krok w krok.

Mini przykład: porównanie liczby sukcesów w zależnej próbie z Bin(n,p) przez „nadmiarowe” losowania – dostajesz górę/dół na ogony bez całego rozkładu zależnego.

Rekomendacja: jeśli myślisz „to zachowuje się jak binom”, spróbuj zdefiniować wspólne rzuty tak, by porządek X≤Y był zachowany prawie na pewno.

Działaj: narysuj dwie kolumny kroków i zaprojektuj wspólny generator losowości.

Metoda probabilistyczna czy konstrukcja: decyzja pod presją

Warto (metoda probabilistyczna), gdy pytanie brzmi „czy istnieje obiekt z parametrami X?” bez potrzeby jawnej budowy. Losowy model + odrzucenie złych zdarzeń (czasem przez LLL) daje szybkie istnienie.

Zależności lokalne i rzadkie zdarzenia: precyzyjne narzędzia

Lokalne Lemma Lovásza: kiedy unia jest za słaba

Warto, gdy masz rodzinę „złych” zdarzeń, każde dotyka tylko kilku innych (lokalność), a ich prawdopodobieństwa są małe. Kryterium startowe: w wersji symetrycznej ep(d+1) ≤ 1, gdzie d to maksymalny stopień w grafie zależności. W wersji asymetrycznej ustaw parametry x_A i sprawdź P(A) ≤ x_A ∏_{B∼A}(1−x_B).

Uważaj, gdy zależności są gęste albo nie potrafisz ich jasno narysować. LLL nie policzy ci liczby obiektów – zwykle da tylko istnienie. Jeśli zdarzenia nie są „lokalne” (dotyczą globalnych sum), przejdź do koncentracji lub metody entropijnej.

Mini przykład: kolorowanie grafu k kolorami bez monochromatycznych krawędzi. Jeśli k ≥ e(Δ+1), gdzie Δ to maksymalny stopień, z LLL wynika, że poprawne kolorowanie istnieje (i nawet konstrukcyjnie – algorytmem Moser–Tardosa).

Rekomendacja: gdy suma-unia rozjeżdża się z intuicją, a konflikty są lokalne, spróbuj LLL. Najpierw policz p = max P(A) i d, dopiero potem inwestuj w parametry x_A.

Działaj: narysuj graf zależności zdarzeń – jeśli d mały, masz zielone światło.

Stein–Chen i przybliżenie Poissona: rozkłady rzadkich sum

Warto, gdy X = ∑X_i to suma wskaźników rzadkich, słabo zależnych zdarzeń, a interesuje cię pełny rozkład (szczególnie P(X=0), P(X=1), ogony). Jeśli λ = E[X] jest umiarkowane, a każde P(X_i=1) małe i ma krótki „sąsiedztwo zależne”, rozkład X bywa bliski Poisson(λ) w wariacji całkowitej.

Uważaj, gdy λ rośnie proporcjonalnie do rozmiaru problemu lub gdy zdarzenia nie są już rzadkie. Wtedy Poisson zaczyna „rozmazywać” wariancję i lepsze może być normalne przybliżenie albo binomial. Problemem jest też długie sąsiedztwo zależności: jeśli każdy X_i koliduje z wieloma innymi, błąd w wariacji całkowitej może przestać być mały mimo małych P(X_i=1).

Mini przykład: liczba trójkątów w G(n,p) dla małego p. Każdy kandydat na trójkąt ma prawdopodobieństwo p^3, a zależności wynikają tylko z trójkątów współdzielących krawędź lub wierzchołek (krótkie sąsiedztwo). Dla p takiego, że E[X] jest stałe lub rośnie wolno, Stein–Chen daje dobrą kontrolę P(X=0) i dalej całego rozkładu. Kontrprzykład: liczba wierzchołków o stopniu co najmniej 1 przy p ~ c/n – zależności spinają prawie cały graf, więc Poisson bywa zbyt optymistyczny.

Normalne przybliżenie (Berry–Esseen): dzwon czy nie?

Warto, gdy sumujesz wiele (prawie) niezależnych, ograniczonych zmiennych i interesuje cię zachowanie w okolicy średniej. Jeśli wariancja σ^2 jest duża (reguła kciuka: σ ≥ 5–10), a składniki nie są skrajnie skośne, przybliżenie normalne z kontrolą błędu Berry’ego–Esseena da szybki i precyzyjny obraz środkowej części rozkładu.

Uważaj, gdy p dla Bernoullich jest bardzo małe lub bardzo duże (np. p ≪ 1/n albo 1−p ≪ 1/n) – wtedy Poisson lub Chernoff zagra lepiej, a normalny „dzwon” przeceni ogony. Kłopotem są też silne efekty kratowe (wynik możliwy tylko w rzadkiej siatce wartości) – potrzebujesz wtedy korekty ciągłości lub w ogóle innego narzędzia.

Mini przykład: X ~ Bin(n,p) z p stałym w (0,1). Dla okien |t| = o(σ) dokładność aproksymacji P(X ≤ μ + t) ≈ Φ(t/σ) ma błąd rzędu O(1/√n). Dla p = 1/2 i n w tysiącach – świetnie; dla p = 1/n – fatalnie (idź w Poissona).

Rekomendacja: zobacz, czy σ^2 = Var(X) jest „duże”, a trzecie momenty nie wyskakują. Jeśli tak – używaj normalnego przybliżenia z prostą korektą ciągłości dla wartości pojedynczych.

Działaj: policz μ i σ^2 w 30 sekund; jeśli σ ≥ 7 i brak skrajności w p, strzel w Berry–Esseen i zamknij wynik oszacowaniem błędu ~ const/√n.

Nierówność Jansona: precyzyjne „brak zdarzeń” w grafach

Warto, gdy X = ∑ I_A liczy lokalne konfiguracje zależne od niezależnych bitów (np. krawędzi w G(n,p)), a zależy ci na P(X=0) lub dolnym ogonie. Klasyczne parametry: μ = E[X] oraz Δ – suma „nakładających się” par E[I_A I_B]. Główne przesłanie: jeśli nakładanie jest rzadkie (Δ ≪ μ), to P(X=0) ≤ exp(−μ + Δ/2) jest bardzo małe – bez rozwijania całej PIE.

Uważaj, gdy rodzina zdarzeń nie jest wzrastająca (monotoniczna) względem niezależnych bitów lub gdy Δ jest porównywalne z μ (duże nakładanie struktur). Wtedy zysk zanika i warto przeskoczyć do Stein–Chena (pełny rozkład) albo koncentracji/CLT (gdy μ, Δ rosną duże).

Mini przykład: liczba 4-cykli w G(n,p) przy p nie za dużym. Każdy cykl zależy tylko od 4 krawędzi; pary nakładają się na co najwyżej 2 krawędzie – Δ da się policzyć mechanicznie. Jeśli μ rośnie, a Δ nie nadąża, Janson szybko „zabija” P(brak 4-cykli).

Rekomendacja: kiedy celem jest brak substruktur w losowym obiekcie i łączą się one tylko lokalnie, spróbuj Jansona przed wejściem w PIE lub ciężkie sprzężenia.

Działaj: wypisz μ i surowe Δ z liczenia par nakładających się; jeśli Δ ≤ 0.5 μ, masz zielone światło na mocne wykładnicze oszacowanie.

Alteracje: losowo + szybka naprawa

Warto, gdy losowy model daje „prawie dobrze”, a każdą usterkę można tanio naprawić (usunąć element, przemalować, przepiąć). Szukasz nierówności w stylu: oczekiwana jakość − koszt napraw ≥ pożądany poziom. Ta technika często daje lepsze stałe niż goła unia/LLL.

Uważaj, gdy naprawy kaskadują (usunięcie jednego konfliktu tworzy nowe) lub koszt napraw rośnie szybciej niż liczba błędów. Potrzebna jest księgowość: policz nie tylko średnią liczbę błędów, ale i maksymalny koszt pojedynczej poprawki.

Mini przykład: gęsty graf bez trójkątów. Wybierz G(n,p) z dobranym p; oczekiwane E[E] ~ p n^2/2, oczekiwane trójkąty ~ p^3 n^3. Usuń po jednej krawędzi z każdego trójkąta: zostaje ≥ E[E] − E[#trójkątów]. Wybierając p proporcjonalne do n^(-1/2), dostajesz graf bez trójkątów z ~ c n^(3/2) krawędziami.

Rekomendacja: jeśli potrafisz policzyć „zysk – koszt” w jednej linijce i saldo jest dodatnie, alteracje dadzą egzystencję (często z dobrym rzędem wielkości).

Działaj: spisz dwa słupki: (i) oczekiwane dobro, (ii) oczekiwany koszt napraw; dopasuj parametr p tak, by (i) – (ii) > 0 i zatwierdź.

Decyzje taktyczne: koncentracja, istnienie i liczenie

Na starcie zadaj sobie kilka krótkich pytań – odpowiedzi poprowadzą cię do właściwego narzędzia:

• Czy moja funkcja od niezależnych bitów ma małe wpływy pojedynczych zmiennych (Lipschitz)?
• Czy lepiej kontroluję wariancję warunkową niż samą rozpiętość kroków?
• Czy chcę tylko „że istnieje X” (P(X>0)>0), czy precyzyjny ogon?
• Czy mogę policzyć „kod”/entropię obiektów zamiast liczyć je wprost?

Azuma–Hoeffding/McDiarmid: kiedy wystarczy Lipschitz

Warto, gdy twoja zmienna X = f(ξ_1,…,ξ_n) zależy od niezależnych ξ_i i każda zmiana jednego ξ_i porusza f najwyżej o c_i (ograniczone wpływy). Dostajesz subgaussowskie ogony w postaci P(|X−E[X]| ≥ t) ≤ 2 exp(−2t^2/∑c_i^2) bez zaglądania w strukturę zależności.

Uważaj, gdy pojedyncza zmienna potrafi „przeorać” wynik (duże c_i) albo wpływy są rzadko małe, a czasem ogromne (cięcia adaptacyjne). Azuma da wtedy słabe stałe. Jeśli f jest sumą, rozważ Chernoff/Bernstein; jeśli zależności są lokalne, Freedman bywa ostrzejszy.

Mini przykład: liczba zajętych kubełków po wrzuceniu m kul losowo do n kubełków. Zmiana pozycji jednej kuli zmienia liczbę zajętych kubełków o ≤ 1, więc c_i=1 i ∑c_i^2=m. McDiarmid daje wykładniczą koncentrację wokół E[X] bez delikatnej rachunkowości zliczeń kolizji.

Rekomendacja: jeśli w 60 sekund potrafisz wypisać c_i i ∑c_i^2 jest małe względem t^2, bierz McDiarmida/Azumę – szybki, bezpieczny, odporny na detale.

Działaj: zrób tabelkę wpływów c_i; jeśli max c_i nie wystaje i suma kwadratów jest sensowna, klep nierówność i idź dalej.

Freedman/Bennett–Bernstein: gdy wariancja rządzi, a kroki są ograniczone

Warto, gdy masz martyngał (lub sumę niezależnych) z ograniczonymi przyrostami |Δ_k| ≤ b, ale potrafisz oszacować przewidywaną wariancję V = ∑E[Δ_k^2 | F_{k-1}]. Freedman daje P(X_n−E[X_n] ≥ t) ≤ exp(−t^2/(2(V+bt/3))) – często ostrzej niż Azuma, zwłaszcza gdy V ≪ nb^2. Dla niezależnych i subekspotencjalnych składników użyj Bennett/Bernstein: parametry (wariancja, b) prowadzą do ogonów lepszych niż Hoeffding.

Uważaj, gdy nie umiesz kontrolować V (brak przewidywalnej wariancji) albo b jest duże – wówczas „bt/3” zjada zysk. Gdy rozkłady mają ciężkie ogony, rozważ najpierw obcięcie (truncation) i dopiero Bernstein na „czystej” części plus ogon Markowa.

Mini przykład: liczba konfliktów w procesie losowego kolorowania krawędzi krok po kroku. Każdy krok zmienia liczbę konfliktów o ≤ b, ale przeciętnie rzadko trafiasz w kolizje – V skaluje się jak liczba faktycznych, a nie możliwych interakcji. Freedman wycina z ogona „puste strzały”, których Azuma nie odróżnia.

Rekomendacja: jeśli masz sensowny, mały V i znasz ograniczenie b – przełącz się z Azumy na Freedmana/Bernsteina; dostaniesz realne, niekonserwatywne stałe.

Działaj: wypisz ograniczenie kroku b i oblicz przewidywaną wariancję V (np. martynałem Dooba po odkrywaniu bitów). Jeśli V ≪ nb^2, wstaw do Freedmana; dla sum niezależnych i znanego b użyj Bernsteina. Gdy V trudno złapać – skróć ogon obcięciem i połącz Markowa z Bernsteinem.

Drugi moment i Paley–Zygmund: pokaż, że dodatnie prawdopodobieństwo nie jest mikroskopijne

Warto, gdy chcesz pokazać, że X>0 z sensownym prawdopodobieństwem, a E[X] umiarkowanie duże względem √Var(X). Klasyczny duet: Chebyshev dla P(X=0) przez Var(X), lub bezpośrednio Paley–Zygmund: P(X ≥ θE[X]) ≥ (1−θ)^2 E[X]^2 / E[X^2], θ∈(0,1). Gdy E[X^2] jest niewiele większe niż E[X]^2, dostajesz stały dolny bound na istnienie obiektu.

Uważaj, gdy X to suma silnie nakładających się wskaźników (E[X^2] eksploduje przez pary), albo gdy E[X] samo w sobie jest małe – wtedy Paley–Zygmund nie wyciągnie cię z dołka. Często pomaga rozcieńczenie (sprinkling) lub redefinicja X na „grubsze” struktury o mniejszych korelacjach.

Mini przykład: liczba par w G(n,p) tworzących niezależne krawędzie w ustalonym matching’u M. Zmienna X to liczba krawędzi z M, które się pojawiły; E[X] = |M|p, a E[X^2] = E[X] + 2∑P(I_eI_f) z niewielkim nakładaniem. Jeśli p nie jest zbyt małe, Paley–Zygmund daje stałe P(X ≥ 0.5E[X]).

Rekomendacja: szukasz „niezerowości” z konkretną frakcją oczekiwanej wartości – najpierw spróbuj Paley–Zygmund, ale policz E[X^2] z uwzględnieniem par nakładających się.

Działaj: rozpisz E[X] i E[X^2], usuń pary zbyt silnie zależne (np. przez wybór rozcieńczonej rodziny), dopiero potem zastosuj Paley–Zygmund z θ=1/2.

Najczęściej zadawane pytania (FAQ)

Jak rozpoznać, że zdarzenia w zadaniu NIE są niezależne?

Jeśli losowanie odbywa się bez zwracania, pojawia się permutacja lub ograniczenia „bez powtórzeń”, to zależności są niemal pewne. Fałszywa niezależność najczęściej wynika z dzielenia jednego, wspólnego zasobu (karty, miejsca, wierzchołki grafu) albo z procedury, w której kolejny krok zależy od poprzednich.

Użyj szybkich testów rozpoznawczych:

• Czy liczba dostępnych wyników zmienia się po każdym kroku? (bez zwracania → zależności)
• Czy to permutacja/rozmieszczenie obiektów? (pozycje „walczą” o te same elementy)
• Czy zdarzenia „dotykają” tych samych obiektów? (nakładanie struktur → współzależność)
• Czy P(A ∩ B) liczysz „z głowy”, czy naprawdę umiesz uzasadnić P(A)P(B)? (jeśli to drugie – włącz hamulec)

Zatrzymaj się, zanim użyjesz P(A ∩ B) = P(A)P(B) – najpierw uzasadnij niezależność na poziomie procedury losowania.