数論と力学系との融合による擬似乱数および準乱数生成アルゴリズムの構築とその応用

擬似乱数および超一様分布列（low-discrepancy sequence; 準乱数とも呼ばれる）は，どちらも確率的シミュレーションの基礎として重要である．本研究課題では，数論的数の上の力学系を用いることによって，数論的アルゴリズムと力学系的アルゴリズムの良さを兼ね備えた新しい擬似乱数および超一様分布列の生成アルゴリズムの構築を目指して研究を行っている．初年度にあたる令和4年度では，ニュートン法を使った真軌道擬似乱数生成の高速化に関して，誤差および計算量の評価を行った．ニュートン法では近似解しか得られないため，生成する擬似乱数列の長さに対してニュートン法を何回反復すれば真軌道計算の場合と（ほぼ）同じ擬似乱数列が得られるかの評価をしておく必要がある．ここでは，2次代数的整数の場合と3次代数的整数の場合とに分けて誤差の評価を行った．また，真軌道計算を用いる場合とニュートン法を用いる場合のそれぞれについて，計算量（computational complexity）の評価も行った．長さNの擬似乱数列を生成するのに必要となる計算量は，真軌道計算ではO(N^2)，ニュートン法ではO(N log N)より少し大きくなることを示した．さらに，誤差を評価する過程で，ニュートン法から得られる擬似乱数列の最初のNビットが，真軌道計算から得られるものと一致するための十分条件が得られた．この条件がみたされるかは，ニュートン法から得られるビット列のパターンにより，簡単に判定できる．超一様分布列の生成アルゴリズムの構築に関しては，p進数上の回転に相当する写像から生成される数列が，1次元超一様分布列であることを証明した．

擬似乱数および超一様分布列（low-discrepancy sequence; 準乱数とも呼ばれる）は，どちらも確率的シミュレーションの基礎として重要である．本研究課題では，数論的数の上の力学系を用いることによって，数論的アルゴリズムと力学系的アルゴリズムの良さを兼ね備えた新しい擬似乱数および超一様分布列の生成アルゴリズムの構築を目指して研究を行っている．初年度にあたる令和4年度では，ニュートン法を使った真軌道擬似乱数生成の高速化に関して，誤差および計算量の評価を行った．ニュートン法では近似解しか得られないため，生成する擬似乱数列の長さに対してニュートン法を何回反復すれば真軌道計算の場合と（ほぼ）同じ擬似乱数列が得られるかの評価をしておく必要がある．ここでは，2次代数的整数の場合と3次代数的整数の場合とに分けて誤差の評価を行った．また，真軌道計算を用いる場合とニュートン法を用いる場合のそれぞれについて，計算量（computational complexity）の評価も行った．長さNの擬似乱数列を生成するのに必要となる計算量は，真軌道計算ではO(N^2)，ニュートン法ではO(N log N)より少し大きくなることを示した．さらに，誤差を評価する過程で，ニュートン法から得られる擬似乱数列の最初のNビットが，真軌道計算から得られるものと一致するための十分条件が得られた．この条件がみたされるかは，ニュートン法から得られるビット列のパターンにより，簡単に判定できる．超一様分布列の生成アルゴリズムの構築に関しては，p進数上の回転に相当する写像から生成される数列が，1次元超一様分布列であることを証明した．