低不一致シーケンス

数学において、低不一致数列とは、すべての値に対してという性質を持つ数列のことである。${\displaystyle N}$、そのサブシーケンス${\displaystyle x_{1},\ldots ,x_{N}}$不一致が少ない。

大まかに言えば、数列の不一致度は、数列内の点が任意の集合Bに収まる割合が、Bの尺度にほぼ比例する場合に低くなります。これは、平均的には（ただし、個々のサンプルではそうではありません）均等分布数列の場合に起こります。不一致度の具体的な定義は、 Bの選択（超球、超立方体など）や、各 B の不一致度の計算方法（通常は正規化）と結合方法（通常は最悪の値を取る）によって異なります。

低不一致数列は、一様分布乱数の代替としてよく用いられることから、準乱数列とも呼ばれます。「準」という修飾語は、低不一致数列の値が乱数でも擬似乱数でもないことをより明確に示すために用いられますが、このような数列は乱数の特性をいくつか共有しており、準モンテカルロ法などの特定のアプリケーションでは、その不一致の小ささが重要な利点となります。

準乱数は、純粋な乱数に比べて、対象となる領域を迅速かつ均等にカバーできるという利点がある。

準乱数には、確率密度関数の特性関数を求める場合や、ノイズの少ない決定論的関数の導関数を求める場合など、2つの有用な応用例があります。準乱数を用いることで、高次のモーメントを非常に高い精度で迅速に計算できます。

ソートを伴わない応用例としては、統計分布の平均、標準偏差、歪度、尖度を求める場合や、複雑な決定論的関数の積分および全体における最大値と最小値を求める場合などが挙げられる。準乱数は、ニュートン・ラフソン法のように局所的にしか機能しない決定論的アルゴリズムの開始点を提供するためにも使用できる。

準乱数は探索アルゴリズムと組み合わせることもできます。探索アルゴリズムを用いることで、準乱数を使用して統計分布の最頻値、中央値、信頼区間、累積分布、および決定論的関数のすべての局所最小値とすべての解を求めることができます。

セットの不一致${\displaystyle P=\{x_{1},\dots ,x_{N}}\}$ニーダーライターの記法 を用いると、次のように定義される。$${\displaystyle D_{N}(P)=\sup _{B\in J}\left|{\frac {A(B;P)}{N}}-\lambda _{s}(B)\right|}$$

どこ$\displaystyle \lambda _{s}}$は${\displaystyle s}$次元ルベーグ測度、 ${\displaystyle A(B;P)}$は、${\displaystyle P}$に該当する${\displaystyle B}$、 そして${\displaystyle J}$は、${\displaystyle s}$次元間隔またはボックスの形式

$${\displaystyle \prod _{i=1}^{s}[a_{i},b_{i})=\{\mathbf {x} \in \mathbf {R} ^{s}:a_{i}\leq x_{i}<b_{i}\}\,}$$

どこ$\displaystyle 0\leq a_{i}<b_{i}\leq 1}$。

星の不一致${\displaystyle D_{N}^{*}(P)}$も同様に定義されるが、上限は集合上で取られる。${\displaystyle J^{*}}$長方形の箱の形状

$${\displaystyle \prod _{i=1}^{s}[0,u_{i})}$$

どこ$u_i$は半開区間[0, 1)に含まれる。

2人は以下の関係にある

$${\displaystyle D_{N}^{*}\leq D_{N}\leq 2^{s}D_{N}^{*}.\,}$$

注：これらの定義では、不一致は一様集合の最悪ケースまたは最大点密度偏差を表します。ただし、他の誤差尺度も意味があり、他の定義や変動尺度につながります。たとえば、${\displaystyle L^{2}}$-不一致または修正された中心${\displaystyle L^{2}}$不一致度は、均一な点集合の品質を比較するためにも頻繁に使用されます。どちらも、大規模な場合、計算がはるかに容易です。${\displaystyle N}$そして${\displaystyle s}$。

