2017年3月13日星期一

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?

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月28日星期二

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. 

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.

2016年12月13日星期二

EA答辩

今天历时一个学期的EA答辩结束了,随手写几点吧。

1.对一个方向特别感兴趣,和真正钻进去研究和学习还是很不一样的。有时候我们满足于自己在某些方面有点见解,可是真正投入到一个方向上,那绝对是一个全新的战场。自己是菜鸟,而其他人都是遍地老手。这个时候才是检验是否是真爱吧?

2.我就是这样一个例子。想着要做随机几何想了好久,终于有机会上手试试了,上述就是我的一些真实感受。然而,当中有那么一段时间全身心投入,拼了命想折腾点东西的劲头还是感动了自己。以及最后写报告时发现好些证明似是而非,只能一一自己补全,也算是一种科研锻炼吧。

3.终了,还是非常喜欢这个方向。有机会让我再去画些奇奇怪怪的东西。以后还要加油干呢。导师也说现在既然已经略窥门径了,要再接再厉啊。比如说做个什么问题或者证明吧,不能说是等着人家告诉你能不能证明和怎么证明,要是这样岂不是变成了DM了么?

4.答辩的时候,PPT要少弄一点。老师说一分钟看一张,快了大家就不开心了……哦不开心了额。

5.以后读论文,粗读一遍看大意,略读一遍掌握思路,然后必须要精读一遍(如果是钻研论文的话)验算过程啊!!!

6.毕竟后来没有拍照合影。我觉得我还是需要一个自己的成果才能填满欲望。定个小目标,3A结束前写出一篇论文吧。

就说这么多了,加油!

2016年12月4日星期日

Erlang and Jackson Network


This is a note for reviewing the MAP554 and some points about network.

M/M/1, M/M/$\infty$, birth and death

The basic model of queue theory. M/M/1 has just one server and has an invariant measure like geometric law,
$$
\pi(n) = p^n(1-p), p = \frac{\lambda}{\mu}
$$
M/M/$\infty$ has infinite server and Poisson law
$$
\pi(n) = e^{-p} \frac{p^n}{n!}, p = \frac{\lambda}{\mu}
$$
where $\lambda$ is the rate of arrival and $\mu$ the rate of waiting. A more general case can be done like change of power.

Erlang network:

This is just an application for truncated technique. That is if we have already a network with reversible invariant measure, we can generate a new by changing the power of that part. That is  
\begin{eqnarray*}
\tilde{q}(x,y) &=& C q(x,y), \forall x \in \mathcal{A}, y \in \mathcal{S} - \mathcal{A}\\
\tilde{q}(x,y) &=& q(x,y) , \text{ otherwise }
\end{eqnarray*}
Then the new invariant measure becomes
\begin{eqnarray*}
\tilde{\pi}(x) &=& K\pi(x) , \forall x \in \mathcal{A} \\
\tilde{\pi}(y) &=& KC\pi(y) , \forall y \in \mathcal{S} -\mathcal{A}\\
K &=& \frac{1}{\pi(\mathcal{A}) + \pi(\mathcal{S} - \mathcal{A})}
\end{eqnarray*}
The application is that we make $C = 0$ then the network is defined in just the part $\mathcal{A}$. For example, in the network of route with restriction $\mathcal{R}$, we can just do the case without restriction to get $\pi$, which is just the case of several M/M/1 independent, then we do restriction and normalization.
$$
\tilde{\pi}(x) = K\pi(x) , \forall x \in \mathcal{A}, K = \frac{1}{\sum_{x \in \mathcal{R}} \pi(x)}
$$

Jackson network

A more general model of network is like that. Each station has rate $\lambda_i$ of arrival and $\phi_i(n_i)\mu_i$ rate to tackling the service. Here $\phi_i(n_i)$ can be considered as the power of server, in the case M/M/1 it is always 1 and M/M/$\infty$ it is always $\phi_i(n_i) = n_i$. However, the difference is that after each service of station $i$, it has possibility $r_{ij}$ to go to the station j

The key is to find a equivalent $\tilde{\lambda}_i$ which satisfies that
$$
\tilde{\lambda}_i = \lambda_i + \sum_j \tilde{\lambda}_j r_{ji}
$$
then the station looks like independent and has the invariant measure
$$
\pi(n) = \Pi_i \frac{\tilde{p}_i^{n_i}}{\Pi_{m=1}^{n_i}\phi_i(m)}, \tilde{p}_i = \frac{\tilde{\lambda}_i}{\mu_i}
$$


2016年12月2日星期五

Levy characterization, representation of martingale and change of probability

I am preparing for the final, so I write some notes for the course maths finance.

Levy characterization for Brownian motion: 
If $\phi_s^T \phi_s = Id$, then
$B_t = \int^t_0 \phi_s dW_s$
is a standard Brownian motion

This theorem is very useful and it describes the nature that after a con-formal transform, the BM keeps its properties.

Representation of martingale:
This theorem has different version. The most general version is that for a $\mathcal{F}_t$ adapted local martingale $M_t$, it can be written as 
$M_t = \mathbb{E}[M_t] + \int_0^t H_s dWs$
where $H_t \in \mathbb{H}^2_{loc}$.

This is a mathematical version of perfect duplication theorem. The proof starts from the case $L^2 \text{martingale} \rightarrow L^1 \text{martingale} \rightarrow \text{local martingale}$. It has many application in the stochastic calculus.

Change of probability: 
First we define $Z_T = \exp{(\int_0^T \phi_s dW_s - \frac{1}{2}\phi_s^2 ds)}$. Generally, it's only a local martingale and if it satisfies $\mathbb{E}[Z_T] = 1$, we can define a change of probability
$\frac{d\mathbb{Q}}{d\mathbb{P}} = Z_T$ 
then under the new probability $\mathbb{Q}$, we can define a new BM in the form
$\tilde{B}_t = B_t - \int_0^t \phi_s ds$
We remark that in the case $\phi$ is deterministic, then the there is no problem since in this case, $Z_T$ is well defined of expectation 1. Otherwise, the expectation is not so clear but there is a theorem Novikov, says that if $\exp{(\int_0^T \frac{1}{2}\phi_s^2 ds)} < \infty$, then all the condition is satisfied.
The change of probability  can simplify the formula and has important applications on Monte-Carlo algorithms.