Gumbel distribution

A very short note for the Gumbel distribution.

$X_i$ i.i.d and have distribution of $\mathcal{Exp}(1)$, then $$\max_{1 \leq i \leq n}X_i - \log{n} \xrightarrow{(d)} G$$
where G represents a Gumbel distribution.

The proof is easy. We just calculate the distribution of this random variable
$$
\mathbb{P}[\max_{1 \leq i \leq n}X_i - \log{n} < y] = \mathbb{P}[\max_{1 \leq i \leq n}X_i  < y + \log{n}] = (1 - e^{- (\log{n} + y)})^n \rightarrow e^{-e^{-y}}
$$
So we conclude the convergence in distribution.

Percolation (1) : 2D Bernoulli percolation, critical point and transition of phase

Recently I attend the seminar talking about the percolation theory in IHES so I wrote some notes here.

Before starting, we have to notice that the terminology of percolation is adopted in different situations and generally in the contexts of graphs - it could be various graphs - like lattice $Z^d$, random graphs, random maps etc. But the phenomena is a little universal that a path starts from $0$ and goes to infinite faraway. In this series of talk, Hugo focuses on the situation of 2D Bernoulli percolation.

Definition and critical point

We give some definitions precisely. In the lattice graph $Z^2$, each site has 4 neighbors and every edge has independently a probability $p$ to be present (open) or a probability $1-p$ to be absent (closed). Then there exits a critical point $p_c$ : when $p \leq p_c$, with probability $0$ there exists a path from 0 to $\infty$, while when $p > p_c$, with probability $\theta(p)$ there exists a path from $0$ to $\infty$.

$$
\begin{eqnarray*}
p \leq p_c &,& \theta(p) = \mathbb{P}[0 \leftrightarrow \infty] = 0 \\
p > p_c &,& \theta(p) = \mathbb{P}[0 \leftrightarrow \infty] > 0
\end{eqnarray*}
$$

In 2D model, the critical point $p_c = 1/2$. Some simple argument supports this point. For example, if we draw the dual percolation between the face whose frontier is closed, we get a dual graph with probability $1-p$. If we suppose that the critical point is unique, then the transition of face happens at the same time in both the primal graph and the dual graph. So $p_c = 1- p_c$ and $p_c = 1/2$.

Quantitative analysis 

We hope to get some stronger result, The following theorem is first obtained by Menshikov, Aizeman and Michael $$\begin{eqnarray*}\forall p < p_c, \exists C_p > 0 \text{ s.t } \mathbb{P}_p[ 0 \leftrightarrow \partial B_n] \leq \exp{(-C_p n)}\\ \forall p > p_c, \exists C > 0 \text{ s.t } \mathbb{P}_p[0 \leftrightarrow \infty] \geq C(p - p_c) \end{eqnarray*}$$

Here, we denote the ball of radius $n$ by $\partial B_n$ and this theorem indeed, gives some numerical estimation of the speed of decrements. 

Proof 1 by (Menshikov, Aizeman, Michael) 

We note $\theta_n(p) = \mathbb{P}_p [0 \leftrightarrow \partial B_n]$ and $$\phi_p (S) = \sum_{x \in S, y \notin S, x \sim y} p\mathbb{P}[0 \leftrightarrow^S x]$$. We can prove it by 5 steps.

1.  We admit at first this important inequality$$ \frac{d}{dp} \theta_n(p) \geq \frac{1}{p(1-p)}[\inf_{0 \in S \subset B_n} \phi_p(S)](1 - \theta_n(p))$$
   then we define $$\tilde{p}_c = \sup \{p : \exists S \ni 0, \text{s.t} \phi_p(S) < 1\}$$
   we can prove $$\theta(P) \geq \frac{1}{p(1-\tilde{p}_c)}(p - \tilde{p}_c)$$
