increasing random variable | Eventually Almost Everywhere

I am aiming to write a short post about each lecture in my ongoing course on Random Graphs. Details and logistics for the course can be found here.

The goal of the second lecture was to establish the sharp phase transition for the connectivity of the random graph G(n,p(n)) around the critical regime $p(n)\sim \frac{\log n}{n}$ . In the end, we showed that when $\omega(n)$ is any diverging sequence, and $p(n)=\frac{\log n-\omega(n)}{n}$ , then we have that G(n,p(n)) is with high probability not connected.

In the next lecture, we will finish the classification by studying $p(n)=\frac{\log n+\omega(n)}{n}$ , and show that for this range of p, the graph G(n,p(n)) is with high probability connected.

The details of the lecture, especially the calculation, are not presented fully here. There, I followed van der Hofstad’s recent book fairly closely, sometimes taking different approximations and routes through the algebra, though all versions remain fairly close to the original enumerations by Renyi.

Immediate remarks

One is allowed to be surprised that for almost all scalings of p(n), G(n,p) is either whp connected or whp not connected. The speed of the transition is definitely interesting.
As defined in lectures, the property that a graph is connected is an increasing property, meaning that it is preserved when you add additional edges to the graph.
Because of the natural coupling between G(n,p) and G(n,q), the fact that connectedness is an increasing property makes life easier. For example, we can insist temporarily that $\omega(n)\ll \log n$ , or whatever scaling turns out to be convenient for the proof, but conclude the result for all diverging $\omega(n)$ . This avoids the necessity for an annoying case distinction.

Heuristics – Isolated vertices

It turns out that the ‘easiest’ way for such a graph to be disconnected is for it to have an isolated vertex. In determining that the graph has a cut into classes of sizes a and b with no edges between them, there is a trade-off between the number of ways to choose the partition (which increases with min(a,b) ) and the probabilistic penalty from banning the ab edges between the classes (which decreases with min(a,b) ). It turns out that the latter effect is slightly stronger, and so (1,n-1) dominates.

Method 1: second-moment method

In the case $p(n)=\frac{\log n - \omega(n)}{n}$ , we use a second-moment method argument to establish that G(n,p) contains an isolated vertex with high probability. Note that a given vertex v is isolated precisely if n-1 edges are not present. Furthermore, two given vertices v,w are both isolated, precisely if 2n-3 edges are not present. So in fact, both the first moment and the second moment of the number of isolated vertices are straightforward to evaluate.

It turns out that the number of isolated vertices, $Y_n$ , satisfies

$\mathbb{E}[Y_n]= \exp(\omega(n)+o(1))\rightarrow\infty.$ (*)

As always, we have to eliminate the possibility that this divergent expectation is achieved by the graph typically having no isolated vertices, but occasionally having very many. So we turn to the second moment, and can show

$\mathrm{Var}(Y_n)= (1+o(1))\mathbb{E}[Y_n],$

and so by Chebyshev’s inequality, we have $\mathbb{P}(Y_n=0)\rightarrow 0$ .

Method 2: first-moment method

Counter-intuitively, although the case $p(n)=\frac{\log n + \omega(n)}{n}$ requires only a first-moment method, it is more technical because it involves the non-clear direction of the informal equivalence:

$\text{Connected}\; ``\iff ''\; \text{no isolated vertices}.$

At the time we showed (*), we also showed that for this regime of p(n), G(n,p) whp has no isolated vertices. It remains to show that it has no splits into (unions of) connected components of sizes k and n-k. Continue reading →

Back when we did GCSE probability, we gave a definition of independent events as:

A and B are said to be independent if $\mathbb{P}(A)\mathbb{P}(B)=\mathbb{P}(A\cap B)$ .

We might also apply Bayes’ definition of conditional probability to say

$\mathbb{P}(A|B)=\mathbb{P}(A)\quad\iff\quad A,B\text{ independent}\quad\iff\quad\mathbb{P}(B|A)=\mathbb{P}(B)$

provided all the terms exist. (Eg the definition of $\mathbb{P}(B|A)$ is at the very least non-obvious if the probability of A is 0.) In my opinion, this is a more naturally intuitive definition. For example, I think that when you toss two coins, the fact that the probability of the second coin being a tail is unaffected by whether the first is heads is more naturally ‘obvious’ than the fact that the joint probability of the two events is 1/4.

But, before getting too into anything philosophical, it is worth thinking about an equivalent situation for non-independent events. We remark that by an identical argument to above:

$\mathbb{P}(A|B)\geq\mathbb{P}(A)\quad\iff\quad \mathbb{P}(A\cap B)\geq\mathbb{P}(A)\mathbb{P}(B)\quad\iff\quad\mathbb{P}(B|A)\geq\mathbb{P}(B)$

Informally, this says that if we know A occurs, it increases the likelihood of B occuring. If we were talking about two random variables, we might say that they were positively correlated. But of course, by considering RVs $1_A,1_B$ , the result above is precisely the statement that the indicator functions have positive correlation.

Aim: To find a sufficient condition for positive correlation of random variables in a product measure.

Consider the following. Suppose A is an event which is positively correlated with the appearance of each edge. We might suspect that two such events A and B would be positively correlated. Instead, we consider a more concrete description. Recall that an event A is a subset of $\Omega=\{0,1\}^E$ . Given $w\in\Omega,e\in E$ , we say $w^e\in\Omega$ defined by taking w and setting edge e to be open (note it may be open already). Now, we say event A is increasing, if

