显示标签为“MMB”的博文。显示所有博文
显示标签为“MMB”的博文。显示所有博文

2017年3月9日星期四

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.

2017年2月1日星期三

MMB (1) : Large deviation

This term, I take two courses M2 in Paris  Orsay and Polytechnique respectively in order to enrich my knowledge in probability. Today, Pascal talks about the large deviation theory.

We know the central limit theory, that is for $\{X_i\}$ i.i.d with finite variance
$$
\sqrt{M} (\bar{X}_M - \mathbb{E}[X] ) \Rightarrow \mathcal{N}(0, Var(X))
$$
However, this gives only the estimation in gap $\sigma$, but what happens for the distribution in large distance from the mean?

This requires the tool of large deviation estimation, This is a basic tool in mathematics and is used every in probability and statistics. For probabilistes, large deviation gives the probability of the events atypical and sometimes the correlation function estimation. For statisticiens, this gives the interval of confiance non-asymptotic. In a word, this is a necessary tool.

Inequality of Chernoff

We start from the typical Markov inequality
$$
\mathbb{P}\left[S_n / n - \mathbb{E}[X] > x\right] = \mathbb{P}[e^{\theta( {S_n}/{n} - \mathbb{E}[X])} > e^{\theta x}]
$$
So we get
$$
\mathbb{P}\left[S_n / n - \mathbb{E}[X] > x\right] \leq e^{- n I(x)}
$$
where we define
$$\begin{eqnarray}
\phi(\theta) &=& \log \mathbb{E}[e^{\theta X}] \\
I(x) &=& \sup_{\theta \in R} \theta x - \phi(\theta)
\end{eqnarray}$$
However, from this simple inequality, a lot technique is developed.


Inequality of Hoeffding

We can give a better estimation for the case $X$ is bounded in $[a,b]$, that is 
$$
\mathbb{P}\left[S_n / n - \mathbb{E}[X] > x\right] \leq \exp(- \frac{2 x^2}{n(b-a)^2})
$$
Idea is to develop the function $\phi$ in 0 and then give a good estimation.

Some generalized version is also possible. For exemple, we can consider not only one function, but a family of function - in another word, a dictionary. The more general theorem depends largely on the theory of covering, or approximation.

Inequality of for Gaussian

However, a big obstacle of the inequality of Hoeffding is that the condition of bound. How to treat the unbounded function, for example, Gaussian, a large class of function?

An idea is a the inequality of type entropy. The entropy of a function under the mesure $\mu$ is to define 
$$ Ent_{\mu}(f)  = \mathbb{E}(f  \log{(f)}) - \mathbb{E}(f) \log{(\mathbb{E}(f))}$$
In some case, the mesure $\mu$ verifies the inequality of log-Soblev such that
$$ Ent_{\mu}(f^2) \leq C_{\mu} \mathbb{E}_{\mu}(|\nabla f|^2) $$
In this case we can deduce an inequality
$$ \mathbb{P}(|f(Y) - \mathbb{E}(f(Y))| > \epsilon) \leq 2 \exp{(-\frac{\epsilon^2}{C_{\mu}|f|^2_{Lip}})}$$ 
It is the type of inequality of large deviation. A natural question is whether the mesure verifies the inequality of log-Soblev. It requires analysis and the answer for Gaussian is positive. However, a general case is just one branch of research.

Theorem of Gramer

A more general principle is the theorem of Gramer, which gives not only the upper bound but also the lower bound of a distribution.
$$\begin{eqnarray}
-\inf_{x \in \Gamma^{O}}I(x)
\leq \liminf_{n \rightarrow \infty} \frac{1}{n} \log \mathbb{P}\left[S_n / n \in \Gamma \right] \\
\leq \limsup_{n \rightarrow \infty} \frac{1}{n} \log \mathbb{P}\left[S_n / n \in \Gamma \right]
\leq -\inf_{x \in \Gamma^{F}}I(x)
\end{eqnarray}$$

In the course, we analyse in detail some properties of the function $\phi(\theta)$ and $I(x)$, like their convexity, zeros and monotony. The upper side is also like the Chernoff upper bound, while the left lower bound use the change of probability to prove it.