Random Trees An Interplay between Combinatorics and Probability
- PDF / 3,616,220 Bytes
- 466 Pages / 439 x 666 pts Page_size
- 71 Downloads / 235 Views
5QKPIMT,ZUW\I
:IVLWUQMVVI=VQ^MZ[Q\a WNMZ_MZ\]VO^WZJMPIT\MV
!;XZQVOMZ>MZTIO?QMV 8ZQV\MLQV/MZUIVa ;XZQVOMZ?QMV6M_AWZSQ[XIZ\WN;XZQVOMZ;KQMVKM*][QVM[[5MLQI [XZQVOMZI\
8ZWL]K\4QIJQTQ\a" 0. The generating function y(x) = n≥1 yn xn of the numbers yn = P{|T | = n} =
ν(T )
|T |=n
satisfies the functional equation y(x) = x Φ(y(x)), where Φ(t) = E tξ =
φj tj
j≥0
with φj = P{ξ = j}. Observe that ν(T ) =
Dj (T )
φj
= ω(T ).
j≥0
The weight of T is now the probability of T . If we condition the Galton-Watson tree T on |T | = n, we thus get the probability distribution (1.4) on Tn . Hence, the conditioned Galton-Watson trees are simply generated trees with φj = P{ξ = j} as above. We have here Φ(1) = j φj = 1, but this is no real restriction. In fact, if (φj )j≥0 is any sequence of non-negative weights satisfying the very weak condition Φ(x) = j≥0 φj xj < ∞ for some x > 0, then we can replace (as above) φj by abj φj with b = x and a = 1/Φ(x) and thus the simply generated tree is the same as the conditioned Galton-Watson tree with offspring distribution P{ξ = j} = φj xj /Φ(x). Consequently, for all practical purposes, simply generated trees are the same as conditioned Galton-Watson trees. The argument above also shows that the distribution of a conditioned Galton-Watson tree is not changed if we replace the offspring distribution ξ ˜ by ξ˜ with P{ξ˜ = j} = P{ξ = j} = τ j /Φ(τ ) and thus Φ(x) = Φ(τ x)/Φ(τ ) for any τ > 0 with Φ(τ ) < ∞. (Such modifications are called conjugate or tilted distributions.) 2
The letters “i.i.d.” abbreviate “independent and identically distributed”.
12
1 Classes of Random Trees
Note that
μ = Φ (1) = E ξ
is the expected value of the offspring distribution. If μ < 1, the Galton-Watson branching process is called sub-critical, if μ = 1, then it is critical, and if μ > 1, then it is supercritical. From a combinatorial point of view we do not have to distinguish between these three cases. Namely, if we replace the offspring distribution by a conjugate distribution as above, the new expected value is τ Φ (τ ) Φ˜ (1) = . Φ(τ ) We can thus always assume that the Galton-Watson process is critical, provided only that there exists τ > 0 with τ Φ (τ ) = Φ(τ ) < ∞, a weak condition that is satisfied for all interesting classes of Galton-Watson trees. It is usually convenient to choose a critical version, which explains why the equation τ Φ (τ ) = Φ(τ ) appears in most asymptotic results. A heuristic reason is that the probability of the event |T | = n that we condition on typically decays exponentially in the subcritical and supercritical cases but only as n−1/2 in the critical case, and it seems advantageous to condition on an event of not too small probability. Example 1.6 For planted plane trees (as in Example 1.2) we start with Φ(x) = 1/(1 − x). The equation τ Φ (τ ) = Φ(τ ) is τ (1 − τ )−2 = (1 − τ )−1 , which is solved by τ = 21 . Random planted plane trees are thus conditioned Galton-Watson trees with the critical offspring distribution given by Φ(
Data Loading...
