--- abstract: 'We consider invasion percolation on Galton-Watson trees. On almost every Galton-Watson tree, the invasion cluster almost surely contains only one infinite path. This means that for almost every Galton-Watson tree, invasion percolation induces a probability measure on infinite paths from the root. We show that under certain conditions of the progeny distribution, this measure is absolutely continuous with respect to the limit uniform measure. This confirms that invasion percolation, an efficient self-tuning algorithm, may be used to sample approximately from the limit uniform distribution. Additionally, we analyze the forward maximal weights along the backbone of the invasion cluster and prove a limit law for the process.' bibliography: - 'Bib.bib' --- <span>**Invasion Percolation on Galton-Watson Trees**</span> Marcus Michelen, Robin Pemantle[^1] and Josh Rosenberg\ <span>{marcusmi, pemantle, tpeters@example.com</span> <span><span>**Keywords**</span>: Backbone, incipient infinite cluster, limit uniform, Poisson point process, pivot, self-organized criticality.</span> Introduction {#sec:intro} ============ Given an infinite rooted tree, how might one sample, nearly uniformly, from the set of paths from the root to infinity? One motive for this question is that nearly uniform sampling leads to good estimates on the growth rate @jerrum-sinclair. One might be trying to estimate the size of a search tree, or, in the case of @randall-sinclair, to determine the growth rate of the number of self-avoiding paths. A number of methods have been studied. One is to do a random walk on the tree, with a "homesickness" parameter determining how much steps back toward the root are favored @LPP-biased. The parameter needs to be tuned near criticality: too much homesickness and the walk gets stuck near the root; too little homesickness and the walk goes to infinity without taking the time to ensure that the path is well randomized. Randall and Sinclair @randall-sinclair solve this by estimating the critical parameter as the walk progresses, re-tuning the homesickness to lie above this by an amount decreasing at an appropriate rate. Another approach is to use percolation. One conditions the percolation cluster to survive to level $N$; as the percolation parameter decreases to criticality and $N$ is taken to infinity, the law of this cluster approaches the law of the <span>*incipient infinite cluster*</span> (IIC). For many graphs—e.g. regular or Galton-Watson trees—the IIC almost surely contains a unique infinite path, thereby giving a mechanism for sampling such a path. In practice, the same considerations arise as with homesick random walks: tuning the percolation parameter too low yields too little likelihood of survival and too great a time cost to rejection sampling; too great a percolation parameter results in too many surviving paths and a selection problem which leads to poor randomization. Invasion percolation was introduced as a model for how viscous fluid creeps through an environment in @invasion. Each site is given an independent $U[0,1]$ random variable, representing how great the percolation probability would have to be before the site would be open. The cluster then grows by adding, at each time step, the site with the least $U$ value among sites neighboring the cluster but not in the cluster. It is not hard to see that the $\limsup$ of $U$-values of bonds chosen is equal to the critical percolation parameter. In other words, instead of running percolation at $p_c$ and conditioning to survive, one allows slightly supercritical bonds but less and less as the cluster grows. As is the case for the IIC, the invasion cluster almost surely contains only one infinite path in the case of regular or Galton-Watson trees, and thus gives a different mechanism for sampling paths. Unlike the IIC and homesick random walk, invasion percolation requires no tuning to criticality and is an instance of self-organized criticality. The invasion cluster has some properties in common with the IIC but not all. For example, results of Kesten @kesten-IIC and Zhang @zhang-invasion show that the growth exponents of the two are equal on the two-dimensional lattice; however the measures of the two clusters are mutually singular on the lattice @damron-invasion as well as on a regular tree @angel-invasion2008. Our focus is the comparison of the laws induced on paths by both the IIC and invasion percolation. On a Galton-Watson tree $T$, there is a natural measure on paths, the limit-uniform measure $\mu_T$, which although it does not restrict precisely to the uniform measure on each generation, approximates this as closely as possible. There is not, however, a fast algorithm for sampling from it. Rules such as "split equally at each node" lead to rapid sampling but the wrong entropy; in other words, the Radon-Nikodym derivative with respect $\mu_T$ on generation $N$ will be exponential in $N$. It is not hard to show that on almost every Galton-Watson tree (assuming a $Z \log Z$ moment for the offspring distribution), the unique path in the IIC has law $\mu$. Since sampling from the IIC is problematic, it is therefore natural to ask how close the law $\nu_T$ of the path chosen by the invasion cluster is to $\mu_T$. Showing that it has the right entropy is not too involved. This is Theorem \[th:small\] below. It is also easy to see that the two laws are typically not equal. As an example, consider the set of trees with first three generations given by ![image](figure.pdf) When averaged over the remaining generations with the Galton-Watson measure—or equivalently, placing independent Galton-Watson trees at the terminal nodes—the limit-uniform measure splits equally at the root, while the invasion measure favors the left subtree regardless of the offspring distribution. The best comparison one might hope for is that $\nu_T$ be absolutely continuous with respect to $\mu_T$, perhaps even with Radon-Nikodym derivative in $L^p$. Our main result is as follows. \[th:main\] Suppose the offspring distribution $Z$ has at least $p$ moments, set $p_1 := \P[Z = 1]$, let $\mu:= \E[Z]$, and denote $q:=\frac{\log\mu}{\log\left(1/p_1\right)}$. If $$2p^2 q^2+(3p^2+5p)q+(-p^2+11p-4)<0,$$ then $\nu_\TT \ll \mu_\TT$ almost surely. The condition in Theorem \[th:main\] is a trade-off between $p_1$ and $p$. In the case of $p = \infty$, the condition becomes $p_1 < 1/\mu^{\frac{3+\sqrt{17}}{2}}$. In the case of $p_1 = 0$, the condition is $p>\frac{11+\sqrt{105}}{2}$. An outline of the argument behind Theorem \[th:main\] is as follows. Let $X_n$ be the KL-distance between the way that $\mu_T$ and $\nu_T$ split at the $n$th step $\gamma_n$ of a path chosen from $\nu_T$. A sufficient condition for absolute continuity is that $\sum_{n=1}^\infty \E X_n < \infty$. A precise statement is given in Lemma \[lem:X\] below. A more detailed outline of why this condition should hold is given at the beginning of Section \[sec:rest\]. The reason we have a hope of estimating $X_n$ is that there is a <span>*backbone*</span> decomposition for invasion percolation. Define the backbone to be the almost surely unique nonbactracking path $\gamma = (\rtt, \gamma_1, \gamma_2, \ldots)$ from the root to infinity. For any vertex $v$ define the <span>*pivot value*</span> at $v$, denoted $\pivot (v)$ \[pivot-def\], to be the least $p$ such that there is a path from $v$ to infinity in the subtree at $v$ with all $U$ variables (not including the one at $v$) at most $p$. On a regular tree, invasion percolation was studied in @angel-invasion2008 [@angel-invasion2013]. For the purposes of studying $\nu_T$, the regular tree is a degenerate case, because $\mu_T$ and $\nu_T$ are equal to each other and to the equally splitting measure. However their results on backbones and pivots extend in a useful way to the Galton-Watson setting. Conditioning on $T$, the way the invasion measure splits at $v$ depends on the whole tree. However, if one also conditions on the pivot at $v$, then the way the invasion measure splits at $v$ becomes independent of everything outside of the subtree at $v$. A similar statement is true if one conditions on the pivot of $v$ being less than or equal to a certain value; these are the Markov properties of Propositions \[pr:markov 2\] and \[pr:markov\]. The limiting behavior of these values are given in Theorem \[theorem:condist\] and Corollary \[cor:LPE\]. Further, Lemma \[lem:qt-ratio-survival\] shows that this conditioned splitting measure is close to a ratio of survival probabilities under supercritical Bernoulli percolation. The problem is thus reduced to proving estimates of the survival probabilities of Galton-Watson trees under supercritical Bernoulli percolation as in Section \[sec:bounds-E\]. The remainder of the paper is organized as follows. Section \[sec:prelim\] sets up the notation and gives some preliminary results. Some care is required to set up the probability space so that we can easily speak of the random measures $\mu_T$ and $\nu_T$, which are conditional on the Galton-Watson tree. Section \[sec:prelim\] culminates in Lemma \[lem:X\] and Corollary \[cor:X\]. Section \[sec:g\] gives an upper bound on survival probabilities and squeezes survival probabilities close to an easier-to-analyze averaged version with high probability. Section \[sec:backbone\] proves two Markov properties for the subtree from $\gamma_n$ together with $\pivot (\gamma_n)$. The remainder of the section extends the work of @angel-invasion2008 by proving a limit law for $\pivot (\gamma_n)$ which then implies an upper bound on the rate at which $\pivot (\gamma_n) \downarrow p_c$. In particular, Corollary \[cor:LPE\] shows convergence to the Poisson lower envelope process, as in @angel-invasion2008. Section \[sec:rest\] proves Theorem \[th:main\] by comparing the conditional invasion measure to the ratio of survival probabilities and by carefully estimating survival probabilities near criticality. A glossary of notation by page of reference is included after the references. Construction and preliminary results {#sec:prelim} ==================================== Galton-Watson trees ------------------- We begin with some notation we use for all trees, random or not. Let $\ulam$ \[ulam-def\] be the canonical <span>*Ulam-Harris*</span> tree @louigi-ford. The vertex set of $\ulam$ is the set $\VU : = \bigcup_{n=1}^\infty \N^n$, \[VU-def\] with the empty sequence $\rtt := \emptyset$ \[rtt-def\] as the root. There is an edge from any sequence $\bfa = (a_1, \ldots , a_n)$ to any extension $\bfa \sqcup j := (a_1, \ldots , a_n , j)$. The depth of a vertex $v$ is the graph distance between $v$ and $\rt$ and is denoted $|v|$.\[depth-def\] We work with trees $T$ that are locally finite rooted subtrees of $\ulam$. The usual notations are in force: $T_n$ \[T\_n-def\] denotes the set of vertices at depth $n$; $T(v)$ \[T(v)-def\] is the subtree of $T$ at $v$, canonically identified with a rooted subtree of $\ulam$, in other words the vertex set of $T(v)$ is $\{ w : v \sqcup w \in V(T) \}$ \[sqcup-def\]; $\partial T$ \[partial-T-def\] denotes the set of infinite non-backtracking paths from the root; if $\gamma \in \partial T$ then \[gamma\_n-def\] $\gamma_n$ $(n \geq 0)$ denotes the $n$th vertex in $\gamma$; the last common ancestor of $v$ and $w$ is denoted $v \wedge w$ \[LCA-vertex-def\] and the last common vertex of $\gamma$ and $\gamma'$ is denoted $\gamma \wedge \gamma'$ \[LCA-path-def\]; $\Par{v}$ denotes the parent of $v$ \[Par-def\]. Let $\mu_T^n$ denote the uniform measure on the $n$th generation of $T$. In some cases, for example for almost every Galton-Watson tree, the limit $\mu_T := \lim_{n \to \infty} \mu_T^n$ \[mu-T-def\] exists and is called the <span>*limit-uniform measure*</span>. Turning now to Galton-Watson trees, let $\phi (z) := \sum_{n=1}^\infty p_n z^n$ \[phi-def\] be the ordinary generating function for a supercritical branching process with no death, i.e., $\phi (0) = 0$. We recall, $$\begin{aligned} \phi' (1) & = & \E Z =: \mu \\ \label{mu-def} \phi'' (1) & = & \E [Z (Z-1)] \end{aligned}$$ where $Z$ \[Z-def\] is a random variable with probability generating function $\phi$. Throughout, we assume $\E[Z^2] < \infty$; in particular, this also means that $\phi''(1) < \infty$. Moreover, since our focus is on $\partial T$, the assumption of $\phi(0) = 0$ can be made without loss of generality by considering the reduced tree, as in @athreya-ney [Chapter I.12]. We will work on the canonical probability space $(\Omega , \F , \P)$ \[space-def\] where $\Omega = (\N \times [0,1])^{\VU}$, $\F$ is the product Borel $\sigma$-field, and $\P$ is the probability measure making the coordinate functions $\omega_v = (\deg_v , U_v)$ IID with the law of $(Z,U)$, where $U$ is uniform on $[0,1]$ \[U\_v-def\] and independent of $Z$. The variables $\{ \deg_v \}$—where $\deg_v$ \[deg-def\] is interpreted as the number of children of vertex $v$—will construct the Galton-Watson tree, while the variables $\{ U_v \}$ will be used later for percolation. Let $\TT$\[TT-def\] be the random rooted subtree of $\ulam$ which is the connected component containing the root of the set of vertices that are either the root or are of the form $v \sqcup j$ such that $0 \leq j < \deg_v$. This is a Galton-Watson tree with ordinary generating function $\phi$. As is usual for Galton-Watson branching processes, we denote $Z_n := |\TT_n|$. \[Z\_n-def\] Extend this by letting $Z_n (v)$ \[Z\_n(v)-def\] denote the number of offspring of $v$ in generation $|v| + n$; similarly, extend the notation for the usual martingale \[W\_n-def\] $W_n := \mu^{-n} Z_n$ by letting $W_n (v) := \mu^{-n} Z_n (v)$. \[W\_n(v)-def\] We know that $W_n (v) \to W(v)$ \[W-def\] for all $v$, almost surely and in $L^p$ if the offspring distribution has $p$ moments. This is stated without proof for integer values of $q \geq 2$ in @harris-BP [p. 16] and @athreya-ney [p. 33, Remark 3]; for a proof for all $q > 1$, see @bingham-doney74 [Theorems 0 and 5]. Further extend this notation by letting $v^{(i)}$ denote the $i$th child of $v$, letting $Z_n^{(i)} (v)$ denote $n$th generation descendants of $v$ whose ancestral line passes through $v^{(i)}$, and letting $W_n^{(i)} (v) := \mu^{-n} Z_n^{(i)} (v)$. Thus, for every $v$, $W(v) = \sum_i W^{(i)} (v)$. For convenience, define $p_c := 1/\mu$ \[p\_c-def\] and recall that $p_c$ is almost surely the critical percolation parameter for $\TT$ @lyons90. Bernoulli and Invasion Percolation ---------------------------------- In this subsection we give the formal construction of percolation on random trees, and for invasion percolation. Our approach is to define a simultaneous coupling of invasion percolations on all subtrees $T$ of $\ulam$ via the $U$ variables, then specialize to the random tree $\TT$. Let \[T-def\] $\T := \sigma (\{ \deg_v : v \in \VU \})$ denote the $\sigma$-field generated by the tree variables. Because $\T$ is independent from the $U$ variables, this means we have constructed a process whose law, conditional on $\T$, is invasion percolation on $\TT$. We use the notation $\E_*$\[E\_\*-def\] to denote $\E [\cdot \| \T]$; similarly $\P_* [\cdot] := \P[\cdot \| \T]$ \[P\_\*-def\]. Moreover, we use $\GW:= \P|_{\T}$ \[GW-def\] to denote the Galton-Watson measure on trees. We begin with a similar construction for ordinary percolation. For $0 < p < 1$, simultaneously define Bernoulli$(p)$ percolations on rooted subtrees $T$ of $\ulam$ by taking the percolation clusters to be the connected component containing $\rtt$ of the induced subtrees of $T$ on all vertices $v$ such that $U_v \leq p$. Let $\F_n$ \[F\_n-def\] be the $\sigma$-field generated by the variables $\{ U_v , \deg_v : |v| < n \}$. Let $p_c = 1/\mu = 1/\phi'(1)$ denote the critical probability for percolation. Write $v \conn_{T,p} w$ \[conn-def\] if $U_u \leq p$ for all $u$ on the geodesic from $v$ to $w$ in $T$. Informally, $v \conn_{T,p} w$ iff $v$ and $w$ are both in $T$ and are connected in the $p$-percolation. The event of successful $p$ percolation on $T$ is $H_T (p) := \{ \rtt \conn_{T,p} \infty \}$ and the event of successful $p$ percolation on the random tree $\TT$, is denoted $H_\TT (p)$ or simply\[H(p)-def\] $H(p)$. Let \[g(T,p)-def\] $g(T , p) := \P [H_T (p)]$ denote the probability of $p$ percolation on $T$. The conditional probability $\P_* [H(p)]$ is measurable with respect to $\TT$ and we may define $g(\TT , p):= \P_* [H(p)]$. Furthermore, we may define \[g(p)-def\] $g(p) = \P [H(p)] = \E g(\TT , p)$. Since $p_c = 1/\mu$ is the critical percolation parameter for a.e. $\TT$, note that $g(\TT,p) = 0$ for all $p \in [0,p_c]$. Before defining invasion percolation, we record some basic properties of $g$. \[pr:K\] The derivative from the right \[K-def\] $K := g'(p_c)$ exists and is given by $$\label{eq:K} K := \frac{2}{p_c^3 \phi'' (1)} \, .$$ Let $\phi_p (z) := \phi (1 - p + p z)$ be the offspring generating function for the Galton-Watson tree thinned by $p$-percolation for $p \in (p_c,1)$. The fixed point of $\phi_p$ is $1 - g(p)$. In other words, $g(p)$ is the unique $s \in (0,1)$ for which $1 - \phi_p (1-s) = s$. The first two derivatives of $\phi_p$ at $1$ are given by $$\begin{aligned} \phi_p'(1) & = & \frac{p}{p_c} \, ; \\[1ex] \phi_p''(1) & = & p^2 \phi'' (1) \, . \\[1ex]\end{aligned}$$ By a Taylor expansion, this leads to $$1 - \phi_p (1-s) = \frac{p}{p_c} s - \frac{1+o(1)}{2} \phi'' (1) p^2 s^2$$ as $p \downarrow p_c$. Setting this equal to $s$ and solving for $s \in (0,1)$ yields the conclusion of the proposition. $\Cox$ \[cor:dersurvprob\]As $p \downarrow p_c$, $g'(p) \to K$. The existence of $g'(p)$ on $(p_c, 1)$ follows from the implicit function theorem. To obtain an expression for $g'(p)$, we differentiate both sides of the expression $\phi(1 - p \cdot g(p)) = 1 - g(p)$ with respect to $p$, which gives $$(-g(p) - p \cdot g'(p)) \phi'(1 - p \cdot g(p)) = -g'(p).$$ Rearranging this expression to isolate $g'(p)$, while using Proposition \[pr:K\], along with the fact that $\phi'(1-x) = \mu-\phi''(1) x + o(x)$ as $x\rightarrow 0$, we get $$g'(p) \; = \; \frac{g(p) \phi'(1-p \cdot g(p))}{1-p\cdot \phi'(1-p \cdot g(p))} \; = \; \frac{2\mu^3}{\phi''(1)}+o(1)$$ as $p \downarrow p_c$. $\Cox$ Define invasion percolation on an arbitrary tree $T$ as follows. Start with $I^T_0 = \bf 0$ where we recall that $\bf 0$ is the root of $T$. Inductively define $I^T_{n+1}$ to consist of $I^T_n$ along with the vertex of minimal weight $U_v$ adjacent to $I^T_n$. The invasion percolation cluster is defined as $I^T := \bigcup I^T_n$. Note that $I^T$ is measurable with respect to the $U$ variables. Let $I := I^\TT$ \[I-def\] denote the invasion cluster of the random tree $\TT$. By independence of the $U$ variables and $\T$, the conditional distribution of $I$ given $\TT$ agrees with that of invasion percolation. \[prop:infst\] For any $p > p_c$, $I$ almost surely reaches some vertex $v$ such that $v \conn_p \infty$ in $\TT (v)$. We consider the following coupling that generates $I$ at the same time as $\TT$: begin with the root, and generate children according to $Z$, giving each new edge a $(0,1)$ weight uniformly and independently. If there exists a weight below $p$, take the edge of minimal weight among all boundary edges and generate children according to $Z$, giving each new edge a weight as before. Continue this process; if it terminates, then choose the minimal weight overall (which will necessarily be greater than $p$), generate children and assign weights as before. Repeat this process. Each event measurable with respect to the law described above has the same probability as with respect to $\P$. At the step after each termination—when all available weights are greater than $p$—the event that the newly generated vertex has an infinite subtree is independent from all that came before and has positive probability $g(p)$. By the second Borel-Cantelli lemma, there will necessarily be an invaded edge with an infinite subtree below it with weights less than $p$. $\Cox$ \[cor-finite\] For any $p > p_c$, the number of edges in $I$ with weight greater than $p$ is almost surely finite. This was proven for a large class of graphs by Häggström, Peres and Schonmann @HPS, but this class doesn't cover the case of Galton-Watson trees conditioned on survival; they exploit quite a bit of symmetry that does not occur in the Galton-Watson case. Let $x$ be the first invaded vertex with an infinite subtree below with weights less than $p$. Then after $x$ is invaded, no edges of weight larger than $p$ will be invaded. $\Cox$ \[cor:path\] There is almost surely only one infinite non-backtracking path from $\bf 0$ in $I$. Equivalently, $\TT$ is almost surely in the set of trees $T$ such that $I^T$ contains almost surely a unique infinite non-backtracking path from $\rtt$. Suppose that there are two distinct paths to infinity in $I$; by Corollary \[cor-finite\], there exist maximal weights $M_1$ and $M_2$ along these paths after they split, $\P$-almost surely. If $M_1 > M_2$, the second infinite path would be invaded before the edge containing $M_1$. Similarly, we cannot have $M_2 > M_1$. Finally, $M_1 = M_2$ has $\P$-probability $0$, completing the proof. $\Cox$ This proof is stated for invasion percolation on regular trees in @angel-invasion2008, but is identical for Galton-Watson trees once Corollary \[cor-finite\] is in place; the unique path guaranteed by \[cor:path\] is typically called the backbone of $I$, and we continue this convention. Note that a regular tree is simply a Galton-Watson tree with $Z \equiv b$. \[the invasion path $\gamma$\] Let \[gamma-def\] $\gamma^T := (\rtt, \gamma^T_1, \gamma^T_2, \ldots)$ be the random sequence whose $n$th element is the unique $v$ with $|v|=n$ such that $v \leftrightarrow \infty$ via a downward path in the invasion cluster $I^T$. Let $\nu_T$\[nu\_T-def\] denote the law of $\gamma^T$ given $T$. Let $\nu_\TT$ denote the random measure on the random space $(\TT , \partial \TT)$ induced by the $\gamma^\TT$. In other words, for measurable $A \subseteq \partial \ulam$, $\nu_\TT (A , \omega) = \P [\gamma^T \in A]$ evaluated at $T = \TT(\omega)$. By Corollary \[cor:path\], this is a well defined probability measure for almost every $\omega$. Preliminary comparison of limit-uniform and invasion measures ------------------------------------------------------------- Our main goal is to see whether $\nu_\TT$ is almost surely absolutely continuous with respect to $\mu_\TT$. The following easy first result shows that $\nu_\TT$ has the same entropy as $\mu_\TT$. Let $T$ be a rooted tree with branching number $\mu$ and $S \subset \partial T$. For each $n$, define $S_n$ to be the set of vertices in paths in $S$ at height $n$. If there exists an $\ee > 0$ so that $|S_n| \lesssim (\mu - \ee)^n$, then we say that $S$ is *exponentially small*. If every exponentially small set $S$ has $\nu_T(S) = 0$, then we say that the *the limit uniform and invasion measures on $T$ have the same entropy.* \[th:small\] For $\GW$-a.e. $\TT$, the limit uniform and invasion measures on $\TT$ have the same entropy. Condition on $\T$ and fix some exponentially small $S \subset \partial \TT$. Let $p \in (\frac{1}{\mu},\frac{1}{\mu-\ee})$; then since $p > p_c$, Proposition \[prop:infst\] implies that there exists an invaded vertex with an infinite subtree of weights less than $p$ below it. Let $v_p$ be the first such invaded vertex. Then the backbone is contained in the subtree below $v_p$ since the parental edge of $v_p$ together with edges of weight larger than $p$ separate the root from infinity. Moreover, all invaded vertices below $v_p$ have parental edge weight at most $p$, implying that the backbone is contained in the set of open edges below $v_p$ with weight at most $p$; call this subtree $C_p$. Note that the law of the subtree below $v_p$ (unconditioned on $\T$) with weight at most $p$ has the law of a Galton-Watson tree with progeny distribution $\Bin(Z,p)$ conditioned on $v_p$ being contained in an infinite open cluster. Thus, conditioned on $\T$ and $v_p$, the law of this subtree is the law of the open cluster containing $v_p$ of Bernoulli($p$) percolation on the subtree below $v_p$ conditioned on this cluster being infinite. Note that since $\TT$ is Galton-Watson, the critical parameter for percolation on the subtree below $v_p$ is $p_c$; in particular, if we call this cluster $C_p$, we have that $\P_*[|C_p| = \infty \| v_p] > 0$ $\nu_\TT$-a.s. Condition on $\T$ and condition further on $v_p$; note that for $x$ below $v_p$ we have $$\label{eq:union-bd} \P_*[x \in C_p \| v_p, |C_p| = \infty] \leq \frac{p^{|x| - |v_p|}}{\P_*[|C_p| = \infty \| v_p]}.$$ Thus for any $n$, we have $$\P_*[S \cap \partial I \neq \emptyset \| v_p] \leq \P_*[S_n \leftrightarrow v_p \| v_p,|C_p| = \infty] \leq \frac{|S_n| p^{n-|v_p|}}{\P_*[|C_p| = \infty \| v_p] }$$ where the last inequality is via a union bound over $S_n$. By the definition of $p$, $|S_n|p^n \to 0$; therefore, for each $v_p$, we have $$\P_*[S \cap \partial I \neq \emptyset \| v_p] = 0.$$ Since there are $\P$-a.s. only countably many vertices in $\TT$, the above gives $$\label{eq:mu-eq-zero} \nu_\TT (S) = \P_*[S \cap \partial I \neq \emptyset ] \leq \sum\limits_{v \in \TT } \P_*[S \cap \partial I \neq \emptyset \| v_p = v] = 0$$ $\P$-a.s. thereby completing the proof. $\Cox$ In the remainder of this section, we give the summability criterion that establishes a sufficient condition for absolute continuity in terms of the KL-divergence of the two measures along a ray chosen from $\nu_\TT$. \[the splits $p$ and $q$ at children of $u$, and their difference, $X$\] \[def:splits\] Let $v$ be a vertex of $\TT$ and let $u$ be the parent of $v$. Define $$\begin{aligned} p(v) & := & \mu_\TT (v)/\mu_\TT (u) \label{p(v)-def}\\ q(v) & := & \nu_\TT (v)/\nu_\TT (u) \label{q(v)-def}\\ X(u) & := & \sum_w q(w) \log [q(w) / p(w)] \label{X-def} \end{aligned}$$ where the sum is over all children $w$ of $u$ and $\nu_\TT(v) = \nu_\TT(\{\gamma : v \in \gamma \})$ and $\mu_\TT(v)$ is defined similarly. The quantity $X$ is known as KL-divergence. The KL-divergence $\KL (\rho,\rho')$ is defined between any two probability measures $\rho$ and $\rho'$ on a finite set $\{ 1 , \ldots , k \}$ by the formula $$\KL (\rho , \rho') := \sum_{i=1}^k \rho'(i) \log \frac{\rho'(i)}{\rho(i)} \, .$$ It is a measure of the difference between the two distributions. It is always non-negative but not symmetric. The following inequality shows that $\KL$ behaves like quadratic distance away from $\rho = 0$. \[pr:KL\] Let $\rho$ and $\rho'$ be probability measures on the set $\{ 1, \ldots , k \}$ and denote $\ee_i := \rho'(i) / \rho(i) - 1$. Then $$\KL (\rho , \rho') \leq \sum_{i=1}^k \rho(i) \ee_i^2 \, .$$ Define the function $R$ on $(-1,\infty)$ by $$R(x) := \frac{(1+x) \log (1+x) - x}{x^2}$$ if $x \neq 0$ and $R(0) := 1/2$. This makes $R$ continuous, positive, and decreasing from 1 to 0 on $(-1,\infty)$. When $\ee = \rho'/\rho - 1$, we may compute $$\frac{\rho' \log (\rho'/\rho) - (\rho'-\rho)}{\rho} = \frac{(1+\ee) \rho \log (1+\ee) - \ee \rho}{\rho} = \ee^2 R(\ee) \, .$$ Because $\sum_{i=1}^k \rho(i) = \sum_{i=1}^k \rho'(i) = 1$, we see that $$\KL (\rho, \rho') = \sum_{i=1}^k (\rho'(i) - \rho(i)) + \rho(i) \ee_i^2 R(\ee_i) = \sum_{i=1}^k \rho(i) \ee_i^2 R(\ee)$$ and the result follows from $0 < R(\ee) < 1$. $\Cox$ Applying Proposition \[pr:KL\] to $\rho' = q$ and $\rho = p$ gives $$\label{eq:KL} X(u) \leq \sum_{w}p(w)\ee(w)^2$$ where $\ee(w) = \frac{q(w)}{p(w)} - 1.$ \[lem:X\] Let $T$ be a fixed tree on which $\nu_T$ and $\mu_T$ are well defined on the Borel $\sigma$-field $\B$ on $\partial T$. If $$\label{eq:L1} \sum_{n=1}^\infty \sum_{|v|=n} X(v) \nu_T (v) < \infty$$ then $\nu_T \ll \mu_T$. On the measure space $(\partial T , \B),$ define a filtration $\{ \G_n \}$ by letting $\G_n$\[G\_n-def\] denote the $\sigma$-field generated by the sets $\{ \gamma : \gamma_n = v \}$. The Borel $\sigma$-field $\B$ is the increasing limit $\sigma ( \bigcup_n \G_n )$. Let $$M_n := \left. \frac{d\nu}{d\mu} \right |_{\G_n} \, .\label{M_n-def}$$ In other words, $M_n (\gamma) = \nu (\gamma_n) / \mu (\gamma_n)$. Let $\Mbar := \limsup_{n \to \infty} M_n$. The Radon-Nikodym martingale theorem @durrett4 [Theorem 5.3.3] says that $\{ M_n \}$ is a martingale with respect to $(\partial T, \B, \mu_T , \{ \G_n \})$ and that $\nu_T \ll \mu_T$ is equivalent to $\nu_T( \{ \Mbar = \infty \} )= 0$. This is equivalent to $\nu_T (\{ \ul{M} = 0\}) = 0$ where $\ul{M} = 1 / \Mbar = \liminf_n 1/M_n$. The sequence $\{ 1/M_n \}$ is a $\nu_T$-martingale, therefore $\{ \log (1/M_n) \}$ is a $\nu_T$-supermartingale and to conclude that it $\nu_T$-a.s. does not go to negative infinity, it suffices to show that its expectation is bounded from below. We compute the conditional expected increment of $\log (1/M_n)$. Letting $\gamma$ denote the ray $(\gamma_1 , \gamma_2, \ldots)$, $$\log \frac{1}{M_{n+1} (\gamma)} - \log \frac{1}{M_n (\gamma)} = \log \frac{\nu_T (\gamma_n)}{\mu_T (\gamma_n)} - \log \frac{\nu_T (\gamma_{n+1})}{\mu_T (\gamma_{n+1})} = - \log \frac{q(\gamma_{n+1})}{p(\gamma_{n+1})} \, .$$ Conditioning on $\G_n$, if $\gamma_{n+1} = u$, then the $\nu_T$-probability of $\gamma_n = v$ is $q(v)$, whence $$\E_{\nu_T} \left [ \log \frac{1}{M_{n+1}} - \log \frac{1}{M_n} \,\bigg|\, \G_n \right ] = \sum_{v \text{ child of } u} - q(v) \log \frac{q(v)}{p(v)} = - X(u) \, .$$ Taking the unconditional expectation, $$\E_{\nu_T} \left [ \log \frac{1}{M_{n+1}} - \log \frac{1}{M_n} \right ] = - \sum_{|v|=n} \nu_T (v) X(v)$$ and summing over $n$ shows that implies that $\log (1 / M_n)$ has expectation bounded from below, establishing $\nu_T \ll \mu_T$. $\Cox$ \[cor:X\] Recall that $\gamma$ denotes the invasion path on $\TT$ and let $X_n$ denote $X (\gamma_n)$. (i) If $\sum_{n=1}^\infty \E X_n < \infty$ then $\nu_\TT \ll \mu_\TT$ $\GW$-almost surely. (ii) Define the filtration $\{ \G_n' \}$ on $(\Omega , \F)$ by letting $\G_n'$ be the $\sigma$-field generated by $\T$ together with $\gamma_1, \ldots , \gamma_n$. Let $Y(v)$ be random variables such that $Y(v) \in \G_{|v|}'$ and $$\P [X(\gamma_n) \neq Y(\gamma_n) \mbox{ infinitely often} ] = 0 \, .$$ Then $\sum_{n=1}^\infty \E Y_n < \infty$ implies that $\GW$-almost surely, $\nu_\TT \ll \mu_\TT$. \ $(i)$ Writing $\E X_n = \E \left[ \E_* X_n \right]$ we see that the hypothesis of $(i)$, namely $\sum_{n=1}^\infty \E X_n < \infty$, implies $\E \sum_{n=1}^\infty \E_* X_n < \infty$. This implies $\sum_{n=1}^\infty \E_* X_n < \infty$ almost surely. A version of $\E_* X_n$ is $\sum_{|v| \in \TT_n} X(v) \nu_\TT (v)$, whence holds for $\GW$-almost every $\TT$, implying almost sure absolute continuity of $\mu_\TT$ with respect to $\nu_\TT$.\ $(ii)$ The argument used to prove Lemma \[lem:X\] may be adapted as follows. Let $\disp M_n := \left. \frac{d \nu_\TT}{d\mu_\TT} \right |_{\G_n'}$, a version of which is the function taking the value $\disp \frac{\nu_\TT (v)}{\mu_\TT (v)}$ on $\{ \gamma_n = v \}$. Again $\{ M_n \}$ is a martingale and $\log (1/M_n)$ is a supermartingale which we need to show converges almost surely. The sequence $$S_M := \sum_{n=1}^M \left ( \log \frac{1}{M_{n+1}} - \log \frac{1}{M_n} \right ) \, \one_{X(\gamma_n) = Y(\gamma_n)}$$ is a convergent supermartingale because its expected increments are either 0 or $-Y(\gamma_n)$; convergence of the unconditional expectations $\E Y (\gamma_n)$ implies almost sure convergence of the expected increments, implying almost sure convergence of the supermartingale $\{ S_M \}$. The hypotheses of $(ii)$ imply that the increments of $S_M$ differ from the increments of $\log (1 / M_n)$ finitely often almost surely, implying convergence of the supermartingale $\log (1 / M_n)$ and hence $\nu_\TT \ll \mu_\TT$. $\Cox$ Survival function conditioned on the tree {#sec:g} ========================================= This section is concerned with estimating $g(\TT , p)$, a random variable measurable with respect to $\T$. We first prove an upper bound on $g$ which gives a uniform bound on the $L^q$ norm of $g$. Additionally, we show that conditioning on only the first $n$ levels gives a random variable exponentially close to $g$. Estimating this averaged random variable is a key element in the proof of Theorem \[th:main\], and is the content of section \[sec:bounds-E\]. The following result from @LP-book will be useful. \[\] \[th:res-prob\] For independent percolation, we have $$\frac{1}{\mathscr{R}(\rtt \leftrightarrow \infty) + 1} \leq \P_*[\rtt \leftrightarrow \infty] \leq \frac{2}{\mathscr{R}(\rtt \leftrightarrow \infty) + 1}$$ where $\mathscr{R}(\bf {0} \leftrightarrow \infty)$ denotes the effective resistance from $\bf 0$ to infinity when each edge $e$ with percolation parameter $p_e$ is given resistance $$r(e) = \frac{1 - p_e}{\prod\limits_{o < x \leq u}p_x}.$$ $\Cox$ From this, we deduce: \[pr:g-upper-bound\] For any $\ee \in (0,1 - p_c)$ and $\GW$-almost surely, $$g(\TT , p_c + \ee) < \frac{2 \ee \overline{W}}{(1 - p_c - \ee)p_c}$$ where $\overline{W} := \sup\limits_n W_n(\TT)$ \[Wbar-def\] is almost surely finite because $\lim_{n \to \infty} W_n$ exists almost surely. To get an upper bound on $g$, we need a lower bound on the resistance. For each height $n$, short together all nodes at this height. For every $p = p_c + \ee$ this gives a lower bound of $$\begin{aligned} \mathscr{R}(\rtt \leftrightarrow \infty) &\geq \sum\limits_{n = 1}^\infty \frac{1 - p_c - \ee}{Z_n (p_c + \ee)^n} \\ &= (1 - p_c - \ee) \sum\limits_{n = 1}^\infty \frac{p_c^n}{W_n(p_c + \ee)^n} \\ & \geq \frac{(1 - p_c - \ee)}{\overline{W}} \sum\limits_{n = 1}^\infty \frac{p_c^n}{(p_c + \ee)^n} \\ &= \frac{(1 - p_c - \ee)p_c}{\overline{W}\ee}. \end{aligned}$$ Using Theorem \[th:res-prob\], we get $$g(\TT,p_c + \ee) \leq \frac{2}{1 + \frac{(1 - p_c - \ee)p_c}{\overline{W} \ee} } \leq \frac{2\ee \overline{W}}{(1 - p_c - \ee)p_c}.$$ \[uniform $L^q$ bound\] Suppose the offspring has a finite $q$ moment. Then for any $\delta > 0$, there is a constant $c_q$ such that for all $\ee \in (0, 1 - p_c - \delta)$, $$\E g(\TT, p_c + \ee)^q \leq c_q \ee^q \,$$ where $c_q = c_q(\delta) > 0.$ First recall that if the offspring has a finite $q$-moment, then $M_q := \E W^q$ is finite as well. By the $L^q$ maximal inequality (e.g., @durrett4 [Theorem 5.4.3]), we have that $$\E\left[\left(\sup\limits_{1 \leq k \leq n} W_k \right)^q\right] \leq \left ( \frac{q}{q-1} \right )^q \E W_n^q \leq \left ( \frac{q}{q-1} \right )^q M_q$$ because $\{ W_n^q \}$ is a submartingale. Note that $\disp \left(\sup_{1 \leq k \leq n} W_k\right)^q \uparrow \overline{W}^q$ as $n \to \infty$. By monotone convergence, this implies $\E[ \overline{W}^q] \leq (q/(q-1))^q M_q$. In particular, for any $\ee < 1 - p_c - \delta$, this implies $$\E[g(\TT,p_c + \ee)^q] \leq \left(\frac{2\ee}{(1 - p_c - \delta)p_c} \right)^q \E[\overline{W}^q] \leq \left(\frac{2\ee}{(1 - p_c - \delta)p_c}\right)^q \left ( \frac{q}{q-1} \right )^q M_q \, ,$$ proving the proposition with $\disp c_q = \left ( \frac{2q}{(q-1)(1-p_c - \delta) p_c} \right )^q M_q$. $\Cox$ Let $\T_n$ denote $\sigma (\deg_v : |v| \leq n)$. Because $\T_n \uparrow \T$ and $g$ is bounded, we know that $\E [ g(\TT,p) \| \T_n ] \to g(\TT , p)$ almost surely and in $L^1$. It turns out that $g_n := \E [g(\TT,p) \| \T_n]$ is much easier to estimate that $g$ itself. Our strategy is to show this convergence is exponentially rapid, transferring the work from estimation of $g$ to estimation of $g_n$. \[lem:mean\] For any $\delta > 0$, there are constants $c_i > 0$ such that for all $p \in (p_c,\sqrt{p_c} - \delta)$ $$\big | \, g(\TT,p) - g_n(\TT,p) \, \big | \leq c_1 e^{-c_2 n}$$ with probability at least $1 - e^{-c_3 n}$. Define a random set $S = S(n,p)$ to be the set of vertices $v \in \TT_n$ such that $\rt \conn_p v$. Let $\pi_\TT$ denote the law of the random variable $S$, an atomic probability measure on the subsets of the random set $\TT_n$. Using $$g(\TT,p) = \P[H(p) \| \T] = \E \left [ \P [H(p) \| \F_n'] \| \T \right ]$$ where $\F_n'$ \[F\_n'-def\] be the $\sigma$-field generated by $\F_n$ and $\T$, we obtain the explicit representation $$\label{eq:f} g(\TT,p) = \sum_S \pi_\TT (S) \left [ 1 - \left ( \prod_{v \in S} (1 - g(\TT(v) , p) ) \right ) \right ] \, .$$ Order the vertices in $\TT_n$ arbitrarily and define the revealed martingale $\{ M_k \}$ by $$M_k := \E \left [ g(\TT,\ee) \| \T_n , \{ \TT(v_j) : j \leq k \} \right ]$$ as $k$ ranges from 0 to $|\TT_n|$. By definition, $M_0 = g_n$. Also, $M_{|\TT_n|} = g(\TT,p)$ because from $\T_n$ together with $\{ \TT(v) : v \in \TT_n \}$ one can reconstruct $\TT$. Arguing as in , we obtain the explicit representation $$\label{eq:M_k-rep} M_k = \sum_S \pi_{\TT}(S) \left[1 - \prod_{v \in S_{\leq k}}(1 - g(\TT(v),p) (1 - g(p))^{|S_{>k}|} \right]$$ where for a given set $S \subset \TT_n$, $S_{\leq k }$ denotes the vertices in $S$ indexed $\leq k$ and $S_{> k}$ denotes the set indexed $> k$. We claim the increments of $\{ M_k \}$ are bounded by $p^n$. Indeed, implies $$|M_{k+1} - M_k| \leq \sum_{S \ni v_k} \pi_{\TT(S)}|g(\TT(v_k),p) - g(p)| \leq \sum_{S \ni v_k} \pi_{\TT(S)} = \P[\rtt \conn_p v_k] = p^n.$$ Now the lemma without the factor of $\ee$ on the right-hand side follows from Azuma's inequality @azuma: the bounded differences yield Gaussian tails on $|M_{|\TT_n|} - M_0|$ with variance $|\TT_n| p^{2n}$, which is exponentially small in $n$ when $\mu p^2 < 1$. $\Cox$ Pivot Sequence on the Backbone {#sec:backbone} ============================== Markov property --------------- Define the shift function $\theta : \Omega \to \Omega$ by $$\label{eq:theta} (\theta (\omega))_v := \omega_{\gamma_1 \sqcup v} \, .$$ Informally, $\theta$ shifts the values of random variables at nodes $\gamma_1 \sqcup v$ in $T(\gamma_1)$ back to node $v$; these values populate the whole Ulam tree; values of variables not in $T(\gamma_1)$ are discarded; this is a tree-indexed version of the shift for an ordinary Markov chain. The $n$-fold shift $\theta^n$ shifts $n$ steps down the backbone. This subsection is devoted to several versions of the Markov property involving the shift $\theta$ as well as the limiting behavior of $\pivot_n:=\beta(\gamma_n)$. \[pivot\_n-def\] \[dual trees and pivots\] \[def:dual-piv\] Recall that $T(v)$ denotes the subtree from $v$, moved to the root. Let $T^*(v)$ \[dual-tree-def\] denote the rooted subtree induced on all vertices $w \notin T(v)$, and let $\dual_{v,w}$ represent the pivot of the vertex $w$ on $T^*(v)$, that is, the least $x$ such that $w$ is connected to infinity without going through $v$. The dual pivot \[dual-def\] $\dual_v$ is defined to be $\underset{w<v}{\text{min}}\ \dual_{v,w}$. In keeping with the notation for pivots, we denote $\dual_n := \dual_{\gamma_n}$. \[dual-n-def\] We define the following $\sigma$-fields.\ (i) For fixed $v \neq \rtt$, define \[CC\_v-def\] $\CC_v$ to be the $\sigma$-field generated by $\deg_w$ and $U_w$ for all $w \neq v$ in $T(v)$ along with $\deg_v$. Define $\BB_v^*$ to be the $\sigma$-field generated by all the other data: $U_w$ and $\deg_w$ for all $w \in \T^* (v)$, along with $U_v$. (ii) For $n \geq 1$, let $\BB_n^*$ denote the $\sigma$-field containing $\gamma_n$ and all sets of the form $\{ \gamma_n = v \} \cap B$ where $B \in \BB_v^*$. Informally, $\BB_n^*$ is generated by $\gamma_n$ and $\BB_{\gamma_n}^*$. (iii) Let $\CC_n$ \[CC\_n-def\] be the $\sigma$-field generated by $\theta^n \omega$; in other words it contains $\deg (\gamma_n)$ and all pairs $(\deg_{\gamma_n \sqcup x} , U_{\gamma_n \sqcup x})$. It is not important, but this definition does not allow $\CC_n$ to know the identity of $\gamma_n$. It is elementary that $\{ \BB_n^* \}$ is a filtration, that $\BB_n^* \cap \CC_n$ is trivial, and that $\BB_n^* \vee \CC_n = \F$. We define the following conditioned measures.\ (i) For $x \in (p_c,1)$, let $\QQ_x := (\P \| \pivot_0 \leq x)$ denote the conditional law given $\rtt \leftrightarrow_x \infty$, in other words, $\QQ_x [A] = \frac{g_A (x)}{g(x)}$ where $$g_A (x) := \P [A \cap \{ \pivot_0 \leq x \} ] \, .$$ (ii) Let $\cL$ denote the law of $\pivot_0$, the pivot at the root. By @durrett4 [Theorem 5.1.9], one may define regular conditional distributions $\P_x := (\P \| \pivot_0 = x)$. These satisfy $\P_x [\pivot_0 = x] = 1$ and $\int \P_x \, \,d\cL(x) = \P$. Also, $\QQ_y = (1/g(y)) \int \P_x \,d\cL|_{[0,y]} (x)$. A common null set for all the conditioned measures is the set where either the invasion ray is not well defined or $\pivot (v) = \dual_v$ for some $v$. Statements such as below are always interpreted as holding modulo this null set. \[Markov property for dual pivots\] \[pr:markov 2\] \ (i) For any $A \in \F$, $$\P [\theta^n \omega \in A \| \BB_n^*] = \QQ_{\dual_n} [A] \, .$$ (ii) More generally, if $0 < y \leq 1$ then for any $A \in \F$, $$\QQ_y [\theta^n \omega \in A \| \BB_n^*] = \QQ_{\dual_n \wedge y} [A] \, .$$ (iii) Under $\P$, the sequence $\{ \dual_n \}$ is a time homogeneous Markov chain adapted to $\BB_n^*$ with transition kernel $p(x,S) = \QQ_x [\beta_1^* \wedge x \in S]$ and initial distribution $\delta_1$. <span>Proof:</span> $(i)$ By definition of conditional probability, the conclusion is equivalent to $\P [\theta^n \omega \in A ; G] = \int_G \QQ_{\beta_n^*} [A] \, d\P$ for all $G \in \BB_n^*$. Writing $G$ as the countable union of $\BB_n^*$-measurable sets $\bigcup_v (G \cap \{ \gamma_n = v \})$, it suffices to verify the previous identity for each piece $G \cap \{ \gamma_n = v \}$. By the definition of $\BB_n^*$, each of these may be written as $\{ \gamma_n = v \} \cap B^*$ for $B^* \in \BB_v^*$. Thus, it suffices to prove $$\label{eq:cond prob 2} \int_{\{ \gamma_n = v \} \cap B^*} \QQ_{\dual_v} [A] \, d\P = \int_{\{ \gamma_n = v \} \cap B^*} \one_A (\theta^n \omega) \, d\P$$ for all $v \in T_n$, $B^* \in \BB_v^*$ and $A \in \F$. Fixing $v$, identify $(\Omega , \F , \P)$ as a product space $(\Omega_1 , \F_1 , \P_1) \times (\Omega_2 , \F_2 , \P_2)$ where $\Omega_1 = (\N \times [0,1])^{T(v) \setminus \{ v \}} \times \N$ and $\Omega_2 = (\N \times [0,1])^{T^*(v)} \times [0,1]$. Let $\pi_i : \Omega \to \Omega_i$ denote the coordinate maps; then $\pi_2$ is a measure preserving map on $(\Omega , \BB_v^* , \P)$ and $\pi_1$ is a measure preserving map on $(\Omega , \CC_v , \P)$. In particular, $B^* = \pi_2^{-1} B$ for some $B \in \F_2$. Working on the left-hand side of , observe that $\pivot \circ \pi_2 = \dual_v$ and hence, if we let $H$ represent the event that the invasion percolation ever gets to $v$, then we have $$\label{eq:pivot < dual} \{ \gamma_n = v \} = \{ \pivot (v) \leq \dual_v \}\cap H = \{ \pivot_0 (\pi_1 \omega) < \dual_v (\pi_2 \omega) \}\cap H\, .$$ Using this, we obtain $$\begin{aligned} \int_{\{ \gamma_n = v \} \cap B^*} \QQ_{\dual_v} [A] \, d\P & = & \int_\Omega \one_B (\pi_2 \omega) \one_{\left\{\pivot (\pi_1 \omega) < \dual_v (\pi_2 \omega)\right\}\cap H} \QQ_{\dual_v (\pi_2 \omega)} [A] \, d\P \\[1ex] & = & \int_{\Omega_2} \one_B (\omega_2) \QQ_{\dual_v (\omega_2)} [A] \left [ \int_{\Omega_1} \one_{\left\{\pivot (\omega_1) < \dual_v (\omega_2)\right\}\cap H_2} \, d\P_1 (\omega_1) \right ] \, d\P_2 (\omega_2) \\[1ex] & = & \int_{\Omega_2} \one_B (\omega_2) \frac{g_A (\dual_v (\omega_2))}{g(\dual_v (\omega_2))} \left [ \int_{\Omega_1} \one_{\left\{\pivot (\omega_1) < \dual_v (\omega_2)\right\}\cap H_2} \, d\P_1 (\omega_1) \right ] \, d\P_2 (\omega_2) \end{aligned}$$ where $H_2$ above denotes $\pi_2(H)$. The integral over $\Omega_1$ is equal to $g(\dual_v (\omega_2)) \one_{H_2}(\omega_2)$ so we may simplify and continue. Writing $g_A (x)$ as $\int_{\Omega_1} \one_{A \cap \{ \pivot_0 < x \}} (\omega) \, d\P_1 (\omega)$ in the second line, is finished as follows. $$\begin{aligned} \phantom{\int_G \QQ_{\dual_v} [A] \, d\P} & = & \int_{\Omega_2} \one_B (\omega_2) g_A (\dual_v (\omega_2)) \one_{H_2}(\omega_2) \, d\P_2 \\[1ex] & = & \int_{\Omega_1 \times \Omega_2} \one_B (\omega_2) \one_A (\omega_1) \one_{\pivot (\omega_1) < \dual_v (\omega_2)} \one_{H_2}(\omega_2) \, d\P_1 (\omega_1) \, d\P_2 (\omega_2) \\[1ex] & = & \int_{\{ \gamma_n = v \} \cap B^*} \one_A (\pi_1 \omega) \, d\P \\[1ex] & = & \int_{\{ \gamma_n = v \} \cap B^*} \one_A (\theta^n \omega) \, d\P\end{aligned}$$ because $\pi_1 \omega = \theta^n \omega$ on $\{ \gamma_n = v \}$. $(ii)$ Begin with the observation that $$\label{eq:decomp} \{ \pivot_0 < y \} \cap \{ \gamma_n = v \} = \{ \pivot (\pi_1 \omega < y) \} \cap \{ U_w < y \mbox{ for all } w \leq v \} \cap \{ \pivot (\pi_1 \omega) < \dual_v (\pi_2 \omega) \}\cap H \, .$$ As before, letting $G = \{ \gamma_n = v \} \cap \pi_2^{-1} (B)$, we aim to prove the second identity in $$\label{eq:cond prob 3} \int_G \QQ_{\dual_v \wedge y} [A] \, d\QQ_y = \int_G \frac{g_A (\dual_v \wedge y)}{g (\dual_v \wedge y)} \, d\QQ_y = \int_G \one_A (\theta^n \omega) \, d\QQ_y \, ,$$ the first being definitional. Also by definition, $\QQ_y [\cdot] = (1/g(y)) \P [\cdot \cap \{ \pivot_0 < y \}]$, whence, using , the left-hand side of becomes $$\frac{1}{g(y)} \int_{\Omega_1 \times \Omega_2} \one_{B\cap H_2} (\omega_2) \; \one_{U_w < y \forall w \leq v} (\omega_2) \; \frac{g_A (\dual_v (\omega_2) \wedge y)}{g (\dual_v (\omega_2) \wedge y)} \; \one_{\pivot (\omega_1) < y} \; \one_{\pivot (\omega_1) < \dual_v (\omega_2)} \; d(\P_1 \times \P_2) \, .$$ Integrating over $\Omega_1$ turns the last two indicator functions into $g(\dual _v (\omega_2) \wedge y)$, again canceling the denominator and yielding $$\frac{1}{g(y)} \int_{\Omega_2} \one_B (\omega_2) \; \one_{U_w < y \forall w \leq v} (\omega_2) \; g_A (\dual_v (\omega_2) \wedge y) \one_{H_2}(\omega_2) \, d\P_2 (\omega_2) \, .$$ Rewriting $g_A (x)$ as $\int_{\Omega_1} \one_{A \cap \{ \pivot_0 < x \}} \, d\P_1$, this becomes $$\frac{1}{g(y)} \int_{\Omega} \one_B (\pi_2 \omega) \; \one_{U_w < y \forall w \leq v} (\pi_2 \omega) \; \one_{\pivot (\pi_1 \omega) < \dual_v (\pi_2 \omega)} \; \one_{\pivot (\pi_1 \omega) < y} \; \one_A (\omega_1) \one_{H_2}(\omega_2) \; d\P \, .$$ Observing that the first three indicator functions define $G$, this simplifies to $$\begin{aligned} \frac{1}{g(y)} \int_{G \cap \left\{ \pivot_0 (\omega) < y \right\}} \one_A (\pi_1 \omega) \, d\P & = & \frac{1}{g(y)}\int_G \one_A(\pi_1 \omega) \one_{\pivot_0 < y}(\omega) \, d\P \\[1ex] & = & \int_G \one_A(\pi_1 \omega) \, d\QQ_y \\[1ex] & = & \int_G \one_A(\theta^n \omega) \, d\QQ_y \, \end{aligned}$$ where the last inequality follows from the fact that $\gamma_n=v$ on $G$, which implies $\pi_1 \omega = \theta^n \omega$. Hence, that completes the proof of $(ii)$. $(iii)$ Begin by observing that $\gamma_{n+1} = v \sqcup j$ if and only if $\gamma_n = v$ and $\pivot (v \sqcup j) < \dual_1 \circ \pi_1$. In other words, given that the backbone contains $v$, the next backbone vertex depends only on $\theta^n \omega$ and is chosen in the same way the first backbone vertex of $\omega$ was chosen. From this it follows that $$\dual_{n+1} = \dual_n \wedge \dual_1 \circ \theta^n \, .$$ Therefore, $$\begin{aligned} \P [\dual_{n+1} \in S \| \BB_n^*] & = & \P [\dual_n \wedge (\dual_1 \circ \theta^n) \in S \| \BB_n^*] \\[1ex] & = & \P [\theta^n \omega \in \{ \omega' : \dual_1 \omega' \wedge \dual_n (\omega) \in S\} \| \BB_n^*] \\[1ex] & = & \QQ_y [\dual_1 \wedge y \in S] \|_{y = \dual_n}\end{aligned}$$ as desired. $\Cox$ $Remark.$ Note that the final equality in the proof of $(iii)$ does not immediately follow from the proof of $(i)$ since $\{\omega':\dual_1\omega' \wedge \dual_n\omega\in S \}$ is not a fixed set, but rather depends on $\dual_n$. Nevertheless, the proof of this equality follows from a slight modification of the proof of $(i)$, where we simply replace the expressions $\QQ_{\dual_v(\pi_2\omega)}[A]$, $g_A(\dual_v(\omega_2))$, and $\one_A(\pi_1\omega)$ by the expressions $\QQ_{\dual_v(\pi_2\omega)}[\dual_1 \wedge \dual_v \in S]$, $\P[\{\pivot_0<\dual_v(\omega_2)\}\cap \{\dual_1 \wedge \dual_v\in S \}]$, and $\one_{\{\dual_1(\pi_1\omega) \wedge\dual_v(\omega)\in S \} }$ respectively. It is immediate that $\QQ_x \ll \P$ for all $x$. The following more quantitative statement will be useful. \[pr:variance\] Let $q > 1$ and suppose that the offspring distribution has a finite $q$-moment. Then there exists a constant $C_q$ such that for all $A \in \T$ and for all $\delta > 0$ and all $x \in (p_c,1)$, $$\P [A] \leq \delta \; \text{ implies } \; \QQ_x [A] \leq C_q \delta^{1 - 1/q} \, .$$ On $\T$, the density of $\QQ_x$ with respect to $\P$ is given by $$\frac{d\QQ_x}{d\P} (T) = \frac{g(T,x)}{g(x)} \, .$$ Combining Corollary \[cor:dersurvprob\], which implies $g(x) \sim K x$, with Proposition , which shows $\int g(T,p_c + \ee)^q \, d\GW(T) \leq c_q \ee^q$ provided $p_c + \epsilon$ is bounded away from $1$, we see that $$\int \left | \frac{d\QQ_x}{d\P} (T) \right |^q \, d\GW (T) \leq c_q'$$ for some constant $c_q'$ and all $x \in (0,1)$. Applying H<span>ö</span>lder's inequality with $1/p + 1/q = 1$ then gives $$\QQ_x [A] = \int \one_A \frac{d\QQ_x}{d\P} \; d\P \leq \left [ \int \one_A \, d\P \right ]^{1/p} \left [ \int \left ( \frac{d\QQ_x}{d\P} \right )^q \, d\P \right ]^{1/q} \leq C_q \delta^{1-1/q}$$ when $C_q = (c_q')^{1/q}$. $\Cox$ The measures $\P_x$ are in some sense more difficult to compute with than $\QQ_x$ because of the conditioning on measure zero sets. Relations such as the Markov property, however, are conceptually somewhat simpler. The following statement of the Markov property generalizes what was proved in @angel-invasion2008 [Theorem 1.2 and Proposition 3.1], with $\BB_n^+$ representing the $\sigma$-field generated by $\BB_n^*$ together with $\pivot_n$. \[Markov property for pivots\] \[pr:markov\] For any $A \in \F$, $$\P \left [ \theta^n \omega \in A \| \BB_n^+ \right ] = \P_{\pivot_n} [A]$$ on $(\Omega , \F , \P_x)$. By definition of conditional probability, the conclusion is equivalent to $$\label{eq:cond prob} \P [B \cap \{ \theta^n \omega \in A \}] = \int_B \P_{\pivot_n} [A] \, d\P \,$$ holding for all $B \in \BB_n^+$ and $A \in \F$. It is enough to prove for sets that are subsets of $\{ \gamma_n = v \}$ for some $v$: if it holds for sets of this form, then $$\begin{aligned} \P [B \cap \{ \theta^n \omega \in A \}] & = & \sum_v \P [B \cap \{ \gamma_n = v \} \cap \{ \theta^n \omega \in A \}] \\ & = & \sum_v \int_{B \cap \{ \gamma_n = v \}} \P_{\pivot_n} [A] \, d\P \\ & = & \int_B \P_{\pivot_n} [A] \, d\P \, . \end{aligned}$$ We now fix $v$ and assume without loss of generality that $B \subseteq \{ \gamma_n = v \}$. The identity we need to prove now reduces to $$\label{eq:fix v} \P [B \cap \{ \sigma^v \omega \in A \}] = \int_B \P_{\pivot(v)} [A] \, d\P$$ and we need to show it holds for all $B \in \BB_v^+$ where we recall $\BB_v^+$ denotes the $\sigma$-field generated by $\BB_v^*$ together with $\pivot_v$ and $\sigma^v$ denotes \[shift-def\] shifting to $v$. We claim it is enough to prove for sets $B$ of the form $B_1 \times B_2$ where $B_2 = \{ \pivot (v) \leq b\}$ and $B_1$ is an element of $\BB_v^*$ contained in the event $\{ \dual_v \geq a \}$ for real numbers $0 < b < a < 1$. To see why this is enough, observe that the set of all $B$ for which holds is a $\lambda$-system, meaning it is closed under increasing union and set theoretic difference of nested sets. The class of sets of the form
{'source': 'arXiv_out/1711'}