高次元均等分布性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/09/21 14:27 UTC 版)
「64ビット最適均等分布F2-線形発生法」の記事における「高次元均等分布性」の解説
高次元均等分布性は、擬似乱数発生法の理論的評価指標であり、次に定義されるvビット精度k次元均等分布性により評価される。 擬似乱数列x0, x1, ..., xP-1, xP = x0, ... を周期Pの符号なしwビット2進整数列とする。ここで、wはコンピュータのワードサイズとする(64ビット出力の場合、w = 64)。また、truncv(xi)をxiの上位vビットのみを取りだしたものとする。このとき、一周期に対して、連続したk個の出力を組にしたvkビットの組(truncv(xi), truncv(xi+1), ..., truncv(xi+k-1)), i = 0, ..., P-1 に着目する。wビット整数列がvビット精度k次元均等分布するとは、上述のvkビットを一周期Pに渡って見た際に、2kv通りのすべてのビットパターンが同じ回数同じだけ出現するときにいう。ただし、全部0の組が1回少ないものとする。 この定義は、高位のビットは、より大きな数を表すため、その動きが重要であるという仮定に基づく。与えられた上位vビットに対して、この性質をみたす最大の次元kをvビット精度均等分布次元と呼び、k(v)で表す。特に、出力列{xi}の上位vビットは、次元k(v)までは、一様に分布することが保証される。したがって、擬似乱数における一様性の規準として、各v = 1, 2, ..., wに対して、なるべく高い次元k(v)をとることが望ましい。 一方、各v = 1, 2, ..., wに対して、 k(v) ≤ log2⌊(P+1)/v⌋ となり、均等分布次元k(v)は上限をもつ。そこで、上限とk(v)の差の和を Δ = ∑(log2⌊(P+1)/v⌋ -k(v)) とおく(ただし、∑はv = 1, 2, ..., wにおける和とする)。Δ = 0のとき、すなわち、すべての上位ビットv = 1, 2, ..., wに対して、均等分布次元k(v)が理論上の上限に達しているとき、最適均等分布性をもつという。
※この「高次元均等分布性」の解説は、「64ビット最適均等分布F2-線形発生法」の解説の一部です。
「高次元均等分布性」を含む「64ビット最適均等分布F2-線形発生法」の記事については、「64ビット最適均等分布F2-線形発生法」の概要を参照ください。
- 高次元均等分布性のページへのリンク
