Lecture 4 – Hitting time theorem

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.

This lecture consisted of revision of the most relevant theory of Galton-Watson trees, with a focus on the case where the offspring distribution is Poisson, since, as we have seen in previous lectures, this is a strong candidate to approximate the structure of G(n,\lambda/n). It makes sense to cover the theory of the trees before attempting to make rigorous the sense of approximation.

Given a Galton-Watson tree T, it is natural to label the vertices in a breadth-first order as \varnothing=v_1,v_2,\ldots,v_{|T|}. This is easiest if we have constructed the Galton-Watson tree as a subset of the infinite Ulam-Harris tree, where vertices have labels like (3,5,17,4), whose parent is (3,5,17). If this child vertex is part of the tree, then so are (3,5,17,1), (3,5,17,2), and (3,5,17,3). This means our breadth-first order is canonically well-defined, as we have a natural ordering of the children of each parent vertex.

Note: one advantage of using breadth-first order rather than depth-first order (which corresponds to the usual dictionary, or lexicographic ordering of the labels) is that if the tree is infinite, we don’t explore all of it during a depth-first search. (In the sense that there exist vertices which are never given a finite label.) For breadth-first search, a similar problem arises precisely when some vertex has infinitely many children. For a conventional Galton-Watson tree, the latter situation is much less of a problem than the infinite total population problem, which happens with positive probability whenever \mu=\mathbb{E}[X]>1.

Anyway, given the depth-first order, one can consider an exploration process S_0,S_1,S_2,\ldots,S_{|T|} given by

S_0=1,\quad S_i=S_{i-1}+(X_i-1),

where X_i is the number of children of v_i. In this way, we see that

S_i=\big| \Gamma(v_1)\cup\ldots\cup\Gamma(v_i)\backslash \{v_1,\ldots,v_i\}\big|,\quad i\ge 1,

records the number of vertices in some stack containing those which we have ‘seen but not explored’. Some authors prefer to start from 0, in which case one ends up with a similar but slightly different interpretation of the ‘stack’, but that’s fine since we aren’t going to define formally what ‘seen’ and ‘explored’ means in this post.

Essentially, we exhaust the vertices of the tree whenever S_t=0, and so the condition that |T|=n requires

S_n=0,\quad S_m\ge 1,\; m=0,1,\ldots,n-1.

Conveniently, so long as we have avoiding ordering ambiguity, for example by insisting that trees live within the Ulam-Harris tree, we can reconstruct T uniquely from (S_0,S_1,\ldots,S_{|T|}).

Furthermore, if T is a Galton-Watson process, then the numbers of children X_i are IID, and so in fact this exploration process is a random walk, and the size of the tree can be recovered as the hitting time of zero.

Note: making fully rigorous the argument that children in the GW tree are independent of the breadth-first walk fully rigorous is somewhat technical, and not to be dismissed lightly, though not of principle interest at the level of this topics course. See Proposition 1.5 in Section 1.2 of Le Gall’s notes or Section 1.2.2 of my doctoral thesis for further discussion and argument.

The hitting time theorem allows us to study the distribution of the hitting time of a random walk whose increments are bounded below by -1, in terms of the distribution of the value of the random walk.

Theorem: Let (S_n,\, n\ge 0) be a random walk with S_0=0 and IID increments (X_n,n\ge 1) satisfying \mathbb{P}(X_n\ge -1)=1. Let H_{-k}=\inf \left\{n\,:\, S_n=-k\right\} be the hitting time of -k.

Then \mathbb{P}\big( H_{-k}=n\big) = \frac{k}{n}\mathbb{P}\big(S_n=-k).

Commentary: there are local central limit theorem estimates and large deviation estimates that allow good control of the probability on the RHS for a rich class of contexts. So at a meta-level, the hitting time theorem allows us to reduce a complicated (though still classical) problem, to a real classical problem, which is particularly helpful when the LHS is a device for capturing relevant information about our random tree model.

Proof context/history: The case k=1, as relevant to the trees, is often referred to as Dwass’s theorem, though the combinatorial argument pre-dates this, sometimes in the form of the similar ballot theoremA complete reference list would be challenging, but it certainly appears in Feller, due to Spitzer. In his recent book, van der Hofstad uses an argument by induction on n, noting that the statement is obvious when n=0,1,…,k-1, and obvious for different reasons when n=k. This argument can also be found published here.

