ストリームの重なりの確率

遷移 $T$ が状態を長さ $P$ の 1 つのサイクル $C$ として巡回させる生成器を考える。$s \ge 2$ 本のストリームの長さを $L$ とし、$2L - 1 \le P$ とする。

1. 開始状態 $\sigma_1, \ldots, \sigma_s$ が $C$ 上の一様分布に従う互いに独立な確率変数ならば、ある 2 本のストリームが同じ状態を含む確率 $p_{\mathrm{overlap}}$ は $p_{\mathrm{overlap}} \le \dfrac{s(s-1)(2L-1)}{2P} \le \dfrac{s(s-1)L}{P}$ を満たす。
2. 開始状態を $\sigma_j = T^{jJ}(\sigma_0)$（$j = 0, \ldots, s-1$）と取り、$J \ge L$ かつ $sJ \le P$ ならば、どの 2 本のストリームも同じ状態を含まない。