再帰的な生成器の停止と大きさ

$0 \lt p \lt 1$ とする。$0$ と $1$ からなる有限の文字列（空の文字列 $\varepsilon$ を含む）の全体を $\{0, 1\}^{*}$ とし、確率空間の上に、独立な確率変数の族 $(\xi_u)_{u \in \{0, 1\}^{*}}$ で $P(\xi_u = 1) = p$、$P(\xi_u = 0) = 1 - p$ を満たすものが与えられているとする。文字列 $u$ のすべての真の接頭辞 $v$ について $\xi_v = 1$ であるとき、$u$ は生成されるといい、生成される文字列の全体を $\mathcal{T}$ とする（$\varepsilon$ は根で、つねに生成される。生成された $u$ は、$\xi_u = 1$ なら 2 つの子 $u0$、$u1$ をもつ節点、$\xi_u = 0$ なら葉である）。長さ $j$ の生成される文字列の個数を $Z_j$、木の大きさを $S = \sum_{j \ge 0} Z_j \in \{1, 2, \ldots\} \cup \{\infty\}$ とする。

1. $E[Z_j] = (2p)^j$。したがって $p \lt 1/2$ ならば $E[S] = \dfrac{1}{1 - 2p}$、$p \ge 1/2$ ならば $E[S] = \infty$。
2. $P(S \lt \infty) = \min\Bigl(1, \dfrac{1 - p}{p}\Bigr)$。すなわち $p \le 1/2$ ならば確率 $1$ で生成は止まり、$p \gt 1/2$ ならば止まらない確率が $\dfrac{2p - 1}{p} \gt 0$ である。
3. $p \lt 1/2$ のとき、任意の $a \gt 0$ について $P(S \ge a) \le \dfrac{1}{(1 - 2p)\,a}$。
4. 深さ $d$ で打ち切る（長さ $d$ の文字列は必ず葉にする）と、大きさはつねに $2^{d+1} - 1$ 以下である。