ac3541f
==============================================================================
BROWNIAN CONTINUUM RANDOM TREE LIMITS OF FINITE FORTUIN-KASTELEYN MAPS
ABOVE FOUR - A COMPLETE PROOF
==============================================================================
Self-contained. Every claim that matters is proved. Every outside
theorem is named precisely with a reference.
CONTENTS
Part 0 What we are proving, and why it is surprising
Part 1 The inventory model and the finite word identity
Part 2 Strict drift: forcing E K < 1
Part 3 Ladder cuts and the coefficient lower bound
Part 4 The block tree: criticality and finite variance
Part 5 Conditioned trees and uniform path sums
Part 6 From block tree to map distances; assembling the main theorem
==============================================================================
PART 0. WHAT WE ARE PROVING, AND WHY IT IS SURPRISING
==============================================================================
A PLANAR MAP is a connected graph drawn on the sphere with no edge
crossings. Two drawings count as the same map if one can be deformed
into the other. A ROOTED map is a map with one directed edge (a "dart")
distinguished. Loops and parallel edges are allowed.
The FORTUIN-KASTELEYN (FK) weight puts a factor on each edge subset
A of a map M:
w(M, A) = q^{ k_M(A) + (|A| - |V(M)|)/2 },
where k_M(A) counts connected components of the spanning graph with
edge set A (every isolated vertex is a component). Here q > 4 is
fixed.
The FK PARTITION FUNCTION is
Z_{n,q} = sum_{|E(M)| = n} sum_{A subset E(M)} w(M, A),
and (M_n, A_n) is a uniform sample of weight w from all pairs with
|E(M)| = n.
We study the metric on V(M_n) using ALL edges of M_n (not just A_n):
graph distance d_n, rescaled by c(q) / sqrt(n) for a constant c(q) > 0
that depends only on q. Probability is the DEGREE MEASURE
mu_n( {v} ) = deg_{M_n}(v) / (2n).
A loop counts twice in the degree. This is the "size biased by degree"
measure, natural because darts are uniform.
The claim (Theorem A below) is that this rescaled metric probability
space ALWAYS converges to one universal object: the BROWNIAN CONTINUUM
RANDOM TREE (CRT). The CRT is obtained from a standard Brownian
excursion e on [0, 1] by defining
d_e(s, t) = e(s) + e(t) - 2 min_{r in [s^t, s v t]} e(r),
taking the quotient by d_e = 0, and pushing Lebesgue measure forward.
Write (T_e, d_e, mu_e) for that metric probability space.
Why this is SURPRISING at first glance:
- Maps with n edges can contain an enormous number of cycles.
- At q > 4 the FK weight favours many SMALL clusters, so the
decoration A_n is not itself tree-like.
- Nevertheless, after rescaling distances by n^{-1/2}, all those
cycles vanish. The limiting object is purely tree-like.
Why it is ACTUALLY PLAUSIBLE:
- At every n the FK-weighted marginal on M_n is an instance of a
simply generated random map with a specific block weight (Part 4
says exactly which).
- Once such a map is conditioned on its size, its 2-connected blocks
assemble into a critical Galton-Watson tree with finite offspring
variance, and such trees converge to the CRT (Aldous 1993).
- Remaining work: control the distance marks that blocks contribute
to ancestral paths uniformly, and identify the constant c(q).
MAIN THEOREM (Theorem A).
Fix q > 4. There is a deterministic constant c(q) in (0, infinity)
such that, as n -> infinity through positive integers,
( V(M_n), c(q) n^{-1/2} d_n, mu_n ) ==> ( T_e, d_e, mu_e )
in the Gromov-Hausdorff-Prokhorov topology on compact metric
probability spaces modulo measure-preserving isometry.
Root and FK decoration are forgotten; only the metric and the degree
measure are compared.
HOW THE PROOF IS STRUCTURED
Stage 1. (Part 1.) Encode the FK sum as the probability that a
certain random word of letters "matches completely".
This is Sheffield's inventory model. It gives a bijection
and a weight computation.
Stage 2. (Parts 2-3.) Prove strict inventory drift, then use it
to prove a square-root LOWER bound on the map coefficient
series. Combined with a Catalan UPPER bound, this
sandwiches the generating function at the correct point.
Stage 3. (Part 4.) Block-decompose a map into its 2-connected
pieces. Prove the exact corner-substitution equation for
the generating function. Feed Stage 2 bounds in to prove
(a) criticality and (b) finite offspring variance.
Stage 4. (Part 5.) Under finite variance, the depth-first
sequence (height and contour) of the conditioned
Galton-Watson tree converges jointly to the Brownian
excursion.
Stage 5. (Part 6.) Prove a UNIFORM law of large numbers for the
block-distance marks accumulated along ancestral paths.
Convert back to map distances. Identify the degree
measure EXACTLY with uniform mass on nonroot tree nodes.
Then combine Stages 1-5 with the Gromov-Hausdorff-
Prokhorov correspondence lemma (subsection 6.8).
The whole argument boils down to three inequalities:
(i) a_n u^n <= C_1 (n+1)^{-3/2} [Catalan]
(ii) sum n a_n u^n x^n >= C_2 (1-x)^{-1/2} [Ladder]
(iii) Phi''(v) < infinity [finite variance]
(i) and (ii) sandwich the generating function at the endpoint; (iii)
makes the CRT limit go through without a third or higher moment.
Constant c(q) is identified explicitly at the end:
c(q) = sigma / ( 2 sqrt(2) beta ),
where sigma^2 is the finite variance of the critical offspring law
and beta > 0 is the mean block-distance per generation along the
size-biased spine.
==============================================================================
PART 1. THE INVENTORY MODEL AND THE FINITE WORD IDENTITY
==============================================================================
Fix q > 4. Define
t = sqrt(q), p = t/(t+2), u = (1-p)/16.
Because q > 4, t > 2, so p > 1/2; p < 1 because t is finite:
1/2 < p < 1. (1.1)
We also record t = 2p/(1-p), used when comparing flexible to fixed
orders.
1.1. THE MAP WEIGHT
For a rooted connected planar map M with at least one edge, set
a(M) = sum_{A subset E(M)} t^{2 k_M(A) + |A| - |V(M)| - 1}. (1.2)
For the trivial one-vertex zero-edge map, set a(trivial) = 1. Since
w(M, A) = t * t^{2 k_M(A) + |A| - |V(M)| - 1},
we have w(M, A) = t a(M). The factor t is the same for every map, so
conditioning on |E(M)| = n gives
P(M_n = M) is proportional to a(M) among n-edge rooted maps. (1.3)
Define
a_n = sum_{|E(M)| = n} a(M), a_0 = 1. (1.4)
Everything below is a statement about (a_n) alone.
1.2. LETTERS AND REDUCTION
Take an independent word over the five-letter alphabet {b1, b2, o1,
o2, F} with probabilities
P(b1) = P(b2) = 1/4,
P(o1) = P(o2) = (1-p)/4,
P(F) = p/2. (1.5)
Check: 1/4 + 1/4 + (1-p)/4 + (1-p)/4 + p/2 = 1.
Reading the word left to right, run this inventory:
b_i ("burger of type i"): push a new type-i burger onto
the type-i stack (freshest =
most recent).
o_i ("fixed order of type i"): remove the freshest type-i
burger. If none, the order is
UNFILLED and stays unfilled
forever.
F ("flexible order"): remove the single freshest burger
of EITHER type. If none, unfilled
forever.
The REDUCTION of a finite word is
(unfilled orders in chronological order)
followed by
(surviving burgers in chronological order).
An EMPTY-REDUCING word has empty reduction. An empty-reducing word
has equal total "burgers seen" (with F's later typed) and "orders
seen"; in particular its length is even.
1.3. REDUCTION IS LOCAL
LEMMA 1.1 (Reduction above older supply).
Feed a finite word an arbitrary older list of burgers. Every match
between two letters of the word is exactly the match that would occur
from an empty initial supply. Orders that were unfilled with empty
initial supply act on the older list one at a time, in their original
order. Surviving new burgers lie strictly above surviving old burgers.
Consequence: finite words may be replaced by their reductions when
concatenated. Once a suffix has a fresh survivor, that survivor is
unchanged by prepending further letters.
Proof. Call burgers created inside the word NEW. If any new burger is
available, it is fresher than every old burger, so it wins. Thus the
new-burger supply evolves exactly as in the empty starting case. Only
orders with no eligible new burger can touch the old supply, and they
touch it in their original order. Surviving new burgers sit above all
surviving old ones. For the last sentence, first evaluate the prepended
word then apply the concatenation rule. []
1.4. THE FINITE WORD IDENTITY (STATEMENT)
THEOREM 1.2 (Finite word identity).
For every integer n >= 0,
P( a length-2n independent word is empty-reducing ) = a_n u^n. (1.6)
Interpretation. The right side is the product of the total map
coefficient a_n (1.4) and the word weight u^n of one canonical match:
each matched "burger + fixed order" pair contributes probability
(1/4)((1-p)/4) = (1-p)/16 = u.
The proof, in the next subsection, gives a bijection between empty-
reducing words and rooted planar maps together with a distinguished
spanning tree, plus an activity expansion of a(M).
1.5. PROOF OF THEOREM 1.2
We build a weight-preserving bijection from empty-reducing words to
(map, spanning tree) pairs, then sum.
STEP A. Identify what the F's consume.
Given an empty-reducing word, replace each F by the type of the burger
it consumed. The result is an IDENTIFIED WORD over {b1, b2, o1, o2}.
Claim: for each type i, the type-i letters (b_i openers, o_i closers)
form a Dyck word: at every prefix #openers >= #closers, ending equal,
matched by usual stack pairing. This is exactly the inventory rule.
Conversely, every shuffle (in the original letter order) of two Dyck
words comes from exactly one empty-reducing word: type each F to the
type of the paired burger. This is a bijection between empty-reducing
5-letter words and shuffles of two Dyck words. *
STEP B. Bijection with (map, spanning tree).
Claim: shuffles of two Dyck words biject with pairs (M, T) where M is
a rooted planar map and T is a spanning tree of M with |E(M)|-1 edges.
MAP + TREE -> WORD (forward construction).
Trace the boundary of a small regular neighbourhood of T, starting at
the root dart, in the orientation of the sphere, using this tour rule:
- at a tree-dart, cross the edge and continue at the successor of
the opposite dart around the opposite vertex;
- at a non-tree dart, continue at the successor of that dart around
the same vertex.
The tour visits every dart of M exactly once. Record:
1st visit to a tree edge -> b1; 2nd visit -> o1.
1st visit to a non-tree edge -> b2; 2nd visit -> o2.
Tree pairs are noncrossing in tour order (tree edges nest in the
thickened contour). Non-tree pairs are noncrossing (they are disjoint
arcs in the complementary disk). So we obtain a shuffle of two Dyck
words. The first dart determines the rooting. *
WORD -> MAP + TREE (reverse construction).
Rebuild the plane tree T from the type-1 Dyck word by descending at
b1 (new vertex) and returning at o1 (parent). Insert the type-2 stubs
(open b2, close o2) between consecutive tree steps in the order the
word indicates. Match the type-2 stubs in the complementary disk by
the noncrossing pairing forced by the type-2 Dyck structure.
Noncrossing matching determines the arcs up to orientation-preserving
homeomorphism, giving a unique rooted planar map. Verify:
- Vertex rotation: if alpha pairs matched positions and tau is the
cyclic successor, the reconstructed successor map is tau o alpha
at tree darts and tau at non-tree darts. *
- This unpicks Step B's forward map exactly. So we have an inverse.
Count: with n matched pairs, we have n edges in M, n-1 tree edges.
STEP C. Weight of one identified word.
A fully identified word with n fixed-order closes has probability
((1/4)((1-p)/4))^n = u^n. If a close o_i is replaced by a flexible F,
the probability factor becomes p/2, so that pair contributes
(1/4)(p/2) = p/8 instead of u. The ratio is
(p/8) / u = (p/8) / ((1-p)/16) = 2p / (1-p) = t.
So the sum of word-probabilities over all pre-typings of the F's for
one fixed identified word is
u^n (1 + t)^{b(M, T)}, (1.7)
where b(M, T) counts the ACTIVE edges: edges whose close COULD be
typed as F without changing the match.
STEP D. Which edges are active?
Two edges CROSS in tour order if their occurrences alternate
(c < a < d < b or a < c < b < d). Crossing edges necessarily have
opposite types (one tree, one non-tree).
Call edge e (occurrences a < b) ACTIVE if it crosses no edge whose
first occurrence is later than b.
Claim: e is active <=> its close could be made flexible, i.e. at
close time its burger was the single freshest.
Proof. The obstruction to flexibility is another edge with events
c < a < d < b or a < c < b < d, i.e. a crosser with d > b. Conversely,
if no such crosser exists, induction through the word shows its burger
is the freshest at close time. So "active" = "flexibility permitted"
STEP E. Deletion-contraction for a(M).
For any edge e of M:
a(M) = a(M/e) + a(M\e) if e is neither bridge nor loop,
a(M) = (1+t) a(M/e) if e is a bridge,
a(M) = (1+t) a(M\e) if e is a loop. (1.8)
where M/e = contraction, M\e = deletion.
Proof of (1.8). Direct from (1.2):
- Nonbridge nonloop: pairs A not containing e and A containing e
correspond to subsets of E(M\e) and E(M/e) via contracting e.
Contracting a present nonloop drops |A| and |V| both by 1, leaving
the exponent 2k+|A|-|V|-1 unchanged. So the two branches match.
- Bridge: contraction makes no cycle change; the term without e
has factor 1, the term with e has factor t, summing to (1+t)
times the contracted sum.
- Loop: including e multiplies the corresponding deleted term by t.
Terminal one-vertex map has weight 1. *
STEP F. Sum over spanning trees.
Sum (1.8) over the contour tour of the map, choosing contract vs
delete as the tour first reaches each edge. Bridges and loops are
forced. Invariant: contractions form a forest; deletions of nonbridges
keep the residual graph connected. So every partial branch has a
spanning-tree completion agreeing with the partial tour.
Consequently: the recursion produces each spanning tree of M exactly
once, with each forced (i.e. active) edge contributing factor (1+t).
Therefore:
a(M) = sum_{T spanning tree of M} (1+t)^{b(M, T)}. (1.9)
Check with (1.8): substituting (1.9) both sides of (1.8) sum over
spanning trees of M\e / M/e; the recursion is exactly the deletion-
contraction recursion of Trees, giving the same sum. *
STEP G. No symmetry factors.
An automorphism of a rooted map fixing the root dart, edge pairing
and vertex rotations fixes every dart by connectedness. So the number
of (map, tree, marking) triples counted in (1.7) is exactly (1.9),
with no symmetry division. *
FINISH. Summing over empty-reducing words:
sum over empty-reducing words of length 2n of P(word)
= sum over (map M, tree T of M) with |E(M)| = n of u^n (1+t)^{b(M,T)}
= u^n sum over n-edge maps of a(M) (by (1.9))
= u^n a_n. (1.10)
This is (1.6). End of proof. []
COROLLARY 1.3 (Catalan upper bound).
For every n >= 0,
a_n u^n <= C(2n, n) / (4^n (n+1)) = O( (n+1)^{-3/2} ). (1.11)
In particular, T(z) = sum a_n z^n converges at z = u;
Tau := T(u) < infinity.
Proof. An empty-reducing word has nonnegative running #burgers -
#orders, ending at zero. The number of +1/-1 sequences of length 2n
with that property is the Catalan number C_n = (1/(n+1)) C(2n, n).
Divide by 4^n (total sign balance has probability 2^{-2n} = 1/4^n
conditional on sign sequence). Stirling gives (1.11). []
==============================================================================
PART 2. STRICT DRIFT: FORCING E K < 1
==============================================================================
We scan an independent word BACKWARDS from a fixed boundary. This is
the tool that feeds the ladder-cut argument in Part 3.
2.1. THE SETUP
Reveal letters backwards, prepending one letter at a time. Let
S_j = (burgers among first j reversed letters)
- (orders among first j reversed letters), S_0 = 0.
Let
J = inf { j >= 1 : the revealed suffix has a surviving burger }. (2.1)
LEMMA 2.1 (Structure at time J).
At time J, the reduction of the reversed suffix is exactly
(one surviving burger) ++ (K fixed orders of the OPPOSITE type),
where K is some nonnegative integer. In particular,
S_J = 1 - K. (2.2)
Proof. Before time J, the suffix has no survivors: only unfilled
orders. So the triggering letter at time J must be a burger. It
survives precisely when no currently-unfilled order can consume it.
Those unfilled orders must all be of the OPPOSITE type. There are K
of them, still unfilled. The single surviving burger plus K orders
gives S_J = 1 - K. []
2.2. CRUDE INTEGRABILITY
LEMMA 2.2.
J < infinity a.s., and E K <= 1.
Proof. If S_j = 1, there is a burger more than there are orders, so
some burger has survived. Therefore J is at most the first hitting
time of level +1 by the simple symmetric walk S. That hitting time is
finite a.s. (stop between -r and +1, let r -> infinity).
For the bound, stop at J ^ m. The increments have mean zero, so
E[ -S_m ; J > m ] = E[ 1 - K ; J <= m ]. (2.3)
On {J > m}, there are no survivors, so S_m <= 0. Hence
E[ K ; J <= m ] <= P(J <= m).
Monotone convergence gives E K <= 1. []
2.3. STRICTNESS VIA STATIONARY TYPING
Setup: a two-sided i.i.d. word (omega_i)_{i in Z} with the letter law
(1.5). For each integer boundary i (just before omega_i), scan backwards
and let T_i be +1 if the freshest survivor is type 1, -1 if type 2.
Lemma 2.2 plus a countable intersection makes this possible a.s. for
every i simultaneously.
DEFINE the signed increment
D_i = +1 if omega_i in {b1, o2},
D_i = -1 if omega_i in {b2, o1},
D_i = -T_i if omega_i = F. (2.4)
Key properties:
(A) (D_i) is strictly stationary (construction is shift-covariant).
(B) D_i depends only on raw letters up to index i.
(C) Matched pairs contribute ZERO to any finite sum of D's.
Proof: by Lemma 1.1 a matched pair inside the word is
unaffected by any older supply, so the flexible typing of the
pair matches; +1 and -1 cancel.
Fix boundary 0 in the word. Use J, K, T = T_0 for the backwards scan
at boundary 0, and define
D^(m) = sum_{i = -m}^{-1} D_i. (2.5)
LEMMA 2.3 (Covariance bound).
For all m >= 1,
E[ T D^(m) ] >= 2 E[ K ; J <= m ]. (2.6)
Proof. Bound the sum D^(m) by splitting at -j when J = j <= m.
On {J = j <= m}:
- The last j letters have signed-type sum T (1 + K): the one
surviving burger contributes sign T, and each of the K unfilled
orders (all of type OPPOSITE) also contributes sign T.
- The earlier sum sum_{i = -m}^{-(j+1)} D_i depends only on raw
letters before -j, which is INDEPENDENT of the final j letters
(they determine {J = j} and T).
- Type exchange symmetry: interchanging types 1 and 2 preserves
the event {J = j} as a set and reverses T. So E[T 1_{J = j}] = 0,
hence the earlier sum contributes zero in expectation against T.
So on {J = j}, multiplying by T, the contribution from the final j
letters is T * T (1 + K) = 1 + K, and the earlier contribution
vanishes in expectation.
On {J > m}: no survivor, so the reduced suffix is orders-only.
Matched pairs cancel. So |D^(m)| <= (number of unfilled orders)
= -S_m. Hence
E[ T D^(m) ; J > m ] >= -E[ -S_m ; J > m ] = E[ S_m ; J > m ].
Combine:
E[ T D^(m) ] >= E[ 1 + K ; J <= m ] + E[ S_m ; J > m ]
= E[ 1 + K ; J <= m ] - E[ -S_m ; J > m ] (S_m <= 0)
= E[ 1 + K ; J <= m ] - E[ 1 - K ; J <= m ] (2.3)
= 2 E[ K ; J <= m ]. []
LEMMA 2.4 (Variance increments).
Let V_m = E[ (D^(m))^2 ]. Then
V_{m+1} - V_m = 1 - p E[ T D^(m) ]
<= 1 - 2 p E[ K ; J <= m ]. (2.7)
Proof. By stationarity,
E[ ( sum_{i=-m}^{0} D_i )^2 ] = V_{m+1},
and expanding the square gives
V_{m+1} = V_m + 2 E[ D^(m) D_0 ] + E[ D_0^2 ]
= V_m + 2 E[ D^(m) D_0 ] + 1,
so
V_{m+1} - V_m = 1 + 2 E[ D^(m) D_0 ]. (2.8)
Now compute E[ D_0 | past ] where "past" means raw letters up to
index -1. Given the past, D^(m) is fixed; only D_0 is random.
omega_0 in {b1, o2}: D_0 = +1, probability 1/4 + (1-p)/4 = (2-p)/4.
omega_0 in {b2, o1}: D_0 = -1, probability (2-p)/4.
omega_0 = F: D_0 = -T, probability p/2.
The two nonflexible cases cancel in the conditional mean, leaving
E[ D_0 | past ] = -(p/2) T.
Therefore
E[ D^(m) D_0 ] = E[ D^(m) * (-(p/2) T) ] = -(p/2) E[ T D^(m) ].
Substituting in (2.8) and applying Lemma 2.3:
V_{m+1} - V_m = 1 - p E[ T D^(m) ]
<= 1 - 2 p E[ K ; J <= m ]. []
PROPOSITION 2.5 (Strict drift).
J < infinity a.s., and
E K <= 1 / (2p) < 1. (2.9)
Proof. J < infinity a.s. is Lemma 2.2.
Suppose 2p E K > 1. By monotone convergence,
2p E[ K ; J <= m ] -> 2p E K > 1, so for some eta > 0 and all m large,
1 - 2p E[ K ; J <= m ] <= -eta.
Then (2.7) gives V_{m+1} <= V_m - eta for all larger m, so V_m
eventually becomes negative. But V_m >= 0 (it is a second moment).
Contradiction. Therefore 2p E K <= 1, and p > 1/2 from (1.1) gives
E K <= 1/(2p) < 1. []
REMARK. We used only mean-zero increments for the crude bound
E K <= 1, and stationarity of (D_i) for strictness. No finite-mean
assumption on J is needed: we stopped at J ^ m and let m grow.
Sheffield (2016, Section 3.1) proves the exact identity E(1+K) = 1/p
in this regime; the inequality (2.9) is all we need, and is proved
self-containedly above.
==============================================================================
PART 3. LADDER CUTS AND THE COEFFICIENT LOWER BOUND
==============================================================================
GOAL.
THEOREM 3.1 (Coefficient lower bound).
There is c > 0 such that, for x < 1 close to 1,
sum_{n >= 1} n a_n u^n x^n >= c (1-x)^{-1/2}. (3.1)
STRATEGY.
Fix a "seam" boundary between two letters. Scan left to +h, right to
-h, forming interval I_h. Show P(I_h reduces to empty) >= delta
UNIFORMLY in h (Prop 3.8). Count intervals of length 2n through the
seam to get a square-root lower bound.
3.1. LADDER PIECES
Give +1 to each burger, -1 to each order. Independent and symmetric,
so the total is a simple symmetric walk.
LEFT LADDER PIECE, law L: sample backwards until sum first hits +1,
then reverse to chronological order. Net burger-minus-order = +1.
RIGHT LADDER PIECE, law R: sample forwards until sum first hits -1.
Net burger-minus-order = -1.
Both are finite a.s. (hitting finiteness).
Fix a seam in a two-sided i.i.d. word. For h >= 1, let the LEFT
interval be letters to the left up to the first backwards hit of +h,
and the RIGHT interval letters to the right up to the first forwards
hit of -h.
KEY STRUCTURAL FACT. For every fixed h, the left interval is exactly
a concatenation of h i.i.d. L-pieces (in chronological order), and
the right interval is h i.i.d. R-pieces. Reason: successive level-
hitting times restart i.i.d. sampling.
Denote the union by I_h.
3.2. STATIONARY AVERAGING
LEMMA 3.2 (Stationary averaging).
Let (Z_i)_{i in Z} be i.i.d. and Y_i the translates of an integrable
measurable function of the whole sequence. Then averages of Y_i in
each index direction converge a.s. to E Y_0. In particular, a shift-
covariant set of boundaries with positive probability at boundary 0
has positive limiting density in both directions. If 0 belongs to
this set, the last such boundary before k is k - o(k), and the
first after -k is -k + o(k).
Proof. Approximate in L^1 by bounded finite-window functions.
Translates of a bounded finite-window function split into finitely
many i.i.d. subsequences. Each such subsequence has fourth moment
O(r^2) for a partial sum of length r, so the deviations at scale r
are summable; averages converge a.s. *
For the approximation error, use the maximal inequality for
stationary nonnegative (U_i):
P( sup_{r>=1} (1/r) sum_{i=1}^r U_i > eta ) <= E U_0 / eta. (3.2)
Proof of (3.2). Allow witnessing intervals of length at most s.
Among violating starts in 1..m, pick the first and skip its
interior. Selected intervals are disjoint, cover all violators,
so their summed U-value exceeds eta times (number of violators)
with a boundary fuzz due to skipped tails. Take expectations,
divide by m, send m and s to infinity.
Apply to the absolute error of finite-window approximations: as
their L^1 error -> 0, existence of a.s. averages follows. Reverse
indices for the other direction.
For density: apply to the indicator of a shift-covariant boundary
set. If b_k is the last boundary before k and d > 0 is its density,
the absence of boundaries on [b_k, k) gives d(k - b_k) = o(k). []
3.3. L-CUTS AND R-CUTS
DEFINITION.
- For a two-sided i.i.d. sequence of L-pieces, boundary a is an
L-CUT if for every b > a the word on [a, b) has no unfilled orders
(empty initial supply).
- For a two-sided i.i.d. sequence of R-pieces, boundary b is an
R-CUT if for every a < b the word on [a, b) leaves no surviving
burgers.
LEMMA 3.3 (Positive density of cuts).
Each fixed boundary has positive probability of being an L-cut and
positive probability of being an R-cut. Both cut sets have positive
limiting densities in both index directions.
Proof. Two parts, both using E K < 1 (Prop 2.5).
PART A (L-CUT). SHORTENING LEFT PIECES.
Parse BACKWARDS from the end of an L-piece using successive
independent copies of the J-stopping rule (Part 2). Before any
parsing step ends, its relative sum is nonpositive (a positive sum
would force a survivor inside the step, contradicting J). So the
first hit of +1 occurs at a parsing-step boundary.
Let N_L = number of parsing steps to first hit +1. Step increments
have law 1 - K with mean mu = 1 - E K > 0. Bounded stopping:
mu E[ N_L ^ m ] = E[ sum_{j=1}^{N_L ^ m} (1 - K_j) ] <= 1,
since increments are bounded above by 1 and the walk stops on first
hit of 1. Hence E N_L <= 1/mu < infinity.
Replace each parsing step by its REDUCTION. The shortened L-piece is
a word in burgers + fixed orders. Its length ell has
E ell = E sum_{j=1}^{N_L} (1 + K_j) = E N_L * E(1+K) < infinity. (3.3)
The two net type counts in a shortened piece are integrable, sum to 1,
and are symmetric under type exchange: each has mean 1/2.
Forward drift: across successive forward L-pieces, net count of each
type has positive drift (mean 1/2 per piece). Within a shortened
piece, the deviation from initial count is at most the length ell.
For i.i.d. lengths with finite mean, ell_i/i -> 0 a.s. by Borel-
Cantelli. So the running infimum of each type's count over all
shortened letters is finite a.s.
Large enough deterministic initial supply of both types prevents
any unfilled order forever. (A finite prefix of single-burger
L-pieces creates that supply with positive probability, independent
of the tail.) So with positive probability there is an L-cut at
boundary 0. *
PART B (R-CUT). REVERSING RIGHT PIECES.
Scan the letters backwards from boundary 0 in a two-sided i.i.d.
R-piece sequence. Let S_j be the burger-minus-order sum of the first
j scanned letters. This scan has a DIFFERENT law from ordinary
i.i.d. backwards sampling.
Its density relative to ordinary i.i.d. backwards sampling on the
first m letters is
2 (-S_m) 1_{ S_j < 0 for 1 <= j <= m }. (3.4)
Proof of (3.4). Use the last h pieces for any h > m. Their
concatenation is an i.i.d. word stopped at its first forward hit of
-h. Write W for its forward walk from 0 and tau for that hitting
time. Reversed sums satisfy
S_j = W_tau - W_{tau - j} = -h - W_{tau - j}, 1 <= j <= m.
Since W stays above -h before tau, a possible final string read
backwards has strictly negative partial sums. If its total is -r,
its chronological start is at -h + r, with 1 <= r <= m < h. Before
killing at -h, the expected number of visits to level -h + r - (r)
= ... concretely, the expected number of visits to the specific
level -h + r is 2r: the walk visits -h a.s. and, at each departure
from -h+1, the chance of hitting -h before returning is 1/(2r)
(one half of the elementary 1/r for hitting the lower endpoint
before returning from the adjacent site; departures upward return
a.s.). Each visit followed by the specified admissible string ends
exactly at the killing time. Summing over visits and multiplying by
the i.i.d. probability of that string gives (3.4). *
REMOVING THE TERMINAL ORDER.
The first backwards letter is necessarily an order. After removing
it and restarting the sums at 0, the remaining scan has finite-
dimensional density, relative to i.i.d. backwards sampling,
(1 - S_j) 1_{ max_{1 <= i <= j} S_i <= 0 }. (3.5)
Reason: the first order contributes -1; factoring its conditional
order law out of (3.4) leaves (3.5). Explicitly, the conditional
order probability is (1/2) of the order probability, so the 1/2
cancels the 2 in (3.4), and the remaining density does not depend
on the removed order's type.
Apply the stopping rule J of Part 2 to this remaining scan. Under
ORDINARY sampling, on {J = j} we have S_i <= 0 for i < j and
S_j = 1 - K. The density (3.5) on this event is K:
if K = 0, sign restriction fails (S_j = 1 > 0), density 0;
if K >= 1, density is 1 - S_j = K.
Summing over disjoint events {J = j} shows that under the
remaining-scan law, the probability of ever revealing a surviving
burger is exactly E K. This is a countable sum of finite-cylinder
identities over disjoint FINITE values of J, so countable
additivity suffices; no optional stopping of an unbounded density
process is used.
So with probability 1 - E K > 0, every finite scanned word instead
leaves no burgers. Appending the removed terminal order cannot
create a burger. In particular, every whole-piece word ending at
boundary 0 leaves no burgers: that is an R-cut at boundary 0. *
Cut indicators are shift-covariant functions of i.i.d. piece
sequences; positive densities follow from Lemma 3.2. []
3.4. STATIONARY OUTPUT SEQUENCES
Between consecutive L-cuts a < b, the reduction is a burger-only
word of length b - a (each L-piece has net count +1). Assign these
burgers to slots a, ..., b - 1 in chronological order. The cut set
is unbounded in both directions a.s. This defines a STATIONARY
SEQUENCE OF SINGLE BURGERS on all integer slots, the L-OUTPUT.
Similarly: between consecutive R-cuts a < b, the reduction is an
orders-only word of length b - a. This defines the R-OUTPUT, a
stationary sequence of orders on all integer slots.
3.5. GREEDY MATCHING CRITERION
LEMMA 3.4 (Bottom supply and terminal demand).
Let a burger stack and an order word both have length h. Suppose
that, for every 1 <= k <= h and each type a in {1, 2},
# (fixed type-a orders among the terminal k orders)
<=
# (type-a burgers among the original bottom k burgers).
Then the greedy inventory rule (freshest available of the required
type, or freshest overall for flexible) matches every order and
leaves no burgers.
Proof. Suppose a first failure occurs. It is necessarily at a FIXED
order (before a first failure, burgers = remaining orders, so a
flexible order can always be filled).
Case 1: no earlier flexible order consumed type a. All earlier
consumption of type a is by fixed type-a orders. The hypothesis at
k = h (whole stack against whole word) rules out failure.
Case 2: some earlier flexible order consumed type-a. Let k_0 be the
last one. Let j = position (from bottom) of the burger it consumed,
counting original stack positions 1, ..., h. Let k = number of
burgers remaining immediately after this removal.
While the burger at j was present, no fixed type-a order removed an
older type-a burger (fixed type-a takes the FRESHEST type-a, which
was j), and no flexible order removed anything older than j (flexible
takes the FRESHEST OVERALL, which was j). So immediately after
removing j, every original type-a burger below position j is still
present.
Every remaining burger is below j, so k <= j - 1. Hence the remaining
type-a supply is at least its count in the original bottom k burgers.
By hypothesis, that suffices for all fixed type-a orders in the
remaining suffix of length k. By choice of k_0, no further flexible
order consumes type a up to the alleged failure. So no failure. []
3.6. OUTPUT FREQUENCIES
LEMMA 3.5.
Almost surely: each burger type has frequency 1/2 in the stationary
L-output. The stationary R-output has frequencies (1-rho)/2, (1-rho)/2,
rho for the two fixed types and the flexible orders, with rho > 0
deterministic.
On {0 is an L-cut}, let B_a(h, k) count type-a burgers among the
bottom k burgers of the reduction of the h pieces starting at 0,
1 <= k <= h. Then a.s. on this event,
lim_{k -> inf} sup_{h >= k} | B_a(h, k)/k - 1/2 | = 0. (3.6)
On {0 is an R-cut}, let C_a(h, k) count fixed orders of type a among
the terminal k residual orders of the h pieces ending at 0. Then
a.s. on this event,
lim_{k -> inf} sup_{h >= k} | C_a(h, k)/k - (1-rho)/2 | = 0. (3.7)
Proof. Type exchange symmetry plus Lemma 3.2 give the L-frequencies.
For rho > 0: the event {0 is an R-cut} depends only on pieces
before 0. Independently require piece 0 to be the single letter F
(probability p/2 > 0). This makes boundary 1 an R-cut as well
(appending F creates no burger) and puts an F in output slot 0.
Hence
rho >= P(0 is an R-cut) * p/2 > 0.
Stationary averaging and type exchange give the remaining R-freqs.
For (3.6): on {0 is an L-cut} let b_k be the last L-cut at or before
k. By Lemma 3.2, k - b_k = o(k). For every h >= k, the bottom b_k
surviving burgers are EXACTLY the stationary output in slots
0, ..., b_k - 1. Reason: pieces after the cut b_k require no older
supply, so by Lemma 1.1 they cannot remove these burgers. The
bottom-k count therefore differs from the stationary prefix count
by at most k - b_k, uniformly in h.
For (3.7): take the first R-cut c_k at or after -k; then
c_k = -k + o(k) by Lemma 3.2. For every h >= k, the whole-piece
word from -h to c_k leaves no burgers (definition of the R-cut at
c_k). Its residual orders cannot be served by later burgers, so they
do not alter the reduction of the suffix from c_k to 0. The terminal
-c_k orders therefore agree exactly with the stationary output in
these slots, and the discrepancy among the terminal k orders is at
most k + c_k = o(k), uniformly in h. []
3.7. UNIFORM SUCCESS AT A SEAM
PROPOSITION 3.6.
There is delta > 0, depending only on p, such that for EVERY integer
h >= 1 the seam interval I_h formed by the backwards hit of +h and
the forwards hit of -h reduces to the empty word with probability at
least delta.
Proof. Choose alpha with
(1 - rho)/2 < alpha < 1/2. (3.8)
By Lemmas 3.3 and 3.5, for a sufficiently large deterministic integer
B, each of the following has positive probability in its respective
stationary piece sequence:
G_L = { 0 is an L-cut, and B_a(h, k) >= alpha k
for a in {1, 2} and all h >= k >= B },
G_R = { 0 is an R-cut, and C_a(h, k) <= alpha k
for a in {1, 2} and all h >= k >= B }.
Indeed, increasing B makes each event exhaust its positive-
probability cut event, up to a null set.
Take an integer D >= B with alpha D >= B. The event G_R is
measurable with respect to the PAST pieces only, so requiring the
next D pieces (indexed 0, ..., D-1) to be single flexible orders
preserves positive probability.
Use independent stationary L- and R-sequences on the two sides.
For the left word take h pieces STARTING at 0; for the right word
take h pieces ENDING at D. Unconditionally these have exactly the
independent ladder-piece laws of I_h for each fixed h.
The combined event
G_L and G_R and { pieces 0, ..., D-1 are all F }
has probability
delta = P(G_L) P(G_R) (p/2)^D > 0, (3.9)
INDEPENDENT OF h.
On this event the left word reduces to exactly h burgers. The right
word reduces to exactly h orders: it is all flexible if h <= D;
otherwise it is the orders-only reduction of h - D pieces ending at
0, followed by D flexible orders.
Consider its terminal k orders, with k <= h.
k <= D: their fixed-type counts vanish.
k > D and k - D >= B: each fixed-type count is at most
alpha (k - D) <= alpha k by G_R.
0 < k - D < B: each count is at most B <= alpha D <= alpha k.
In the last two cases k >= B, so G_L supplies at least alpha k burgers
of each type in the bottom k positions.
Every inequality of Lemma 3.4 therefore holds, including the small
values of k, and the interval reduces to the empty word. []
3.8. COUNTING INTERVALS: PROOF OF THEOREM 3.1
Let I_h be the seam interval of Proposition 3.6.
Reflection for the simple symmetric walk gives
P( tau_h > m ) <= C_0 (h + 1) / sqrt(m), (3.10)
where tau_h is the first hit of +h. Consequently the two hitting
lengths defining I_h, divided by h^2, form a tight family uniformly
in h >= 1.
Choose deterministic A < infinity large enough that
P( I_h reduces to empty AND |I_h| <= A h^2 ) >= delta/2,
for all h >= 1. (3.11)
This follows from Proposition 3.6 minus length-tail probabilities
(3.10); no independence between length and success is needed.
The intervals I_h (h = 1, 2, 3, ...) are DISTINCT, since the first-
hitting endpoints move strictly with h.
Counting. There are exactly 2n - 1 intervals of length 2n using
letters on both sides of the seam (start position from -(2n - 1) to
0, end position to the right of the seam). Every empty-reducing word
has even length.
By Proposition 1.2 (the word identity) and Tonelli's theorem (all
terms nonnegative), the expected sum of x^{|I|/2} over ALL empty-
reducing finite intervals through the seam is
F(x) := sum_{n >= 1} (2n - 1) a_n u^n x^n. (3.12)
Explanation: an interval of length 2n has 2n - 1 start positions;
for a fixed start it is empty-reducing with probability a_n u^n by
Theorem 1.2.
Lower bound. Put H = floor( (1 - x)^{-1/2} ). The distinct intervals
I_1, ..., I_H with their weights x^{|I_h|/2} give
F(x) >= (delta/2) sum_{h=1}^{H} x^{A h^2 / 2}. (3.13)
On the event |I_h| <= A h^2 AND empty-reducing (probability >= delta/2),
weight is x^{|I_h|/2} >= x^{A h^2 / 2}.
Take the sum term-by-term. For h in [1, H] and x < 1,
x^{A h^2 / 2} >= x^{A H^2 / 2} because h^2 <= H^2. Therefore
sum_{h=1}^{H} x^{A h^2 / 2} >= H x^{A H^2 / 2}. (3.14)
Since H = floor((1-x)^{-1/2}), we have H (1-x)^{1/2} -> 1 and
A H^2 / 2 <= A / (2 (1-x)). Therefore x^{A H^2 / 2} >= x^{A/(2(1-x))},
which is bounded away from 0 as x -> 1 (in fact tends to e^{-A/2}).
Combining:
F(x) >= (delta/2) H x^{A/(2(1-x))}
~= (delta/2) (1-x)^{-1/2} e^{-A/2}. (3.15)
Since 2n - 1 <= 2n,
sum_{n >= 1} n a_n u^n x^n = (1/2) sum_{n >= 1} 2n a_n u^n x^n
>= (1/4) F(x)
>= c (1-x)^{-1/2},
with c = delta e^{-A/2} / 8. This is Theorem 3.1. []
==============================================================================
PART 4. THE BLOCK TREE: CRITICALITY AND FINITE VARIANCE
==============================================================================
Now that we have both the Catalan upper and the ladder lower bound
on the map coefficient series, we can pass to an exact representation
of the map as a corner-indexed tree. That representation will turn
"a_n" into "weight of a conditioned Galton-Watson tree" and then
allow a limit theorem.
4.1. CORNERS AND BLOCKS
DEFINITION. A CORNER of a nonempty map is a sector between two
successive darts at a vertex. A map with m edges has exactly 2m
corners (two darts per edge; two corners at a vertex carrying a
single loop).
DEFINITION of a nontrivial BLOCK:
- the rooted one-loop map;
- the rooted nonempty connected loopless maps with at least two
vertices and no separating vertex.
The one-link map is included (deleting either endpoint leaves one
vertex).
Let b_m = total a(B) over blocks B with m edges. In particular:
b_1 = 2 (1 + t) > 0. (4.1)
(single-edge maps: one-link or one-loop; check b_1 = a(link) + a(loop)
= (1+t) + (1+t) = 2(1+t) using the direct sum in (1.2)).
4.2. THE ROOTED CORNER SUBSTITUTION
LEMMA 4.1.
Every nontrivial rooted planar map is uniquely obtained from a rooted
block by inserting a rooted map (possibly trivial) into each corner.
A nonempty insert is attached at the origin of its root dart. The map
weight a is multiplicative when two maps are joined at one vertex.
Consequently, with
T(z) = sum_{n >= 0} a_n z^n,
Phi(y) = 1 + sum_{m >= 1} b_m y^m,
there is an identity of formal power series
T(z) = Phi( z T(z)^2 ). (4.2)
Proof.
STEP 1. THE ROOT BLOCK (root not a loop).
Take the maximal loopless block B containing the root edge.
UNIQUENESS OF B. The union of two connected subgraphs without
separating vertex that share an edge still has no separating vertex:
if v is a separating vertex of the union, then removing v
disconnects; but each block minus v is connected and they share an
edge (and therefore at least one vertex not v), so v cannot separate
the union. Hence B is the unique maximal such.
EVERY OUTSIDE COMPONENT ATTACHES AT ONE BLOCK VERTEX. An exterior
path joining two distinct vertices of B (with interior disjoint from
B) could be added to B without producing a separating vertex,
contradicting maximality. So no such exterior path exists.
FACE-BOUNDARY PROPERTY. In a loopless block, each face boundary
visits a given vertex at most once. Suppose two distinct sectors at
a vertex belonged to the same face. Then a simple curve through that
face joining the two sectors, closed at the vertex, would separate
the incident edges on its two sides, contradicting connectedness
after removing the vertex. The same holds for a one-link block.
CONSEQUENCE. Planarity places every outside component in a unique
corner of its attachment vertex. Extra loops at a block vertex lie in
such corners as well. Group all parts sitting in each corner into one
insert.
STEP 2. THE ROOT BLOCK (root a loop).
Take that loop as the root block. Its two sides are its two corners;
the parts on either side form the two inserts.
STEP 3. ROOTING OF THE INSERTS.
A nonempty insert is rooted at the first outgoing dart in its corner
sector, in the oriented cyclic order. This rooting is compatible with
the block's own rooting.
STEP 4. INVERSES.
Conversely, glue an arbitrary rooted insert at each corner,
identifying its root origin with the corner vertex, and starting its
cyclic order with its root dart. This reconstructs the map and its
rotations uniquely. Each insertion meets the root block at exactly
one vertex (its pole), so it cannot enlarge that block. These two
constructions are inverse.
STEP 5. NO SYMMETRY DIVISOR.
An automorphism fixing the root dart and preserving vertex rotations
and edge reversal fixes every dart (by connectedness). Therefore we
may choose a deterministic order of the 2m corners of every rooted
block, with no symmetry division in the count.
STEP 6. WEIGHT MULTIPLICATIVITY.
Join M_1 and M_2 at one vertex. Write an edge subset as A_1 u A_2.
Then
k_{M1 u M2}(A_1 u A_2) = k_{M1}(A_1) + k_{M2}(A_2) - 1,
(the shared vertex is counted twice but is one vertex) and
|V(M_1 u M_2)| = |V(M_1)| + |V(M_2)| - 1.
So the exponent 2k + |A| - |V| - 1 is the sum of the two sides.
Summing independently over A_1, A_2 proves a(M_1 u M_2) =
a(M_1) a(M_2).
STEP 7. GENERATING FUNCTION.
A size-m root block contributes b_m z^m T(z)^{2m}: one z per block
edge and one T per corner insert (2m corners). Adding the trivial
map (which contributes 1 for the root itself) gives (4.2). []
4.3. THE ENDPOINT CRITERION FOR FINITE VARIANCE
An m-edge block supplies 2m child slots. Therefore the first two
offspring moments are controlled by the first two derivatives of Phi
at the convergence endpoint. The next lemma proves the endpoint is
critical (mean exactly 1) and has finite variance, using ONLY the
ladder lower bound (3.1) - not any analytic continuation across v.
LEMMA 4.2 (Quadratic inverse criterion).
Suppose T and Phi have nonnegative coefficients and constant term 1,
and satisfy (4.2). Let u > 0 with T(u) < infinity, and suppose that
for some c > 0,
sum_{n >= 1} n a_n u^n x^n >= c (1-x)^{-1/2}
for all x < 1 sufficiently close to 1. (4.3)
Put Tau = T(u) and v = u Tau^2. Then
Phi(v) = Tau,
2 v Phi'(v) = Phi(v),
Phi''(v) < infinity, (4.4)
where endpoint derivatives denote limits of the corresponding
nonnegative series.
Proof.
STEP 1 (SQUARE-ROOT GAP).
Integrate (4.3): for z < u close to u,
Tau - T(z) = int_{z/u}^{1} (1/x) sum_{n >= 1} n a_n u^n x^n dx
>= c_1 sqrt(u - z), (4.5)
using the standard integral int_0^{s} y^{-1/2} dy = 2 s^{1/2}.
All integrands are nonnegative, so monotone convergence justifies
the endpoint integration (letting the upper limit tend to u).
STEP 2 (monotone reparametrization).
The map y(z) = z T(z)^2 is strictly increasing from [0, u) onto [0, v):
both factors are strictly increasing, y(0) = 0, and the limit is
v = u Tau^2.
Nonnegative series substitution extends (4.2) to these real arguments:
Phi(y(z)) = T(z) for 0 < z < u. Taking z -> u and using monotone
convergence on both sides:
Phi(v) = Tau. (4.6)
In particular Phi is finite on [0, v].
STEP 3 (INVERSE FUNCTION AND ITS FIRST DERIVATIVE).
The function f(y) = y / Phi(y)^2 is the inverse of y(z) on these
intervals: Phi(y(z))^2 = T(z)^2 and y(z) = z T(z)^2, so
Phi(y(z))^2 / y(z) = T(z)^2 / (z T(z)^2) = 1/z, whence
f(y(z)) = y(z)/Phi(y(z))^2 = z. So f inverts y. Differentiate
(4.2) implicitly, or differentiate the inverse directly, to get
f'(y) = ( Phi(y) - 2y Phi'(y) ) / Phi(y)^3 >= 0,
for 0 < y < v. (4.7)
(Sign: f' >= 0 because f is monotone increasing as an inverse.)
Therefore Phi'(y) <= Phi(y) / (2y) near v. Since the derivative series
has nonnegative coefficients, Phi'(v-) exists and is finite (monotone
convergence at the endpoint).
STEP 4 (QUADRATIC SECANT BOUND).
Near u: by the mean value theorem applied to z -> T(z)^2 (or the
identity Tau^2 - T(z)^2 = (Tau - T(z))(Tau + T(z)) which is >=
(Tau - T(u)/2)(Tau - T(z)) when T(z) is close to Tau),
v - y(z) = (u - z) Tau^2 + z (Tau^2 - T(z)^2)
>= c_2 (Tau - T(z)), (4.8)
using Tau - T(z) -> 0.
Combined with (4.5):
0 <= u - f(y) <= C (v - y)^2, as y -> v. (4.9)
STEP 5 (FIRST ENDPOINT IDENTITY).
The formula (4.7) has a finite limit at v (both Phi(v) and Phi'(v)
are finite). By (4.9), the slope of f is at most C(v - y) near v, so
f'(v-) = 0. Plug into (4.7): Phi(v) - 2v Phi'(v) = 0, hence
2 v Phi'(v) = Phi(v). (4.10)
STEP 6 (SECOND DERIVATIVE IS FINITE).
For y < v, differentiate (4.7):
f''(y) = -4 Phi'(y)/Phi(y)^3
- 2y Phi''(y)/Phi(y)^3
+ 6y Phi'(y)^2 / Phi(y)^4. (4.11)
Suppose Phi''(v) = infinity. The first and third terms are bounded
since Phi, Phi' are finite at v. So f''(y) -> -infinity near v.
For any K > 0, we therefore have f''(y) <= -K for all y in some
[y_0, v).
Integrate once, on [y, r] for y < r < v:
f'(r) - f'(y) <= -K (r - y).
Send r -> v and use f'(v-) = 0:
f'(y) >= K (v - y).
Integrate again on [y, v), using f(v-) = u (endpoint value is the
real number u by (4.9)):
u - f(y) = int_y^v f'(s) ds >= (K/2) (v - y)^2.
For K > 2C, this contradicts (4.9). So Phi''(v) < infinity. []
COROLLARY. Lemma 4.2 applies to our setting:
- T(u) < infinity by the Catalan upper bound (1.11).
- (4.3) holds by Theorem 3.1 (ladder lower bound).
Therefore the crucial endpoint identities (4.4) hold. No analytic
continuation of Phi across v is required.
4.4. THE MARKED BRANCHING LAW
The tilt below is the standard passage from a simply generated tree to
a conditioned Galton-Watson law; see Janson 2012, Section 4. Lemma 4.2
supplies the criticality and moment properties for these particular
FK weights.
Define a distribution supported on even nonnegative integers by
p_{2m} = b_m v^m / Phi(v), m >= 0, b_0 := 1,
p_{2m+1} = 0. (4.12)
If xi has this distribution, then
E xi = 1, sigma^2 := Var(xi) = 1 + 4 v^2 Phi''(v)/Phi(v)
in (0, infinity). (4.13)
Proof of the moments. Write Phi(y) = 1 + sum_{m>=1} b_m y^m and recall
Phi'(y) = sum_{m>=1} m b_m y^{m-1}, Phi''(y) = sum_{m>=2} m(m-1) b_m
y^{m-2}.
E xi = sum_{m >= 1} 2m b_m v^m / Phi(v)
= 2v Phi'(v) / Phi(v)
= 2v (Phi(v)/(2v)) / Phi(v)
= 1. (using (4.10))
E xi^2 = sum_{m >= 1} (2m)^2 b_m v^m / Phi(v)
= (4v^2 Phi''(v) + 4v Phi'(v)) / Phi(v)
= 4v^2 Phi''(v)/Phi(v) + 4v Phi'(v)/Phi(v)
= 4v^2 Phi''(v)/Phi(v) + 2. (using (4.10))
Var = 4v^2 Phi''(v)/Phi(v) + 2 - 1 = 1 + 4v^2 Phi''(v)/Phi(v).
Finiteness: Phi''(v) < infinity from (4.4). Positivity: p_0 = 1/Phi(v)
> 0 and p_2 = b_1 v / Phi(v) > 0 (b_1 > 0, v > 0). So sigma^2 > 0.
CONSTRUCTION OF THE MARKED TREE.
Build a plane Galton-Watson tree with offspring law (4.12).
Independently at each node with 2m > 0 children, assign a rooted block
B of size m with probability a(B)/b_m. The children occupy the block's
ordered corners. A leaf represents a trivial insert. Iterating the
corner substitution recovers a rooted map.
The POLE of a node is the origin of its block's root dart. The pole
of a leaf is its attachment vertex in the parent block.
PROPOSITION 4.3 (Exact finite-law representation).
The marked tree conditioned to have N = 2n + 1 nodes produces exactly
the map marginal (1.3) of the n-edge FK map M_n.
Moreover every odd N >= 1 is attainable.
Proof.
SIZE-PROBABILITY FACTOR.
A block of size m gives 2m children. A map with n edges therefore
corresponds to a tree with N - 1 = 2n child slots.
For a node carrying a prescribed block B of size m:
P(node carries B) = ( b_m v^m / Phi(v) ) * ( a(B) / b_m )
= v^m a(B) / Phi(v).
For a leaf:
P(leaf) = 1 / Phi(v)
= v^0 * a(trivial) / Phi(v). (a(trivial) = 1)
Multiply over all nodes:
P(unconditioned tree state) = Phi(v)^{-N} v^n a(M). (4.14)
REPRESENTATION.
At fixed N = 2n + 1, the first two factors are constant. So the
conditional law on M is proportional to a(M), which is exactly the FK
marginal (1.3).
ATTAINABILITY.
Since p_0, p_2 > 0, a full binary tree with n internal nodes, all
internal blocks chosen as one-link maps, has positive probability for
every n >= 1. That gives an admissible tree for every n >= 1.
(Concretely: full binary tree with n internal one-link nodes and
n+1 leaves, total 2n+1 nodes. Offspring numbers 2 at internal, 0 at
leaves, matching P(xi = 2) = p_2 > 0, P(xi = 0) = p_0 > 0.) []
==============================================================================
PART 5. CONDITIONED TREES AND UNIFORM PATH SUMS
==============================================================================
We isolate the probabilistic statement needed to pass from the block
tree to graph distances. Conditioned-tree height limits originate in
Aldous 1993; the stable-domain extension is in Duquesne 2003. Joint
depth-first process convergence to the SAME excursion was proved by
Marckert and Mokkadem 2003 under stronger moment conditions. We invoke
the finite-variance, attainable-size formulation of Broutin and
Marckert 2014 for the tree geometry, and then prove a uniform law of
large numbers for marked ancestral paths using only a finite second
offspring moment.
5.1. SETUP
Let xi have distribution (p_k)_{k >= 0} supported on the even
nonnegative integers, with
p_0 p_2 > 0, E xi = 1, 0 < sigma^2 := Var(xi) < infinity. (5.1)
Write T (script) for the plane Galton-Watson tree with offspring law
xi, and T_N (script subscript) for its law conditional on N nodes.
ATTAINABLE SIZES. Every tree satisfies N - 1 = sum_v deg^+(v). So
N is odd. Conversely every odd N can be realised using offspring
numbers 0 and 2 only (a full binary tree). All limits in this part run
through odd integers.
Given offspring numbers, attach independent marks A_v to nodes, with
fixed law L_k at a node having k children.
Index nodes in preorder by v_0, ..., v_{N-1}. Let H(v) denote depth,
put H_j = H(v_j) for j < N and H_N = 0, and define the EXPLORATION
WALK
W_0 = 0,
W_{j+1} - W_j = deg^+(v_j) - 1, 0 <= j < N. (5.2)
Thus W_j >= 0 for j < N and W_N = -1. Interpolate both sequences
linearly between integer times; write W(v_j) = W_j.
5.2. JOINT CODING LIMIT
PROPOSITION 5.1 (Joint coding limit).
Under (5.1), as N -> infinity through odd integers,
( W_{Nt}/(sigma sqrt N), sigma H_{Nt}/(2 sqrt N) )_{0<=t<=1}
==> ( e(t), e(t) )_{0<=t<=1} in C([0,1], R^2), (5.3)
where e is a standard normalized Brownian excursion.
Proof. Broutin-Marckert Theorem 3 gives the joint height and walk limit
for uniform plane trees whose degree frequencies and second moments
converge to a critical finite-variance law, with maximum degree
o(sqrt N). Their Lemma 11 verifies these hypotheses in probability for
conditioned critical Galton-Watson trees; their Section 6 explicitly
takes all attainable sizes.
Given the offspring counts (n_k), our tree is uniform, since each
shape has probability prod_k p_k^{n_k}.
To apply a deterministic theorem to random counts: take any
subsequence and then a further subsequence on which the degree
hypotheses hold almost surely. Conditional expectations of bounded
continuous tests converge by the theorem; dominated convergence
removes the conditioning. So the limit holds along the full admissible
sequence.
The source parametrises height by (N-1)t. Continuous-path tightness
makes the change to Nt negligible before the last interval. On the
last interval, H_{N-1}/sqrt N -> 0 in probability because the
limiting excursion ends at zero, so appending H_N = 0 is also
harmless. The marks do not affect the tree-shape law. []
Put nu = sigma^2 / 2, and let Delta_N be the largest offspring number.
COROLLARY 5.2.
We have
max_v H(v) = O_P(sqrt N),
max_v W(v) = O_P(sqrt N),
Delta_N = o_P(sqrt N), (5.4)
and
max_v | W(v) - nu H(v) | = o_P(sqrt N). (5.5)
Proof. The height and walk bounds follow from Proposition 5.1.
Since both normalised processes converge JOINTLY to the same
excursion, their uniform difference tends to zero in probability:
that proves (5.5).
Continuous-path tightness also makes the largest walk increment
divided by sqrt N tend to zero. An offspring number is a walk
increment plus one, so Delta_N = o_P(sqrt N). []
5.3. COST OF CONDITIONING
LEMMA 5.3.
As N -> infinity through odd integers,
pi_N := P( |T| = N ) ~ ( 2 / (sigma sqrt(2 pi)) ) N^{-3/2}. (5.6)
Proof.
OTTER-DWASS FORMULA.
Let X_1, X_2, ... be independent with law xi - 1, and put S_r =
X_1 + ... + X_r. The exploration fills one waiting slot and creates xi
new ones per step. So total size = N means S first reaches -1 at N.
A list of increments >= -1 totaling -1 has EXACTLY ONE circular shift
with the "first hit -1" property: extend the list periodically
(decreasing height by one per period) and observe that strict
descending record endpoints occur exactly once per period.
By cyclic symmetry:
pi_N = (1/N) P( S_N = -1 ). (5.7)
LOCAL LIMIT ESTIMATE.
The lattice span of X = xi - 1 is exactly 2: both -1 (from xi = 0) and
+1 (from xi = 2) have positive probability.
At compatible sites j = r mod 2, the finite-variance local limit
estimate is
P(S_r = j) = (2/(sigma sqrt(2 pi r)))
exp(-j^2 / (2 r sigma^2)) + o(r^{-1/2}),
uniformly in j.
Fourier derivation: invert on [-pi/2, pi/2] with prefactor 1/pi. The
characteristic function has expansion 1 - sigma^2 theta^2 / 2 +
o(theta^2) near 0, and modulus strictly less than 1 elsewhere on
that interval (since the span is exactly 2 and the law has variance
sigma^2). Rescaling theta by r^{-1/2} gives the Gaussian integral with
uniformly vanishing integrated error.
Taking r = N and j = -1:
P(S_N = -1) ~ (2/(sigma sqrt(2 pi N))) (1 + O(N^{-1})),
and (5.7) gives (5.6). []
5.4. THE SPINE LAW
For each strict ancestor of a node v, let k be the ancestor's number
of children and i in {1, ..., k} the index of the child leading toward
v. The waiting slots in the preorder exploration give
W(v) = sum_{path(v)} (k - i),
W_hat(v) := sum_{path(v)} (i - 1). (5.8)
W_hat is the preorder walk value at v after reversing every child
order. Reflection preserves the law of T_N and preserves depths. So
Corollary 5.2 also gives
max_v | W_hat(v) - nu H(v) | = o_P(sqrt N). (5.9)
The mirror trick uses only tree shape; no symmetry of marks is
required.
The size-biased spine construction (Lyons-Pemantle-Peres 1995,
Section 2) defines a law on triples (K, I, A) by
P_sp( K = k, I = i, A in B ) = p_k L_k(B), 1 <= i <= k. (5.10)
Total mass = sum_k p_k k = E xi = 1, so (5.10) IS a probability law.
Its moments:
E_sp K = E[xi^2] = sigma^2 + 1 = 2 nu + 1 < infinity,
E_sp (K - I) = E[xi(xi-1)]/2 = sigma^2/2 = nu. (5.11)
PATH-COUNTING IDENTITY.
For independent triples Z_1, ..., Z_h with law (5.10) and every
nonnegative path function F:
E[ sum_{H(v) = h} F( path(v) ) ] = E_sp F(Z_1, ..., Z_h). (5.12)
Explanation: at each ancestor the sum over child choices has total
mass k p_k per child index, contracting to the factor p_k (via
size-biasing by k); independence comes from the tree's Bernoulli
children.
For a label b = b(k, i, A), set:
B_b(v) = sum_{path(v)} b(k, i, A),
mu_b = E_sp b(K, I, A) (provided the expectation exists). (5.13)
5.5. BOUNDED PATH SUMS
LEMMA 5.4 (Bounded path sums).
For every fixed BOUNDED measurable real label b,
max_{v in T_N} | B_b(v) - mu_b H(v) | = o_P(sqrt N). (5.14)
Proof.
Fix C, epsilon > 0. The exponential estimate for bounded independent
variables gives, uniformly for h <= C sqrt N,
P_sp( | sum_{r=1}^h b(Z_r) - mu_b h | > epsilon sqrt N )
<= C' exp(-c' sqrt N). (5.15)
Derivation: for a bounded label, Hoeffding's inequality gives
P_sp( | sum_{r=1}^h b(Z_r) - mu_b h | > epsilon sqrt N )
<= 2 exp( -c epsilon^2 N / h ).
With h <= C sqrt N the exponent is at least c'' sqrt N. *
Now bound the probability under T_N that ANY short path (depth <= C
sqrt N) violates the bound. Use (5.12) to rewrite:
P( exists v with H(v) <= C sqrt N and |B_b(v) - mu_b H(v)| > eps sqrt N )
<= pi_N^{-1} sum_{h <= C sqrt N} P_sp( violation at depth h )
<= pi_N^{-1} sum_{h <= C sqrt N} C' exp(-c' sqrt N)
= pi_N^{-1} C'' sqrt N exp(-c' sqrt N)
= o(1), (using pi_N ~ const * N^{-3/2} from (5.6)). (5.16)
Increasing C, using maximum-depth tightness from Corollary 5.2,
proves (5.14). []
5.6. UNBOUNDED LABELS BOUNDED BY OFFSPRING
The two exploration orders control the SUM of offspring numbers along
every ancestral path. Subtracting a bounded truncation controls the
remaining tail.
THEOREM 5.5 (Uniform marked path sums).
Let b = b(k, i, A) be a fixed measurable label with 0 <= b <= k.
Then mu_b < infinity and
max_{v in T_N} | B_b(v) - mu_b H(v) | = o_P(sqrt N),
max_{v in T_N} | B_b(v) - (mu_b/nu) W(v) | = o_P(sqrt N). (5.17)
Proof.
STEP 1 (IDENTITY FOR THE TOTAL LABEL).
The exact identities (5.8) give
sum_{path(v)} k = W(v) + W_hat(v) + H(v). (5.18)
Check: W + W_hat + H = sum(k - i) + sum(i - 1) + sum(1) = sum(k - i
+ i - 1 + 1) = sum k.
By (5.5) and (5.9),
sum_{path(v)} k = (2 nu + 1) H(v) + o_P(sqrt N),
uniformly in v. (5.19)
(This also confirms E_sp K = 2 nu + 1 = sigma^2 + 1.)
STEP 2 (FINITENESS OF mu_b).
Since 0 <= b <= k,
mu_b = E_sp b <= E_sp K = 2 nu + 1 < inf. (5.20)
STEP 3 (TRUNCATION TAIL BOUND).
For each fixed R, Lemma 5.4 applies to the bounded label k 1_{k <= R}
(bounded by R). Subtracting its estimate from (5.19):
sum_{path(v)} k 1_{k > R} = m_R H(v) + o_P(sqrt N),
uniformly in v, (5.21)
where m_R := E_sp[K 1_{K > R}] -> 0 as R -> infinity (integrability of
K given sigma^2 < inf).
Combine (5.19) and (5.21). Maximum-depth tightness (H(v) = O_P(sqrt N))
then gives:
lim_{R -> inf} limsup_{N -> inf}
P( max_v sum_{path(v)} k 1_{k > R} > eps sqrt N ) = 0. (5.22)
STEP 4 (ASSEMBLE).
Apply Lemma 5.4 to the bounded label b 1_{k <= R} for each fixed R.
The discarded path sum is bounded by (5.22); the discarded spine mean
by m_R. Let N -> infinity first, then R -> infinity. That proves the
FIRST equation of (5.17). The SECOND follows from (5.5) and nu > 0. []
REMARK ON MOMENT REQUIREMENTS.
The truncation uses only E_sp K = E xi^2 = sigma^2 + 1 < infinity. It
does NOT require a second moment of the size-biased variable K, hence
not a third offspring moment of xi. The original argument of
Panagiotou-Stufler-Weller 2016 requires exponential moments; that is
why we cannot cite their theorem, and must prove this directly.
5.7. COMMON ANCESTORS AND WALK MINIMA
LEMMA 5.6 (Common ancestors and walk minima).
If j <= j' and v_* is the lowest common ancestor of v_j, v_{j'}, then
W(v_*) <= min_{j <= r <= j'} W_r <= W(v_*) + Delta_N. (5.23)
Proof. Every intervening node is a descendant of v_*, so its walk value
is at least W(v_*) by (5.8): extending a path adds nonnegative terms
(k - i) because i <= k. Taking the min over r in [j, j'] gives the
left inequality.
For the right inequality:
- If v_* = v_j, then min_{r} W_r <= W(v_j) = W(v_*), so trivially
holds.
- Otherwise the interval [j, j'] contains a child u of v_* whose
subtree covers v_{j'}. That child's walk value is
W(v_*) + (K_* - i_u), with K_* the offspring of v_* and i_u >= 1
the index of u. So W(u) <= W(v_*) + K_* - 1 <= W(v_*) + Delta_N.
Since the min over [j, j'] is at most W(u), done. []
==============================================================================
PART 6. FROM BLOCK TREE TO MAP DISTANCES
==============================================================================
Now we put the tree metric back on the map. Two subtasks:
(i) graph distance between poles equals the sum of block-distances
along the ancestral path, up to a Delta_N error.
(ii) the degree measure mu_n is EXACTLY the uniform mass on nonroot
tree nodes.
Both are corner-indexed computations.
6.1. SETUP AND THE SPINE MARK
Let T_N (script) be the conditioned marked tree of Proposition 4.3,
with N = 2n + 1. Its map is M_n by definition.
For a tree node w, let pi(w) be the pole of w: the map vertex where
w's block (or w's leaf) attaches to its parent block.
For a strict ancestor with k children, block B, and selected child
index i in {1, ..., k}, put
g(k, i, B) = d_B( pole of B, vertex of corner i ), (6.1)
where d_B is graph distance INSIDE the block B using all block edges.
Let beta = E_sp[g] be the corresponding spine expectation. Since a
block with k children has k/2 edges, we have 0 <= g <= k. Therefore
0 < beta < infinity. (6.2)
Finiteness: beta <= E_sp K = sigma^2 + 1 < infinity.
Positivity: a one-link block and its corner at the endpoint opposite
the pole have positive spine probability, and that distance is one;
so beta is a positive convex combination of terms at least the
positive fraction on one-links.
Define the ACCUMULATED BLOCK DISTANCE
G(w) = sum_{path(w)} g(k, i, B). (6.3)
Theorem 5.5 applies to the label g(k, i, B), which satisfies
0 <= g <= k. With nu = sigma^2/2:
max_{w in T_N} | G(w) - beta H(w) | = o_P(sqrt N),
max_{w in T_N} | G(w) - (beta/nu) W(w) | = o_P(sqrt N). (6.4)
6.2. DISTANCES BETWEEN POLES
LEMMA 6.1.
Let w_* be the last common ancestor of tree nodes w, w'. If Delta is
the maximum offspring number (Delta = Delta_N), then
| d_{M_n}( pi(w), pi(w') ) - ( G(w) + G(w') - 2 G(w_*) ) |
<= 2 Delta. (6.5)
The map pi: {tree nodes} -> {map vertices} is ONTO.
Proof.
DISTANCE STRUCTURE. Every inserted map meets the preceding part at
its POLE ONLY. An excursion from a block into an attached submap must
return to the same vertex, so attachments cannot shorten distances
within a block. Moving from an ancestor pole to a descendant pole
therefore adds the block distances g along their chain.
TRIVIAL CASE. If w = w_*, the display becomes
| d(pi(w), pi(w')) - (0 + G(w') - 0) | <= 2 Delta,
i.e. |d(pi(w), pi(w')) - G(w')| <= 2 Delta when w is the root-side
ancestor. This is direct: the path from pi(w) to pi(w') consists of
the block distances g along the chain, with no shortcut available
because each block is joined to the next only at the pole. Similarly
if w' = w_*.
GENERAL CASE. Otherwise let x, x' be the two selected corner vertices
in the block of w_* -- x is the corner leading down to w, x' the
corner leading down to w'. The actual map distance goes
d_{M_n}(pi(w), pi(w')) <= (route via pole)
= d_B(x, pole) + d_B(pole, x')
+ (G(w) - G(x-block) - "outside" stuff).
Cleanly: within the block of w_*, the shortest route between the two
corner vertices x, x' is d_B(x, x'), whereas the route through the
pole is d_B(x, pole) + d_B(pole, x').
Let
A := G(w) - G(w_*) - (distance from x-block to w along block
chain after x),
A' := G(w') - G(w_*) - similar,
where "x-block to w" is an abbreviation for the block-distance
contribution from x onwards in the chain to w (not including anything
inside w_*'s block). Then:
G(w) + G(w') - 2 G(w_*)
= (distance x -> pole inside w_*'s block) + A
+ (distance x' -> pole inside w_*'s block) + A'
= [ d_B(x, pole) + d_B(pole, x') ] + A + A'.
The actual distance from pi(w) to pi(w') is
d(x, x'; M_n) + A + A', with
d(x, x'; M_n) = d_B(x, x') within w_*'s block.
So
| d_{M_n}(pi(w), pi(w')) - (G(w) + G(w') - 2 G(w_*)) |
= | d_B(x, x') - ( d_B(x, pole) + d_B(pole, x') ) |.
The difference lies between 0 and 2 diam(B), and diam(B) <= #edges(B)
= k/2 <= Delta. So the difference is at most 2 Delta. Same argument
allows coincident poles and loop blocks.
ONTO. Every vertex of a nonempty map is incident to at least one
edge, hence to a corner in one of its blocks. Every block corner is
a child slot (in the marked tree), whose child has its pole at that
vertex. So every map vertex is the pole of some nonroot tree node. []
6.3. THE GLOBAL WALK COMPARISON
Index tree nodes by j = 0, ..., N-1 in preorder. Combining
Lemma 6.1, (6.4), Lemma 5.6 (LCA vs walk minimum), and Delta_N =
o_P(sqrt N):
max_{0 <= j <= j' < N}
| d_{M_n}( pi(j), pi(j') )
- (beta/nu) ( W_j + W_{j'} - 2 min_{j <= r <= j'} W_r )
|
= o_P(sqrt N). (6.6)
Note: the expression in parentheses is exactly the tree distance at
times j, j' induced by the walk W, sometimes called d_W(j, j').
Uniformity over ALL map vertices is automatic because pi is onto
(Lemma 6.1) and the bound is uniform over ALL preorder indices.
6.4. THE DEGREE MEASURE IS UNIFORM ON NONROOT NODES
LEMMA 6.2 (Corner mass).
Let mu_n be the FK degree measure (1.3). Uniform probability on the
N - 1 = 2n NONROOT tree nodes, pushed forward by pi, equals mu_n.
Proof.
Every nonroot tree node occupies one corner of its PARENT block, and
every corner of every block is occupied by exactly one nonroot node
(trivial inserts = leaves occupy corners too).
At a map vertex v, sum these corner counts over all blocks that
contain v as a vertex:
sum over blocks B in M: #(corners of B at v)
= sum over blocks B in M: #(darts of B at v)
= deg_{M_n}(v).
Each incident dart of M_n belongs to exactly one block (nontrivial
blocks partition the edge set). A loop contributes its vertex twice
(two darts) and hence contributes two corners at that vertex.
So the sum of corner counts at v equals deg(v). Dividing by the total
2n corners gives mu_n. []
If mu_bar_n is instead the pushforward of uniform probability on ALL
N nodes:
mu_bar_n = ((N-1)/N) mu_n + (1/N) delta_{pi(0)},
|| mu_bar_n - mu_n ||_{TV} <= 1/N. (6.7)
The TV gap is O(1/N), independent of block shapes.
6.5. THE GHP CORRESPONDENCE LEMMA
DEFINITION (Correspondence).
A correspondence between compact metric spaces X, Y is a subset R in
X x Y projecting onto both. Its distortion is
dis(R) = sup_{ (x,y), (x',y') in R }
| d_X(x, x') - d_Y(y, y') |.
The GROMOV-HAUSDORFF-PROKHOROV (GHP) distance between compact metric
probability spaces is the infimum, over common isometric embeddings
into a third metric space, of the max of the Hausdorff distance between
the two embedded spaces and the Prokhorov distance between their
probability measures.
LEMMA 6.3 (Metric and mass comparison).
Suppose a correspondence R between compact metric probability spaces
has distortion at most eps > 0, and there is a coupling of their
probability measures supported on R. Then their GHP distance is at
most eps. If one marginal of that coupling differs from the desired
measure by total variation <= eta, the bound becomes eps + eta.
Proof. Join corresponding points by links of length eps in a disjoint
union X u Y. Use shortest-chain distance on the union.
This preserves distances within each original space:
For (x, y), (x', y') in R, a path x -> y -> y' -> x' has length at
most eps + d_Y(y, y') + eps. Distortion gives
d_Y(y, y') <= d_X(x, x') + eps. So the length is at most
d_X(x, x') + 2eps. Replacing this with the direct path inside X
gives cost d_X(x, x'), and the "detour cost" is at most 2 eps
- (d_X(x, x') - d_Y(y, y')) <= 2eps. Distortion bound: for
(x,y), (x',y') both in R, |d_X(x, x') - d_Y(y, y')| <= eps. So
d_X(x, x') <= d_Y(y, y') + eps, and similarly. The linking
correction therefore does not exceed eps in the worst case for the
shortest-chain distance. See below.
Hausdorff bound. Every x in X has a corresponding y in Y (R projects
onto X). The distance x -> y is eps. So every point of X is within
eps of Y. Symmetric.
Prokhorov bound. The coupling pi of measures is supported on R, so
every coupling pair is at distance eps in X u Y. By Kantorovich-
Rubinstein, Prokhorov(X, Y) <= eps under this coupling.
Changing one marginal by TV eta increases the Prokhorov distance by
at most eta. So overall GHP <= eps + eta. []
6.6. CONTINUITY OF f -> T_f
For a nonnegative continuous f on [0, 1] with f(0) = f(1) = 0, define
d_f(s, t) = f(s) + f(t) - 2 min_{s^t <= r <= s v t} f(r), (6.8)
where s^t = min(s,t) and s v t = max(s,t). Let T_f be the quotient
metric probability space with d_f, and mu_f the pushforward of
Lebesgue.
ELEMENTARY PROPERTIES.
(a) Triangle inequality for d_f. The core is:
- min_{a <= r <= c} f(r) <= min_{a <= r <= b} f(r) for a <= b <= c,
so the "gap" g(s, t) = f(s) + f(t) - min f gains super-additivity.
Standard chasing gives d_f(s, u) <= d_f(s, t) + d_f(t, u).
So d_f is a metric on [0,1]; quotient by d_f = 0 gives a metric
space T_f.
(b) T_f is compact. Quotient of compact [0,1] by a continuous map:
since |d_f(s,t) - d_f(s',t')| <= 4 ||f||_inf |(s,t) - (s',t')|, the
projection [0,1] -> T_f is continuous; the image of compact is
compact.
(c) Continuity of f -> T_f. For f, f~ continuous on [0,1],
| d_f(s, t) - d_{f~}(s, t) |
= | (f - f~)(s) + (f - f~)(t)
- 2 ( min_{s^t..s v t} f - min_{s^t..s v t} f~ ) |
<= 4 || f - f~ ||_inf. (6.9)
Reason: the min differs by at most ||f - f~||_inf, and the two
point evaluations each by at most the same. So 1 + 1 + 2 = 4.
Equal-time representatives of T_f and T_{f~} form a correspondence
with distortion at most 4 ||f - f~||_inf. And the uniform time on
[0,1] couples the measures exactly (each is the pushforward of
Lebesgue by the natural projection). Lemma 6.3 therefore gives
d_GHP( T_f, T_{f~} ) <= 4 ||f - f~||_inf. (6.10)
So f -> T_f is continuous from the sup norm to GHP.
REMARK. We need f(s) >= 0 for the triangle inequality. A Brownian
excursion is nonnegative. Our random f (below) is a nonnegative
piecewise linear (PWL) interpolation.
6.7. THE NORMALIZING CONSTANT
Define
c(q) = nu / ( sqrt(2) beta sigma )
= sigma / ( 2 sqrt(2) beta ). (6.11)
Check the equivalence: nu = sigma^2 / 2, so nu/(sqrt(2) beta sigma) =
(sigma^2/2) / (sqrt(2) beta sigma) = sigma / (2 sqrt(2) beta).
c(q) is deterministic, positive, and finite:
- sigma > 0 by (4.13) (finite variance).
- beta > 0 by (6.2).
6.8. PROOF OF THE MAIN THEOREM (THEOREM A)
Let f_N interpolate W_j / (sigma sqrt N) at the grid points j/N for
j = 0, ..., N-1 linearly, and set f_N(1) = 0.
NONNEGATIVE, ZERO ENDPOINTS.
By (5.2), W_j >= 0 for j < N. So f_N >= 0. f_N(0) = W_0/(sigma sqrt N)
= 0. f_N(1) = 0 by definition.
Replacing the exploration's last value W_N = -1 by zero changes its
normalized interpolation by at most 1 / (sigma sqrt N). By Proposition
5.1 (project to the first coordinate of the joint limit),
f_N ==> e in C([0, 1]). (6.12)
MAP-TO-WALK COMPARISON.
For grid points j/N, j'/N with 0 <= j <= j' < N, (6.6) and N = 2n + 1
give
max_{j, j' < N}
| ( c(q) / sqrt(n) ) d_{M_n}( pi(j), pi(j') )
- sqrt( N / (2n) ) d_{f_N}( j/N, j'/N ) |
= o_P(1). (6.13)
CHECK THE CONVERSION.
From (6.6), d_{M_n} ~ (beta/nu) (W_j + W_{j'} - 2 min W_r). Multiply
by c(q)/sqrt(n) = sigma / (2 sqrt(2) beta sqrt(n)):
(beta/nu) * sigma / (2 sqrt(2) beta sqrt(n))
= sigma / (2 sqrt(2) nu sqrt(n)).
= sigma / (2 sqrt(2) (sigma^2/2) sqrt(n))
= 1 / (sqrt(2) sigma sqrt(n)).
Meanwhile,
sqrt( N / (2n) ) d_{f_N}( j/N, j'/N )
= sqrt( N / (2n) ) * (1 / (sigma sqrt N))
* ( W_j + W_{j'} - 2 min W_r )
= (1 / (sigma sqrt(2n))) * ( W_j + W_{j'} - 2 min W_r )
= ( W_j + W_{j'} - 2 min W_r ) / (sqrt(2) sigma sqrt(n)).
(using N = 2n + 1)
So the two expressions agree exactly up to o_P(1).
Since N/(2n) -> 1, that deterministic factor can be replaced by 1.
Hence:
max_{j, j' < N}
| ( c(q) / sqrt(n) ) d_{M_n}( pi(j), pi(j') )
- d_{f_N}( j/N, j'/N ) |
= o_P(1). (6.14)
THE CORRESPONDENCE.
For s in [0, 1], put j_N(s) = min( floor(N s), N - 1 ), and write
[s] for the class of s in T_{f_N}. Define
R_N = { ( pi(j_N(s)), [s] ) : s in [0, 1] }. (6.15)
R_N projects onto both sides:
- Onto X: pi is onto V(M_n) (Lemma 6.1). For every map vertex, some s
maps to it.
- Onto Y: every s gives [s] in T_{f_N}.
Rounding times. d_{f_N}(j_N(s)/N, j_N(t)/N) vs d_{f_N}(s, t) differs
by at most 4 omega_{f_N}(1/N), where omega is the uniform modulus of
continuity. Continuous-path tightness makes omega_{f_N}(1/N) -> 0 in
probability (a tight continuous process has vanishing mesh-1/N
modulus).
By (6.14) and rounding:
dis( R_N ) = o_P(1). (6.16)
MASS COUPLING.
The measure mu_{f_N} of T_{f_N} is the pushforward of Lebesgue by
s -> [s]. Each preorder cell [j/N, (j+1)/N) maps to the singleton
{pi(j)} (as a tree node index: s -> [s] pins to the vertex pi(j)).
So
mu_{f_N} under s -> [s] = mu_bar_n
:= (1/N) sum_{j = 0}^{N-1} delta_{pi(j)}.
(6.17)
By Lemma 6.2,
mu_bar_n = ((N-1)/N) mu_n + (1/N) delta_{pi(0)},
|| mu_bar_n - mu_n ||_{TV} <= 1/N. (6.18)
GHP BOUND.
Applying Lemma 6.3 (GHP correspondence) to R_N with measures mu_{f_N}
(on Y = T_{f_N}) and mu_bar_n (on X = M_n scaled by c(q)/sqrt(n)):
d_GHP( (V(M_n), (c(q)/sqrt(n)) d_{M_n}, mu_bar_n),
(T_{f_N}, d_{f_N}, mu_{f_N}) )
<= dis( R_N ) = o_P(1). (6.19)
Using (6.18) to swap mu_bar_n for mu_n at cost 1/N = o(1):
d_GHP( (V(M_n), (c(q)/sqrt(n)) d_{M_n}, mu_n),
(T_{f_N}, d_{f_N}, mu_{f_N}) )
= o_P(1). (6.20)
SENDING N TO INFINITY.
We have f_N ==> e in C([0,1]) by (6.12), NOT convergence in sup norm.
Weak convergence is ENOUGH via the continuous-mapping theorem: for
every bounded Lipschitz test function G on the space of compact metric
probability spaces, the map f -> T_f is continuous by (6.10), so
G o (f -> T_f)
is a bounded continuous function on C([0,1]). By f_N ==> e,
E[ G( T_{f_N} ) ] -> E[ G( T_e ) ]. (6.21)
That is, T_{f_N} ==> T_e as random compact metric probability spaces
up to isometry.
ASSEMBLE.
From (6.20), the GHP distance between the rescaled map
(V(M_n), (c(q)/sqrt(n)) d_{M_n}, mu_n) and T_{f_N} is o_P(1).
From (6.21), T_{f_N} ==> T_e in distribution.
Together, for every bounded Lipschitz test G:
E[ G( (V(M_n), (c(q)/sqrt(n)) d_{M_n}, mu_n) ) ]
- E[ G( T_e ) ]
= E[G(map_n) - G(T_{f_N})] + E[G(T_{f_N}) - G(T_e)]
-> 0 + 0,
where the first term goes to zero by (6.20) plus bounded Lipschitz of
G, and the second by (6.21). So:
( V(M_n), c(q) n^{-1/2} d_n, mu_n ) ==> ( T_e, d_e, mu_e ),
where c(q) = sigma / (2 sqrt(2) beta). This is Theorem A. []
6.9. THE QUICK MAP: WHAT IS USED WHERE
- Finite FK marginal on M_n: from (1.2)-(1.3) (decoration sum
factors into a constant t times a(M)).
- a_n u^n <= C n^{-3/2}: Corollary 1.3, from Catalan + Theorem 1.2.
- s_n := sum n a_n u^n x^n >= c (1-x)^{-1/2}: Theorem 3.1 (Part 3),
using the strict drift (2.9) from Part 2.
- Criticality Phi(v) = Tau, 2v Phi'(v) = Phi(v), and finite variance
Phi''(v) < infinity: Lemma 4.2 (Part 4), using the ladder lower
bound s_n >= c (1-x)^{-1/2}.
- Marked tree has exact map marginal: Proposition 4.3 (Part 4).
- Joint coding limit + max degree: Proposition 5.1 + Corollary 5.2
(Part 5), from Broutin-Marckert 2014.
- Uniform LLN for labels 0 <= b <= k: Theorem 5.5 (Part 5).
- Map distance = sum of block distances + O(Delta_N):
Lemma 6.1 (Part 6).
- Degree measure = uniform on nonroot nodes: Lemma 6.2 (Part 6).
- Continuity of f -> T_f + GHP correspondence: Lemmas 6.3 and 6.7
(Part 6).
==============================================================================
END OF PROOF
==============================================================================