Tag Archives: subcritical

Lecture 3 – Couplings, comparing distributions

Posted on by
2

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 p=\frac{\lambda}{n}. The goal for today was to give a self-contained proof of the result that in the subcritical setting \lambda<1, there is no giant component, that is, a component supported on a positive proportion of the vertices, with high probability as n\rightarrow\infty.

More formally, we showed that the proportion of vertices contained within the largest component of G(n,\frac{\lambda}{n}) vanishes in probability:

\frac{1}{n} \left| L_1\left(G\left(n,\frac{\lambda}{n}\right)\right) \right| \stackrel{\mathbb{P}}\longrightarrow 0.

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] outwards from v, at all times the number of ‘children’ of v which haven’t already been considered is ‘at most’ \mathrm{Bin}(n-1,\frac{\lambda}{n}). Since, for example, if we already know that eleven vertices, including the current one w are in C(v), then the distribution of the number of new vertices to be added to consideration because they are directly connected to w has conditional distribution \mathrm{Bin}(n-11,\frac{\lambda}{n}).

Firstly, we want to formalise the notion that this is ‘less than’ \mathrm{Bin}(n,\frac{\lambda}{n}), and also that, so long as we don’t replace 11 by a linear function of n, that \mathrm{Bin}(n-11,\frac{\lambda}{n})\stackrel{d}\approx \mathrm{Poisson}(\lambda).

Couplings to compare distributions

A coupling of two random variables (or distributions) X and Y is a realisation (\hat X,\hat Y) on the same probability space with correct marginals, that is

