低不一致シーケンス

数学において、低不一致数列とは、すべての値に対してという性質を持つ数列のことである。${\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}}\}$. Jozef Beck ^[1] established a double log improvement of this result in three dimensions. This was improved by D. Bilyk and M. T. Lacey to a power of a single logarithm. The best known bound for s > 2 is due D. Bilyk and M. T. Lacey and A. Vagharshakyan.^[2] There exists a ${\displaystyle t>0}$ depending on s so that $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq t{\frac {\log ^{{\frac {s-1}{2}}+t}N}{N}}}$$

for any finite point set ${\displaystyle \{x_{1},\dots ,x_{N}}\}$.

Because any distribution of random numbers can be mapped onto a uniform distribution, and quasirandom numbers are mapped in the same way, this article only concerns generation of quasirandom numbers on a multidimensional uniform distribution.

There are constructions of sequences known such that $${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq C{\frac {(\ln N)^{s}}{N}}.}$$ where ${\displaystyle C}$ is a certain constant, depending on the sequence. After Conjecture 2, these sequences are believed to have the best possible order of convergence. Examples below are the van der Corput sequence, the Halton sequences, and the Sobol’ sequences. One general limitation is that construction methods can usually only guarantee the order of convergence. Practically, low discrepancy can be only achieved if ${\displaystyle N}$ is large enough, and for large given s this minimum ${\displaystyle N}$ can be very large. This means running a Monte-Carlo analysis with e.g. ${\displaystyle s=20}$ variables and ${\displaystyle N=1000}$ points from a low-discrepancy sequence generator may offer only a very minor accuracy improvement .

Random numbers

Sequences of quasirandom numbers can be generated from random numbers by imposing a negative correlation on those random numbers. One way to do this is to start with a set of random numbers ${\displaystyle r_{i}}$ on ${\displaystyle [0,0.5)}$ and construct quasirandom numbers ${\displaystyle s_{i}}$ which are uniform on ${\displaystyle [0,1)}$ using:

${\displaystyle s_{i}=r_{i}}$ for ${\displaystyle i}$ odd and ${\displaystyle s_{i}=0.5+r_{i}}$ for ${\displaystyle i}$ even.

A second way to do it with the starting random numbers is to construct a random walk with offset 0.5 as in:

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

That is, take the previous quasirandom number, add 0.5 and the random number, and take the result modulo 1.

For more than one dimension, Latin squares of the appropriate dimension can be used to provide offsets to ensure that the whole domain is covered evenly.

ハルトンシーケンス

ハルトン数列は、ファン・デル・コルプト数列を高次元に自然に一般化したものである。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}$^{[ 7 ]}で定義される

$${\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によって生成されました。 ^{[ 9 ]} Fortran でのアルゴリズムの実装はNetlibから入手できます。

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

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