I’m going to give a combinatorial argument, similar to one I’ve given in a post from years ago (back then, for the case k=1), because there wasn’t time to include this in the lecture.

Proof: from the point of view of the course, the most important probabilistic take home message from this argument is that we get significant control by introducing the randomness in two stages, and conditioning on the first round of randomness.

Here, what we do is to condition on the increments (X_1,X_2,\ldots,X_n)_{\mathrm{cyc}} in cyclic order, ie without distinguishing between (x_1,x_2,\ldots,x_n) and (x_4,x_5,\ldots,x_n,x_1,x_2,x_3). We’ll declare which of these is the true ordering at the end. Anyway, the punchline is the following lemma.

Lemma: when x_1+\ldots +x_n=-k, and all x_i\ge -1, then exactly k of the n orderings corresponding to the cyclic ordering (x_1,\ldots,x_n)_{\mathrm{cyc}} have the property that x_1+\ldots+x_\ell \ge -k+1.

With this lemma, it’s clear why the hitting time theorem holds. We condition on (x_1,\ldots,x_n)_{\mathrm{cyc}}. If the sum of these elements is not -k, then there’s no chance that the hitting time is n. If the sum is -k, then when we choose a true ordering at random, we get the hitting time as n with conditional probability k/n.

Proof of lemma: At all times, take indices modulo n. We want labels \alpha satisfying:

x_\alpha,\; x_\alpha+x_{\alpha+1},\; \ldots\;, ;\ x_{\alpha}+\ldots+x_{\alpha+n-2}\text{ are all }\ge -(k-1). (*)

Step 1: Suppose there are \alpha_1<\alpha_2<\ldots<\alpha_{k+1} satisfying (*). It’s helpful to think about going round the circle of values. If we go all the way round the circle, we get -k, but if we go from x_{\alpha_{i+1}}\to x_{\alpha_i-1} then we have an initial segment from x_{\alpha_{i+1}}, and so

x_{\alpha_i}+\ldots+x_{\alpha_{i+1}-1} = -k - (x_{\alpha_{i+1}}+\ldots+x_{\alpha_i-1}) \le -k - \left(-(k-1)\right) = -1.

However, if we repeat this for the k+1 such blocks, we end up going all the way round the circle, and get

\left(x_{\alpha_1}+\ldots+x_{\alpha_2-1}\right) + \left(x_{\alpha_2}+\ldots+x_{\alpha_3-1}\right) + \ldots

\ldots+ \left(x_{\alpha_{k+1}} + \ldots+x_{\alpha_1-1}\right) \le -(k+1),

which is a contradiction since the total sum is k. So we have at most k such values of \alpha.

Step 2: Now we show that there is at least one such \alpha. Let

\beta=\mathrm{argmin}_{1\le m\le n} (x_1+\ldots+x_m),

and if there are multiple such m, let \beta be the minimal such. Now set \alpha=\beta+1, and we will show this satisfies the requirements.

  • Then x_\alpha+x_{\alpha+1}+\ldots+x_{\alpha+m}\ge 0, whenever \alpha+m\le n.
  • And when m<\beta, we have

x_{\alpha}+\ldots+x_n+x_1+\ldots+x_m = -k+(x_1+\ldots+x_m)-(x_1+\ldots+x_\beta).

And by assumption, the first bracket is strictly greater than the second bracket, so

x_\alpha + \ldots+x_n+x_1+\ldots+x_m \ge -(k-1).

Step 3: Now we have an \alpha which satisfies, we may assume WLOG that it is \alpha_0=1. Now we construct the hitting times:

\alpha_1=\min\big(m\,:\, x_1+\ldots+x_m=-1\big),

\alpha_{k-1}=\min\big(m\,:\, x_1+\ldots+x_m=-(k-1)\big).

We claim that all these also satisfy the requirements for \alpha. This is fairly clear from a diagram, or from the fact that when \alpha_i\le m<\alpha_{i+1}, then

x_{\alpha_k}+x_{\alpha_k+1}+\ldots+x_m\ge x_{\alpha_k}+\ldots+x_{\alpha_i}= i-k,

(or i-k+n \text{ if } i<k).


1 thought on “Lecture 4 – Hitting time theorem

  1. Pingback: Lecture 8 – Bounds in the critical window | Eventually Almost Everywhere

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s