2.  We choose $S \subset B_{k-1}$ such that $\phi_p (S) < 1$ and prove$$\theta_{nk}(p) \leq (\phi_p(S))^n$$
3. We conclude that $\tilde{p}_c = p_c$
4. Verify the identity $$\frac{d}{dp}\mathbb{P}_p(X) = \sum_{e \in E} \frac{1}{p(1-p)}Cov(w_e, X)$$
5. We put $X = -\mathbb{I}_{0 ! \leftrightarrow \partial B_n}$ and we prove the important inequality.

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.

SLE (1) : A magical random evolution

When I came to France, I have spent longtime thinking about my future and the research field when I stayed in language school. One day, I read a introductory article which states a theorem that

"The Hausdorff dimension of the frontier of Brownian motion is  $\frac{4}{3}$"

I know the definition of Hausdorff dimension. A dimension mesures the fractal object, a good definition but very hard to calculate in maths. Usually, the mathematician gives its upper bound and lower bound but no exact value. How we reach it?

Some further search tells me a word - Schramm-Loewner Evolution, a magical random evolution relates many different models in maths and physics, especially those with fractal structure.

"Yes, it is the maths I want." I told myself and I begins the journey to understand it.

What is SLE

In short, SLE gives us a generally method to define a growing random set $K_t$, which can be considered as the scaling limit of some other random model, such as the interface of the Ising model, the frontier of the Browmian motion, and the limit of uniform spanning tree etc. 

More surprisingly, the description of the random compact set depends only on an equation - Yes, it is the most successful method ever existed for mathematicians and physicians to study the natural phenomena, and moreover, SLE relates the complex analysis and stochastic analysis together, so it takes advantages of a lot of theorems in both these fields. 

But we have to say, there exists a lot of open problems to study, since our nature is so complicated and the physical or biological models are difficult and specific enough - we have to spend a longtime understanding them.

How to define a growing compact set

The classical complex analysis studies conformal mapping and the Riemann mapping theorem tells us there is unique mapping between two domain such that the one point is fixed an the distortion at this point is also fixed. We denote $\mathbb{H}$ the half-upper plane. For a compact set $K$ such that $\mathbb{H} \backslash K$ is simple connected, we have a conformal mapping

$$
\Phi : \mathbb{H} \backslash K \rightarrow \mathbb{H}
$$

We make a linear transform (Hydrodynamic normalisation) such that the $\Phi$ has a analytic development near infinity
$$
\Phi(z) = z + \frac{2a(K)}{z} + o(\frac{1}{z^2}) \dots
$$

We remark that this mapping $\Phi$ exists using Schwartz reflection theorem and is the only one such that
$$
\| \Phi(z) - z \| \rightarrow 0 \text{ as } z \rightarrow \infty
$$

Here, $a(K)$ is called the capacity of $K$ since it measures how big $K$ is, An interesting property is that if we throw a 2-D Brownian motion starting from $Z_0 = iy$ and let $\tau$ be the exiting time of $\mathbb{H} \backslash K$, then
$$
2a = \lim_{y \rightarrow + \infty} y\mathbb{E}[Im(Y_{\tau})]
$$
this means that the capacity is a real positive number.

There is a lot of properties about this maps, such as the composition of map makes just makes the sum of capacity and the scaling property.
$$
\begin{eqnarray*}
a(\Phi_1 \circ \Phi_2) &=& a(\Phi_1) + a(\Phi_2)\\
a(\lambda K) &=& \lambda^2 a(K)\\
\end{eqnarray*}
$$

We would like this application be dynamical - that is to say we would like to define a family of mapping $g_t$ which corresponds to the standard mapply from
$$
\mathbb{H} \backslash K_t \rightarrow \mathbb{H}
$$
Obviously, this time, the series of compact set $K_t$ should have some condition. In maths, it requires that $K_t$ grows locally slowly, monotone and have good paramatrization $a(K_t) = t$. We can prove that, in this case, the growing random compact set can be characterized  by a ODE. - Loewner equation
$$
\partial_t g_t(z) = \frac{2}{g_t(z) - U_t}
$$
The ODE is well define if only there is no sigularity. We call $w_t$ the driven function and we know at the end of the lifetime $\tau$
$$
g_{\tau}(z) = U_{\tau}
$$
otherwise, we can always extend our solution.

