Az A. 832. feladat (2022. szeptember)

A. 832. Tegyük fel, hogy minden embernek egymástól függetlenül \(\displaystyle 0, 1,\dots\) vagy \(\displaystyle n\) gyermeke születhet, és annak a valószínűsége, hogy éppen \(\displaystyle i\) gyermeke születik, \(\displaystyle p_i\), ahol \(\displaystyle p_0+p_1+\ldots +p_n=1\) és \(\displaystyle p_n \ne 0\). (Ez az ún. Galton–Watson folyamat.)

Mely \(\displaystyle n\) pozitív egész és \(\displaystyle p_0,p_1,\dots,p_n\) valószínűségek esetén lesz maximális annak a valószínűsége, hogy egy adott ember utódai éppen a tizedik generációban halnak ki?

(7 pont)

A beküldési határidő 2022. október 10-én LEJÁRT.

Megoldás: Legyen \(\displaystyle f(x)\) a gyerekek számának valószínűségi eloszlás által generált polinom, azaz

\(\displaystyle f(x)=p_nx^n+p_{n-1}x^{n-1}+\ldots +p_1x+p_0.\)

Jelölje az \(\displaystyle f(f(\ldots(f(x))\ldots))\) függvényt, ahol \(\displaystyle n\)-szer van egymásba ágyazva a polinom. Ekkor nem nehéz belátni azt az ismert állítást a Galton-Watson-folyamatról, hogy az \(\displaystyle n\)-edik generációban a gyerekek számának valószínűségi eloszlása által generált polinom éppen \(\displaystyle f^{(n)}(x)\).

Mivel \(\displaystyle f(1)=p_n+p_{n-1}+...+p_1+p_0=1\), ezért

\(\displaystyle \frac{1-f(x)}{1-x}=\frac{f(1)-f(x)}{1-x}=\frac{\int_{x}^{1} f'(y) dy}{1-x}.\)

Ez \(\displaystyle f'(y)\) átlagos értéke \(\displaystyle [x,1]\)-en. Az \(\displaystyle f'\) egy nemnegatív együtthatós polinom, így értéke monoton nő, ezért az \(\displaystyle [x,1]\)-en felvett átlagos értéke is monoton nő.

Legyen \(\displaystyle t_n\) annak a valószínűségi, hogy van élő családtag az \(\displaystyle (n+1)\)-edik generációban. Ekkor \(\displaystyle t_n=1-h_n\), ahol \(\displaystyle h_n\) annak a valószínűsége, hogy \(\displaystyle 0\) gyerek születik az \(\displaystyle n\)-edik genrációban, ami az \(\displaystyle n\)-edik generációhoz tartozó \(\displaystyle f^{(n)}(x)\) polinom konstans tagja, azaz

\(\displaystyle h_n=f^{(n)}(0),\)

amiből az következik, hogy \(\displaystyle h_{n+1}=f(h_{n})\), vagyis \(\displaystyle t_{n+1}=1-f(1-t_{n}).\)

Világos, hogy \(\displaystyle t_n\) (annak az esélye, hogy az \(\displaystyle n+1\)-edik generációban még van túlélő) monoton csökken, így \(\displaystyle 1-t_n\) monoton nő. Az \(\displaystyle x=1-t_{n}\) helyettesítéssel \(\displaystyle \frac{t_{n+1}}{t_n}=\frac{1-f(x)}{1-x}\), és láttuk, hogy ez monoton nő, ahogy \(\displaystyle x\) értéke nő.

Használva \(\displaystyle \frac{t_{n+1}}{t_n}\) monotonitását, és hogy \(\displaystyle t_0=1\),

\(\displaystyle t_{n-1}=\frac{t_{n-1}}{t_{n-2}} \cdot \frac{t_{n-2}}{t_{n-3}} \cdot \ldots \cdot \frac{t_1}{t_0}\le \left(\frac{t_{n}}{t_{n-1}}\right)^{n-1}.\)

Emiatt

\(\displaystyle t_{n-1}-t_{n}\le \left(1-\frac{t_{n}}{t_{n-1}}\right)\left(\frac{t_{n}}{t_{n-1}}\right)^{n-1}.\)

Figyeljük meg, hogy annak a valószínűsége, hogy éppen az \(\displaystyle n\)-edik generációban halnak ki az utódok \(\displaystyle t_{n-1}-t_{n}\). Legyen \(\displaystyle y=\frac{t_{n}}{t_{n-1}}\), ekkor

\(\displaystyle t_{n-1}-t_{n}\le (1-y)y^{n-1}.\)

Az \(\displaystyle (1-y)\)-ból és \(\displaystyle n-1\) darab \(\displaystyle \frac{y}{n-1}\)-ből álló (nemnegatív) szám \(\displaystyle n\)-es számtani közepe \(\displaystyle \frac{1}{n}\), így a mértani közepe ennél nem nagyobb, tehát

\(\displaystyle \frac{(1-y)y^{n-1}}{(n-1)^{n-1}}\le \frac{1}{n^n}.\)

Átrendezve

\(\displaystyle (1-y)y^{n-1} \le \frac{1}{n}\left(1-\frac{1}{n}\right)^{n-1}.\)

Tehát azt kaptuk, hogy \(\displaystyle \frac{1}{n}\left(1-\frac{1}{n}\right)^{n-1}\) egy felső becslés arra, hogy az utódok éppen az \(\displaystyle n.\) generációban halnak ki, és ez éles, mivel elérhető azzal a valószínűségi eloszlással, amikor \(\displaystyle \frac{1}{n}\) valószínűséggel \(\displaystyle 0\) és \(\displaystyle 1-\frac{1}{n}\) valószínűséggel \(\displaystyle 1\) gyerek születik.

A bizonyításból az is könnyen kiolvasható, hogy ez az egyetlen valószínűségi eloszlás, ami eléri a maximális valószínűséget arra, hogy pontosan az \(\displaystyle n\)-edik generációban hal ki a család.

Megjegyzés: Egy tömör összefoglaló a Galton-Watson folyamatokról például itt olvasható:
https://upcommons.upc.edu/bitstream/handle/2117/370276/4pp-branching-e-handout.pdf?sequence=1

Érdekesség: IV. Henrik úgy lépett a francia trónra, hogy a tíz generációval korábban élt Szent Lajos volt az utolsó királyi felmenője, mégis ő volt a trón jogos fiú-ági örököse, ugyanis éppen addigra halt ki az összes rangidősebb ág. Ez az alacsony valószínűségű esemény ihlette a feladatot.

Statisztika:

13 dolgozat érkezett.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	2 versenyző.
1 pontot kapott:	8 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2022. szeptemberi matematika feladatai