W losowym rozdaniu przedmiotów średnio jedna osoba trafi na swój — a szansa, że nikt nie trafi, dąży do 1/e
Jeśli n osobom losowo rozdamy n oznaczonych przedmiotów po jednym, liczba osób otrzymujących własny przedmiot ma wartość oczekiwaną równą 1 — niezależnie od n. Jednocześnie prawdopodobieństwo, że nikt nie trafi na swój przedmiot, dąży wraz ze wzrostem n do 1/e, czyli około 36,8%. Takie permutacje bez punktów stałych nazywa się derangements. Wynik łączy dwa mechanizmy: liniowość wartości oczekiwanej pozwala łatwo policzyć średnią liczbę trafień, a zasada włączeń i wyłączeń prowadzi do zaskakującej granicy związanej z liczbą e.
Dlaczego średnia zawsze wynosi 1
Dla każdej konkretnej osoby prawdopodobieństwo otrzymania własnego przedmiotu wynosi 1/n. Możemy wprowadzić wskaźnik równy 1, gdy dana osoba trafi, i 0 w przeciwnym razie. Jego wartość oczekiwana to 1/n. Suma n takich wskaźników liczy liczbę trafień, a liniowość wartości oczekiwanej daje n·(1/n)=1. Co ważne, do tego kroku nie potrzebujemy niezależności trafień poszczególnych osób.
Średnia 1 nie znaczy „zwykle dokładnie jedna”
Wartość oczekiwana opisuje średnią po wielu powtórzeniach, a nie najbardziej typowy pojedynczy wynik. W pewnych rozdaniach nikt nie dostanie własnego przedmiotu, w innych trafi kilka osób, a czasami wszyscy. Fakt, że średnia liczba punktów stałych wynosi 1, jest stabilny dla każdego n, ale pełny rozkład zawiera znacznie więcej informacji niż sama średnia.
Permutacje bez trafień
Aby policzyć prawdopodobieństwo zera trafień, trzeba policzyć permutacje bez punktów stałych. Zasada włączeń i wyłączeń daje udział D_n/n! = Σ_{k=0}^n (-1)^k/k!. Gdy n rośnie, suma ta zbliża się do szeregu rozwijającego e^{-1}, więc granicą jest 1/e≈0,367879. Zaskakujące jest to, że nawet przy ogromnej liczbie osób szansa całkowitego braku trafień nie staje się ani bardzo mała, ani bardzo duża — stabilizuje się w pobliżu 37%.
Dlaczego zależności nie przeszkadzają wartości oczekiwanej
Jeśli jedna osoba dostała swój przedmiot, zmienia to szanse pozostałych, więc zdarzenia trafień nie są niezależne. Mimo to średnią liczbę trafień można policzyć przez zsumowanie indywidualnych prawdopodobieństw. Liniowość wartości oczekiwanej działa także dla zmiennych zależnych. To jedna z najbardziej użytecznych technik w probabilistyce, często pozwalająca ominąć trudne liczenie pełnego rozkładu.
Gdzie pojawia się e
Liczba e nie jest tu sztucznie dopisana. Pojawia się, ponieważ naprzemienna suma 1−1+1/2!−1/3!+… jest rozwinięciem e^{-1}. Zasada włączeń i wyłączeń generuje dokładnie takie wyrazy, gdy kolejno odejmujemy permutacje mające co najmniej jeden ustalony element, dodajemy z powrotem te z co najmniej dwoma itd. Stała znana z analizy matematycznej wyrasta więc naturalnie z czysto kombinatorycznego problemu.
Klasyczny problem kapeluszy ma głębszą lekcję
Historia o pomieszanych kapeluszach jest tylko wygodną ilustracją losowej permutacji. Ten sam model opisuje losowe przyporządkowania, błędne etykiety i wiele algorytmów. Rekord pokazuje także, że dwie proste statystyki jednego procesu mogą mieć zupełnie różny charakter: średnia liczba trafień jest dokładnie równa 1 dla każdego n, a prawdopodobieństwo zera trafień dopiero zbliża się do stałej 1/e.
Pełny rozkład zbliża się do rozkładu Poissona
Dla dużego n liczba punktów stałych w losowej permutacji ma rozkład bardzo bliski rozkładowi Poissona o średniej 1. To natychmiast tłumaczy zarówno średnią równą 1, jak i prawdopodobieństwo zera bliskie e^{-1}. Przybliżenie sugeruje także prawdopodobieństwa jednego, dwóch czy trzech trafień: około e^{-1}/k! dla k punktów stałych. Dzięki temu problem kapeluszy okazuje się czymś więcej niż pojedynczą sztuczką z 1/e — jest klasycznym miejscem, w którym złożona zależna struktura permutacji prowadzi w granicy do prostego rozkładu probabilistycznego znanego z liczenia rzadkich zdarzeń.