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.
In this third lecture, we made our first foray into the scaling regime for G(n,p) which will be the main focus of the course, namely the sparse regime when 
More formally, we showed that the proportion of vertices contained within the largest component of 
The argument for this result involves an exploration process of a component of the graph. This notion will be developed more formally in future lectures, aiming for good approximation rather than bounding arguments.
But for now, the key observation is that when we ‘explore’ the component of a uniformly chosen vertex ![v\in[n]](https://s0.wp.com/latex.php?latex=v%5Cin%5Bn%5D&bg=ffffff&fg=333333&s=0&c=20201002)
Firstly, we want to formalise the notion that this is ‘less than’ 
Couplings to compare distributions
A coupling of two random variables (or distributions) X and Y is a realisation 
We saw earlier in the course that we could couple G(n,p) and G(n,q) by simulating both from the same family of uniform random variables, and it’s helpful to think of this in general: ‘constructing the distributions from the same source of randomness’.
Couplings are a useful notion to digest at this point, as they embody a general trend in discrete probability theory. Wherever possible, we try to do as we can with the random objects, before starting any calculations. Think about the connectivity property of G(n,p) as discussed in the previous lecture. This can be expressed directly as a function of p in terms of a large sum, but showing it is an increasing function of p is essentially impossible by computation, whereas this is very straightforward using the coupling.
We will now review how to use couplings to compare distributions.
For a real-valued random variable X, with distribution function 
![U\sim U[0,1]](https://s0.wp.com/latex.php?latex=U%5Csim+U%5B0%2C1%5D&bg=ffffff&fg=333333&s=0&c=20201002)
Note that when the value taken by U increases, so does the value taken by 
The total variation distance between two probability measures is
with supremum taken over all events in the joint support S of 
(Think of the difference in heights between the bars, when you plot
The total variation distances records how well we can couple two distributions, if we want them to be equal as often as possible. It is therefore a bad measure of distributions with different support. For example, the distributions 
When there is more overlap, the following result is useful.
Proposition: Any coupling 
is separable for each d, and the Stone-Weierstrass theorem shows that continuous functions with on a bounded interval are also separable with the uniform topology, as they can be approximated uniformly well by polynomials with rational coefficients. One heuristic is that a separable space does not have ‘too many’ open sets.
whenever 
. Note that it is very hard to have even deterministic convergence in this space, since the only way to be close to a element of the space is indeed to be equal to that element. We will construct random variables and it will unsurprising that they cannot possibly converge almost surely in any coupling, but the exact nature of the construction will lead to convergence in distribution.
to be an IID sequence of non-negative RVs defined on the probability space 
, with expectation under Lebesgue measure equal to 1. It is not obvious how to do this, with the restriction on the probability space. One example might be to write 
as 
, the binary expansion, and then set 
. We will later require that 
is not identically 1, which certainly holds in this example just given.
be the extension of Lebesgue measure to the power set 
. Now define the measures:
, the class of sets distinguishable by the outcomes of the first k RVs.
, 
. By MCT, we can extend this convergence to any bounded 
-measurable function.
for all 
, but we only have it so far for 
. But since 
, which is the base field of the probability space under the (non-AC) assumption, we can take conditional expectations. In particular for any ![\mathbb{E}_\mu[\mathbf{1}_B | \mathcal{F}]](https://s0.wp.com/latex.php?latex=%5Cmathbb%7BE%7D_%5Cmu%5B%5Cmathbf%7B1%7D_B+%7C+%5Cmathcal%7BF%7D%5D&bg=ffffff&fg=333333&s=0&c=20201002)
is a bounded, 
and the extended MCT result:![\mu_n(B)=\mathbb{E}_\mu[X_n\mathbb{E}_\mu[\mathbf{1}_B|\mathcal F]]=\mathbf{E}_{\mu_n}[\mathbb{E}_\mu[\mathbf{1}_B|\mathcal F]] \rightarrow \mathbb{E}_\mu [\mathbb{E}_\mu[\mathbf{1}_B |\mathcal{F}]].](https://s0.wp.com/latex.php?latex=%5Cmu_n%28B%29%3D%5Cmathbb%7BE%7D_%5Cmu%5BX_n%5Cmathbb%7BE%7D_%5Cmu%5B%5Cmathbf%7B1%7D_B%7C%5Cmathcal+F%5D%5D%3D%5Cmathbf%7BE%7D_%7B%5Cmu_n%7D%5B%5Cmathbb%7BE%7D_%5Cmu%5B%5Cmathbf%7B1%7D_B%7C%5Cmathcal+F%5D%5D+%5Crightarrow+%5Cmathbb%7BE%7D_%5Cmu+%5B%5Cmathbb%7BE%7D_%5Cmu%5B%5Cmathbf%7B1%7D_B+%7C%5Cmathcal%7BF%7D%5D%5D.&bg=ffffff&fg=333333&s=0&c=20201002)
is 
-measurable, applying the tower law gives that this is equal to 
. So we have
(*)
. At first glance it might look like we have proved a much stronger condition than we need. But recall that in any set equipped with the discrete topology, any set is both open and closed, and so to use the portmanteau lemma, (*) really is required.
satisfying 
. But citing the example I gave of 
are 0 and 2, and irrespective of the coupling,
. For example, take U uniform on [0,1], and 
.)
, where P is a distribution with separable support. Then we can define a probability space 
and random variables 
on this space such that the laws of 
are 
respectively and 
for all 
.
. Then
from a realisation of X. We take X, and a partition of the support of X into small measurable sets, chosen so that the probability of lying in a particular set is almost the same for 
, there must be some radius 
such that 
. This is where we use separability. Since every point in the space is within 
of some element of a countable sequence of elements of the space, we can take a countable subset of these open balls 
which cover the space. Furthermore, we can take a finite subset of the balls which cover all of the space apart from a set of measure at most 
. We want the sets to be disjoint, and we can achieve this by removing the intersections inductively in the obvious way. We end up with a collection 
, where 
is the leftover space, such that
.
, for which 
. Unsurprisingly, this scaling of 
such that for 
, we have
(*)
, for each 
with non-zero probability under P, take 
to be independent random variables with law 
equal to the restriction onto the set. Now take ![\xi\sim U[0,1]](https://s0.wp.com/latex.php?latex=%5Cxi%5Csim+U%5B0%2C1%5D&bg=ffffff&fg=333333&s=0&c=20201002)
independent of everything so far. Now we make concrete the heuristic for constructing 
yet. But, from (*), there is a unique distribution such that taking 
. Note that by iteratively defining random variables which are independent of everything previously defined, our resulting probability space 
will be a large product space.
controls whether the 
. So define 
. Then, 
, and so by Borel-Cantelli, with probability 1, 
holds for all m larger than some threshold. Let us call this 
, and on this event E, we have by definition 
. So we have almost sure convergence. But we can easily convert this to sure convergence by removing all 
and setting 
on 
, as this does not affect the distributions.
.
to see the fluctuations on a finite positive scale.
denotes an induced subgraph. Then it is relatively clear what the limit should be, as it is well-defined to take a union. This won’t work directly for a limit of random graphs, because the above relation in probability doesn’t even really make sense if we have a different probability space for each finite graph. This is a general clue that we should be looking to use convergence in distribution rather than anything stronger.
consists of a single vertex v. If the limit graph (remember this is just the union, since that is well-defined) has bounded degrees, then there is some N such that 
contains all the information we might want about the limiting neighbourhood of vertex v. For some larger N, 
is the random rooted infinite graph (G, p) if the neighbourhoods of 
around a randomly chosen vertex converge in distribution to the neighbourhoods of G around p. Formally, say ![(G_n)[U_n]\stackrel{d}{\rightarrow} (G,p)](https://s0.wp.com/latex.php?latex=%28G_n%29%5BU_n%5D%5Cstackrel%7Bd%7D%7B%5Crightarrow%7D+%28G%2Cp%29&bg=ffffff&fg=333333&s=0&c=20201002)
if for all r>0, for any finite rooted graph (H,w), the probability that (H,w) is isomorphic to the ball of radius r in 
branching process, this is exactly the limit sense we mean. The approximation fails if we fix n and take the neighbourhood size very large (eg radius n), but for finite neighbourhoods, or any radius growing more slowly than n, the approximation is good.
vertices). If we fix the root, then the limit is the infinite-level binary tree, though this isn’t especially surprising or interesting.
vertices are leaves, not counting the base of the tree, and 
are distance 1 from a leaf, and 
are distance 2 from a leaf and so on.
will be function of n, a parameter which will tend to infinity. So we do not want to be too rooted in the actual set 
. You want to make the most money, assuming that your opinion of the distribution is correct (which in your opinion, of course it is!). So assuming the bookmaker will accept an arbitrarily complicated (but finite obviously, since there are only 
.
, and so we might as well go with the original intuition of![||\mu-\nu||_{TV}=\max_{A\subset\Omega} \left[\mu(A)-\nu(A)\right].](https://s0.wp.com/latex.php?latex=%7C%7C%5Cmu-%5Cnu%7C%7C_%7BTV%7D%3D%5Cmax_%7BA%5Csubset%5COmega%7D+%5Cleft%5B%5Cmu%28A%29-%5Cnu%28A%29%5Cright%5D.&bg=ffffff&fg=333333&s=0&c=20201002)
, and similarly for 
of 
, we are interested in 
. The problem is that doing everything in terms of some general 
is some signed measure on 
is a norm on this space. In fact, it is (equivalent to – dividing by 1/2 makes no difference!) the product norm of the 
, are precisely the delta-measures at some point of the state space 
. So in fact, we can replace our definition of d(t) by:
is the same as 
. Furthermore, we can immediately apply this idea to get a second result for free. In some problems, particularly those with neat couplings across all initial distributions, it is easier to work with a larger class of transition probabilities, rather than the actual equilibrium distribution, so we define:
immediately. But we want to show 
, and we can do that as before, by considering
, and so it attains its maximum at a boundary point, which must be 
. Hence 
is equal to the displayed expression above, which is certainly greater than or equal to the original formulation of d(t), as this is the maximum of the same expression over a strict subset.
and 
if:
for all bounded Lipschitz functions f.
for all closed sets F. Note that we demanded that all the measures be Borel, so there is no danger of 
not being defined.
for all open sets G.
whenever 
. Such an A is called a continuity set.
that contains the ones we use will be sufficient to determine weak convergence.
where 
in some non-trivial way. Then there is some open set eg X\{x} such that 
but 
. Informally, we might say that in the limit, some positive mass could ‘leak out’ into the boundary of an open set.
. Then find a Lipschitz function f which is 0 outside F’ and 1 on F. We obtain
. If we assume c) and d) and apply them to 
, then e) follows.
have positive mass under each of 
. So given 
, we can choose a sequence
such that 
,
for all k,n. Now it is clear what to do. ![\{f\in[a_k,a_{k+1}]\}](https://s0.wp.com/latex.php?latex=%5C%7Bf%5Cin%5Ba_k%2Ca_%7Bk%2B1%7D%5D%5C%7D&bg=ffffff&fg=333333&s=0&c=20201002)
is a continuity set, so we can apply e), then patch everything together. There are slightly too many Ms and 
. With high probability (that is, with probability tending to 1 as n grows), we have a so-called giant component, with O(n) vertices.
. The number of neighbours of each of these which we haven’t already considered is then 
, conditional on k, the number of vertices we have already discounted. After any finite number of steps, k=o(n), and so it is fairly reasonable to approximate this just by 
. Furthermore, as n grows, this distribution converges to 
(that is, the probability that it is infinite) of a branching process with 
, because we require 
for the survival probability to be non-zero. Obviously, all of this needs to be made precise and rigorous, and this is treated in sections 4.3 and 4.4 of the notes.
is number of vertices we have explored or seen, ie are connected to a vertex we have explored. Suppose the remaining vertices are called unseen, and we began the exploration at vertex 1. Then any vertex with label in {2,…,n} is unseen if it successively avoids being in the neighbourhood of v(1), v(2), … v(t). This happens with probability 
, and so the probability of being an explored or seen vertex is the complement of this.
.
.
. We have:
. In fact we also have a central limit theorem for S_t, which enables us to deduce that 
with high probability, as well as in expectation, which is precisely what is required to prove that the giant component of 
.
after a natural rescaling is distributed as N(0,1). As a starting point for investigating similar results for a more general class of underlying distributions, it is worth considering what properties we might require of a distribution if it is to appear as a limit in distribution of sums of IID RVs, rescaled if necessary.
, with the initial sums 
. Then we say 
is stable in the broad sense if
for every n. If in fact 
then we say 
exists and is 0, then so are all the 
s.
for some 
.
(independent copies naturally!). The behaviour of 
is also preserved. Now we can work with an underlying distribution that is symmetric about 0, rather than merely centred. The deduction that 
, and express
(*)
in the above, and using that X is symmetric, we can obtain an upper bound
if we take 
large enough. But since
), this implies that 
cannot be very close to 0. In other words, 
is bounded above. This is in fact regularity enough to deduce that 
. Note that this equality case 
corresponds exactly to the 
, we will show that the variance of X is finite, so CLT applies. This gives some control over 
s is 
and that the sum of the rest is non-negative. This has, by independence, exactly half the probability of the event demanding just that the maximum be bounded below, and furthermore is contained within the event with probability 
shown above. So if we set
![\frac14>\mathbb{P}(S_n>tc_n)\geq\frac12\mathbb{P}(\max X_i>tc_n)=\frac12[1-(1-\frac{z}{n})^n]](https://s0.wp.com/latex.php?latex=%5Cfrac14%3E%5Cmathbb%7BP%7D%28S_n%3Etc_n%29%5Cgeq%5Cfrac12%5Cmathbb%7BP%7D%28%5Cmax+X_i%3Etc_n%29%3D%5Cfrac12%5B1-%281-%5Cfrac%7Bz%7D%7Bn%7D%29%5En%5D&bg=ffffff&fg=333333&s=0&c=20201002)
is bounded as 
varies. Rescaling suitably, this gives that
is not hugely important, as a broadly stable distribution is in the domain of attraction of the corresponding strictly stable distribution.
, where the 
is some function which almost certainly increases fairly fast with 
and consider the probabilities
(*)
. Of course, it is possible that this expectation does not exist, but that is certainly a question for another post!
. So object 
whatever that means, certainly cannot be a proper random variable, as if we were to have convergence in distribution, this would imply that the limit RV consisted of point mass at each of 
.
. For example, we might expect:
. This is what we mean by a large deviation event. Although we always have to define everything concretely in terms of some finite sum 
in some sense) for an enormous class of distributions, and in particular, most distributions that one might encounter in practice (ie finite mean, finite variance). There is even greater universality, as furthermore the limit distribution at this interface has the same form (some appropriate normal distribution) whenever 
. But of course, we also have a Strong Law of Large Numbers, which asserts that the empirical mean converges almost surely. What is the threshhold for almost sure convergence, because there is no a priori reason why it should be 
?
-a.s. if 
.
in 
-probability if 
for any 
.
if 
for any bounded, continuous function f. Note that this definition is valid for RVs defined on any metric space. When they are real-valued, this is equivalent to the condition that 
for every point 
where 
for all 
.
-convergence: 
; that is, 
.![\sup_{n,A\in\mathcal{F}}\{\mathbb{E}[|X_n|1(A)]|\mathbb{P}(A)\leq \delta\}\rightarrow 0](https://s0.wp.com/latex.php?latex=%5Csup_%7Bn%2CA%5Cin%5Cmathcal%7BF%7D%7D%5C%7B%5Cmathbb%7BE%7D%5B%7CX_n%7C1%28A%29%5D%7C%5Cmathbb%7BP%7D%28A%29%5Cleq+%5Cdelta%5C%7D%5Crightarrow+0&bg=ffffff&fg=333333&s=0&c=20201002)
as 
.
, then the collection is not UI.
Eventually Almost Everywhere 