Project Overview

I am currently researching the asymptotic behaviour of a variant of Wilson’s algorithm for generating random spanning forests which grows in discrete time steps. In particular I am interested in knowing the convergence in the sense of Gromov–Hausdorff–Prokhorov sense.

Wilson’s Generalized Algorithm

    Let $G$ be transient graph. Denote the forest at time $t$ by $F_t$.
  1. At time $t = 0$, let $F_0 = \varnothing$ be the empty forest.
  2. Increase $t$ by 1. Choose a vertex $v$ uniformly at random from $G \setminus F_{t-1}$. Start a loop-erased random walk (LERW) $W$ from $v$:
    1. If $W$ hits $F_{t-1}$, set $$F_t = F_{t-1} \cup W,$$ color the last vertex of the LERW blue, and connect this blue vertex to $F_{t-1}$ instead of the usual hitting point.
    2. Otherwise, sample an independent Bernoulli$(p)$ variable. If it equals $1$, set $$F_t = F_{t-1} \cup W,$$ color the first vertex of $W$ red and declare it a root, then go to (iii).
    3. Let $W$ take one additional step. Return to step (ii)(a).
  3. If $F_t$ is a spanning forest, stop. Otherwise return to (ii).

sample of Wilsons forrest with killing

Recent work has developed tools for handling forests and fragmentation processes, including GHP metrics for disconnected spaces, cut-tree representations, and scaling limits of random trees. These ideas motivate our approach to describing the geometry of forests generated by a killed Wilson algorithm.

Phase transition

In order to get some meaningful limit we must decrease the rate of killing, and there seems to be an interesting phase transition depending on the asymptotic behaviour of the killing rate. In the critical case we seem to see a forest that can be constructed by way of cutting the continuum random tree (CRT) by poisson rate along its skeleton.

Cut-Tree Perspective

The cut-tree encodes an entire fragmentation process of a tree by recording the order in which edges are removed. In the case of taking a random spanning tree, and removing the edges in a random order, this yields a well-defined fragmentation. However, with killing, the geometry varies with the killing rate, so the resulting process is not a strict fragmentation in the usual sense.

Componentwise Convergence

To study convergence of entire forests, we use an ℓp-type Gromov–Hausdorff–Prokhorov (GHP) metric on sequences of compact measured metric spaces. This allows us to compare forests through the joint convergence of all components.

Stick-Breaking Forest

We introduce a stick-breaking construction based on a bi-coloured Poisson point process with intensity (x + c)dx. Blue points attach line segments to existing components, while red points start new ones. For c = 1, this recovers Aldous’s classical CRT construction. The resulting forest matches the scaling limit of the killed Wilson algorithm in the critical sense.