させて${\displaystyle {\overline {I}}^{s}}$になる${\displaystyle s}$次元単位立方体、${\displaystyle {\overline {I}}^{s}=[0,1]\times \cdots \times [0,1]}$。 させて${\displaystyle f}$変動範囲が限定されている${\displaystyle V(f)}$の上${\displaystyle {\overline {I}}^{s}}$ハーディとクラウスの意味で。${\displaystyle x_{1},\ldots ,x_{N}}$で${\displaystyle I^{s}=[0,1)^{s}=[0,1)\times \cdots \times [0,1)}$、

$${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|\leq V(f)\,D_{N}^{*}(x_{1},\ldots ,x_{N}).}$$ コクスマ・フラフカの不等式は、次の意味で厳密である。任意の点集合に対して${\displaystyle \{x_{1},\ldots ,x_{N}\}}$で${\displaystyle I^{s}}$そしてどんな${\displaystyle \varepsilon >0}$関数があります${\displaystyle f}$限定された変動と${\displaystyle V(f)=1}$そのため

$${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|>D_{N}^{*}(x_{1},\ldots ,x_{N})-\varepsilon .}$$

したがって、数値積分規則の品質は、不一致のみに依存します。${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})}$。

させて${\displaystyle D=\{1,2,\ldots ,d\}}$。 のために${\displaystyle \emptyset \neq u\subseteq D}$私たちは書く $${\displaystyle dx_{u}:=\prod _{j\in u}dx_{j}}$$ そして、${\displaystyle (x_{u},1)}$xからuに含まれない座標を置き換えることによって得られる点${\displaystyle 1}$。 それから

$${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du=\sum _{\emptyset \neq u\subseteq D}(-1)^{|u|}\int _{[0,1]^{|u|}}\operatorname {disc} (x_{u},1){\frac {\partial ^{|u|}}{\partial x_{u}}}f(x_{u},1)\,dx_{u},}$$

どこ${\displaystyle \operatorname {disc} (z)={\frac {1}{N}}\sum _{i=1}^{N}\prod _{j=1}^{d}1_{[0,z_{j})}(x_{i,j})-\prod _{j=1}^{d}z_{i}}$これは不一致関数です。

積分と和に対するコーシー・シュワルツの不等式をフラウカ・ザレンバの恒等式に適用すると、次の式が得られます。${\displaystyle L^{2}}$Koksma-Hlawka 不等式のバージョン:

$${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|\leq \|f\|_{d}\operatorname {disc} _{d}(\{t_{i}\}),}$$

どこ

$${\displaystyle \operatorname {disc} _{d}(\{t_{i}\})=\left(\sum _{\emptyset \neq u\subseteq D}\int _{[0,1]^{|u|}}\operatorname {disc} (x_{u},1)^{2}\,dx_{u}\right)^{1/2}}$$

そして

$${\displaystyle \|f\|_{d}=\left(\sum _{u\subseteq D}\int _{[0,1]^{|u|}}\left|{\frac {\partial ^{|u|}}{\partial x_{u}}}f(x_{u},1)\right|^{2}dx_{u}\right)^{1/2}.}$$

${\displaystyle L^{2}}$不一致は、与えられた点集合に対して高速な明示的計算が可能であるため、実用上非常に重要です。このようにして、点集合最適化ツールを簡単に作成できます。${\displaystyle L^{2}}$不一致を基準とする。

大規模な点集合の差異の正確な値を求めるのは計算上困難である。エルデシュ・トゥラン・コクスマの不等式は上限値を与える。

させて${\displaystyle x_{1},\ldots ,x_{N}}$点${\displaystyle I^{s}}$そして${\displaystyle H}$は任意の正の整数とする。

