Problem B. 5164. (March 2021)

B. 5164. Two players continue playing rock-paper-scissors games until one of them wins the third time. Assume that each player in each game selects rock, paper or scissors at random (independently of each other and of previous games), with probabilities of \(\displaystyle \frac13 : \frac13 : \frac13\). Determine the expected value of the number of games needed.

(5 pont)

Deadline expired on April 12, 2021.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Osszuk fel a párbajt meccsekre. Egy meccs addig tart, ameddig valamelyik játékos meg nem nyer egy menetet. Tehát egy meccs egy vagy több menetből áll, melyek közül az utolsó kivételével mindegyik menet döntetlen. Értelemszerűen az nyeri a párbajt, aki előbb nyer meg három meccset.

Minden menet \(\displaystyle \frac13\) eséllyel lesz döntetlen, függetlenül az előző menettől. Így annak a valószínűsége, hogy egy meccs pontosan \(\displaystyle n\) menetből áll, \(\displaystyle m_n = \left( \frac13 \right)^{n-1} \cdot \frac23 \).

Tehát az egy meccsen belüli menetek számának várható értéke így számítható ki:

\(\displaystyle M = \sum_{n=1}^{\infty} = nm_n = \sum_{n=1}^{\infty} n \left( \frac13 \right)^{n-1} \frac23 = \left( 1 + 2 \cdot \frac13 + 3 \left(\frac13\right)^2 + 4 \left(\frac13\right)^3 + \ldots \right) \cdot \frac23 = \frac94 \cdot \frac23 = \frac32.\)

(Valószínűségszámításban képzett megoldók azt is mondhatják erre, hogy az egy meccsen belüli menetek száma geometriai eloszlású, \(\displaystyle p=\frac23\) paraméterrel, tehát várható értéke \(\displaystyle \frac1p = \frac32\)).

Mivel a játék szimmetrikus, így mindegyik meccset \(\displaystyle \frac12\) eséllyel nyeri \(\displaystyle A\) játékos és \(\displaystyle \frac12\) eséllyel \(\displaystyle B\) játékos. A különböző meccsek eredményei pedig függetlenek egymástól. Ezt felhasználva határozzuk meg a párbaj eldöntéséhez szükséges meccsek számának eloszlását.

• Akkor elég 3 meccs, ha az első három meccset ugyanaz nyeri. Ennek esélye \(\displaystyle \displaystyle p_3 = 2 \cdot \left( \frac12 \right)^3 = \frac14 \).
• Akkor dől el a \(\displaystyle 4\). meccs végén a párbaj, ha az első négy menet győzteseinek sorozata a következő 6 sorozat valamelyike: \(\displaystyle AABA,ABAA,BAAA\) (ilyenkor \(\displaystyle A\) nyer), \(\displaystyle ABBB,BABB,BBAB\) (ilyenkor \(\displaystyle B\) nyer). Egy-egy ilyen sorozat esélye \(\displaystyle \left(\frac12\right)^4\), tehát annak az esélye, hogy 4 meccsből áll a párbaj: \(\displaystyle \displaystyle p_4 = 6 \cdot \left( \frac12 \right)^4 = \frac38 \).
• Legkésőbb az 5. meccs végére el kell dőljön a párbaj (a skatulyelv alapján az 5 meccsből legalább 3-at ugyanannak az embernek kell nyerni), így annak az esélye, hogy 5 meccsből áll a párbaj: \(\displaystyle \displaystyle p_5 = 1 - p_3 - p_4 = \frac38 \).

Legyen most \(\displaystyle X_i\) az a valószínűségi változó, amelyik megadja az \(\displaystyle i.\) meccsen belüli menetek számát. Ha a 4., illetve 5. meccs nem valósul meg, akkor \(\displaystyle X_4=0\) (illetve \(\displaystyle X_5=0\)).

Így a teljes meccs meneteinek száma éppen \(\displaystyle X_1+X_2+X_3+X_4+X_5\), ennek várható értéke (felhasználva, hogy a várható érték additív):

\(\displaystyle \mathbb{E} (X_1) + \mathbb{E} (X_2) + \mathbb{E} (X_3) + \mathbb{E} (X_4) + \mathbb{E} (X_5). \)

