The Setting
Take a critical Galton-Watson tree with finite offspring variance and even offspring degrees, conditioned for to have vertices. Its Lukasiewicz exploration walk and vertex height process trace the tree in preorder, posing the question of what joint scaling limit their rescaled piecewise linear interpolations approach as grows.
In the continuum, shifting a Brownian bridge at its first global minimum via the Vervaat transform invites comparison with a standard normalized Brownian excursion on . Specializing the offspring law to the block weights of the Fortuin-Kasteleyn (FK) burger-order inventory model with parameter then asks whether the rescaled height path of a marked FK tree sample approaches the same Brownian excursion limit.
Tree Codes, Offspring Laws, and Path Interpolations
For a sequence of length , the degree sequence partial walk of is the integer sequence (1)✦ For any sequence of length , the total step of is the integer . A discrete bridge sequence of length is a sequence satisfying in (1).✦ A sequence satisfies the valid tree code condition if and for all ✦; the Lukasiewicz tree code set consists of all sequences of length satisfying this condition.
Given a positive integer and an offset , the cyclic rotation of degree array is the permutation of sending a sequence to .✦ Its restriction to discrete bridge sequences of length defines the cyclic rotation of bridges .✦ For a discrete bridge sequence of positive length , the good rotation index is the unique shift index whose cyclic rotation turns into a valid tree code✦, and the canonical tree code of is the Lukasiewicz tree code obtained by applying that shift.✦ For , the tree code from bridge map is the map sending each integer sequence to the Lukasiewicz tree code in obtained by applying its good rotation shift.
A critical even offspring distribution is a probability mass function on (its offspring probability mass function) such that for every odd , , , the mean is , and the second moment is finite.✦ For a critical even offspring distribution , the offspring distribution variance is the nonnegative real number (2), and the offspring standard deviation is the nonnegative real number . (2) A sequence of block offspring probability weights is a nonnegative real sequence satisfying . The doubled block mass sequence of a sequence is the sequence defined by for even and for odd . For block offspring probability weights satisfying , , , and , the constructed even offspring distribution is the critical even offspring distribution with mass sequence .✦
For a critical even offspring distribution and length , the independent and identically distributed (i.i.d.) offspring product measure on is the -fold product of .✦ For , conditioning the i.i.d. offspring product measure of length on total step gives the conditioned offspring bridge law✦, and pushing this law forward under the tree code from bridge map yields the conditioned tree code law on .✦ Given a family of measures on a measurable space , the conditional mark measure on code for is the product measure on , forming the tree code marking kernel from to , and the joint distribution of the conditioned tree code law at size with this kernel on gives the marked tree code law on . For a critical even offspring distribution and length , the tree code partition function is the nonnegative real number (3), and for each Lukasiewicz tree code the tree code weight is the nonnegative real number (3). (3)
For a sequence of length and an index , the tree vertex height is the number of indices such that for every integer with , where is given by (1).✦ For and a real sequence , the piecewise linear interpolation is defined using the interpolation hat functions for by (4) For a critical even offspring distribution with standard deviation from (2) and a Lukasiewicz tree code of length , the normalized preorder height path and the joint tree code path are formed from (4) as (5) For a critical even offspring distribution with standard deviation , any function , and , the tree code test expectation of under is the real number given using (3) and (5) by (6)
Brownian Bridges, the Vervaat Transform, and Excursions
Given a real-valued stochastic process on a probability space , its Brownian motion path is the restriction on , and its Brownian bridge path is given for by .✦
For any continuous path , its first minimum time is the least time satisfying for all .✦ Given and , the cyclic path shift is defined for by (7)✦ The Vervaat transform of is the continuous path defined by (7).
Given three real-valued processes on , the three-bridge excursion path of is the continuous path on defined by (8) and the standard Brownian excursion path is the continuous path equal to from (8) when continuous and zero otherwise.✦ Associated with is the diagonal Brownian excursion path , and for any function , the joint Brownian test expectation is the real number (9)
The Burger-order Inventory Model and Fortuin-kasteleyn Heights
An FK model parameter is a real probability .✦ An inventory order is either a flexible order or a fixed order of one of two burger types in ✦, and a burger-order alphabet letter is either a burger token of type or an inventory order, forming a five-letter alphabet .✦ For , the letter mass function assigns probability to each burger token, to the flexible order, and to each fixed order, inducing the letter distribution on . The i.i.d. inventory stream measure is the infinite product measure of this letter distribution on ✦, and for a stream and length , the letter stream initial word of is the word .
An inventory stack evaluation state is a pair consisting of a list of pending orders and a freshest-first stack of burger types in .✦ The evaluation of a word maps a finite word of letters in and an evaluation state to the state obtained by updating sequentially via single-step transitions (where an order consumes the freshest eligible burger).✦ The word reduction of a word in is its evaluation starting from empty pending orders and an empty burger stack✦, and a word satisfies the empty-reducing word condition if its word reduction leaves both lists empty.✦ Under , the empty-reducing word probability is the probability under that satisfies the empty-reducing word condition✦, and the total empty word probability is the real number . For , the flexible order parameter and inventory radius parameter are the real numbers (10)
A typed burger-order letter is either a burger token or an order token carrying an explicit type in ; the resulting four-letter alphabet consists of the tokens and for .✦ Given a stack of types in , the typed word stack execution processes a finite word of typed letters step by step and returns either the resulting stack or failure on an illegal closure✦; the empty-reducing typed word set consists of all typed words of length whose execution starting from an empty stack succeeds and terminates with an empty stack.✦ For a typed word and an initial stack of types in , the flexible closing count counts the flexible order closures encountered before any illegal closure when processing from ; writing , the inventory word monomial weight of at is , where is the length of .✦
For a finite sequence and a list of ordered pairs, forms a non-crossing arch matching on under three inductive rules: the empty pair list matches the empty sequence; matches whenever matches ; and matches whenever matches and matches .✦ The arch transposition product of a pair list is the permutation defined recursively by and , where is the transposition of and .✦ For a set , a two-stack matching certificate for a map along a finite sequence in consists of two non-crossing arch matchings and on whose combined endpoints form a permutation of , such that every pair satisfies and while every pair satisfies and , with stack matching mate permutation defined as the permutation .
Given a positive integer and a permutation on , its chord opening endpoints are the indices with , two openers and satisfy the chord crossing relation if either or ✦, and the chord intersection graph of is the simple graph on its openers whose edges are pairs satisfying this crossing relation.✦ A typed word of length satisfies the connected core word condition if, writing for its sequence of letters (so ), there exists a two-stack matching certificate for along such that is a chord opening endpoint of from which every chord opening endpoint of is reachable in the chord intersection graph of .✦ A connected typed core is a typed word satisfying the connected core word condition✦, and the optional core label set consists of an empty label with arity and all connected typed cores with arity ; an optional core label is an element of .
For and , the core generating polynomial coefficient and block generating polynomial coefficient are the real numbers (11) Under FK model parameters , the actual FK block mass at size is the real number defined from (10) and (11) by (12) For , the critical FK corner offspring law is the critical even offspring distribution constructed from the block weights in (12).
Given scalars , the parametric core label mass assigns weight to the empty label and weight (via the inventory word monomial weight at parameters and ) to each connected typed core .✦ Evaluating this mass at from (10) gives the root core mark mass and defines the root core mark distribution on . For each , the conditional core mark distribution on is the root core mark distribution conditioned on labels of arity if any such label exists, and the point mass at otherwise.✦ For , a marked tree code sample of size is a pair .✦ The law of marked code draw is the marked tree code law of at size with mark kernel ✦, and the actual tree height path scales (5) by the height scaling factor : (13)
The Claim
Theorem 1. Let be a critical even offspring distribution with standard deviation . For every probability space , any three independent standard Brownian motions on , and every bounded continuous function , the tree code test expectations (6) and joint Brownian test expectation (9) satisfy (14)✦ Furthermore, for any FK model parameter , any probability space , any three independent standard Brownian motions on , and pairs distributed according to for each , the actual tree height path (13) converges in distribution as to the standard Brownian excursion path : (15)✦ Finally, for any probability space , any standard Brownian motion on , and any three independent standard Brownian motions on , the Vervaat transform of the Brownian bridge path has the same distribution in as : (16)✦
In the paper, the result reads: under the critical even offspring assumptions on with standard deviation , the rescaled pair (interpolating the walk and height at tree size ) converges in distribution in to , where is a standard normalized Brownian excursion. The library states this convergence along through expectations of bounded continuous test functions on the piecewise linear paths and the diagonal Brownian excursion path in (14), alongside the FK height limit (15) and the Vervaat identity (16).
What Is Checked
The joint tree coding claim (14) is stated over any critical even offspring distribution with standard deviation , its tree code weights and partition functions , the piecewise linear joint tree code paths built from the partial walk and vertex height , three independent standard Brownian motions on a probability space , the diagonal Brownian excursion path , and bounded continuous test functions . The FK height limit (15) is stated over FK model parameters , the marked tree code law constructed from the critical FK corner offspring law (via the actual FK block masses (12) and the constructed even offspring distribution) and conditional core mark distributions (via connected typed cores, two-stack matching certificates, and chord intersection graphs), the actual tree height path , and the standard Brownian excursion path . The Vervaat identity (16) is stated over a standard Brownian motion and three independent standard Brownian motions on , the Brownian bridge path , the Vervaat transform via the first minimum time and cyclic path shift, and .
Beyond these claims, the library establishes that the actual FK block masses (12) satisfy for all ✦, with ✦ and ✦. It also establishes that rotating any discrete bridge sequence of positive length by its good rotation index satisfies the valid tree code condition✦, and that every continuous function on attains its global minimum at a least time in .✦