$\forall w\in\Omega,\forall e\in E: w\in A\Rightarrow w^e\in A$ .

Note that this certainly implies the property previously mentioned, but the converse is not necessarily true.

Anyway, our revised aim will be to show that increasing events A and B are positively correlated for product measure.

For now, we approach the problem from the other direction, namely we attempt to find which measures on $\{0,1\}^E$ have the property that A and B are positively correlated for all increasing A, B. Note that as before, we can think of this as $\mathbb{E}1_A1_B\geq\mathbb{E}1_A\mathbb{E}1_B$ , and again here it is useful to rephrase our framework in terms of random variables. There is a natural (product) partial ordering of $\Omega=\{0,1\}^E$ , and from this there is an easy notion of increasing random variables. Recall a random variable is defined as a measurable map $\Omega\rightarrow\mathbb{R}$ so no further work is required.

X is increasing if $w\geq w'\Rightarrow X(w)\geq X(w')$ .

So we clarify our aim, which is to find a condition on the measure $\mu$ such that $\mu(XY)\geq \mu(X)\mu(Y)$ for all increasing X, Y. When this occurs, we say $\mu$ is positively associated. Note that this is equivalent to $\mu(A\cap B)\geq \mu(A)\mu(B)$ for all increasing events A, B. Why? We can build up X and Y from increasing indicator functions like $\{X\geq x\}$ in a usual monotone class argument.

On the way, we need a partial ordering on the set of probability measures. Obviously, if $\mu(A)\leq \nu(A)$ for all events A, then in fact $\mu=\nu$ ! So instead we say $\mu\leq_{st}\nu$ if $\mu(A)\leq \nu(A)$ for all increasing A. This is called the stochastic ordering, and there is a technical result of Strassen, proving the intuitively obvious claim that if $\mu_1\leq \mu_2$ , then we can couple the measures in a natural way. Formally:

Theorem: $\mu_1\leq\mu_2 \iff \exists$ a probability measure $\nu$ on $\Omega^2$ such that the marginals are $\mu_1,\mu_2$ and

$\nu(\{(w_1,w_2):w_1\leq w_2\})=1$ .

Our main result will be the FKG inequality which asserts that when $\mu$ satisfies the following FKG lattice property

$\mu(w_1\vee w_2)\mu(w_1\wedge w_2)\geq \mu(w_1)\mu(w_2),\quad\forall w_1,w_2\in\Omega$

then $\mu$ is positively associated. We will prove the case $|E|<\infty$ .

We proceed by showing that $\mu_1\leq\mu_2\propto Y\mu_1$ , rescaled, for Y an increasing RV. [Note that we are now suppressing the ‘st’ subscript, as context makes the use clear.]

To show this, we prove the more general Holley’s Theorem:

This states that if two positive probability measures satisfy a related lattice condition:

$\mu_2(w_1\vee w_2)\mu_1(w_1\wedge w_2)\geq \mu_1(w_1)\mu_2(w_2)\quad\forall w_1,w_2\in\Omega$

then we have the stochastic domination result: $\mu_1\leq \mu_2$ .

Note that the lattice condition states, very informally, that adding edges results in a greater relative increase with respect to the measure $\mu_2$ , which has a natural similarity to the definition of stochastic domination.

We prove this, perhaps unexpectedly, by resorting to a Markov chain. We note that there is a Markov chain on $\Omega$ with equilibrium distribution given by $\mu_1$ . This is simple: the non-zero transition rates are those given by the addition or removal of a single edge. Assume that edges are added at unit rate, and that edges are removed with rate: $G(w^e,w_e)=\frac{\mu_1(w_e)}{\mu_1(w^e)}$ .

Similarly, we can construct a Markov chain on state space $\Omega^2$ , where non-zero transitions are given by the addition of an edge to both states in the pair, the removal of an edge from both states in the pair, and the removal of an edge from only the first edge in the pair. Note that, as before, we may be ‘adding’ an edge which is already present. Assuming we start in this set, this choice means that we are restricting the sample space to $\{(\pi,w):\pi\leq w\}$ . We need the transition rate of the third type of transition to have the form: $\frac{\mu_1(\pi_e)}{\mu_1(\pi^e)}-\frac{\mu_2(w_e)}{\mu_2(w^e)}$ . So the lattice condition precisely confirms that this is non-negative, and thus we have a well-constructed Markov chain. The marginals have equilibrium distributions $\mu_1,\mu_2$ by construction, and by the general theory of Markov chains, there is an equilibrium distribution, and this leaves us in precisely the right position to apply Strassen to conclude the result.#

Summary of consequences: We have demonstrated that product measure is positively associated, as it certainly satisfies the FKG condition. Recall that this is what we had suspected intuitively for reasons given at the start of this account. Next time, I will talk about the most natural companion result, the BK inequality, and the stronger Reimer’s Inequality.

References: Both the motivation and the material is derived from Prof. Grimmett’s Part III course, Percolation and Related Topics, which was one of the mathematical highlights of the year. This account of the subject is a paraphrase of his lecture notes, which were themselves based on his book Probability on Graphs. Mistakes, naturally, are mine. Background on the course, and an online source of the book can be found on the course website here.

Eventually Almost Everywhere

A blog about probability and olympiads by Dominic Yeo

Tag Archives: increasing random variable

Lecture 2 – Connectivity threshold

Independence and Association