Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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.
7 pontot kapott:Foris Dávid, Sztranyák Gabriella.
6 pontot kapott:Molnár-Szabó Vilmos, Wiener Anna.
5 pontot kapott:2 versenyző.
4 pontot kapott:1 versenyző.
3 pontot kapott:1 versenyző.
2 pontot kapott:2 versenyző.
1 pontot kapott:3 versenyző.

A KöMaL 2022. szeptemberi matematika feladatai