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

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.

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 30/05/2017 : Courbure de Ricci sur graphe

Cette séminaire est très intéressante car elle réponds ma question sur comment définir une courbure sur un graphe, même si pour l'instant, la définition ne suffit pas de retrouver toutes les propriétés géométriques. Comme je travaille maintenant  sur la carte aléatoire et la gravité quantique, j'aimerais vraiment avancer encore une étape d'attaquer la partie géométrique. Pour la suite, je vais taper plusieurs propositions dans cette séminaire.(D'après Hervé Pajot)

Rappelle de géométrie Riemannienne 

Soit $M$ une variété muni de métrique $g$, on peut définir la distance de courbe $$L(r) = \int_0^1 \sqrt{g(\frac{\partial r}{\partial t}, \frac{\partial  r}{\partial t})}dt$$

et la volume $$ Vol(A) = \int_A \sqrt{det(g)} dx$$

En plus, on peut aussi définir la courbure de Ricci, qui reflet beaucoup de propriétés de cette variété. Par exemple, on sait que une variété avec la courbure de Ricci positive a une croissance de volume comme dans l'espace $\mathbb{R}^d$. Et surtout, borné en bas nous permet d'utiliser l'inégalité de Poincaré. Donc, on aimerait d'avoir une généralisation dans espace métrique.

Espace métrique

Différent que la variété Riemannienne, dans un espace métrique, la distance de courbe n'est pas bien défini à priori. C'est pour ça, on travaille dans un espace métrique, mesuré, de distance $(X, d, \mu)$. Une manière de construction est la courbure d’alexandra, qui est invariant sous la convergence de distance de Gromov-Haussdorff. D'ailleurs, la variété avec la courbure de Ricci positive  est pré-compacte dans l'espace $(K, d_{GH})$. 

Espace Wasserstein

Dans  la recherche de transport optimal,  on utilise souvent la distance de Wasserstein et l'espace de Wasserstein $(P(X), W_2)$. En fait, si l'espace $X$ est de distance, ainsi que l'espace de Wasserstein. Donc il existe géodésique entre deux distribution. Plus précisément, les élément dans  $(P(X), W_2)$ sont tous distribution de probabilité et une géodésique $\mu_t$ est la courbe plus courte de relier $\mu_0$ et $\mu_1$. Comme ça on sait comment trouver le transport optimal, c'est juste  trouver cette géodésique.

En utilisant cette idée, les mathématiciens définissent aussi une généralisation de courbure de Ricci qui s'appelle N-Ricci. Soit une une suite d'espace de courbure  positive, alors sa limite dans le sens de Gromov-Haussdorff est aussi de courbure positive. En plus, sur l'espace comme ça, on peut appliquer l'inégalité de Poincaré.

Généralisation sur graphe

Même si l'on a plusieurs manière de définir la courbure de Ricci sur un graphe, mais dans mon avis, ils ne retrouvent pas toutes les propriétés. Peut-être c'est aussi parce que l'objet étudié par probabiliste est plus concret et la description d'analyse ne suffit pas de tout dessiner.

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.

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

Random Graph : Erdos-Renyi Graph

OK, Finally I finish finding the way to add maths equation into the blog and this will be my first blog with the beautiful equations.

Recently, in the course of MAP554, we talk about different types of random graphs, a branch very active in maths and its applications since the appearance of the social network. In fact, there exists various types of random graphs to simulate different situations, we will start one by one and in this post we concentrate on Erdos-Renyi Graph

Definition of Erdos-Renyi graph

The definition of Erdos-Renyi graph is very simple. In graph $G(n, p)$, each edge between vertex $u,v$ has probability $p$ to appear, and for different edges, they are independent. This model simulates well the situation the propagation of virus in the society, or the diffusion of message in a small environment, where every one is same and no limit of distance.

We consider a concrete question: Now the ads is diffused, what's the probability that all the people are influenced? What's the possible size of the largest connected component?

The emergence of great connected component

We simulate the propagation of the information in the way like the random walk associated with Watson-Galton branching movement. Each step, we deactiver a vertex and add all the vertex non-explored who has connection with that one. If we note $A_k$ the number active and $D_k$ the number explored in the k-th time. That is
$$
A_k = A_{k-1} + D_{k} - 1
$$
where $D_k$ follows the distribution of $Bin(n - A_{k-1} - k + 1)$.

