Ciąg gier

[mol_ksiazkowy]

Gracze \(\displaystyle{ A}\) i \(\displaystyle{ B}\) rozgrywają ciąg gier, dopóki jeden z nich ma o dwa zwycięstwa więcej niż jego przeciwnik. W każdej pojedynczej grze \(\displaystyle{ A}\) wygrywa z prawdopodobieństwem \(\displaystyle{ p}\), przegrywa z prawdopodobieństwem \(\displaystyle{ q}\) lub jest remis z prawdopodobieństwem \(\displaystyle{ 1-p-q}\). Jakie jest prawdopodobieństwo że \(\displaystyle{ A}\) będzie wygranym tego ciągu gier ?

Ukryta treść:    

Ross Honsberger Mathematical Delights

[kerajs]

W - wygrana A
R - remis
P - wygrana A
Jak uzyskać ciąg 2k elementowy zawierający elementy W,R,P obrazujący wygraną A w 2k-tym ruchu? Mogę wziąć dwa elementy W, z których drugi będzie ostatnim elementem ciągu, dobrać dla i układów PW miejsca przed i za pierwszym W (na i+1 sposobów), a następnie wybrać położenie dla 2n-2-2i elementów R. Stąd dla \(\displaystyle{ k \in \NN_+}\) ilość ciągów 2k-elementowych obrazujących wygraną A to: \(\displaystyle{ \sum_{i=0}^{k-1}(i+1) {2k-1 \choose 2i+1}}\), a prawdopodobieństwo wygranej A w 2k-tym ruchu to:
\(\displaystyle{ P(2k)=p^2 \sum_{i=0}^{k-1}(i+1)(pq)^i {2k-1 \choose 2i+1}(1-p-q)^{2k-2-2i} }\)
Analogicznie prawdopodobieństwo wygranej A w nieparzystej ilości ruchów to
\(\displaystyle{ P(2k+1)=p^2(1-p-q) \sum_{i=0}^{k-1}(i+1)(pq)^i {2k \choose 2i+1}(1-p-q)^{2k-2-2i} }\)
Sumując powyższe:
\(\displaystyle{ P(A \ wygrywa)=p^2 \sum_{k=1}^{ \infty } \sum_{i=0}^{k-1}(i+1)(pq)^i(1-p-q)^{2k-2-2i}\left({2k-1 \choose 2i+1}+{2k \choose 2i+1}(1-p-q) \right) }\)

Spróbuję uprościć ten wynik.
\(\displaystyle{ P(A \ wygrywa)+P(A \ nie \ wygrywa)=1 \wedge P(A \ nie \ wygrywa)=P(B \ wygrywa)}\)
Ponadto :
\(\displaystyle{ P(B \ wygrywa)=q^2 \sum_{k=1}^{ \infty } \sum_{i=0}^{k-1}(i+1)(pq)^i(1-p-q)^{2k-2-2i}\left({2k-1 \choose 2i+1}+{2k \choose 2i+1}(1-p-q) \right)=\\ = \frac{q^2}{p^2} \cdot p^2 \sum_{k=1}^{ \infty } \sum_{i=0}^{k-1}(i+1)(pq)^i(1-p-q)^{2k-2-2i}\left({2k-1 \choose 2i+1}+{2k \choose 2i+1}(1-p-q) \right)=\\ =\frac{q^2}{p^2}P(A \ wygra) }\)
Ostatecznie:
\(\displaystyle{ P(A \ wygrywa)+\frac{q^2}{p^2}P(A \ wygrywa)=1\\
P(A \ wygrywa) = \frac{p^2}{p^2+q^2} }\)

[Tmkk]

Takie zadania robi się też wygodnie z łańcuchów Markowa. Mamy \(\displaystyle{ 5}\) stanów: \(\displaystyle{ \left\{ AA, A, R, B, BB\right\} }\), gdzie stan \(\displaystyle{ AA}\) oznacza, że gracz \(\displaystyle{ A}\) ma dwa punkty przewagi, stan \(\displaystyle{ A}\) oznacza, że gracz \(\displaystyle{ A}\) ma jeden punkt przewagi, stan \(\displaystyle{ R}\) oznacza remis. Dla \(\displaystyle{ B}\) i \(\displaystyle{ BB}\) analogicznie.

Niech \(\displaystyle{ P_k}\) oznacza prawdopodobieństwo wygranej gracza \(\displaystyle{ A}\), jeżeli jesteśmy obecnie w stanie \(\displaystyle{ k \in \left\{ AA, A, R, B, BB\right\} }\). Interesuje nas \(\displaystyle{ P_R}\), jako, że gra zaczyna się od remisu (gdyby zaczynała się od innego stanu, to byłoby takie same rozumowanie). Możemy ułożyć następujące równania:

\(\displaystyle{ \begin{cases} P_{AA} = 1 \\ P_A = pP_{AA} + qP_{R} + (1-p-q)P_A \\ P_R = pP_A + qP_B + (1-p-q)P_R \\ P_B = pP_R + qP_{BB} + (1-p-q)P_B \\ P_{BB} = 0 \end{cases} }\)

Pierwsze równanie jest jasne - jeśli jesteśmy w stanie \(\displaystyle{ AA}\), to gracz \(\displaystyle{ A}\) właśnie wygrał.
Drugie równanie bierze się stąd, że jesteśmy w stanie \(\displaystyle{ A}\). Jeśli gracz \(\displaystyle{ A}\) wygrał (dzieje się to z prawdopodobieństwem \(\displaystyle{ p}\)), to przechodzimy do stanu \(\displaystyle{ AA}\). Jeśli przegrał (dzieje się to z prawdopodobieństwem \(\displaystyle{ q}\)), to przechodzimy do stanu \(\displaystyle{ R}\). A jeśli będzie remis (z prawdopodobieństwem \(\displaystyle{ 1-p-q}\)), to zostajemy w stanie \(\displaystyle{ A}\). Reszta analogicznie.

Ten układ się super łatwo rozwiązuje i wychodzi jak wyżej: \(\displaystyle{ P_R = \frac{p^2}{p^2+q^2}}\).