Connection probability on oriented percolation does not depend on root

There is a long time that I have not updated my blog. This time, I would like to talk about once again a question in Alibaba competition (2021) as I did not solve it that day. 

Question: On a general connected graph $G=(V, E)$, every bond contains two oriented edges. Then we pose an oriented percolation model on it. We choose a vertex as root, then try to prove that the probability to have oriented path from every vertex to root is independent to the choice of root.

It is natural to think of a bijection, but it is not easy. During the exam, I only treat the very simple case that $G$ is a tree, which is very easy. However, it is still useful because we will see an argument to combine the two.

We denote by $h(a) = \mathbb P_p[G \to a]$ the connection probability. It suffices to prove that $h(a) = h(b)$ for every $a \sim b$. We prove it by induction on the number of bonds $\vert E \vert$. Then the basic case is the tree and we have already proved it and we need to finish the induction step.

For every configuration $\omega$, we define $$Pivot(\omega, a, \overrightarrow{ba}) := \{v \in V: v \to a \text{ when } \omega(\overrightarrow{ba}) = 1, v \nrightarrow a \text{ otherwise}\}.$$

Then we treat two cases:

Case 1: $\omega \in \{G \to a\}, Pivot(\omega, a, \overrightarrow{ba}) = \emptyset$. For this case, $\omega \setminus \overrightarrow{ba}$ can be thought as a connection configuration in $(V, E\setminus \{a,b\})$. Then by induction, for this case the probability does not depend on the choice of $a,b$ by adding an oriented edge and we can flip it.

Case 2: $\omega \in \{G \to a\}, Pivot(\omega, a, \overrightarrow{ba}) \neq \emptyset$. Then this implies that $\omega(\overrightarrow{ba}) = 1$ and $b \in Pivot(\omega, a, \overrightarrow{ba})$. We should add one more restriction that $a \nrightarrow b$, otherwise it is the common part for two. Then we flip the orientation  $\overrightarrow{ba}$, and one can check that 

$$\mathbb P_p[\omega \in \{G \to a\} \cap \{a \nrightarrow b\}, b \in Pivot(\omega, a, \overrightarrow{ba}) ] \\= \mathbb P_p[\omega \in \{G \to b\} \cap \{b \nrightarrow a\}, a \in Pivot(\omega, b, \overrightarrow{ab}) ].$$

With these arguments, we finish the step of induction and establish the result for the general graph $G$.

A small theorem of Boolean approximation

I would like to record one theorem learned in the Alibaba competition this year. In fact, this problem has also appeared in the maths competition at Peking University for high school students. Let $(a_i)_{1 \leq i \leq n}$ be positive sequence such that $\sum_{i=1}^n a_i = a$ and $\sum_{i=1}^n (a_i)^2 = 1$, then we can always find a configuration $\epsilon_i \in \{\pm 1\}$ such that $$\vert \sum_{i=1}^n \epsilon_i a_i \vert  \leq \frac{1}{a}.$$

Let us see what this theorem tells us. From AG inequality, we know that if every number is equal, $a = \sqrt{n}$ and every $a_i = \frac{1}{\sqrt{n}}$. Then by a choice of the best Boolean approximation $\sum_{i=1}^n \epsilon_i a_i $, one can get a number very close to the $0$ with an error $\frac{1}{\sqrt{n}}$ --- that is the error of one term.

This makes us think of the concentration inequality in the probability --- like Markov inequality, Hoeffding inequality etc. That is the case when I did Alibaba competition, but I have to say this is a very dangerous trap in this question. In fact, even after the competition, I continue trying this idea many times, but it seems no easy way to figure it out. In fact, let us recall what concentration inequality teaches us: yes, if we put $\epsilon_i$ centered variable, the measure should be concentrated and $$\mathbb{P}[\vert \sum_{i=1}^n \epsilon_i a_i \vert  \geq \frac{1}{a} ] \leq 2\exp(-2/a^2)$$.

Good, you will see an explosion and this does not give useful information. Indeed, the concentration inequality always told us the measure should be in the $\sigma$ region, but it tells nothing how good the measure is concentrated in the $\sigma$ region. In this question, a random choice is clearly not good because the $\sigma$ for $\sum_{i=1}^n \epsilon_i a_i $ is $1$.

One has to keep in mind that the probabilistic method is good and cool, but not the only way and sometimes not the best way.

A simple solution is just by induction and one step exploration, or someone calls it the greedy method. This problem is equivalent to prove $$\left(\min_{\epsilon_i \in \{\pm\}} \vert \sum_{i=1}^n \epsilon_i a_i \vert  \right) (\sum_{i=1}^n a_i) \leq \sum_{i=1}^n (a_i)^2.$$ We do at first the optimization for $n$ variable and then choose the sign for the last one. We can also manipulate the choice of the last variable. For example, one can let $a_{n+1}$ always be the smallest one, thus its influence is always smaller than $\frac{1}{a}$. Once we get the correct direction, the theorem is not difficult.

Maximal correlation

This is a question about the correlation. Let $X,Y$ be two Gaussion random variable $\mathcal{N}(0,1)$ with correlation $\beta$, then prove that the best constant of Cauchy inequality is 

$$Cov(f(X), g(Y)) \leq \vert \beta \vert \sqrt{Var(f(X)) Var(g(Y))}$$.

In fact, one can define the maximal correlation of random variable by the best constant above and of course it should be bigger than $\beta$. Let us remark how to prove the inequality above quickly. We can use the expansion by Hermit polynomial that we have 

$$\mathbb{E}[H_n(X) H_m(Y)] = \delta_{n,m} \left(\mathbb{E}\frac{1}{n!}[XY]\right)^n.$$

Then a centered $L^2$ functions have projection on $H_0$ zero. Then we have 

$$\mathbb{E}[f(X)g(Y)] = \sum_{n=1}^{\infty}\langle f, H_n \rangle \langle g, H_n \rangle \frac{1}{n!} \beta^n \\ \leq \vert \beta \vert \sqrt{\sum_{n=1}^{\infty}\langle f, H_n \rangle^2 \frac{1}{n!} } \sqrt{\sum_{n=1}^{\infty}\langle g, H_n \rangle^2 \frac{1}{n!} } \\ \leq \beta \vert \sqrt{Var(f(X)) Var(g(Y))}.$$
This concludes the proof.

Strong Markov property for Brownian Bridge

The strong Markov property for Brownian motion is well known and it is also naturally true for the Brownian Bridge. In fact, since Brownian Bridge ended at $(T, 0)$ is thought as a Brownian Motion conditionned the end point, or thought as a perturbation for a linear interpolation, it is natural when we restart from another mid-point.

To prove it rigorously, for example, the Markov property for the Brownian Bridge, we have to do some calculus. Let $(W_t)_{t \geq 0}$ be the standard Brownian motion issued from $0$, and we have $(B_t)_{s \leq t \leq T}$ defined as 

$$ B_t = x + W_t - W_s - \frac{t-s}{T-s}(x + W_T -W_s) ,$$

a Brownian Bridge between $s, T$ and at $s$ it is $x$ and at $T$ its value is $0$. One way to see this formula is that the term $x + W_t - W_s$ is the Brownian Motion while we have to reduce the term at the endpoint $T$. Some simple calculus shows that it is equal to 

$$B_t = \frac{T-t}{T-s}(x + W_t - W_s) - \frac{t-s}{T-s}(W_T - W_t).$$

A Markov property is very simple but requires calculus: we would like to show that for $s < r < t < T$ we have

$$B_t = B_r + W_t - W_r - \frac{t-r}{T-r}(B_r + W_T -W_r). \quad (\star)$$ 

Now we prove it. An intermediate step tells us 

$$ - \frac{t-r}{T-r}(B_r + W_T -W_r) = - \frac{t-r}{T-s}(x + W_T - W_s)$$ and we put it into the formula that 

$$RHS (\star) = x + W_r - W_s - \frac{r-s}{T-s}(x + W_T -W_s) + W_t - W_r - \frac{t-r}{T-s}(x + W_T - W_s)\\ = x + W_t - W_s - \frac{r-s}{T-s}(x + W_T -W_s) - \frac{t-r}{T-s}(x + W_T - W_s) \\ = x + W_t - W_s - \frac{t-s}{T-s}(x + W_T -W_s).$$ 

This proves the Markov property. Then the strong Markov property is just an approximation and the regularity of the trajectory. 

Spin glass (1) : Basic definition, some basic fact about Ising model

(I took this course at 2019 but the note is revised at 2020 as I would like to understand better this course.)

In this semester, I take one course about spin glass. This model is very classical. We decide the configuration in $\{\sigma_i\}_{1 \leq i \leq N} \in \{1,-1\}^{N}$, and we treat a Hamilton energy as