This description is the most important way and we will repeat that many and many times in the proof. The estimation about the size of Watson-Galton is very standard by the Chernoff inequality:
$$
\mathbb{P}(C > k) \leq \mathbb{P}(A_k > 0) = \mathbb{P}(D_1 + D_2 + \dots D_k > k)
\leq  e^{-\theta k } \mathbb{E}[e^{\theta(D_1 + D_2 + \dots D_k )}]
$$
Then, we use the technique to minimize the right term.

We declare directly the conclusion : In the case sub-critical, $np < 1$, the largest connected component is of the order $\log{n}$ with a large probability. In the case super-critical, $np > 1$, with large probability, the largest connected component is of the order $O(n)$, but the second one is of the order $\log{n}$.

The probability of a connected graph   

The conclusion: $\lim_{n \rightarrow \infty} np - \log{n} = c$, then the probability that the graph is connected is $e^{-e^{-c}}$.

The proof of this theorem uses the first and second moment method, the approximation of Poisson distribution (little number theorem). Something amazing is that in fact, this probability is very close to that of non isolated vertex in the graph. That is to say, when $n$ is big enough, we can consider the two equivalent.

Conclusion: The Erdos-Renyi graph is the simplest model of random graph, since there are no geometric structures, which makes it simple and accessible. When the probability is so small, there are high probability that the graph isn't connected and when it rises, the probability of connectivity climbs, the biggest connected component will also grow from the $\log{n}$ to $O(n)$. Moreover, in some more complicated model like Ising model or percolation, there are also the similar conclusion like sub-critical and super-critical.

Phase transition, the critical point, the asymptotic behavior, scaling limit and continuous model associated, the random walk on the random graph, the mixing time of the former...These will compose my future research. Exciting!

How the TCP works ?

In the course probabilistic algorithm, we talk about how the TCP works. In fact, what we do on the course is a reverse engineering, that is, we know the policy taken in our reality and then try to find the philosophy behind.

What the TCP does?

What TCP does is very simple. When we send the pocket on Internet, there are always limits for the bandwidth. The PC will increase the number sent if it receives a success signal in order to accelerate the speed, but divide by 2 to avoid the traffic problem if it receives a signal of failure.  Intuitively, this is a good strategy, but what it achieves?

A general model

Inspired by the model in economics, we apply the model of optimization. In this model, we aim at a function of utility and some limits. In our problem, the limit is clearly the physical limit: the sum of flux cannot be greater than the admissible one. But the goal function, in fact, can be very different. There are max-min, proportional function, alpha weight function. The TCP is just one specific case of alpha weighted function.

Technique part 1: primal algorithm

The next problem is that what can we do when facing a general optimization problem. We ca ignore the condition and just treat the relaxed question and apply the primal algorithm. The Lyapunov function and ODE theory assures that this method converges.

Technique part 2: Lagrange  multiplier and dual method

A second method which treat the problem directly is the theory of optimization. Maybe we know always the method of Lagrange multiplier method, it is correct and always correct given a good function. However, the most profound theory is Kuhn-Tucker theory and a dual problem. If we would like to minimiser the function, we can minimiser given the parameter, and then maximiser the parameter. This procedure always works if we find the Kuhn-Tucker vector, this is true when it has control from the lower bound. So this idea propose the dual algorithm for our question.

Greedy algorithm for viral marketing is good engough

The viral marketing is a very mathematical question. We assume that each client has some probabilities to distribute the information to other places, then we need to calculate the minimum number to ensure that all the network is infected after some time. We can just simplify the question such that we choose a community and then consider its neighborhood. Then a naive method is to find the vertex who will add the most number into the community. Is this method smart enough?

The answer is amazing, Yes! If we do like this, we can achieve a solution that infected the network at least constant times of the optimal solution.

In the following, we list the main steps in the proof. We denote F(A) the number of vertex connected. Then a key formula is 

F(A \union B) + F(A \intersection B) <= F(A) + F(B)

Then, in the stream of greedy algorithm C_i, the increment is not so bad. That is 

F(C_{i+1}) - F(C_i) >= 1\k * (F(C) - F(C_i))

If we change a little this formula, we will get 

F(C) - F(C_i) <= (1 - 1\k)^k * (F(C) - F(0))

So the greedy algorithm attends at least 1 - 1/e = 0.632 times the optimal solution, a result good enough in certain situation. 

OK, greedy algorithm is not always the best but not bad.