The tree conditioned on λ_∅ ≥ k: tilted offspring laws and generation sizes #
The tree-law part of the proof of Lemma lem:S_lh (source lines 3066–3114, inventory P23).
Write π_s = P(λ_∅(𝒯) ≥ s) (piSeq), P_k = P(· | λ_∅(𝒯) ≥ k), Z_i = genCount i,
C_k = skelSize k = Z_0 + ⋯ + Z_{k-1}, L_k = Z_k.
cond_rootDegree_children_mem_tilt: fors ≥ 1, underP_sthe root hasjchildren with probabilityμ_tilt_s(j) = μ_j π_{s-1}^j / π_s(tiltLaw,j ≥ 1), and the child subtrees are then independent with lawP_{s-1};hasSum_tiltLaw,hasSum_mul_tiltLaw:μ_tilt_sis a probability law with meanm_s = π_{s-1} g'(π_{s-1}) / π_s(tiltMean).lintegral_genCount_cond_eq:E_k[Z_i] = m_k m_{k-1} ⋯ m_{k-i+1}fori ≤ k, obtained from the depth-one many-to-one formulasetLIntegral_sum_children.tiltMean_le:m_s ≤ κ exp(π_{s-1}/(κ μ_κ));lintegral_genCount_cond_le: oneC > 0withE_k[Z_i] ≤ C κ^iuniformly in0 ≤ i ≤ k(≤ Cwhenκ = 1), using∑_s π_s ≤ 1/μ_0.lintegral_skelSize_add_genCount_cond_le:E_k[C_k + L_k] ≤ C k(κ = 1,k ≥ 1) and≤ C κ^k(κ ≥ 2).
The paper's estimates m_s = 1 + O(π_{s-1}) (κ = 1) and m_s = κ + O(π_{s-1}) (κ ≥ 2)
are replaced by the explicit bound m_s ≤ κ + π_{s-1}/μ_κ ≤ κ exp(π_{s-1}/(κ μ_κ)), which
gives the same uniform constant.
Expected generation sizes on {λ_∅ ≥ k} #
𝐏_μ(λ_∅ ≥ k) = π_k, in ℝ≥0∞.
The recursion E[Z_{i+1}; λ_∅ ≥ k + 1] = G'_μ(π_k) E[Z_i; λ_∅ ≥ k]: on {λ_∅ ≥ k + 1}
there is no leaf among the first generations, and the children are independent.
The mean m_s = π_{s-1} g'(π_{s-1}) / π_s of the tilted offspring law μ_tilt_s (source lines
3088–3096).
Equations
Instances For
Exact first moments: for i ≤ k,
E[Z_i(𝒯); λ_∅(𝒯) ≥ k] = π_k m_k m_{k-1} ⋯ m_{k-i+1}.
Expected generation sizes under P_k = P(· | λ_∅ ≥ k) (source lines 3097–3107):
for i ≤ k, E_k[Z_i] = m_k m_{k-1} ⋯ m_{k-i+1}.
Bounds on the tilted means and the generation sizes #
m_s ≤ κ exp(π_{s-1} / (κ μ_κ)) for s ≥ 1: since π_s = g(π_{s-1}) ≥ μ_κ π_{s-1}^κ,
m_s ≤ κ + π_{s-1}/μ_κ (source lines 3097–3101: m_s = κ + O(π_{s-1})).
m_k m_{k-1} ⋯ m_{k-i+1} ≤ C κ^i uniformly in 0 ≤ i ≤ k, with
C = exp(1/(μ_0 κ μ_κ)), because ∑_s π_s ≤ 1/μ_0 (source lines 3097–3107).
Expected generation sizes (source lines 3097–3107, inventory P23): there is C > 0
such that, uniformly in 0 ≤ i ≤ k, E[Z_i(𝒯) | λ_∅(𝒯) ≥ k] ≤ C κ^i (that is, ≤ C when
κ = 1 and ≤ C κ^i when κ ≥ 2).
E_k[C_k + L_k] = ∑_{i ≤ k} E_k[Z_i].
Skeleton-plus-frontier bound (source lines 3108–3114, inventory P23): with
C_k = Z_0 + ⋯ + Z_{k-1} and L_k = Z_k, there is C > 0 such that
E[C_k + L_k | λ_∅ ≥ k] ≤ C k for all k ≥ 1 if κ = 1, and ≤ C κ^k for all k if
κ ≥ 2.
The tilted offspring law #
The tilted offspring law μ_tilt_s(j) = μ_j π_{s-1}^j / π_s for j ≥ 1 (and μ_tilt_s(0) = 0)
of a vertex that must remain protected for another s ≥ 1 generations (source lines
3088–3092).
Equations
- One or more equations did not get rendered due to their size.
Instances For
μ_tilt_s is a probability law on ℕ (s ≥ 1), since π_s = g(π_{s-1}).
The conditional tree law given λ_∅ ≥ s (source lines 3085–3092, inventory P23): for
s ≥ 1, under P(· | λ_∅(𝒯) ≥ s) the root has j children with probability μ_tilt_s(j), and,
given this, the child subtrees are independent with law P(· | λ_∅(𝒯) ≥ s - 1):
P(k_∅ = j, 𝒯_i ∈ A_i ∀ i < j | λ_∅ ≥ s) = μ_tilt_s(j) ∏_{i<j} P(A_i | λ_∅ ≥ s - 1).
Iterating, the first k generations under P(· | λ_∅ ≥ k) form a Galton–Watson tree with the
generation-dependent offspring laws μ_tilt_k, μ_tilt_{k-1}, …, μ_tilt_1.