Az egyes \(\displaystyle \mathbb{E} (X_i)\) értékeket egyenként meg tudjuk mondani:

• \(\displaystyle \mathbb{E} (X_1) = \mathbb{E} (X_2) = \mathbb{E} (X_3) = M\), hiszen az első három meccs biztosan megvalósul.
• \(\displaystyle \mathbb{E} (X_4) = M (1-p_3)\) , hiszen \(\displaystyle X_4\) értéke \(\displaystyle p_3\) eséllyel \(\displaystyle 0\), míg \(\displaystyle 1-p_3\) eséllyel lesz 4. meccs, így ha \(\displaystyle n\geq 1\), akkor \(\displaystyle P(X_4 = n) = (1-p_3)\left( \frac13 \right)^{n-1} \cdot \frac23\)
• \(\displaystyle \mathbb{E} (X_5) = M p_5\), hiszen \(\displaystyle X_5\) értéke \(\displaystyle p_3+p_4\) eséllyel \(\displaystyle 0\), míg \(\displaystyle p_5\) eséllyel megvalósul ez a meccs, így \(\displaystyle P(X_5 = n) = p_5 \left( \frac13 \right)^{n-1} \cdot \frac23\).

Tehát a feladat kérdésére a válasz

\(\displaystyle M(3+ (1-p_3) + p_5) = \frac32 \left(1 + 1+ 1 + \frac34 + \frac38 \right) = \frac32 \cdot \frac{33}{8} = \frac{99}{16}. \)

Megjegyzés: Ha \(\displaystyle Y\)-nal jelöljük a meccsek számát jelölő valószínűségi változót, akkor \(\displaystyle \mathbb{E}(Y) = 3 \cdot \frac14 + 4 \cdot \frac38 + 5 \cdot \frac38 = \frac{33}{8}\), azaz éppen teljesül, hogy:

\(\displaystyle \mathbb{E}(X_1) \cdot \mathbb{E}(Y) = \frac{99}{16}. \)

Így is kiszámítható lenne a feladat végeredménye?

Mivel \(\displaystyle X_1\) és \(\displaystyle Y\) független, teljesül \(\displaystyle \mathbb{E}(X_1) \cdot \mathbb{E}(Y) = \mathbb{}{E} (X_1 Y)\), de \(\displaystyle X_1Y\) általában nem egyezik meg a menetek számával (bár némi köze van hozzá). Tehát erre nem tudunk hivatkozni.

Valójában ez a kiszámítási mód egy mély és általános összefüggés, az úgynevezett Wald-azonosság (ld. https://en.wikipedia.org/wiki/Wald's_equation) egy egyszerű speciális esete.

Az azonosság feltalálójáról, Wald Ábrahámról érdemes elolvasni ezt a történetet is:

https://ematlap.hu/konyvespolc-2017-03/443-hogy-ne-tevedjunk-wald-abraham-es-a-hianyzo-lovedeknyomok

Statistics:

54 students sent a solution.
5 points:	Beinschroth Ninett, Csizmadia Miklós, Diaconescu Tashi, Duchon Márton, Fekete Richárd, Han Ziying, Hegedűs Dániel, Koleszár Domonkos, Kovács Alex, Kökényesi Márk Péter, Lenkey Gyöngyvér, Lovas Márton, Mácsai Dániel, Metzger Ábris András, Molnár-Szabó Vilmos, Nagy 551 Levente, Németh Márton, Simon László Bence, Szanyi Attila, Sztranyák Gabriella, Terjék András József, Varga Boldizsár, Velich Nóra, Wiener Anna, Zömbik Barnabás.
4 points:	Argay Zsolt, Baski Bence, Bencsik Ádám, Bencsik Dávid, Jánosik Máté, Kercsó-Molnár Anita, Móricz Benjámin, Nádor Benedek, Osztényi József, Richlik Bence, Virág Rudolf.
3 points:	3 students.
2 points:	4 students.
1 point:	6 students.
0 point:	5 students.

Problems in Mathematics of KöMaL, March 2021