[Kombinatoryka] Indianie w kółku

[Swistak]

W kółku siedzi n Indian. Na poczatku jeden z nich zaczyna palić fajkę pokoju. Potem z prawdopodobieństwem 1/2 przekazuje ją sąsiadowi po lewej, i z prawdopodobieństwem 1/2 sąsiadowi po prawej. Indianie powtarzają to do momentu, w którym każdy z nich zapali ją choć raz. Dla każdego Indianina wyznacz prawdopodobieństwo, że będzie on ostatnim, który zapali fajkę.

[marcin_smu]

Fajne zadanko

Ukryta treść:    

Od momentu kiedy pierwszy z sąsiadów danego indianina zapali fajkę szansa na to, że to on będzie ostatni jest niezależna od tego, ile indian już zapaliło fajkę(i tak każdy z nich będzie ją musiał ponownie zapalić). A ten moment dla każdego indianina z pewnością nadejdzie, czyli szansa każdego jest taka sama i wynosi \(\displaystyle{ \frac{1}{n-1}}\).

[Swistak]

Niesamowite rozwiązanie )).

Z małych szczegółów trzeba jeszcze udowodnić, że fajka nie może krążyć w nieskończoność nie odwiedzając jakiegoś Indianina, ale to jest proste i nie tu leży istota problemu.

[pawels]

Z chęcią zobaczę dowód faktu, że taka sytuacja nie może zajść (szczególnie, że to nie prawda ). Za wciskanie kitu, że \(\displaystyle{ P(A)=0\Rightarrow A=\emptyset}\) należy się antygwiazdka .

Btw jakoś nie mogę zrozumieć tego rozwiązania...

[Swistak]

Istnieją sytuacje, w których fajka krąży w nieskończoność, ale ich prawdopodobieństwo wynosi 0 ...

[pawels]

Dokładnie. Jedyny problem polega na tym, że aby wykazać że ich prawdopodobieństwo wynosi 0 można najpierw rozwiązać to zadanie. Sam inaczej nie umiem tego wykazać.

[Swistak]

Jesteśmy w zerze i wykonujemy ciąg operacji +1 i -1, każdą z prawdopodobieństwem 1/2. Prawdopodobieństwo, że fajka nigdy nie odwiedzi jakiegoś Indianina to prawdopodobieństwo, że nie zajdziemy dalej niż jakieś a i wcześniej niż jakieś a-n, czy coś podobnego - ważne, że to coś jest skończone . A to dość znane, że prawdopodobieństwo czegoś takiego jest równe 0.

[pawelsuz]

a to dosc znane to co to wlasciwie jest?

[tkrass]

No jakby miało nie dojść nigdy do jakiegoś indianina to musiałby istnieć jakiś przedział taki, że w jego krańcach fajka będzie nieskończenie wiele razy, ale zawsze będzie potem szła do środka przedziału. Prawdopodobieństwo każdego takiego skręcenia z powrotem do środka jest 1/2, więc prawdopodobieństwo, że fajka zostanie w tym przedziale jest \(\displaystyle{ \frac{1}{2} \cdot \frac{1}{2} \cdot ... = 0}\).

[Swistak]

@up blef
0, 1, 2, 1, 0, -1, -2, -2, -1, 0, 1, 0, 1, 0, 1, 0 ...

Jednak można to tak naprawić, że istnieje taki punkt, w którym fajka będzie nieskończenie wiele razy i tylko skończenie wiele razy pójdzie w jakąś ustaloną stronę.

[tkrass]

Żaden blef. Zresztą ja mówiłem o przedziale indian, a nie liczb, ale w tym przykładzie co Ty dałeś, jeżeli do końca jest 1, 0, 1, 0 ... to tym przedziałem jest \(\displaystyle{ <0, 1>}\). Ogólnie to by trzeba dłużej uzasadniać, że jak do jakiegoś indianina nie dojdzie, to u pozostałych n-1 będzie nieskończenie wiele razy. I teraz mamy takie możliwości - u jego sąsiada będzie nieskończenie wiele razy, lub skończenie wiele. Jeżeli skończenie, to u sąsiada tego sąsiada to samo, w końcu musimy dojść z obu stron do takich różnych indian, że będzie u nich fajka nieskończenie wiele razy (gdybyśmy nie doszli to niedobrze, bo w sumie byłoby skończenie wiele ruchów). Tych dwóch indian stanowi krańce przedziału, w którym będzie fajka od pewnego momentu i nieskończenie wiele razy do tych krańców dojdzie. Dalej tak jak pisałem. Co Ci się nie podoba?

[xiikzodz]

Mnie też się podoba rozwiązanie marcin_smu, ale moim zdaniem jest ono wyjątkowo niemiłe w zapisie.

Wypiszę nieco milsze w zapisie rozwiązanie, a w dodatku nie wymagające żadnych niesamowitych pomysłów.

Dla porządku ustalmy o jakie prawdopodobieństwo chodzi. Jest ono określone na zbiorze \(\displaystyle{ \{-1,1\}^*}\) wszystkich skończonych ciągów o wyrazach ze zbioru \(\displaystyle{ \{-1,1\}}\) poprzez rozszerzenie wzoru:

\(\displaystyle{ P((a_1,a_2,\ldots,a_n))=\frac 1{2^n}}\)

na wszystkie podzbiory \(\displaystyle{ \{-1,1\}^*}\).

A teraz do rozwiązania.

Wybierzmy Indianina różnego od startowego. Prawdopodobieństwo, że fajka kiedyś dotrze do jednego z jego sąsiadów jego samego pominąwszy wynosi 1. Żeby to zobaczyć, zauważmy, że prawdopodobieństwo, że fajka startując od dowolnego Indianina poza tym wybranym dotrze do jednego z jego sąsiadów w niewięcej niż \(\displaystyle{ n}\) krokach jest niezerowe, czyli większe od pewnego ustalonego \(\displaystyle{ \varepsilon}\). Wówczas prawdopodobieństwo, że fajka w \(\displaystyle{ mn}\) krokach nie dotrze do sąsiada wybrańca jest niewiększe niż \(\displaystyle{ (1-\varepsilon)^m}\). Z kolei \(\displaystyle{ \lim_{m\to\infty}(1-\varepsilon)^m=0}\), więc prawdopodobieństwo, że fajka nie dotrze do sąsiada jest mniejsze od dowolnej liczby rzeczywistej dodatniej, zatem równe zeru.

W związku z powyższym, jeśli \(\displaystyle{ p}\) jest prawdopodobieństwem, że fajka dotrze do jednego z sąsiadów wybrańca bez odwiedzania drugiego i samego wybrańca, to \(\displaystyle{ 1-p}\) jest prawdopodobiństwem, że fajka dotrze najpierw do drugiego z jego sąsaiadów. Oznaczmy jeszcze \(\displaystyle{ q}\), prawdopodobieństwo, że fajka powędruje od jednego do drugiego z sąsiadów z pominięciem wybranego Indianina. Możemy wówczas wypisać prawdopodobieństwo, że wybrany Indianin jako ostatni zapali:

\(\displaystyle{ p\cdot q+(1-p)\cdot q=q}\).

Liczba \(\displaystyle{ q}\) zależy jedynie od liczby Indian w kółku, a nie od wyboru Indianina spośród \(\displaystyle{ n-1}\), którzy potencjalnie mogą być ostatni w kolejce, zatem \(\displaystyle{ q=\frac{1}{n-1}}\).