$$H(\sigma,) = \sum_{1 \leq i,j \leq N} - J_{i,j} \sigma_i, \sigma_j ,$$

then every configuration has a Gibbs measure $\frac{1}{Z_N} \exp (-\beta H(\sigma))$, where $Z_N$ is the function of partition. 

Despite the simple description of the model, this spin model is at the center of the research for a long time since it has nice properties. Some very famous varied models like free energy $J_{i,j}$ is random, Ising model $J_{i,j} = 1$ for short-range while $0$ for long-range and mean-field case where $J_{i,j}$ is always $1$. 

Ising model and its free energy

The Ising model is famous model in statistic physics. We define the Hamilton energy with $\sharp$ boundary condition and with a $h$ exterior magnetic field on the domain $\Lambda$

$$H_{\Lambda}^{\sharp}(\beta, h, \sigma) = - \beta \sum_{\{i,j\} \cap \Lambda \neq 0, i \sim j}  \sigma_i, \sigma_j - h \sum_{i \in \Lambda} \sigma_i,$$ 

and then we define the function of partition as 

$$Z^{\sharp}(\beta, h) = \sum_{\sigma} \exp\left( - H_{\Lambda}^{\sharp}(\beta, h, \sigma) \right).$$

This defines a Gibbs measure and we use always $\langle \cdot \rangle^{\sharp}_{\Lambda, \beta, h}$ to represent the Gibbs measure. We define also the normalized free energy as 

$$F^{\sharp}_{\Lambda}(\beta, h) = \frac{1}{|\Lambda|} \log(Z^{\sharp}(\beta, h)),$$

since it plays an important role in physics. By Holder's inequality, we know that $$(\beta, h) \mapsto F^{\sharp}_{\Lambda}(\beta, h) \text{ is convex}.$$ Then, let $\square_n = \left(\frac{-3^n}{2}, \frac{3^n}{2}\right)$, we can prove use the renormalization argument to prove that 

$$F^{\sharp}_{\square_{n+1}}(\beta, h) \leq F^{\sharp}_{\square_n}(\beta, h) + O(3^{-n}),$$

moreover, since different only has a very small perturbation, this implies that  when the volume grows to $\infty$, the normalized free energy has a limit that 

$$F(\beta, h) = \lim_{\Lambda \rightarrow \infty}F^{\sharp}_{\Lambda}(\beta, h)  $$

and it does not depend on the choice of the boundary condition. 

Magnetization

The magnetization is an important quantity and it is defined as $m_{\Lambda}(\sigma) = \frac{1}{|\Lambda|}\sum_{i \in \Lambda} \sigma_i$, and the average magnetization $\bar{m}^{\sharp}_{\Lambda} = \langle m_{\Lambda}\rangle^{\sharp}_{\Lambda, \beta, h}$ . One important observation is that

$$\bar{m}^{\sharp}_{\Lambda}(\beta, h) =  \partial_h F^{\sharp}_{\Lambda}(\beta, h).$$

Thus a natural question is if we cand define $\bar{m} = \lim_{\Lambda \rightarrow \infty} \bar{m}^{\sharp}_{\Lambda}$ and whether it also holds that

$$\boxed{\bar{m}(\beta, h) =  \partial_h F_{\Lambda}(\beta, h)}.$$

This equation is the key to the topic. Very naturally, to make sense this equation, the right hand should be well-defined. The basic information is that $F$ is convex, so it admits left and right derivative. So the least condition to make sense the equation is at the point of differential point. As $\bar{m}^{\sharp}_{\Lambda}(\beta, h) =  \partial_h F^{\sharp}_{\Lambda}(\beta, h)$ is bounded, it admits a limit $C$ for its subsequence. Using the convexity