$${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq \left({\frac {3}{2}}\right)^{s}\left({\frac {2}{H+1}}+\sum _{0<\|h\|_{\infty }\leq H}{\frac {1}{r(h)}}\left|{\frac {1}{N}}\sum _{n=1}^{N}e^{2\pi i\langle h,x_{n}\rangle }\right|\right)}$$

どこ

$${\displaystyle r(h)=\prod _{i=1}^{s}\max\{1,|h_{i}|\}\quad {\text{for}}\quad h=(h_{1},\ldots ,h_{s})\in \mathbb {Z} ^{s}.}$$

予想1.定数が存在する${\displaystyle c_{s}}$寸法のみに依存する${\displaystyle s}$、したがって $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c_{s}{\frac {(\ln N)^{s-1}}{N}}}$$ 任意の有限点集合に対して${\displaystyle {x_{1},\ldots ,x_{N}}}$。

予想2.定数が存在する${\displaystyle c'_{s}}$のみに依存する :${\displaystyle s}$次のような場合：${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c'_{s}{\frac {(\ln N)^{s}}{N}}}$

無限の数の${\displaystyle N}$任意の無限数列に対して${\displaystyle x_{1},x_{2},x_{3},\ldots }$。

これらの予想は同等である。これらは証明されている。${\displaystyle s\leq 2}$WM Schmidtによる。高次元の場合、対応する問題はまだ未解決である。最もよく知られている下限値は、Michael Laceyとその共同研究者によるものである。

させて${\displaystyle s=1}$。 それから

$${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2N}}}$$

任意の有限点集合に対して${\displaystyle \{x_{1},\dots ,x_{N}}\}$。

させて${\displaystyle s=2}$WM Schmidt は、任意の有限点集合に対して、${\displaystyle \{x_{1},\dots ,x_{N}}\}$、

$${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq C{\frac {\log N}{N}}}$$

どこ

$${\displaystyle C=\max _{a\geq 3}{\frac {1}{16}}{\frac {a-2}{a\log a}}=0.023335\dots .}$$

任意の寸法${\displaystyle s>1}$KFロスは、

$${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2^{4s}}}{\frac {1}{((s-1)\log 2)^{\frac {s-1}{2}}}}{\frac {\log ^{\frac {s-1}{2}}N}{N}}}$$

任意の有限点集合に対して${\displaystyle \{x_{1},\dots ,x_{N}}\}$ヨゼフ・ベック^{[ 1 ]}は、この結果を3次元で二重対数改善した。これはD.ビリクとMTレイシーによって単一対数のべき乗に改善された。s > 2に対する最もよく知られている境界は、 D .ビリク、MTレイシー、A.ヴァガルシャキヤンによるものである。^{[ 2 ]}  ${\displaystyle t>0}$sに応じて $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq t{\frac {\log ^{{\frac {s-1}{2}}+t}N}{N}}}$$

任意の有限点集合に対して ${\displaystyle \{x_{1},\dots ,x_{N}}\}$。

平均局所不一致の一般的な下限は、最小ギャップサイズと平均ギャップを超えるギャップサイズのみを使用して計算できます^{[ 3 ]}。

乱数の分布はどのようなものでも一様分布にマッピングでき、準乱数も同様にマッピングできるため、この記事では多次元一様分布上での準乱数の生成のみを扱います。

既知の数列の構成法では、 $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq C{\frac {(\ln N)^{s}}{N}}.}$$ どこ${\displaystyle C}$は、数列によって異なる定数です。予想2以降、これらの数列は可能な限り最良の収束次数を持つと考えられています。以下の例は、ファン・デル・コルプト数列、ハルトン数列、ソボル数列です。一般的な制限の1つは、構成法では通常、収束次数しか保証できないことです。実際には、低い不一致は、次の場合にのみ達成できます。${\displaystyle N}$は十分に大きく、与えられた s が大きい場合、この最小値は${\displaystyle N}$非常に大きくなる可能性があります。これは、例えばモンテカルロ解析を実行することを意味します。${\displaystyle s=20}$変数と${\displaystyle N=1000}$低不一致シーケンスジェネレータからのポイントは、精度をわずかに向上させるだけかもしれない。

