An Olympiad inequality Iran96

One day, Xiaoke asks me an Olympiad inequality, which recalls me of a lot of beautiful memories.

For any $a,b,c \in \mathbb{R}$, try to prove$$(ab + bc + ca)(\frac{1}{(a+b)^2} + \frac{1}{(b+c)^2} + \frac{1}{(c+a)^2}) \geq \frac{9}{4}$$

This is a very hard inequality named "Iran96". In the WeChat post, it is said that this one is so hard that many students who participates in competitions cannot solve  it. I believe that it is a little exaggerated. Even for a Olympiad question, this is not the most difficult one.

Let us do some transform.

$$LHS = 4\sum [a^5b + b^5 a + 2a^4 b^2 + 2 a^2 b^4 + 5  a^4 bc + 3 b^3 c^3 + 13 a^3  b^2 c + 13  a^3 b c^2 + 8  a^2b^2c^2]$$

$$RHS = 90a^2b^2c^2 + 9\sum[a^4b^2 + a^2b^4 + 2a^3b^3 + 6a^3b^2c + a^2b^3c + 2 a^4bc]$$

We do some simplification and finally we have to prove this inequality$$\sum[4 a^5b + 4ab^5 + 2a^4bc + 2a^2b^2c^2] \geq \sum[a^4b^2 + a^2b^4 + 6b^3c^3 + 2a^3b^2c + 2a^3bc^2]$$

It reduces to three inequalities$$\begin{eqnarray*}3\sum(a^5b + ab^5) &\geq& 3\sum a^3b^3\\\sum(a^5b + ab^5) &\geq& \sum(a^4b^2 + a^2 b^4)\\2abc(\sum a^3 + 3abc) &\geq& 2abc\sum(a^2b + ab^2)\end{eqnarray*}$$

The last one is a very famous inequality called inequality of Schur.

Wright-Fisher model and Kingman Coalescence

In the last course of ecology and model of probability at Polytechnique, we talk about Wright-Fisher model and Kingman coalescence, two models used for the simulation of the genes of human beings. The former is easy to understand and the latter, relates the theory of combinatoire, provides some very interesting formulas.

Wright-Fisher model

Suppose that in the population there exists two types of genes A and a, then we denote $X_n$ the number of A in the population, whose size is always $N$. Then the evolution is a Markov chain and the transition matrix is a binomial type
$$\mathbb{P}(X^N_{n+1} =  k| X^N_{n} = i) = C_N^k \left(\frac{i}{N}\right)^k \left(1 - \frac{i}{N}\right)^{N-i}$$
I
It is easy to check that $X^N_n$ is a martingale and its $L^2$ norm is bounded and the Markov chain is positive recurrent, so
$$
X^N_n \xrightarrow[a.s]{n \rightarrow \infty} X^N_{\infty} \in \{0, N\}
$$
Using the theorem of stopping time we get that $\mathbb{P}(X^N_{\infty} = N) = \frac{i}{N}$ where $i$ is the initial state.

Some other version can also be developped like the model with mutation and selection. On another hand,  if we change the scale of time like $Z_t = \frac{1}{N}X^N_{[Nt]}$, the convergence of trajectoire implies that
$$
Z_t = Z_0 + \int_0^t \sqrt{Z_s (1 - Z_s)} dB_s
$$
which relates a discrete model with a continuous random process.

Kingman coalescence model

The state is defined on the partition of $[1,N]$ and the initial state is $X_0 = \{1\}\{2\}\cdots\{N\}$. We note $T_i$ the i-th jump time which follows the law $\mathcal{Exp}(\frac{(N-i)(N-i-1)}{2})$ and choose uniformly two block to make one block. Some obvious properties are observed.

1. Each time, the number of block minus one.

2. The expectation of fusion time is $\sum_{i=1}^{N-1} \frac{2}{(N-i)(N-i-1)} = 2(1 - \frac{1}{N-1})$ and it converges.

3. We define the genetic relation $\pi' \rightarrow \pi$ if the later is the generated by fusing two blocks of the former. The transition matrix is 