$$F^{\sharp}_{\Lambda}(\beta, h') \geq  F^{\sharp}_{\Lambda}(\beta, h) + (h' - h)\partial_h F^{\sharp}_{\Lambda}(\beta, h'),$$

we take the limit to have 

$$F(\beta, h') \geq  F(\beta, h) + (h' - h)C,$$

so by convexity analysis we know if $F(\beta, \cdot)$ differentiable at $h$, the then $C$ has no choice but $\partial_h F(\beta, h)$. For the point non-differentiable, we call the phase transition.

Limit measure and phase transition

We can continue to study other descriptions of the phase transition. From the viewpoint of the probability measure, it is natural to ask if $\langle \cdot \rangle_{\Lambda, \beta, h}^+$ and $\langle \cdot \rangle_{\Lambda, \beta, h}^-$ admit a limit measure. This is true and the proof relies on the FKG inequality. It suffices to study the problem for increasing function, and we use the domain Markov property of the model: for $V \subset U \subset \mathbb{Z}^d$

$$\langle f \rangle_{V, \beta, h}^+ = \langle f  \vert \sigma_i = 1, i \in U \backslash V \rangle_{V, \beta, h}^+ = \frac{ \langle f  \mathbf{1}_{\left\{\sigma_i = 1, i \in U \backslash V\right\}} \rangle_{U, \beta, h}^+}{\langle  \mathbf{1}_{\left\{\sigma_i = 1, i \in U \backslash V\right\}} \rangle_{U, \beta, h}^+}  \geq  \langle f  \rangle_{U, \beta, h}^+.$$

This proves the decreasing of measure, so the limit is well-defined and this measure is stationary. Then we can define

$$\bar{m}^+(\beta,h) =  \langle \sigma_0\rangle_{\beta, h}^+ , \qquad \bar{m}^-(\beta,h) =  \langle \sigma_0\rangle_{\beta, h}^-, $$

and one can prove further

$$\bar{m}^+(\beta,h) = \partial_h^+ F(\beta, h),   \qquad \bar{m}^-(\beta,h) = \partial_h^- F(\beta, h).$$

These two equations make the bridge between the analytic object (derivative on two sides) and the statistic object (magnetization under different boundary conditions). Finally, the phase transition can also be described as $\langle \sigma_0\rangle_{\beta, h}^+ \neq \langle \sigma_0\rangle_{\beta, h}^-$, or the magnetization is non-null because we have naturally $\bar{m}^+(\beta,h)  = - \bar{m}^-(\beta,h) $. 

Head run game

The head run game may be one of mathematics topic in research, but I think it is more well-known because it appears in many questions of exam of courses or of interview. Today I met one question asked by one friend, but its answer is very surprising.

We give a series of random variables $(X_i)_{i \geq 1}$ of i.i.d Bernouil law of parameter $p$ and we denote by $(\Omega, \mathcal{F}, \mathbb{P})$ the probability space. Alice and Bob has a game : if pattern $(1, 1, 0)$ appears before $(1,0,1)$, then Alice wins, otherwise Bob wins. So, what is the probability that  Alice wins the game ?

If it is the first time that one meets this question, it may be difficult. If one has met the similar problem, we define $\tau_{110}$ and $\tau_{101}$ for the two patterns, then in the case $p = 1$, a well known result is that $\mathbb{E}[\tau_{110}] = 6$ and $\mathbb{E}[\tau_{101}] = 5$, thus one may guess that $(1,0,1)$ appears at first.

However, it is not the case. And a more amazing result is that, for any $p \in (0,1)$ Alice always has a bigger probability to win the game ! One direct method to do it is to decompose the probability as 

the sum 

$$\mathbb{P}[\tau_{110} < \tau_{101}] = p_{00} + p_{01} + p_{10} + p_{11}$$ where we define that $$p_{00} = \mathbb{P}[\tau_{110} < \tau_{101}, X_1 = 0, X_2 = 0].$$ And then, we use the fact that the event is only locally correlated, which means using strong Markov property, when conditionned all the history, we only have to keep the last two runs. Then we have a big recursive equation that $$  \left[ {\begin{array}{c} p_{00} \\ p_{01} \\ p_{10} \\ p_{11}  \end{array}} \right] = \left[ {\begin{array}{cccc} 1-p& 1-p& 0& 0\\  0& 0& 1-p& 1-p\\ p& 0& 0& 0\\ 0& 0& 0& p\\ \end{array}} \right]   \left[ {\begin{array}{c} p_{00} \\ p_{01} \\ p_{10} \\ p_{11}  \end{array}} \right]  +  \left[ {\begin{array}{c} 0 \\ 0 \\ 0\\ p^2(1-p)  \end{array}} \right]$$

Thus, we can solve the equation and obtain that $$\mathbb{P}[\tau_{110} < \tau_{101}] = \frac{1}{2-p}$$.

From the formula, we get that Alice always has bigger probability to win. (And it is like this I find this amazing result.) But does it have a more natural explication why Alice can win ? In fact, we see that Alice and Bob have to wait for a $1$ to win the game. Once it happens, in the following two round, we have $(0,0), (0,1), (1,0), (1,1)$ 4 types of configurations, and $(0,1),(1,0)$ have the same probability. If $(0,0)$ happens, they have to restart the game. If $(1,1)$ happens, we see that stochasticly Alice has bigger probability to win under this condition. That explains the reason.

Levy’s equivalence theorem

We often says that the convergence almost surely, convergence in probability and convergence in law cannot be mixed and the first one implies the second one, which implies the third one. But in some situation, these three claims can be the same. One very famous situation is the Levy's equivalence theorem : We set $(X_m)_{m \geq 1}$ a family of independent random variables and we define $S_n = \sum_{m=1}^n X_m$, then convergence in law can imply the convergence almost surely !

This seems a little incredible and such an amazing theorem does not often appear in a general textbook. Maybe it is for the reason that such an easy theorem requires sometimes technical proof. Here, I give a personal argument using many big theorems.

The key idea is to use the Kolmogorov's three-series theorem. It is an equivalent criteria for that $S_n$ converges almost surely. The three conditions are to define that $Y_m = X_m \mathbf{1}_{|X_m| \leq A}$ and
$$
\sum_{m=1}^{\infty} \mathbb{P}[|X_m|>A] < \infty,  \quad \sum_{m=1}^{\infty}\mathbb{E}[Y_m]\text{ converges }, \quad \sum_{m=1}^{\infty}\mathbf{Var}[Y_m] < \infty.
$$

For the first one, we put the random variables in Skorohod representation theorem, and say that one is necessary to say the fluctuation is not so often.

For the third one, we argue by absurd and put it in the Lindeberg Feller central limit theorem, to say that if the variance goes to infinite, then
$$
\frac{\sum_{m}^n Y_m - \mathbb{E}[Y_m]}{\sqrt{\sum_{m=1}^{n}\mathbf{Var}[Y_m]}} \Rightarrow \mathcal{N}(0,1),
$$
and we know $\sum_{m}^{\infty} Y_m$ also converges in law to some random variable. Thus, the normalization seems too stronger and we obtain that  $\frac{\sum_{m}^n  - \mathbb{E}[Y_m]}{\sqrt{\sum_{m=1}^{n}\mathbf{Var}[Y_m]}} \Rightarrow \mathcal{N}(0,1),$ which is a contradiction.

Finally, to prove that the expectation is finite, we still argue by absurd. We go back to the very basic definition to test it by a function. However, we have a intuition that $\sum_{m=1}^{\infty}X_m \simeq \sum_{m=1}^{\infty}Y_m$ which will go to infinite, because that its drift is infinite while its variance is finite. This is the situation of vague convergence.

So we prove the three conditions and prove this theorem.

Circle packing and its applications

One topic of this year's lecture of Saint-flour is about the circle packing, a very nice theory abridging complex analysis, probability and graph theory. I will record some main results in the two week's lectures.

Drawing circle packing : finite and infinite

A circle packing is a collection of disk $P$ to represent a planar graph.$G = (V, E)$, where the center of disk represents the vertex of graph and two disks are tangent if and only if the two vertex are connected.

For a circle  packing, we could draw easily a graph, but could we construct a circle packing from any planar graph ? This is the first question. The question could be answered by two steps : in finite case, we could have an algorithm to solve it by minimizing the energy, which depending only on the radius and for given radius we could draw the graph. Moreover, this drawing unique up to Mobius transform if we add an infinite point to make the out face a triangle.

In infinite case, the question is completed. However,  if we suppose that the bounded degree condition, this is a direct result of compactness.

Reversible Markov chain and electric network

The main question of the topic is to study the recurrence of a reversible Markov chain. In fact, we could always realize it by a electric network by designing conductance on the edges. The recurrence of an infinite simple random walk on this graph (Markov chain) is equivalent to say  $R_{eff}(x \leftrightarrow \infty) = \infty$. Very intuitively, this means that the effective resistance is infinite so we could not go to infinite freely.

Two useful lemma may be Dirichlet and Thomson : the voltage is a harmonic function which minimizes the energy and the current is unit flow which minimize the energy. 

By the electric network, the problem of recurrence is transformed to a problem of analysis of graph.

He-Schramn theorem : Classification of by circle packing

However, it's not easy to analyze the effective resistance. But He-Schramm theorem tells a classification of the infinite graph with only bounded degree : hyperbolic, circle packing in unit disk and transient; or parabolic, circle packing in plane and recurrent.

The main idea is that the circle packing provides a new view point to see the graph. The radius of disk gives something more than the distance on the graph, and this geometric information matches well with the analysis of resistance. If the circle packing is in plane, it could have a log increment of the effective resistance.

Benjamini-Schramm theorem

Our final object should be that of UIPT, which is a random object and the bounded degree condition is missing. To go pass it, a more powerful tool of Benjamini-Schramm theorem is called. This says that we could always start from some limit graph and if the object studied is a local limit of the finite, uniform rooted graph of bounded degree, it's current.

The proof of this theorem is tricky and depends mainly on a very nice estimate called "magic" lemma. Personally, I believe that this lemma has something to do with the maximal inequality and Whitney covering.

Recurrence of UIPT

The final step to prove UIPT requires all the preparation. Moreover, we apply some surgery to replacing some big degree vertex by some trees. This modification makes the Benjamini-Schramm theorem work since it reduces the degree of vertex. Moreover, some quantitative analysis is also needed to calibrate the increment of effective resistance, for example, we should know that the distribution of degree is exponential.


A final remark is that this  seems a nice proof, but how we collect all the necessary result of probability, graph theory and complex analysis ? This is a nice question. And the connection between these three area could be more profound in all senses.

One not so simple question of probability

The sum of i.i.d random variable is one of most classical topic in probability. However, there are always questions not so easy even in the first year course.

Question : Let $X_n$ be a series of independent random variables and $S_n = \sum_{i=1}^{n}X_i$. We would like to study the behavior of $\limsup S_n, \liminf S_n$ in the following two situations : 

(1)$$\begin{eqnarray}\mathbb{P}[X_n = n] &=& \frac{1}{n+1} \\ \mathbb{P}[X_n = -1] &=& \frac{n}{n+1}\end{eqnarray}$$ 

(2)$$\begin{eqnarray}\mathbb{P}[X_n = n^2] &=& \frac{1}{n^2+1} \\ \mathbb{P}[X_n = -1] &=& \frac{n^2}{n^2+1}\end{eqnarray}$$ 

In another word, we would like to study the behavior of a random walk.

Even we have some advanced tools, we may make mistakes in this questions. Here, I give two false proofs that I have thought.

False proof (1) : OK, the sum $S_n$ is a martingale, so we apply the representation of martingale and we know that we can embed this martingale to the Brownian motion by Dubins-Schwartz theorem. (It's false since it's discrete and we may choose some specific moment in the random process)

False proof (2) : We use the theorem of optional stopping theorem to the stopping time $T = T_a \wedge T_{-b}$ and study it as the ruin of gambler. (This time the errors in the proof is harder to find. In fact, since the positive jump becomes bigger and bigger, even the martingale $S_{n \wedge T}$ isn't U.I. This isn't the same case as simple random walk or continuous martingale) 

Let's give a correct proof :

The question (2) isn't so difficult. We apply Borel-Cantelli lemma that

$$\sum_{n=1}^{\infty} \mathbb{P}[X_n = n] = \sum_{n=1}^{\infty} \frac{1}{n^2+1} < \infty$$

this means that the positive only appears finite times almost surely. So, we have of course $\lim_{n \rightarrow \infty} S_n = - \infty$.

The question (1) has an easy part. We apply once again the Borel-Cantelli lemma that 

$$\sum_{n=1}^{\infty} \mathbb{P}[X_n = n] = \sum_{n=1}^{\infty} \frac{1}{n^2+1} = \infty$$

so it will happen infinite times. Moreover, we know once the positive jump occurs, it will cover all the negative jump before this step. So as the positive jump accumulates, we conclude that

$$\limsup_{n \rightarrow \infty} S_n = \infty$$

The hard part, we apply another sub-martingale $\exp(- \lambda S_{n \wedge T})$. This time, a very big positive jump doesn't matter as we know this guy is smaller than $\exp(\lambda b)$. So by the optional stopping theorem, we get

$$(1 - \mathbb{P}[T_b < T_a])e^{-\lambda a} + \mathbb{P}[T_b < T_a] \geq 1 \Rightarrow \mathbb{P}[T_b < T_a] \geq \frac{1- e^{-\lambda a}}{e^{\lambda b} - e^{- \lambda a}}$$

We take $a \rightarrow \infty$ and get $\mathbb{P}[T_b < \infty]  \geq e^{-\lambda b}$ then we take $\lambda \rightarrow 0$ and get $\mathbb{P}[T_b < \infty] = 1$.

TCL theorem for one type Riemann integral of Brownian motion

This is one question in the exercise of "Local time and excursion", but I think it is very interesting.

We consider a measurable function $g$ and a Brownian motion $(B_t)_{t \geq 0}$ one integral defined as  

$$A_t = \int_0^t g(B_s)ds$$

means the integration along the path. We suppose that $g$ is intégrable then this formula makes sense. Well, if $g$ is continuous this is obvious : although there is random part, it's in fact a Riemann integral (or Lebesgue) of continuous function. In general case, we apply a very useful formule called time of occupation

$$\int_0^t g(B_s)ds = \int g(a) L^a_t(B)da$$

Then, since $\left(L^a_t(B)\right)_{a \geq 0}$ is continuous and zero at infinity, the one has a max so $A_t$ is well defined.
One more remark for this formule : One large advantage of Lebesgue integral is the introduction of measure, so when we compare two integral, we have not to compare it point-wisely, but cut them into blocks. However, the integral like Riemann isn't good, but local time transform it again with the style of Lebesgue one. The stochastic integral face the same problem, luckily we have Ito, Doob, BDG so we can make that one like "one deterministic term + one random error".

Our main theorem is to prove that

$$\frac{1}{\sqrt{t}} A_t \Rightarrow \int g(a)da |N|$$
where $N \sim \mathcal{N}(0,1)$. This convergence is in weak sense.

We remark why this formula should be correct. One important observation is one Levy's theorem that
$$\left( L^0_t, |B_t| \right)_{t \geq 0} = (\text{law})  \left( S_t, S_t - B_t \right)_{t \geq  0}$$
So we have obviously $\frac{1}{\sqrt{t}}L^0_t$ has the same law as $|N|$. For the local time at other level, once it is touched, it will behavior like $L^0_t$.

However, the problem is that : the convergence in law of sigle random variable doesn't mean the convergence in law of random process. I make the this phrase red to point out the danger. But we know that $a \rightarrow L^a_t(B)$ is also continuous, so what's the error term ? Could this error disappear after the normalization of $\frac{1}{\sqrt{t}}$ ?

We have to go back to the analysis of the regularity of the local time. Using the Tanaka formule
$$L^a_t(B) = 2(B_t - a)^ +  - 2(B_0 - a)^ + - 2\int_{0}^t \mathbb{1}_{\{B_s > a\}} dB_s$$
We  obtain that
$$L^a_t(B) - L^0_t(B) = \left[2(B_t - a)^ +  - 2(B_0 - a)^ + \right] - \left[2(B_t )^ +  - 2(B_0 )^ +\right] + 2\int_{0}^t \mathbb{1}_{\{0 < B_s \leq a\}} dB_s$$
We would like to say that $L^a_t(B) - L^0_t(B)$ is uniformly little. The difficulty is the last one stochastic integration. However, we see that when $s$ grows, it's very rare that the Brownian motion could stay in the interval so it contributes very little to the integral (even in a stochastic one !). The powerful tool like BDG inequality tells totally the moment of this random variable. We estimate the tail so with large probability $1 - \epsilon$, the process will converge uniform to a $|N|$ process. We write down the proof properly by the density argument etc and conclude the proof.

Finally, I have to say once I come to the part of analysis the size of a random variable, the training in the course of statistic helps really a lot. That may be why we say probability and statistics are always together. (Oui, et analyse est aussi son bon amie)

Est-ce que le processus Gaussien peut être différentiable ?

Comme le titre, c'est une très bonne question. Hier mon ami me demande cette question et au premier coup, j'avais envie de dire que c'est pas possible après plusieurs raisons.

1. Le modèle très simple est le mouvement brownien, qui n'est pas de classe $C^1$.

2. Un théorème de Dubins-Schwarts nous dit que une martingale locale continuée est presque un mouvement brownien après un changement du temps.

3. Oui, on parle de dérivée bruit blanc, mais c'est toujours de sens faible ou il veut dire intégration stochastique.

Si on dit la "dérivée" dans l'autre sens non standard, bon, c'est toujours possible. Mais finalement, on trouve un exo qui nous dit c'est possible lorsque la covariance $K(s,t)$ est de classe $C^2$ et en fait on a fait cet exo avant.

Argument est comme suivant :
1. $\left\{\frac{G_{t+ \delta - G_t}}{\delta}\right\}_{t \geq 0}$ est un processus Gaussien après la linéarité d'espace Gaussien.
2. On vérifie il est de suite de Cauchy dans $L^2$. Donc il admet une limite comme Gaussien.
3. La limite a une covariance  $\partial_s \partial_t K(s,t)$.

Donc, on voit dans le sens de limite $L^2$ il admet la limite. C'est tout de propriété de Gaussien, qui est fermé dans le sens limite.

Mais pourquoi on a tendance de mélanger le cas avec la martingale. Voilà, une martingale est un processus ssi il est de croissance indépendante. Mais ici, le processus a vraiment de mémoire et le cas PAIS ne peut pas avoir dérivée. Donc, même si le processus aléa est souvent fractal, il peut être régulier. 

Rappel de probabilité (4) : convergence en loi et TCL

On continue de réviser la base de probabilité et dans cette partie, on veut attaquer le problème de convergence en loi. Peut-être il y déjà un poste sur la convergence dans un espace métrique, mais le TCL et la fonction caractéristique a quand même des intérêts.

Convergence en loi dans $\mathbb{R}$

La définition de convergence en loi dans la situation $\mathbb{R}$ est assez simple et elle est définie par
$$ F_n(x) \rightarrow F(x) $$
pour tous les points de continuité. Un peu d'analyse nous dit que cette convergence est uniforme. Il y a plusieurs façons de caractériser la convergence. Par exemple, on dit $\mu_n \Rightarrow \mu$ si pour toute la fonction continuée et bornée, on a
$$\mu_n(f) \rightarrow \mu(f)$$

Il y a d'autre critère comme l'ensemble ouvert et fermé. 
$$\forall O \text{ouvert}, \liminf \mathbb{P}(X_n \in O) \geq \mathbb{P}(X \in O)$$
Une méthode de mémoriser l'inégalité est une suite de Dirac masse qui converge vers un point dans l’adhérence. La version fermée et bord est aussi facile à décrire.

On remarque dans la démonstration de $\mathbb{R}$, la représentation est assez directe i.e si $X_n \Rightarrow X$, on peut les tous mettre dans un espace en commun tel que $X_n \rightarrow X$ presque sûrement.

D'autre cas spécifique, comme le théorème de Scheffé, qui nous dit si la variable aléatoire a une densité $f_n$ et $f_n \rightarrow f$ ponctuellement, on a aussi la convergence car l'intégration de densité est toujours 1.

Tension

On liste la notation de tension dehors car elle a un rôle très important et peut être généralisé dans d'autre espace. Gros-moto, une suite est tendue si et seulement $\forall \epsilon > 0,$ il existe un compact $K_{\epsilon}$ tel que
$$\sup_n \mathbb{P}(X_n \notin K_{\epsilon}) < \epsilon$$.

L'intérêt de cette propriété est que une suite de mesure est pré-compact si et seulement elle est tendue. Donc, montrer la tension est suivant une partie important de convergence en loi. Une stratégie standard est l'argument "tension + convergence de loi marginal".

Fonction caractéristique 

On utilise aussi la fonction caractéristique d'analyser la convergence faible de variable aléatoire. La raison profonde est l'analyse de Fourier car la fonction caractéristique est la transformée de Fourier d'une mesure. Dans le livre de Durret, on voit beaucoup d'application de la fonction caractéristique. En fait, une formule utile est
$$ \frac{1}{2}(\mu(a) + \mu(b)) + (\mu((a,b)) = \frac{1}{2\pi} \lim_{T \rightarrow \infty} \int_{-T}^{T} \frac{e^{-ita}-e^{-itb}}{it}\phi(t) dt$$

Dans le cas où la fonction caractéristique est intégrable et donc la mesure a une densité, on peut retrouver la densité par la transformée inversée.
$$ f(x) = \frac{1}{2\pi} \int e^{-itx} \phi(t) dt $$

Combiner la propriété de tension et la propriété de fonction caractéristique, si la fonction caractéristique d'une suite de mesure converge, il a une convergence qui s'appelle la convergence vague. i.e la fonction de répartition n'est pas vraiment une fonction de répartition car l'information à limite est perdu. Cependant, si cette fonction a une continuité à 0, la suite a tension donc elle converge vers une mesure.

TCL, Poisson et loi stable

Finalement, on parle un peu du théorème de TCL et loi stable. La démonstration de TCL est classique est directe par la fonction caractéristique, mais on devrait savoir que c'est juste une situation très idéale. En fait, la convergence en loi est un peu robust, dans le sens que ce théorème est correct sous la condition plus faible. Pour le TCL c'est le théorème de Lendeberg-Feller.

La convergence vers une loi de Poisson est souvent appelée "le convergence de petite nombre" car il approche la probabilité d'événement rare. On peut aussi mesurer la vitesse de convergence en distance total - qui est une bonne distance de convergence en loi pour l'état discret.  

En concernant la loi stable, c'est une situation que variance n'est pas fini. Donc on fait une normalisation différente. Les variables $X$ étudiées dans ce problème a une vitesse de décroissance comme $x^{- \alpha}, 0 < \alpha < 2$. Sa limite $Y$ a une propriété que $\forall n, \exists a_n, b_n$ tel que
$$\frac{\sum_{k=1}^n Y_k - b_n}{a_n} \overset{d}{=} Y$$. Pour la paramètre $\alpha$, la normalisation est $n^{\frac{1}{\alpha}}$.

Dans d'autre espace polonais, certaine définition est aussi bien définie mais certaine ne marche plus, surtout ceux qui utilisent la fonction caractéristique, qui demande l'existence de transformée de Fourier.

 

Rappel de probabilité (3) : le théorème de grand nombre

La théorème de grand nombre est une théorie très importante dans probabilité, mais sa démonstration peut être assez technique sous différentes conditions. Pour la suite, on raconte quelques histoires sur le théorème de grand nombre.

La théorie plus classique suppose que $\{X_i\}$ sont i.i.d et sa variance est finie. Sous cette condition, on a inégalité de Markov
$$
 \mathbb{P}[\frac{S_n}{n} > \epsilon] <  \frac{Var(X)}{n \epsilon^2}
$$
qui suffit d’entraîner la loi faible. Concernant la loi forte, on choisit une sous-suite et montre la convergence p.s grâce au lemme de Borel-Cantalli. Puis on contrôle les erreurs entre eux. Cette technique est la base de beaucoup de démonstration.

Pour aller plus loin, une direction est supprimer la condition de variance. Dans ce cas, il faut utiliser la technique de troncature comme
$$
Y_n = X_n \mathbb{I} _{X_n < n}
$$
Cette technique a des propriétés incroyable mais pas évidant :
(1) Avec probabilité 1, il y a que nombre fini de $X_n \neq Y_n$
(2) $\sum_n [Var(Y_n / n)] < \infty$

La première propriété est très utile, il nous dit que l'étude de convergence se réduit comme le comportement de $Y_n$. La deuxième a beaucoup d'application. Soit on suit la même chemin que la méthode classique : montre une convergence de sous-suite et contrôle les erreurs entre eux. Soit on utilise la méthode de Kolmogorov.

La méthode de Kolmogorov est en fait, utiliser l'idée de martingale. En utilisant la convergence de martingale $L^2$, on montre p.s $\sum_n \frac{Y_n}{n}$ converge. Puis, un lemme de Kronecker - un lemme pure d'analyse maths, qui nous dit que dans cette situation,  $\frac{\sum_{k=1}^n Y_k}{n}$ converges.

La situation sans $L^1$ est aussi possible d'étudier mais cela dépend de démonstration. La loi faible peut se généraliser dans le cas de variable aléatoire corrélée ou $L^1$ faible. Mais quelques fois, on essaie aussi d'autre normalisation.

A small note on mixing time of Markov chain

This is a small note after  the note by Nathanael Berestycki and the object is just for reviewing some interesting story about this model and preparing for the coming summer school.  I decide to write it on my blogger since this permit me to write down the idea as quickly as possible  without paying too much attention on the detail and technical part.

Basic notation of mixing time

At first, we have to talk about the motivation of the research of this subject. In abstract measure theory, we talk about the topology of the Radon measure on a metric space and its distance. The distance which induces the weak star convergence is called Levy distance. This theory is very profond, while the situation in discrete state situation is very easy since the topology coincides and we use the total variation distance  

$$\| \mu - \nu \| = \sup_{A \subset S} \mu(A) - \nu(A)$$

to represent the distance between two measures, which is very simple and elegant. On the other hand, the study of this subject  arise because of the emerging of many computer algorithms : we have to know if they converge and moreover, the quantitative behavior of the convergence. Especially, the cutoff phenomenon tells us sometimes we have to do enough step of Markov chain to make sure that it converge.

There is some other equivalent definition of the total variation distance like 

$$\begin{eqnarray*}\| \mu - \nu \| &=& \sup_{A \subset S} \mu(A) - \nu(A) \\ &=& \frac{1}{2}\sum_{x\in S} \mu(x) - \nu(x) \end{eqnarray*}$$

Concerning the distance between a Markov chain, if it has a invariant measure  $\pi$, then we use 

$$d(t) = \sup_{x \in S}\|P^t(x, \cdot) -  \pi(\cdot)  \|$$

to describe the distance from the invariant measure. Sometimes it  interacts with another definition 

$$ \rho(t) = \sup_{x,y \in S}\|P^t(x, \cdot) -  P^t(y, \cdot) \| $$

since the two are equivalent 

$$ d(t) \leq \rho(t) \leq 2 d(t)$$.

The mixing time is defined as 

$$t_{mix}(\epsilon) = \inf \{t | d(t) \leq \epsilon \}$$.

and we use usually $t_{mix} = t_{mix}(1/e)$.

The convergence to the invariant measure is after Perron-Frobenius theorem for irreducible, aperiodic, finite state Markov chain and sometimes we also use the Lyaponov function to treat the infinite state case. However, these criteria isn't so sharp and just give a qualitative description. 

Before finishing this section, we recall the phenomenon of cutoff. Generally speaking, that is the $d(t)$ falls drastically near the point of $t_{mix}$. This phenomenon is a little hard to understand since until now, we didn't find a universal method to analyse this phenomenon but just study the model case by case. Moreover, sometimes it happens but sometimes, it can be avoided and we don't see it in the simulation.

Coupling technique

To estimate the speed of convergence, a first technique is called coupling and it may be the most useful and powerful method which apply in all the case. A coupling of measure $\mu, \nu$ is a couple $(X,Y)$ where $X$ has the law of $\mu$ and $Y$ has the law of $\nu$. We remark that the marginal law can never recover the joint distribution, so this condition doesn't fix the law $(X,Y)$.

A third definition of total variation distance is 

$$\| \mu - \nu \| = \inf_{couple}\mathbb{P}(X \ne Y)$$.

This formula gives us a upper  bound of the $d(t)$ and the upper bound of the $t_{mix}$ since 

$$\begin{eqnarray*} d(t) \leq \rho(t) &=& \sup_{x,y \in S}\|P^t(x, \cdot) -  P^t(y, \cdot) \| \\&\leq& \sup \mathbb{P}(X_t \ne Y_t) \end{eqnarray*}$$

and a useful technique is to demande that when two Markov chain meet, they move together - this induces that 

$$\boxed{d(t) \leq \sup_x \mathbb{P}_x(\tau_{X,Y} > t)}$$

One example is the lazy random walk on the circle $Z / n$. The Markov chain has $1/2$ probability to stay on the same place and $1/4$ to move forward or backward. Then we start two chain $(X,Y)$ and let a first coin to decide which one to move and second one to decide the direction. Once they meet together, the move together. In fact, the meet of two chain is reduced to the ruin of gambler. So using the first moment 

$$d(t) \leq \sup_x \mathbb{P}_x(\tau_{X,Y} > t) \leq \frac{\mathbb{E}(\tau_{X,Y})}{t} = \frac{n^2}{t}$$

We induce that 

$$t_{mix} \leq e n^2$$. 

At the end of this part, we give a small lemma about the log-sub-additivity of the $\rho$ which is 

$$\rho(s+t) \leq \rho(s) \times \rho(t)$$

The proof is easy by the coupling technique.

Strong stationary time technique

Strong stationary time is a very special technique : we have a stopping time $\tau$, once we arrive this point, the law becomes naturally invariant law. Thus 

$$d(t) \leq \mathbb{P}(\tau \geq t)$$.

This idea sounds crazy but the model fonction like this exists. One famous example is the random Top-to-random shuffle. In this model, the cards under the card at the bottom is uniformly random since there is no order under this one a prior. Therefore, once the card at the bottom comes to the top and once go back to the deck, the card becomes totally random. The mixing time is easy to calculate and is the same as the collection of coupon $t_{mix} \sim n\log n$.

However, this technique just applies in some specific case and requires a good observation.

Spectral technique : viewpoint  from operator

The spectral method is especially powerful for the case of reversible Markov chain, which relates the speed of convergence to the gap of eigenvalue. Therefore, the gap of eigenvalue $\gamma$, the convergence of total variation distance, the ration of expansion have been related naturally.

We know that for a irreducible aperiodic finite Markov chain, it has naturally a series of eigenvalue $1 = \lambda_1 > \lambda_2 \geq \lambda_3 \cdots \lambda_n \geq -1$. We can extract a family of eigenvector orthogomal naturally by diagonalisation, however, we would like the orthogomal base in inner product 

$$\langle f, g\rangle_{\pi} = \sum_{x \in S} f(x)g(x)\pi(x)$$  

instead of the orthogomal base in usual $L^2$ inner product. To realize it, we find the orthogomal base $\phi_i$ of the operator $A$ where

$$A(x,y) = \sqrt{\frac{\pi(x)}{\pi(y)}}P(x,y) \Leftrightarrow A = D^{1/2}PD^{-1/2}$$

who is also symmetric and share the same eigenvalue with $P$ that is 

$$A\phi_i = \lambda_i \phi_i$$.

Then we define $f_i = D^{-1/2}\phi_i$, we have 

$$\langle f_i, f_j\rangle_{\pi} = \langle \phi_i, \phi_j \rangle = \delta_{ij}$$

$$Pf_i = D^{-1/2}(D^{1/2}PD^{-1/2})\phi_i = D^{-1/2}A\phi_i = \lambda_i D^{-1/2}\phi = \lambda f_i$$

So $f_i$ is the orthomal base wanted. The orthogomal decomposition tells us 

$$A = \sum_{i=1}^n \lambda_i \phi_i \phi_i^T $$

when we  plug the $f_i$ in, we obtain

$$\boxed{\frac{P(x,y)}{\pi(y)} = \sum_{i=1}^n f_i(x) f_i(y) \lambda_i}$$

One may wonder why we would like find a expression like this. In fact, it has interest since 

$$\begin{eqnarray*}d(t) &=& \sup_{x \in S}\|P^t(x, \cdot) - \pi(\cdot)\| \\ &=& \frac{1}{2}\sum_{y \in S}\pi(y) \left|\frac{P(x,y)}{\pi(y) }- 1 \right| \\&=& \frac{1}{2}\|\sum_{i=2}^n f_i(x) f_i \lambda_i \|_{L^1(\pi)}  \\ &\leq& \frac{1}{2} \|\sum_{i=2}^n f_i(x) f_i \lambda_i \|_{L^2(\pi)} \\ &=& \sqrt{\sum_{i=2}^n f_i^2(x) \lambda_i^2} \end{eqnarray*}$$

We continue the analysis and obtain the  inequality that 

$$\boxed{(t_{rel} - 1)\log(\frac{1}{2\epsilon}) \leq t_{mix}(\epsilon) \leq \log(\frac{1}{2\epsilon \sqrt{\pi_{min}}})t_{rel}}$$

where the relax time is defined as
$$t_{rel} = \frac{1}{\gamma}$$

Spectral technique : viewpoint from geometry

The result obtained by the eigenvalue of operator is so powerful since it gives both the upper and lower bound. However, to calculate the gap of eigenvalue is not so easy for general case, so we propose many other method to estimate the gap $\gamma$. Here we list two  methods : by the optimal constant of Poincare's inequality and Cheeger's inequality.

If we define the Dirichlet energy under the measure $\pi$ as
$$\begin{eqnarray*}E(f,f) &=& \sum_{e}Q(e) \nabla f(e) \nabla f(e)\\ Q(x,y)  &=& \pi(x)P(x,y)\end{eqnarray*}$$,
then  the classical discrete Poincare inequality gives
$$\boxed{Var(f) \leq \frac{1}{\gamma} E(f,f)}$$.
The constant is optimal  so if we have another equality of constant  $C$, we have necessarily $t_{rel} \leq C$ so we get the upper bound of mixing time.

Another method comes from the famous Cheeger's inequality, the ratio of expansion is
$$\Phi(A) = \frac{Q(A, A^C)}{\pi(A)}$$
and the ratio of expansion of the graph is
$$\Phi_* = \inf_{\pi(A) \leq 1/2} \Phi(A)$$.
The famous Cheeger's inequality tells that
$$\frac{\Phi_*^2}{2} \leq \gamma  \leq 2\Phi_*$$

We remark that one good lower bound for the mixing time is that
$$t_{mix} \geq \frac{1}{4\Phi_*}$$
means that if the graph is not so connected, it will take long time to mix the chain.

Comparaison method and continuous time Markov chain

All the result of mixing time can also be converted to the continuous time, where the jumping time is a Poisson process but the state is still finite. We follow the same routine and get that 
$$d(t) \leq \frac{1}{2}d_2(t) = \frac{1}{2}\sqrt{\sum_{j=2}^n e^{-2t\mu_j}} , \mu_j = 1-\lambda_j$$

The comparaison theorem says that for two Markov chains $X,Y$ if $E_X(f,f) \leq AE_Y(f,f)$, then we have  $\mu_j^X \leq A \mu_j^Y$. This helps us to give some analysis for a Markov chain given the information of one chain already well understood.

Coupling from the past

Wilson proposes some interesting algorithm called coupling from the past which gives an exact  law of  invariant measure in some specific case, for example the Ising model. The simulation requires that the state should have a function to make it ordered. Unlike the MCMC, we will come from the past. The coupling technique says that generally, the invariant measure is the case that a coupling meet. Now we apply check if 
$$G(-t,0)(-1) = G(-t,0)(1)$$
where $-1,1$ represent respectively the minimal and maximal element. If it is the case, we take the value and if not, we add a segment of simulation even before it until it meet. The monotone property says it looks like we simulate from $-\infty$ and all the trajectories meet.

Finally, we remark although this program terminates almost surely, its time is a random variable so it takes risk to take longtime before ending.


Cover time

The cover time is another concept similar to mixing time which says the time to visit all the state at least once. The Matthews inequality gives the control 
$$t_{cov} \leq (1 + \frac{1}{2} + \cdots \frac{1}{n}) t_{hit}$$

One surprising result is the relation between the cover time and DGFF that 

$$t_{cov} \sim |E| (\mathbb{E}(\max_{x \in S} h_x))^2$$.

Others

We conclude that the mixing time has to be estimated carefully. The coupling method has a lot of flexibility but requires good observation and technique while the spectral method looks more like analysis on heat equation. We can also reformulate the subject in the language of electronic network so that we use the analysis of structure to estimate the mixing time. 

Séminaire 11/05/2017 : Probabilité de demain

This is the second edition of the seminar of this doctor probability seminar. Here I just cite some high light.

2D Ising model by Dmitry Chelkak : this is a topic which has been studies longtime, but there are still many questions open and the most  tremendous progress is found in recent year. We may  know the scaling limit of the interface of hexagon is $SLE_6$, but how about the others ? In fact, the scaling limit of the configuration is related to a similar random process - CLE conformal loop ensemble, another varied version of SLE. Moreover, a complete system of discrete complex analysis and discrete holomorphic tools are developed. There are a lot of open questions like Ising model on random maps.

Recurrence relation and dimer model by Paul Melotti : We can find a direct correspondent relation between recurrence series and the partition function of dimer model, which helps us express it explicitly, I ask the question if we could also find the recurrence for given partition function ? The answer is negative  since the recurrence is always polynomial and this is not the case for any partition function - the integrable  problem.

Flips of the triangulation on the sphere by Thomas Budzinski : The uniform triangulation is now a very popular topics. However, how we construct them ? The natural way is Monte-Carlo. We start from a configuration and we try  to flip the configuration like MCMC metropolis method. Using the $n^4$ growth and the bottleneck property, Thomas gives a inferior bound for the mixing time as $n^{\frac{5}{4}}$. However, the upper bound is missing (but he says numerical result is like this.) And we want if we could do better ?

Expander by Simon Coste : OK, this is the topic of my PSC at Polytechnique. This talk still gives me some new idea. From the point of random graph, the distribution of random value has demi-circle law and this can be generalized to some more general case - graph oriented, We ask if random map could be a expander ? It seems not but we need to add the weight ... Anyway, the spectral analysis also is an important  technique in random model.

A nonlinear SPDE by Perla EI Kettani : WOW, I find something that I look forward longtime. Once, I ask if Gaussian free field has some application in analysis and this is one example. If we consider the coefficient of each element of orthogonal base is not only a gaussian but also a Brownian motion, we  generally use the stochastic analysis frame to treat PDE, Therefore, the GFF is one type of noise as one of my friend comments on my simulation. So, probability and analysis interacts and I believe that there will be more applications.

Deformation of random field by Julie Fournier : I didn't understand much but it seems like the deformation of random field.

Bismut-Elworthy-Li formula by Henri Elad Altman : Henri fires ! This talk is about the strong Feller property. Just like the transport equation can only keep the regularity but the diffusion equation can improve the regularity, we ask the same question for the semi-group. This formula applies for a general Ito process given that the drift isn't so degenerated. This tool is essential  for the study of some kinds of equation like equation of KPZ.

Cost functional for large random trees by Marion Sciauveau : We would like to generalize  the cost functional from a discrete random tree to a continuous tree coded by Brownian excursion. Before we do the convergence and in fact, we can also embed the discrete tree into the continuous tree. The cost functional helps study the DC complexity.

Hypercube percolation by Remco van der Hofstad : A exhaustive study about the percolation on the hypercube, It is hard to imagine that the work is done without simulation. The critical point is given by
$$
\mathbb{E}_{p_c}[C_0] = 2^{n/3}
$$
and the window is about $2^{-n/3}$, which means in this period we see a drastic transition of phase.

I think a seminar like this gives us a quick understand of different direction of probability, since the subject is always very various in this domain. On the other hand, to make new friends during the seminar is also interesting. However, to see those who grow up together from prepa, master and become collaborator is an envy.

Rappel de probabilité (2) : convergence en loi - théorie générale sur l'espace métrique

La théorie de convergence sur l'espace de probabilité est peut-être plus compliquée que  nous avons pensé. Evidemment, on connait la définition de convergence p.s, de convergence en probabilité et de convergence en loi depuis on apprend la probabilité élémentaire - ou peut-être depuis on apprend l'analyse réelle. Mais ils ont des versions avancée. Par exemple, on peut poser des questions suivante:

-Est-ce que on peut parler de convergence en loi sur un espace abstrait ? Ou au moins, la convergence de processus aléatoire.

-Est-ce que la convergence  en loi a totalement rien à voir avec la convergence p.s ?

-Comment généraliser le nuage de Poisson ? 

Personnellement, c'est l'année dernière quand je lisait des articles sur la géométrie aléatoire, j'arrive de trouver que le contexte de ces terminologies est plus large. Heureusement, les géants ont déjà construit une base solide et assez générale pour nous. - Je crois les probabilistes comme Lévy; Meyer et Neveu comprennent les travaux aujourd'hui, même si le modèle est plus varié et sophistiqué.

Convergence en loi sur $\mathbb{R}^d$

La définition de convergence en loi sur $R^d$ est assez connue : 

Définition : (Convergence en loi $\mathbb{R}^d$)

On dit $\mu_n \Rightarrow \mu$ si $\forall f \in \mathcal{C}_c({\mathbb{R}^d})$, $\mu_n(f) \rightarrow \mu(f)$.

Il existe plusieurs caractérisations de cette définition. 

Caractérisation 1 : Par le théorème de Lévy et fonction génératrice.

Caractérisation 2 : Dans $\mathbb{R}$, la fonction de répartition satisfait $F_n(x) \rightarrow F(x)$ pour tous les points de continuité de $F$.

Caractérisation 3 : Dans $\mathbb{R}$, $\forall < \epsilon$, il $\exists A, t.q \sup_{n} \mu_n(\mathbb{R} \backslash [-A,A]) < \epsilon$, alors il existe une sou-suite $\mu_{\phi({n})} \Rightarrow \mu$.

Convergence en loi sur l'espace métrique

Un première question est "est-ce que l'on peut généraliser ces résultats sur un espace plus abstrait ? " Comme on sait comment définir une fonction continuée bornée $ \mathcal{C}_b((E,d),\mathbb{R})$ sur un espace métrique (en fait, un espace T4 suffit), et on rappelle la construction de mesure sur un espace métrique : c'est après la représentation de théorème de Riez et les fonctionnelles de Radon positives, c'est aussi possible de parler la convergence sur un espace abstrait.

La mesure sur celui a beaucoup de régularité $$\begin{eqnarray*}\forall A \in \mathcal{B}(E), \mu(A) &=& \inf \{\mu (O), O \text{ ouvert }, A \subset O\} \\ &=& \sup\{\mu (F), F \text{ fermé }, F \subset A\}\end{eqnarray*}$$

On dit $\mu_n \Rightarrow \mu$ si $\forall f \in \mathcal{C}_c((E,d),\mathbb{R})$, $\mu_n(f) \rightarrow \mu(f)$.

Cette définition est exactement parallèle que celle dans l'espace $\mathbb{R}^d$. On énonce un théorème, assez générale et en fait, on l'utilise aussi dans la démonstration dans les résultats précédents.

Théorème ; (Définition équivalente)

1. $\mu_n \Rightarrow \mu$.
2. $\forall O$ ouvert, $\liminf_{n \rightarrow \infty} \mu_n(O) \geq \mu(O)$.
3. $\forall F$ fermé, $\limsup_{n \rightarrow \infty} \mu_n(F) \leq \mu(F)$.
4. $\forall A \in \mathcal{B}(E) $ si $\mu(\partial A) = 0$, on a $\lim_{n \rightarrow \infty} \mu_n(A) = \mu(A)$.
5. $\forall f \text{ p.s } \mu $ bornée, $\lim_{n \rightarrow \infty} \mu_n(f) = \mu(f)$.

Espace polonais et métrisation de $\mathcal{M}_1(E)$

Quand on entre le domaine plus générale, c'est-à-dire le cas de l'espace topologique, on a besoin de travailler sur un espace un peu compliqué mais satisfait quand-même des propriétés similaires que celui dans l'espace $\mathbb{R}^d$. C'est l'espace polonais.

-

Définition : (Espace polonais)

Un espace $(E,d)$ polonais est un espace métrique, séparable et complet.

L'intérêt de cet espace est qu'il donne plus description sur la convergence en loi. En fait, la mesure comme un sous ensemble de fonctionnelle, c'est nature d'étudier la topologie sur cet espace $\mathcal{M}_1(E)$. En plus, le résultat suivant est vraiment important.

Proposition : (Topologie de $\mathcal{M}_1(E)$)
Soit $(E,d)$ un espace polonais,  alors on peut donner une distance sur $\mathcal{M}_1(E)$ tel qu'elle induit la même topologie étroite sur $\mathcal{M}_1(E)$. En plus, on peut réaliser que $\mathcal{M}_1(E)$ est un espace polonais sous cette distance.

C'est miracle. Une fois, on a une distance sur l'espace, les études sur $\mathcal{M}_1(E)$ est plus facile. La démonstration est assez intéressant. Grâce au théorème de Weierstrass-Stone, la fonction uniformément continuée est en fait séparable. Alors, on définit
$$
dist(\mu, \nu) = \sum_{n \geq  1}\frac{1}{2^n}|\mu(g_n) - \nu(g_n)| \wedge 1
$$
Cette distance réalise la même topologie et séparabilité. En revanche, la complétude, en fait, a rien à voir avec la topologie. Il y a des distances qui introduisent la même topologie mais avec différente complétude. La distance propre est plus compliquée qui s'appelle la distance de Lévy-Prokhorov.


Et puis, la convergence en lois de mesure est en effet un type de compacité sur $\mathcal{M}_1(E)$. La notation de tension et le théorème de Prokhorov seront utiles dans cette situation. Finalement, on rappelle le dernier résultat - la représentation de Shorokhod

Théorème de Shorokhod :
Soit $\mu_n \Rightarrow \mu$, alors il existe un espace $(\Omega,  \mathcal{F}, \mathbb{P})$ tel qu'il existe une suite de mesure $\nu_n$ ($\nu$)qui ont la même mesure que $\mu_n$($\mu$) mais $\nu_n \rightarrow  \nu$ p.s .

On sens vraiment, ce théorème va tricher dans quelques démonstrations.

Rappel de probabilité (1) : classe monotone et construction de mesure

Il y a toujours des techniques et des points subtiles dans la théorie de probabilité. Dans cet article, on collectionne des petites techniques utilisées suivantes dans la théorie de probabilité, la théorie de mesure et le processus stochastique.

Le premier article est consacré pour la construction de mesure et l'unicité grâce au théorème de classe monotone. En anglais, il s'appelle aussi le lemma de $\pi-$système et $\lambda-$système.

Définition (Classe monotone)
$\mathcal{M} \subset \mathcal{P}(E)$ est dit une classe monotone si et seulement s'il satisfait les propriétés suivantes :

1. $E \subset \mathcal{M}$
2. Soit $A,B \in \mathcal{M}, A \subset B$, alors $B \backslash A \in \mathcal{M}$
3. Soit $A_n \subset A_{n+1} \cdots, A_n \in \mathcal{M}$, alors $\bigcup_n A_n \in \mathcal{M}$ 

Lemma (Classe monotone)
Soit $\mathcal{C} \subset \mathcal{P}(E)$ et $\mathcal{C}$ est stable sous intersections finies, alors $\mathcal{M}(\mathcal{C}) = \sigma(\mathcal{C})$.
PF: On juste liste les idées clés dans la démonstration.

1. Il suffit de montrer que $\mathcal{M}(\mathcal{C})$ est aussi stable sous intersections finies.
2. On définit $\mathcal{M}_1(\mathcal{C}) = \{B \in \mathcal{M}(\mathcal{C}) | A \cap B \in \mathcal{M}(\mathcal{C})\}$  pour $A \in  \mathcal{C}$ et vérifie que $\mathcal{M}_1(\mathcal{C})$ est aussi une class monotone. Vu que $\mathcal{M}_1(\mathcal{C}) \subset \mathcal{M}(\mathcal{C})$, on obtient $\mathcal{M}_1(\mathcal{C}) = \mathcal{M}(\mathcal{C})$.
3. On adapte la même stratégie pour $A \in \mathcal{M}(\mathcal{C})$ et montre que $\mathcal{M}(\mathcal{C})$ est stable sous intersections finies et on conclut. 

Théorème (Unicité de mesure)
Soient $\mu, \nu$ deux mesure sur $(E, \mathcal{A})$ et $\mathcal{C} \subset \mathcal{A}$ stable sous intersections finies et $\sigma(\mathcal{C}) = \mathcal{A}$. Si deux mesures coincident sur $\mathcal{C}$, une condition suivante assure que les deux sont identiques sur $\mathcal{A}$.

1. $\mu(E) = \nu(E) < \infty$
2. $\exists E_n \in \mathcal{C}, E_n \in E_{n+1}, E = \bigcup_n E_n, \mu(E_n) = \nu(E_n) < \infty$

PF: La grande ligne est de montrer que l'ensemble $$\mathcal{G} = \{A \in \mathcal{A} | \mu(A) = \nu(A)\}$$
est une classe monotone, qui implique que l'unicité peut s'extender sur $\mathcal{A}$.   La première condition est en fait suffisant pour une mesure de probabilité et le deuxième généralise ce théorème dans le cas mesure infinie approximation d'une suite de mesure finie définie comme $$\mu_n(\cdot) = \mu(\cdot \cap E_n)$$

SLE (2) : Property of locality

One of the interest to study $SLE_{\kappa}$ is that it simulates the critical behaviors of a lot of random models such as self-avoiding random walk, the interface of Ising and uniform spanning tree. Here, we give an example of the locality property of $SLE_{6}$ and its connection of Ising model in critical case.

Site Ising model

We first introduce the Ising model. This is so called site Ising model that each site has $\frac{1}{2}$ probability to be black or white. We suppose that the negative axis is black and the positive axis is white and a process starts from $0$ who only expolres the  interface of the two. It has two properties:

1. Conformal invariance. It is believed that after an conformal mapping, the process follow the same property.
2. Domain Markov property. When the diameter of lattice goes to $0$, the process should be independent to the one already explored since the trace is determined locally.

One has a third property called locality : that a process in domain has the same law before it goes out of the domain, since also the trace is determined locally.

The conformal invariance and domain Markov implies that its scaling limit should be a $SLE_{\kappa}$.

$SLE_6$ and locality

But why this $SLE_{\kappa}$ should be $SLE_{6}$?

That is required by the property of locality. Generally, we can define the conformal  image of $SLE_{\kappa}$ in domain $D$,  but it doesn't follow the same law as a random process. For example, we define a mapping $$ \phi : D \rightarrow \mathbb{H} $$, then the equation becomes $$\partial_t \tilde{g}_t (z) = \frac{\partial_t hcap}{\partial_t \tilde{g}_t (z) - \tilde{U}_t}$$

Here $\tilde{U}_t$ is not necessarily a standard Brownian motion and $\kappa = 6$ is the case to make it as a real one.

We skip the technique calculus but just talks about its sense. It means that before going out of the boundary, the image $\phi(K_t)$ follows also a $SLE_6$ process. This one implies the property of locality. 

Cardy formula

The most interesting story about the $SLE_6$ is its behavior one equilateral triangle. We first calculate one probability of $SLE_6$ on $\mathbb{H}$ : $\mathbb{P}(\tau_{-y} < \tau_{1}) = F(\frac{y}{1+y}) $ where $$F(z) = c^{-1}\int_0^z \frac{1}{u^{\frac{2}{3}} (1-u)^{\frac{2}{3}}} du$$

which coincides with  the Schwartz-Christoffel formula in complex analysis and satisfies $$F(1+y) = 1 + e^{2\pi i / 3} F(\frac{y}{1+y})$$ which  sends $0, 1, \infty$ to $0, 1, e^{\pi i /3}$ respectively.

We construct an other conformal mapping $\Phi : \mathbb{H} \rightarrow \triangle$ which sends $0, 1, -y$ to $0, 1, e^{\pi i /3}$ respectively. We  can show in this case, $\Phi(\infty) = F(1+y)$. So we get the property that $$\mathbb{P}(\tau_{-y} < \tau_{1}) = \frac{|\Phi(\infty) \Phi(1)|}{|\Phi(-y) \Phi(1)|}$$ 

Using the locality of $SLE_{6}$, this interprets that a $SLE_{6}$ from $0$ to $\Phi(\infty)$ in $\triangle$, the first time to hit each side just has the probability of the length. A similar argument shows that the same process from $0$ to $1$ has the  uniform distribution for the first hit. 

More generally, two $SLE_{6}$ in the same triangle, one from $0$ to $1$ and another from $0$ to $e^{\pi i/3}$, share the same law before until the first hit one the opposite side. 

Hard sphere model (1) : Introduction

The hard sphere model starts from the very basic assumption of classical mechanics and attempts to prove the convergence from microscopic model to macroscopic model.

Notation and basic assumption

We starts from $N$ particles following the rules of classical mechanics and each one can be designed $z_i = (x_i, v_i) \in \mathbb{T}^d \times \mathbb{R}^d, i = 1, 2, 3, \cdots N$. After one collision, the change of speed is expressed as
$$
\begin{eqnarray*}
v' &=& v - ((v - v_1)  \cdot r) r \\
v'_1 &=& v_1 - ((v_1 - v) \cdot  r) r
\end{eqnarray*}
$$

The mechanics can be reversed once we change the direction of time and speed, in another word, this system is reversible. To avoid the  abuse of notation, we always define the evolution of system in a suitable subset of all configuration like
$$
D^N_{\epsilon} = \{(z_1, z_2, \cdots z_N), \forall i \neq j, |x_i - x_j| < \epsilon \}
$$
We define the density of the configuration in a produit probability space on $\mathbb{T}^d \times \mathbb{R}^d$. Some analysis can deduce that : We can define all the configuration on the probability space except a null set.

M_{\beta}^{\otimes N}(V_N)

Boltzmann-Grad scaling and Boltzmann equation

For a single particle, its density has an invariant law following the Liouville equation $$ \partial_t f(t,x) + v \cdot \partial_x f(t,x) = 0 $$ 

We generalize this equation to $N$ hard sphere model, then the Liouville equation is 

$$ \partial_t f_N(t,Z_N) + \sum_{i = 1}^N v_i \cdot \partial_{x_i} f_N(t,Z_N) = 0 $$ 

Since we would like to study the particle chaotic phenomena, a nature idea is to calculate its invariant measure - we know the limit measure is always the invariant measure. In this case, the invariant measure is called Boltzmann measure which is 

$$M_{N, \beta} = \frac{1}{\mathcal{Z}_N} \mathbb{1}_{D^{N}_{\epsilon}}(Z_N) M_{\beta}^{\otimes N}(V_N)$$ 

this one is not exactly a Maxwell-Boltzmann distribution in cause of the exclusion condition. But some detailed analysis tells us that we can do "almost" factorization of the measure to the product of the probability.  

$$|(M_{N, \beta}^{(s)} - M_{\beta}^{\otimes s}) \mathbb{1}_{D^s_{\epsilon}}| \leq C^s \rho M_{\beta}^{\otimes s}$$

In the further blog, we will study the convergence in different context precisely. We will show that, the distribution is very near to the distribution of the solution of linear Boltzmann equation $\partial_t f + v \cdot \nabla_x f = \alpha Q(f,f)$.

Entropy paradox

Entropy introduced by Shannon and Boltzmann is a genius idea to describe the disorder degree as $H(t) = \int_{D^N_{\epsilon}}  - f_N(t, Z_N) \log{f(t,Z_N)} dZ_N$. According to this definition, the entropy of the solution of hard sphere model is constant, but that of the solution of Boltzmann equation will increase. 

In our course, we list two models to explain this paradox. The two baby model like Kac ring model and Ehrenfest model are all reversible, so they have a period or Poincare recurrence result. However, the time to appear the chaos is faster than the period. That is also the case in hard sphere model : we will see the recurrence perhaps, but it takes long long long time and during this time, the chaos repeat again and again. So how do you regard it? A deterministic system or a random system? You got the answer.

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.