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