\hat X\stackrel{d}=X,\quad \hat Y\stackrel{d}=Y.

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 F_X, we always have the option to couple with a uniform U(0,1) random variable. That is, when U\sim U[0,1], we have (F_X^{-1}(U)\stackrel{d}= X, where the inverse of the distribution function is defined (in the non-obvious case of atoms) as

F_X^{-1}(u)=\inf\left\{ x\in\mathbb{R}\,:\, F(x)\ge u\right\}.

Note that when the value taken by U increases, so does the value taken by F_X^{-1}(U). This coupling can be used simultaneously on two random variables X and Y, as (F_X^{-1}(U),F_Y^{-1}(U)), to generate a coupling of X and Y.

The total variation distance between two probability measures is

d_{\mathrm{TV}}(\mu,\nu):= \sup_{A}|\mu(A)-\nu(A)|,

with supremum taken over all events in the joint support S of \mu,\nu. This is particularly clear in the case of discrete measures, as then

d_{\mathrm{TV}}(\mu,\nu)=\frac12 \sum_{x\in S} \left| \mu\left(\{x\}\right) - \nu\left(\{x\}\right) \right|.

(Think of the difference in heights between the bars, when you plot \mu,\nu simultaneously as a bar graph…)

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 \delta_0 and \delta_{1/n} are distance 1 apart (the maximum) for all values of n. Similarly, the uniform distribution on [0,1] and the uniform distribution on \{0,1/n,2/n,\ldots, n-1/n, 1\} are also distance 1 apart.

When there is more overlap, the following result is useful.

Proposition: Any coupling (\hat X,\hat Y) of X\sim \mu,\,Y\sim \nu satisfies \mathbb{P}(X=Y)\le 1-d_{\mathrm{TV}}(\mu,\nu), and there exists a coupling such that equality is achieved. Continue reading →

Branching Random Walk and Amenability

Posted on by
Reply

This post is about some of the things I learned in an interesting given by Elisabetta Candellero in Oxford last week, based on joint work with Matt Roberts. The paper on which this is based can be found here. The main thing I want to talk about are some properties of graphs which were mentioned near the beginning which I hadn’t heard about before.

Branching Random Walk (hereafter BRW) is a model to which much attention has been paid, because of its natural applications in a range of physical and genetic settings. As with many of the best models, the definition is pretty much in the title. We take the ingredients for a random walk on a graph, which is a graph, and a transition matrix P on that graph. For most of the time we will consider simple random walk, so the graph G exactly specifies P. This requires the additional condition that the graph G is locally finite. We will introduce a branching mechanism, so at discrete times {0,1,2,…} we will track both the number of particles, and their current locations. We start at time 0 with a single particle at some vertex. Then at each time-step, all the vertices present die, and each gives birth independently to some number of offspring according to a fixed probability distribution \mu. These offspring then perform one move according to transition matrix P. Note that if you want the system to carry the appearance of having no death, then taking the support of the offspring distribution to be {1,2,3,…} achieves precisely this. The properties we consider will not be very interesting unless G is infinite, so assume that from now on.

There are almost limitless ways we could think of to generalise these dynamics. The offspring distribution could be allowed to depend on the vertex the particle is occupying. The joint transition probabilities of the offspring at a vertex could be biased in favour or against the offspring moving to the same site next. The environment could be chosen in advance before the process starts, but random.

The classical question about BRW is that of recurrence and transience. The definition extends naturally from that of a Markov chain (which any non-branching random walk on a graph is). As in that setting, we say a BRW is recurrent if every vertex is almost surely visited infinitely often by particles of the graph.

Heuristically, we should observe that in some sense, it is quite difficult for simple random walk on an infinite graph to be recurrent. We have examples in \mathbb{Z},\mathbb{Z}^2, but these are about as ‘small’ as an infinite graph can be. An idea might be that if the number of sites some distance away from where we start grows rapidly as the distance grows, then there isn’t enough ‘pull’ back to visit the sites near where we start infinitely often. Extending this argument, it is easier for a BRW to be recurrent, as we have the option to make the branching rate large, which means that there are lots of particles at large times, hence more possibility for visiting everywhere. Note that if the offspring distribution is subcritical, we don’t stand a chance of having interesting properties. If we ignore the random walk part, we just have a subcritical Galton-Watson process, which dies out almost surely.

We need a measure of the concept discussed in the heuristic for how fast the number of vertices in the graph grows as we consider bands of vertices further and further away from the starting vertex. The standard measure for this is the spectral radius, which is defined not in terms of number of vertices, but through the limiting probability of returning to a fixed vertex at large time n. Precisely

\rho:= \limsup \mathbb{P}_i(X_n=i)^{1/n},

so in some approximation sense

\mathbb{P}_i(X_n=i)\sim \rho^{n},

which explains why \rho\le 1. Note that by considering the sum of such terms, if simple random walk on G is recurrent, then \rho=1, but the converse does not hold. (Consider SRW on \mathbb{Z}^3 for example.)

It’s also worth remarking that \rho is a class property. In particular, for a connected graph, the value of \rho is independent of i. This is not surprising, as if d is the graph distance between vertices i and j, then

p_{ii}^{(n)}\ge p_{ij}^{(d)}p_{jj}^{(n-2d)}p_{ji}^{(d)},

and vice versa, which enables us to sandwich usefully for the limits.

Really, \rho is a function of the transition matrix P. In fact, we can be more specific, by considering diagonalising P. The only case we care about is when P is infinite, so this is not especially nice, but it makes it clear why p_{ii}^{(n)} decays like |\rho|^n where \rho is the largest eigenvalue of P. Indeed this is an alternative definition of the spectral radius. Note that Perron-Frobenius theory (which seems to keep coming up on the blog this week…) says that since |\rho|\le 1, then if |\rho|=1, we must have \rho=1. So the spectral radius being 1 is precisely equivalent to having an invariant measure. We don’t know whether we can normalise it, but P-F guarantees the relevant left-eigenvector is non-negative, and hence a measure.

Next we give this situation a name. Say that a random walk is amenable if \rho(P)=1. We can extend this property to say that a graph is amenable if SRW on it is amenable.

This is not the standard definition of amenability. This property is originally defined (by von Neumann) in the context of groups. A group G is said to be amenable if there exists a left-invariant probability measure on G, ie \mu such that

\forall A\subset G, \forall g\in G, \mu(gA)=A.

The uniform distribution shows that any finite group is amenable.

It turns out that in general there are several conditions for a group which are equivalent to amenability. One is that, given G finitely generated by B, the Cayley graph for G with edges given by elements of B does not satisfy a strong isoperimetric inequality. Such an inequality is an alternative way of saying that the graph grows rapidly. It says that the size of the boundary of a subset of the vertices is uniformly large relative to the size of the set. Precisely, there exists a constant c>0 such that whenever U is a finite subset of the vertices, we have |\partial U|\ge c|U|. (Note that finiteness of U is important – we would not expect results like this to hold for very large subsets.)

Kesten proved that it is further equivalent to the statement that simple random walk on Cay(G,B) is amenable in our original sense. This technical and important result links the two definitions.

We finish by declaring the main classical result in BRW, which is a precise condition for transience. As motivated earlier, the rate of branching and the spectral radius have opposing effects on whether the system is recurrent or transient. Note that at some large time, the expected number of particles which have returned to the starting vertex is given by the expected number of particles in the system multiplied by the probability that any one of them is back at its origin, ie \sim \mu^n\rho^n. So the probability that there is a particle back at the origin at this time is (crudely transferring from expectation to probability) 1\wedge (\mu \rho)^n. We can conclude that the chain is recurrent if \mu > \rho^{-1} and transient if \mu<\rho^{-1}. This result is due to Benjamini and Peres.

The remaining case, when \mu=\rho^{-1} is called, unsurprisingly, critical BRW. It was proved in ’06 by Gantert and Muller that, in fact, all critical BRWs are transient too. This must exclude the amenable case, as we could think of SRW on \mathbb{Z} as a critical BRW by taking the branching distribution to be identically one, as the spectral radius is also 1.

In the end, the material in this post is rather preliminary to the work presented in EC’s talk, which concerned the trace of BRW, and whether there are infinitely many essentially different paths to infinity taken by the particles of the BRW. They show that this holds in a broad class of graphs with symmetric properties.

Related articles
Enhanced by Zemanta

Long Paths and Expanders

Posted on by
Reply

I’m in Birmingham this week for the LMS-EPSRC summer school on Random Graphs, Geometry and Asymptotic Structure. The event consists of three five-hour mini-courses, a plenary lecture, leaving plenty of time for problem sheet and discussion. I thought it would be worth trying to say a couple of interesting things each day – I do not know whether this will succeed, but I might as well try.

Today, a few thoughts on the first two lectures of Michael Krivelevich’s course on Long Paths and Hamiltonicity in Random Graphs. The aim is to develop tools to investigate the threshold for the presence of a Hamiltonian cycle in G(n,p). In this first part of the course, we were mainly thinking about long paths.

One tool we used a lot was the Depth-First Search algorithm. This is very similar to the exploration process I’ve talked about before. Essentially, here we consider trying to explore the graph in a depth-first way, but instead of viewing all the edges incident to a vertex we have just arrived at, we only look to see whether there is an edge out of the new vertex. If there is, we explore it, then come back eventually to look for more. It really comes down to a difference in the information we are storing. In this DFS, we store the vertices which we haven’t finished exploring, which is the set of vertices on the explored path between the root and the current vertex. So the size of this set evolves like the contour process. In particular, we can read off the sizes of paths from this description. These dynamics are useful in particular because we know there are no edges between the set of vertices we have finished exploring, and the ones we have yet to explore. The stack of ‘processing’ vertices must glue everything else together.

We can translate one of the arguments back into the language for the old exploration process. Recall the increments of the exploration process are \mathrm{Bin}(\alpha n,\frac{c}{n}) -1 once we have explored \alpha n vertices. We don’t need to worry about the -1 bit for now. Observe that because we are exploring in a depth-first way, if a subsequence of the Binomial variables of length k are all positive, this corresponds to a path of length (k-1).

So to prove, for example, that the longest path in a subcritical random graph is O(log n), it suffices to prove that there are O(log n) consecutive positive entries in the sequence of n binomial entries. Since the distribution changes continuously, it is convenient to prove that there are O(log n) consecutive positive entries in the first \epsilon n binomial entries. The probability that any of these entries is positive is bounded below by some p, so it suffices to consider instead a sequence of Bernoulli RVs with parameter p. So if we never have clog n consecutive, this gives control of the sequence of geometric random variables corresponding to the gaps between 0s in the sequence. Precisely, these are Geom(q), and we must have \frac{\epsilon n}{c\log n} of them independently being less than clog n. We have to chase a few constants, and use the fact that if f(n)\rightarrow\infty, \frac{g(n)}{f(n)}\rightarrow\infty, then

(1-\frac{1}{f(n)})^{g(n)}\rightarrow 0,

by comparison with the standard asymptotic result for $e^{-x}$. In any case, we get that this probability tends to 0 if we choose c small enough, and so with high probability there is a path of length clog n.

This is interesting, because we knew already that the largest component in a subcritical random graph had size O(log n). But we also knew that all the components were trees, or ‘almost trees’, and were uniformly chosen from the set of trees (or trees + an edge or two) with appropriate size. And the largest path in a UST on n vertices is O(n^{1/2}) with high probability. So we learn that there are enough components of size \geq c\log n that it is actually very probable that one of them will have the unlikely property of being much more path-like than a typical tree.

Krivelevich also showed a pleasant elementary proof of the result that a supercritical random graph has a path of length O(n), using a similar idea.

The other definition of major interest was an expander graph. Often when doing calculations about neighbourhoods of sets of vertices, we run into the problem that the neighbourhoods may overlap, and so we cannot get the total outer neighbourhood (or outer boundary) just by summing over the individual neighbourhood sizes. In an expander graph, we demand that all small sets of vertices have neighbourhood at least as large as some constant multiple of the set size, essentially giving us a bound on the above problem. Concretely, G is a (k,\alpha)-expander is for any set of vertices |U|\leq k, |N(U)|\geq \alpha |U|.

There’s a very nice argument using Posa’s lemma, where we consider all the possible ways to rearrange the vertices in some longest path into a different longest path, and then focus on the endpoints of all these paths. With this so-called rotation-extension technique, we can show that a (k,2)-expander has a path of length at least 3k-1.

There are structural similarities between expander graphs and regular graphs, so it seems natural that there will be some interesting spectral properties. I don’t know much about this, but perhaps it will come up later in the week. But, returning to the random graph long path problem, it now suffices to show subcritical G(n,p) is a (clog n,2)-expander for some c. Expander properties are in some sense the opposite of clustering properties, and independence of a RG inhibit most clustering properties (as discussed in much greater detail in some of the posts about network models). Unfortunately, this doesn’t actually work, as in a subcritical graph, the typical expansion coefficient, even of a small set will be c, for G(n,c/n), which is not large enough. However, if you chose the constants carefully, such an argument should work for c>2, so long as you chose k=an, with a small enough that the probability of a vertex elsewhere in the graph being joined to (at least) two of the k vertices in the set, was small compared with (c-2).

REFERENCES

The course notes are not available, though chapter 3 from these 2010 notes by the same lecturer are related and interesting.

Related articles