The Setting
Take a Galton-Watson tree whose critical, finite-variance offspring distribution is supported on even integers, so that its vertex count is necessarily odd. The question is the cost of conditioning to have size : at what rate does the probability that decay as ?
Offspring Distributions and Tree Codes
A critical even offspring distribution is a real-valued function on that is nonnegative at every , sums to , vanishes at every odd , satisfies and , has mean , and has a finite second moment .✦ The offspring probability mass function of a critical even offspring distribution is the probability law on assigning mass to each .✦ For a critical even offspring distribution and a natural number , the independent and identically distributed (i.i.d.) offspring product measure on is the product measure of over the indices .✦
The offspring distribution variance of a critical even offspring distribution is the real sum (1): (1)✦ The offspring standard deviation of a critical even offspring distribution is the square root of the offspring distribution variance.✦
For a natural number and a sequence indexed by , the total step of is the integer sum (2): (2)✦ Given a natural number , a degree sequence , and a step , the degree sequence partial walk is the integer (3): (3)✦
A discrete bridge sequence of length is a degree sequence in whose degree sequence partial walk satisfies ; let denote the set of all discrete bridge sequences of length .✦ Given a critical even offspring distribution and a discrete bridge sequence of length , the bridge weight is the real product .✦ The bridge partition function of length under a critical even offspring distribution is the real sum (4): (4)✦
The valid tree code condition on a degree sequence of length is the requirement that and for every .✦ A Lukasiewicz tree code of length is a degree sequence in meeting the valid tree code condition, and denotes the set of all Lukasiewicz tree codes of length .✦ For a Lukasiewicz tree code of length and a critical even offspring distribution , the tree code weight is the real product .✦ For a critical even offspring distribution and a natural number , the tree code partition function is the real sum (5): (5)✦
The Claim
Theorem 1. Let be a critical even offspring distribution with offspring probability mass function and offspring standard deviation . The tree code partition function along odd lengths satisfies (6): (6)✦ For every integer , the bridge and tree code partition functions are related by the cycle identity (7): (7)✦ There exists a sequence of nonnegative real numbers tending to as such that, for every and every integer with even, the uniform local bound (8) holds: (8)✦ Along odd lengths , the bridge partition function satisfies (9): (9)✦
In the paper, the result reads: as tends to infinity through odd integers, , where is the critical even Galton-Watson tree and is its offspring standard deviation. The limit (6) replaces by the tree code partition function and expresses the asymptotic as the limit of a rescaled sequence along odd lengths as .
What Is Checked
The claims are stated over a critical even offspring distribution with offspring probability mass function , i.i.d. offspring product measure , offspring distribution variance , and offspring standard deviation , together with the total step , the degree sequence partial walk , discrete bridge sequences with bridge weights and bridge partition function , and Lukasiewicz tree codes satisfying the valid tree code condition with tree code weights and tree code partition function , for lengths and and integers and with even.