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

線形合同法の格子構造

定理 4.2（「擬似乱数生成器」§4） ・ ✓公理まで証明済み

線形合同法 xk+1=(axk+c) mod mx_{k+1} = (ax_k + c) \bmod m と d≥1d \ge 1 について、

uk=1m(xk,xk+1,…,xk+d−1)∈[0,1)d,g=1m(1,a,…,ad−1),v0=cm(S0(a),S1(a),…,Sd−1(a))\boldsymbol{u}_k = \frac{1}{m}(x_k, x_{k+1}, \ldots, x_{k+d-1}) \in [0,1)^d, \qquad \boldsymbol{g} = \frac{1}{m}(1, a, \ldots, a^{d-1}), \qquad \boldsymbol{v}_0 = \frac{c}{m}\bigl(S_0(a), S_1(a), \ldots, S_{d-1}(a)\bigr)

と置き、L=Zg+ZdL = \mathbb{Z}\boldsymbol{g} + \mathbb{Z}^d とする。

  1. LL は余体積 1/m1/m の格子で、すべての k≥0k \ge 0 について uk∈(v0+L)∩[0,1)d\boldsymbol{u}_k \in (\boldsymbol{v}_0 + L) \cap [0,1)^d である。
  2. 全周期をもつとき、{uk:0≤k<m}=(v0+L)∩[0,1)d\{\boldsymbol{u}_k : 0 \le k < m\} = (\boldsymbol{v}_0 + L) \cap [0,1)^d である。

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

閉包の状態

✓ 公理まで証明済み

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

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

前提をたどる 証明が使う定理・定義（直接 2 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

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

関連するノック 1 問