$$\mathbb{P}(\pi', \pi) = \frac{2}{\sharp \pi' \cdot (\sharp \pi' -1)} \mathbb{I}_{\pi' \rightarrow \pi}$$

However, the most beautiful formule is 

$$\mathbb{P}_{T_{N-k}}(\pi) = \frac{k !}{N !} \frac{(N-k)!(k - 1)!}{(N-1)!} \prod_{i = 1}^l \sharp B_i$$

for $\pi = \bigsqcup_{i=1}^k \{B_i\}$

The proof is just  a recurrence but the structure of formula is really beautiful, isn't?

MMB (2) : Convergence of Galton-Watson

Before talking about the martingale theory of MMB, we prefer talking more about the model MAB and Galton-Watson model, the most classical model. We will talk about the longtime  behavior of the population.

Martingale in Galtton-Watson

We note $m$ as the expectation of the production. That is
$$
m = \sum_{k=1}^{\infty} k p_k
$$
A simple retira of extinction is that if $m \leq 1$, almost surely, the population will die. But if $m > 1$, the population has a probability to survive and this probability is the smaller fixed point of the characteristic function.
$$
q = \phi(q)
$$

If we would like to say more about the longtime behavior, in the sub-critical case, we have quasi-stationary theory, which is another story of my EA project. In the sup-critical case, we know that
$$
W_n = \frac{Z_n}{m^n}
$$
is a martingale, where $Z_n$ is the number of the population of each generation. The positivity means the convergence of martingale
$$
W_n \xrightarrow[p.s]{n \rightarrow \infty} W_{\infty}
$$
However, a natural question is in which case, we have U.I convergence or $L^1$ convergence. It has other sense in aspect of change of probability and we will study it later. Some special case is that when $\mathbb{E}(Z^2_1)  <  \infty$, then we have
$$
\begin{eqnarray*}
\mathbb{E}(W^2_{n+1}) & \leq &\mathbb{E}(W^2_{n}) + \frac{Var(Z_1)}{m^{n+2}} \\
\Rightarrow \sup_{n} \mathbb{E}(W^2_n) & < &\infty
\end{eqnarray*}
$$
Then we have a convergence in the sense $L^2$ and this implies the convergence in the sense $L^1$.

Generally, use the property of branch, we obtain that $\mathbb{P}(W_{\infty} = 0)$ is also a solution of $\phi(q) = q$. However, we have no idea that it is the smaller one. But in the case $\mathbb{E}(W_{\infty}) = 1$, we know that the in the sup-critical case it is not $1$. Then we get that
$$
\mathbb{P}(W_{\infty} = 0) =  \mathbb{P}(\text{Extinction})
$$
so conditionally non-extinction, we an exponential increment, except that we don't know the constant.

Then exact equivalent condition of convergence will be discussed at last and we just discuss the Galton-Watson with immigration in the second part.

Galton-Watson with immigration

In the model of Galton-Watson with immigration, each step we have not only the reproduction but also the immigration of population. We can of course couple $Z_n$ with a classical Galton-Watson $X_n$, then whether $\frac{Z_n}{m^n}$ converge depends on the intrgration  of $log(Y_1)$. 

We skip the technique  part, the result is that $$\begin{eqnarray*}\mathbb{E}(\log{Y_1}^+) < \infty \Rightarrow \lim_{n \rightarrow \infty} \frac{Z_n}{m^n} = c < \infty \\ \mathbb{E}(\log{Y_1}^+) = \infty \Rightarrow \lim_{n \rightarrow \infty} \frac{Z_n}{m^n} =  \infty\end{eqnarray*}$$

Change of probability and Kesten-Stigum theorem

The Kesten-Stigum theorem is as following.

\begin{eqnarray}
\mathbb{E}(W_{\infty}) &=& 1 \\
\mathbb{P}(W_{\infty} > 0 | \text{non-extinction}) &=& 1  \\
\mathbb{E}(Z_1 (\log{Z_1})^+) &<& \infty \\
\end{eqnarray}

The idea is very technique. To prove the  $\mathbb{E}(W_{\infty}) = 1$, we transform the problem to the change of probability. Then it is a biased Galton-Watson model, which can also be considered as a model with immigration. The we apply the result of the model of immigration. Technique part need the decomposition of measure and the change of probability in filtration.


--------------------------------------------------------------------------------------------------------------------------
Some remarks after two one years.

In 2017, I didn't understand all the part of this story, although the above gives almost all the points. The Kesten-Stigum theorem is important since it studies the the martingale of the Galton-Watson process. The critical and sub-critical case are easy : extinction. However, the super-critical case still has two cases : extinction or an exponential growth. The theorem tells us if there is no extinction, it is an exponential growth.

Secondly, to study the $W_n = \frac{Z_n}{m^n}$, we treat it as a change of probability i.e the probability $\mathbb{Q}$ of Galton-Watson process with immigration. We know that two measures can be decomposed into absolute continuous part and singular part. Moreover, in martingale case, it is that the part $\{W_{\infty} = \infty\}$ makes sense. The infinite part could not be seen as the part absolutely continuous, so we have to treat it specially.

Then the part of lemma Seneta is always technical. In fact, the number of individual of immigration contributes with a discount ration in the population. The criteria of $\log_+ Y$ often appears in the case of random environment.