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$.

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.

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.