乱数

準乱数列は、乱数に負の相関を課すことによって乱数から生成できる。その方法の一つは、乱数のセットから始めることである。${\displaystyle r_{i}}$の上${\displaystyle [0,0.5)}$そして準乱数を生成する${\displaystyle s_{i}}$均一な${\displaystyle [0,1)}$使用方法:

${\displaystyle s_{i}=r_{i}}$のために${\displaystyle i}$奇妙で${\displaystyle s_{i}=0.5+r_{i}}$のために${\displaystyle i}$平。

初期乱数を使ってそれを行う2つ目の方法は、オフセット0.5のランダムウォークを構築することです。例：

$${\displaystyle s_{i}=s_{i-1}+0.5+r_{i}{\pmod {1}}.\,}$$

つまり、前の準乱数に0.5と乱数を加え、その結果を1で割った 余りを取る。

複数の次元の場合、適切な次元のラテン方格を用いてオフセットを設けることで、領域全体が均等に覆われるようにすることができる。

ハルトンシーケンス

ハルトン数列は、ファン・デル・コルプト数列を高次元に自然に一般化したものである。sを任意の次元とし、b ₁ , ..., b _{s を}1 より大きい任意の互いに素な整数とする。

$${\displaystyle x(n)=(g_{b_{1}}(n),\dots ,g_{b_{s}}(n)).}$$

すると、b ₁、 ...、b _sのみに依存する定数Cが存在し、シーケンス { x ( n )} _{n ≥1}はs次元シーケンスで、

$${\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C'{\frac {(\log N)^{s}}{N}}.}$$

ハマーズリーがセット

させて${\displaystyle b_{1},\ldots ,b_{s-1}}$互いに素な1より大きい正の整数とする。${\displaystyle s}$そして${\displaystyle N}$、${\displaystyle s}$-次元ハマーズリーセットのサイズ${\displaystyle N}$^{[ 8 ]}で定義される

$${\displaystyle x(n)=\left(g_{b_{1}}(n),\dots ,g_{b_{s-1}}(n),{\frac {n}{N}}\right)}$$

のために${\displaystyle n=1,\ldots ,N}$。 それから

$${\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C{\frac {(\log N)^{s-1}}{N}}}$$

どこ${\displaystyle C}$は、のみに依存する定数です。${\displaystyle b_{1},\ldots ,b_{s-1}}$。

注：式から、ハマーズリー集合は実際にはハルトン数列であることがわかりますが、線形掃引を追加することで次元が1つ増えます。これは、次の場合にのみ可能です。 ${\displaystyle N}$は事前にわかっています。線形セットは、一般に可能な限り最小の1次元不一致を持つセットでもあります。残念ながら、高次元の場合、そのような「不一致記録セット」は知られていません。${\displaystyle s=2}$ほとんどの低不一致点集合生成器は、少なくともほぼ最適な不一致値を提供する。

下に示した点は、Sobol' 型のシーケンスの最初の 100、1000、および 10000 要素です。比較のために、擬似乱数点のシーケンスの 10000 要素も示しています。低不一致シーケンスは、TOMSアルゴリズム 659によって生成されました。 ^{[ 10 ]} Fortran でのアルゴリズムの実装はNetlibから入手できます。

• 不一致理論
• マルコフ連鎖モンテカルロ法
• 準モンテカルロ法
• 疎なグリッド
• 系統的サンプリング

• ACMアルゴリズム集（アルゴリズム647、659、738を参照。）
• GNU科学ライブラリからの準ランダムシーケンス
• FinancialMathematics.Comにおける制約条件付き準ランダムサンプリング
• C++によるソボル数列生成器
• SciPy QMC APIリファレンス：scipy.stats.qmc