The Setting
Take a critical even Galton-Watson tree conditioned to have vertices and list its vertex out-degrees in preorder. Centered partial sums of these degrees trace a discrete excursion that determines the height of each vertex, while reversing the prefix up to a vertex picks out the degrees and child positions along its ancestral spine and sums vertex marks over that spine.
Critical Even Offspring Laws and Tree Codes
A critical even offspring distribution is a nonnegative real-valued mass function on the nonnegative integers summing to such that for every odd , , , , and .✦ The offspring distribution variance of a critical even offspring distribution is the nonnegative real number defined by (1): (1)✦
For a critical even offspring distribution and each , the independent and identically distributed (i.i.d.) offspring product measure on is the product measure of copies of .✦ Writing for the integers, the total step of an array is the integer given by (2): (2)✦ For a critical even offspring distribution and , the conditioned offspring bridge law on is the measure conditioned on the event .✦
Given , a degree sequence , and step , the degree sequence partial walk of at step is the integer .✦ A discrete bridge sequence of length is a sequence in satisfying .✦ Given , the valid tree code condition on a sequence is the condition that and for every .✦ A Lukasiewicz tree code of length is a sequence in satisfying the valid tree code condition, and denotes the set of Lukasiewicz tree codes of length .✦
When and , the cyclic rotation sends entrywise to ()✦ and induces a permutation of the discrete bridge sequences of length .✦ Every discrete bridge sequence of length admits a unique good rotation index such that satisfies the valid tree code condition.✦ The canonical tree code of a discrete bridge sequence of length is the Lukasiewicz tree code .✦ For any , each array with total step defines a discrete bridge sequence of length ✦, and for the tree code map sends each array in to a Lukasiewicz tree code of length .
Spine Ladder Law and Spine Records
The infinite offspring product measure on of a critical even offspring distribution is the countable product of copies of .✦ Given a stream and step , the offspring walk partial sum is the integer defined by (3), and denotes the sequence : (3)✦ The ladder epoch condition for an index and a stream is the condition that either , or for every and .✦ The first weak ladder epoch of a stream is the smallest index satisfying the ladder epoch condition for ✦, and the weak ladder overshoot of is the nonnegative integer .✦ The spine ladder variable pair of a stream is the pair ✦, and the offspring spine ladder distribution of a critical even offspring distribution on is the pushforward measure of under .✦
For an array (), the zero-extended stream is the stream with for and for .✦ For , the reversed prefix index map is for and for ✦, and the reversed prefix of a stream at is the stream with .✦ For a sequence and , the running maximum of up to is the integer ✦, and the set of weak record times up to is given by (4): (4)✦ Given , a Lukasiewicz tree code , and , the spine record set of at is the set .✦ For a stream and step , putting , the record type is the pair defined by (5): (5)✦ For , a Lukasiewicz tree code , , and , the spine record type is the pair ✦, and for the spine record vertex of is the index .✦
The Claim
Definition 1. For a critical even offspring distribution and size parameter , the conditioned tree code law on is the pushforward measure (6): (6)✦ Given , a sequence , and step , the tree height process is the integer given by (7): (7)✦ The exploration walk of an array () at step is the integer defined by (8): (8)✦ The offspring standard deviation of a critical even offspring distribution with variance is the nonnegative real number (9): (9)✦ For , a mark set , a weight function , a Lukasiewicz tree code , an index , and vertex marks , the marked spine sum is the sum (10): (10)✦
Theorem 1. If is a critical even offspring distribution with variance and offspring spine ladder distribution , then (11) holds: (11)✦
What Is Checked
The conditioned tree code law (6), tree height process (7), exploration walk (8), offspring standard deviation (9), spine mean identity (11), and marked spine sum (10) are stated over a critical even offspring distribution (a nonnegative real-valued mass function on summing to , vanishing on odd integers, with , , mean , and finite second moment), its variance and offspring spine ladder distribution , a size parameter or length , a degree sequence or array , and a Lukasiewicz tree code with index , a mark set , vertex marks , and a weight function .
Moreover, every stream admits an index satisfying the ladder epoch condition.✦