情報科学 › 乱数と確率的数値計算 › 擬似乱数生成器

有限状態の生成器は最終的に周期的

命題 2.3（「擬似乱数生成器」§2）・ ✓公理まで証明済み

生成器 $(S, T, g)$ と任意の種 $s_0$ について次が成り立つ。

状態の列 $(s_k)$ は最終的に周期的で、周期 $\lambda$ と前周期 $\mu$ は $\mu + \lambda \le |S|$ を満たす。
出力の列 $(y_k)$ も最終的に周期的で、その周期は $\lambda$ の約数である。特に $|S|$ 以下である。
$T$ が全単射ならば、状態の列も出力の列も純周期的である。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義

証明は Rikai の他の定理を参照していません（定義と論理だけで示されています）。

これを使っている定理証明で参照している 3 件

乗算型合同法の周期✓命題 3.6・擬似乱数生成器
法 $2^e$ の線形合同法の下位ビット✓命題 3.7・擬似乱数生成器
$F_2$ 線形生成器の最大周期✓定理 5.3・擬似乱数生成器

関連するノック 1 問

乱数と確率的数値計算第 5 問