In fact, we can treat $g_t(z)$ in two ways. First, we fix $z$, then $g_t(z)$ is a solution of ODE and we get the value of time t. Second, we fix t, then $g_t(z)$ becomes a conformal mapping. Generally, the first one is easier to get calculate the value, but if we would like to get the set $K_t$, the second is more intuitive. $K_t$ is the $z$ such that well define until the time $t$. Formally,
$$
K_t = \mathbb{H} \backslash g_t^{-1}(\mathbb{H})
$$
We have also the analytic serise
$$
g_t(z) = z + \frac{2t}{z} + o(\frac{1}{z})
$$

Some connection between harmonic function and BM is known for longtime, such as the law of BM is same after a normalized conformal mapping. The connection between this equation and probability theory is to make the driven funciton $w_t$ a random process like BM. We will states it in the next section.

Chordal SLE

We studies at first one kind of SLE which starts at 0 and walks always on the half-plan $\mathbb{H}$. We define $SLE_{\kappa}$ as following.

$$
\begin{eqnarray*}
\partial_t g_t(z) &=& \frac{2}{g_t(z) - U_t}\\
g_0(z) &=& z\\
U_t &=& \sqrt{\kappa}B_t
\end{eqnarray*}
$$

Generally, what makes different is that the driven function is a Brownian motion. But we know that the Brownian motion has some universality  in certain sense. We list some most basic properties that make the chordal $SLE_{\kappa}$ different. We recall that the random object here is the compact set $K_t$ and the function aims to help us understand the random compact set.

1. Markov on domain. Let $T$ be a stopping time, then
   $$
   \begin{eqnarray*}
   g_T(K_{T+t} \backslash K_T) - U_T & \perp & \mathcal{F_T}\\
   g_T(K_{T+t} \backslash K_T) - U_T & \sim^{d} & K_t\\
   \end{eqnarray*}
   $$
2.  Scaling invariace
   $$
   \frac{1}{\sqrt{\lambda}}K_{\lambda t} \sim^{d} K_t
   $$
3.  Symmetry.
   $$
   -K_t \sim^{d} K_t
   $$

We can compare these three properties with the basic properties of Brownian motion. There are just totally parallel, That is why the researcher now consider SLE as a basic random object in dimension 2 as Brownian motion.

However, one would like to know why the driving function must be a Brownian motion. In fact, in many statistical physics, it requires a conformal Markov property.
$$
\text{ Conformal Markov preperty } = \text{ Markov on domain } + \text{ Scaling invariance }
$$
In this case, we come back to see that the driving function should be stationary, independant increment and scaling invariant, so the only choice is Brownian motion.

Phase transition

The phase transition is a very interesting topic in chordal $SLE_{\kappa}$. A baby version is to consider how the $K_t$ will eat the axis. The theorem is 

• If $\kappa \leq 4$, a.s $\bigcup_{t \geq 0} K_t \bigcap \mathbb{R} = \{0\}$
• If $\kappa > 4$, a.s $\mathbb{R} \subset \bigcup_{t \geq 0} K_t$

The main idea is to write $X_t = \frac{g_t(1) - U_t}{\sqrt(\kappa)}$ then this problem transforms to  a problem of Bessel process and we get the result wanted.

The proof that the $SLE_{\kappa}$ is generated by a curve is more difficult, but if we admit this property, using the Markov property that $g_t(K_{t+s}) - U_t \sim^{d} \tilde{K}_s$, then when $\kappa \leq 4$, the curve after $g_t(K_{t+s}) - U_t$ will not touch the axis, which means that it will not intersect itself and the curve is a simple curve. This is a very interesting result. 

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.