Summer Research Project

I did my summer research project in 2014 in the field of random walks in random environments supervised by Dr David Croydon.

The first part of the thesis is a survey of known results concerning the limiting behaviour of biased random walks on supercritical and critical Galton-Watson trees conditioned to survive and the remainder consisted of extending these results to the subcritical case.

To be more specific let $(p_k)_{k\geq0}$ denote the offspring distribution of a Galton-Watson process with mean $\mu<1$ , variance $\sigma^2$ (possibly infinite) and write $\xi$ to be a variable under this law. It is well know that the process becomes extinct almost surely. Using Kolmogorov's continuity theorem one can define a probability measure over such Galton-Watson processes conditioned to survive. These processes have an interesting structure in which there is an infinite line of descent which we refer to as the backbone. Each vertex on the backbone (independently of the rest of the tree) has a number of offspring according to a size biased distribution $(q_k)_{k\geq 1}$ where $q_k=kp_k/\mu$ . One of these vertices is chosen arbitrarily to be on the backbone and all others act as roots of subcritical Galton-Watson trees with the original offspring distribution. It is interesting that this structure is similar to the supercritical tree constructed by Harris however in the supercritical case the backbone structure is itself a non-trivial Galton-Watson tree and the number of offspring from backbone vertices has a more complicated distribution. Most importantly, the distribution of offspring from backbone vertices has finite mean which is not necessarily true for the subcritical tree.

Such a process gives rise to a random tree with vertices corresponding to individuals and edges connecting individuals with their offspring. We then consider a biased random walk $X_n$ on such a graph $T$ whereby the walk starts at the root $\rho$ of the tree and makes transitions with fixed probabilities so that the walk is $\beta$ times more likely to move to a given offspring of the current vertex than it is to move to the parent.

We are mainly interested in the distance between the walker and the root of the tree $|X_n|$ over time. It is clear that the walk is transient if and only if $\beta>1$ using electrical network theory and the fact the walk can only escape along the backbone. This simply follows from the fact that, for transience, it suffices that the walk has positive average drift along the backbone.

The main object of interest for the thesis was the speed $r_\beta$ of the walk; that is, the almost sure limit of $|X_n|/n$ as $n \rightarrow \infty$ under the annealed measure. Using regeneration arguments I was able to show that, provided the offspring distribution satisfies $\mathbf{E}[\xi\log(\xi)]<\infty$ , the speed always exists. Furthermore, I have shown that, under the same conditions on the offspring distribution, the walk is ballistic if and only if $1<\beta<\mu^{-1}$ and $\sigma^2<\infty$ . This is very similar to the supercritical case in the sense that for small bias the walk is recurrent and therefore has zero speed and for large bias the time spent in finite traps of the tree is large and slows the walk enough to result in a sub-ballistic regime. The main difference is the extra condition that $\sigma^2<\infty$ . This is required so that the vertices on the backbone have finite expected degree and thus the walk doesn't spend too much time stuck around vertices of high degree. This isn't required in the supercritical case because vertices on the backbone have finite expected degree without any additional assumptions.

Using an ergodic theory argument I was then able to determine the speed in the ballistic regime to be

$r_\beta=\frac{\mu(\beta-1)(1-\beta\mu)}{\mu(\beta+1)(1-\beta\mu)+2\beta(\sigma^2-\mu(1-\mu))}.$