Problem A. 832. (September 2022)

A. 832. Let us assume that the number of offsprings for every man can be \(\displaystyle 0, 1,\dots\) or \(\displaystyle n\) with probabilities \(\displaystyle p_0,p_1,\dots,p_n\) independently from each other, where \(\displaystyle p_0+p_1+\dots+p_n=1\) and \(\displaystyle p_n \ne 0\). (This is the so called Galton–Watson process.)

Which positive integer \(\displaystyle n\) and probabilities \(\displaystyle p_0,p_1,\dots,p_n\) will maximize the probability that the offsprings of a given man go extinct in exactly the tenth generation?

(7 pont)

Deadline expired on October 10, 2022.

Solution: Let \(\displaystyle f(x)\) be the polynomial generated by the distribution of the number of children, i.e.

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

Let \(\displaystyle f^{(n)}(x)\) denote the \(\displaystyle n^{th}\) iterate of \(\displaystyle f\). i.e. \(\displaystyle f(f(\ldots(f(x))\ldots))\), where \(\displaystyle f\) occurs \(\displaystyle n\) times. It is easy to check that the distribution of the number of children in the \(\displaystyle n^{\text{th}}\) generation is \(\displaystyle f^{(n)}(x)\).

Since \(\displaystyle f(1)=p_n+p_{n-1}+...+p_1+p_0=1\), thus

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

which is the average value of \(\displaystyle f'(y)\) on interval \(\displaystyle \left[x,1\right]\). \(\displaystyle f'\) is a polynomial with non-negative coefficients, thus it is monotonously increasing on the non-negative numbers, so the same is true for its average value on \(\displaystyle \left[x,1\right]\).

Let \(\displaystyle t_n\) denote the probability that there is a living descendant in the \(\displaystyle (n+1)^{\text{th}}\) generation. The probability of having zero children being born in the \(\displaystyle n^{\text{th}}\) generation is \(\displaystyle h_n=1-t_n\), but on the other hand \(\displaystyle h_n\) is the constant term in \(\displaystyle f^{(n)}(x)\), and thus \(\displaystyle h_n=f^{(n)}(0)\). This implies \(\displaystyle h_{n+1}=f(h_n)\), and thus \(\displaystyle t_{n+1}=1-f(1-t_n).\)

It is clear that \(\displaystyle t_n\) decreases, and thus \(\displaystyle 1-t_n\) increases. Substituting \(\displaystyle x=1-t_n\) we get that \(\displaystyle \frac{t_{n+1}}{t_n}=\frac{1-f(x)}{1-x}\), and we have seen that this increases with \(\displaystyle x\).

Since \(\displaystyle t_0=1\) and \(\displaystyle \frac{t_{n+1}}{t_n}\) increases, we get that

\(\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},\)

and thus

\(\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}.\)

Here \(\displaystyle t_{n-1}-t_{n}\) is the probability that the descendants go extinct in exactly the \(\displaystyle n^{\text{th}}\) generation. By letting \(\displaystyle z=\frac{t_n}{t_{n-1}}\) we get that the probability is at most \(\displaystyle (1-z)z^{n-1}\). It is easy to see that this is maximized by \(\displaystyle z=\frac{1}{n}\), and thus the probability is at most \(\displaystyle \frac{1}{n}\left(1-\frac{1}{n}\right)^{n-1}\), and this can be achieved when there is a probability of \(\displaystyle \frac{1}{n}\) of having 0 children and a probability of \(\displaystyle 1-\frac{1}{n}\) of having 1 child. In fact, by inspecting the proof we can see that this is the only distribution that maximizes \(\displaystyle t_n-t_{n-1}\).

Statistics:

13 students sent a solution.
3 points:	1 student.
2 points:	2 students.
1 point:	8 students.
0 point:	2 students.

Problems in Mathematics of KöMaL, September 2022