MatematykaPrawdopodobieństwo i przypadek — intuicja często przegrywa z rachunkiem

Dwa wzorce o tej samej długości mogą wymagać zupełnie innego czasu oczekiwania

W trzech rzutach uczciwą monetą wzorce HHH i HHT mają w pojedynczym, z góry ustalonym oknie takie samo prawdopodobieństwo 1/8. Gdy jednak rzucamy monetą bez końca i czekamy na pierwsze pojawienie się wzorca, oczekiwany czas różni się: dla HHH wynosi 14 rzutów, a dla HHT 8. Powodem jest nakładanie się wzorca na samego siebie. Po HHH część potencjalnych trafień „dzieli” te same orły, a po nieudanej próbie stan pamięci procesu zależy od końcówki dotychczasowego ciągu. Równe prawdopodobieństwo w jednym oknie nie oznacza równego czasu pierwszego wystąpienia.

Okna w długim ciągu nie są niezależne

W ciągu rzutów patrzymy na pozycje 1–3, potem 2–4, potem 3–5 itd. Kolejne trzyrzutowe okna współdzielą po dwa rzuty, więc nie można traktować ich jak niezależnych prób z szansą 1/8. To właśnie wspólne fragmenty powodują, że struktura wzorca ma znaczenie. Prawdopodobieństwo HHH w jednym konkretnym oknie jest takie samo jak HHT, lecz droga do pierwszego trafienia pamięta to, co zostało na końcu po poprzedniej próbie.

Dlaczego HHH czeka dłużej

Wzorzec HHH może nakładać się na samego siebie. Jeśli właśnie pojawiło się HH i wypadnie T, cały postęp zostaje utracony. Z kolei długie serie H tworzą sytuacje, w których wiele potencjalnych trzyznakowych okien jest ze sobą powiązanych. Analiza stanów „nic”, „H”, „HH”, „HHH” prowadzi do oczekiwanej wartości 14 rzutów. To więcej niż naiwne 1/(1/8)=8, ponieważ kolejne okazje nie są niezależne.

HHT zachowuje się inaczej

Dla HHT średni czas oczekiwania wynosi 8. Wzorzec nie ma takiego samego rodzaju samonakładania jak HHH. Gdy pojawia się wiele H z rzędu, końcówka HH pozostaje gotowym początkiem HHT i wystarczy T, aby zakończyć wzorzec. Szczegóły można opisać łańcuchem Markowa śledzącym najdłuższy sufiks, który jest jednocześnie początkiem poszukiwanego wzorca.

To nie przeczy równym częstościom lokalnym

W bardzo długiej sekwencji każde konkretne trzyznakowe okno ma prawdopodobieństwo 1/8 bycia HHH i 1/8 bycia HHT. Oczekiwany odstęp między wystąpieniami oraz czas do pierwszego wystąpienia są jednak innymi wielkościami, w których nakładanie może mieć znaczenie. Problem jest dobrym ostrzeżeniem przed zastępowaniem jednego pytania probabilistycznego innym tylko dlatego, że używają podobnych symboli.

Wzorce mają własną „geometrię”

Dla dłuższych słów binarnych różnice stają się jeszcze bogatsze. Istotne jest to, które końcówki wzorca są równocześnie jego początkami. Ta sama idea leży u podstaw algorytmów wyszukiwania wzorców w tekstach i analizy procesów losowych. Prawdopodobieństwo łączy się tu z informatyką: efektywne śledzenie częściowego dopasowania wymaga pamiętania dokładnie tych fragmentów, które mogą zostać wykorzystane po niepowodzeniu.

Dlaczego to ciekawsze niż zagadka

Sednem nie jest zapamiętanie liczb 14 i 8. Ważna jest zasada: w procesie sekwencyjnym wynik zależy nie tylko od częstości pojedynczego układu, ale też od sposobu, w jaki możliwe wystąpienia zachodzą na siebie w czasie. To mechanizm, którego intuicja często nie zauważa, bo patrzy na osobne okna zamiast na jeden ciąg z pamięcią wynikającą z nakładania.

Nakładanie można opisać automatem stanów

Najczystszy sposób liczenia takich czasów polega na zapisaniu stanów odpowiadających najdłuższemu końcowi dotychczasowej historii, który może być początkiem szukanego wzorca. Dla HHH stanami są: brak dopasowania, H, HH i stan końcowy HHH. Po każdej nowej literze przechodzimy do odpowiedniego stanu i zapisujemy równania dla oczekiwanego czasu pozostałego do sukcesu. Ta sama technika działa dla dowolnych słów i jest blisko spokrewniona z automatami używanymi w algorytmach wyszukiwania tekstu. Probabilistyka pokazuje tu, że „pamięć” procesu nie musi pochodzić z zależnych rzutów — może powstać wyłącznie z tego, jak definiujemy poszukiwany wzorzec w nakładających się oknach.

#czas oczekiwania#łańcuch Markowa#rzuty monetą#wzorce
Źródła i weryfikacja
Otrzymuj codzienne losowe ciekawostki