Type of mathematical sequence
数学 において 、 低乖離数列 とは、 のすべての値に対して、その部分列の 乖離度 が小さいという 特性を持つ 数列のこと です 。 N {\displaystyle N} x 1 , … , x N {\displaystyle x_{1},\ldots ,x_{N}}
大まかに言えば、任意の集合B に含まれる点の割合が B の 測度 にほぼ比例する場合、数列の不一致は低いと言えます。これは、 等分布数列 の場合、平均的には（特定のサンプルではそうではないものの）そうなるでしょう。不一致の具体的な定義は、 B の選択 （ 超球面 、 超立方体 など）や、各 B の不一致の計算方法（通常は正規化）と結合方法（通常は最悪値を取る）によって異なります。
低乖離数列は、一様分布 乱数 の代替として一般的に用いられることから、 準乱数 列とも呼ばれます。「準」という修飾語は、低乖離数列の値がランダムでも 疑似ランダムでもないことをより明確に示すために使用されますが、このような列はランダム変数のいくつかの特性を共有しており、 準モンテカルロ法 などの特定の用途では、 その乖離度が低いことが重要な利点となります。
アプリケーション データポイント数の関数としての推定尖度の誤差。「加法準乱数」は c = ( √5 − 1)/2のときに最大誤差を与える。「ランダム」は乱数を6回実行した平均誤差を与える。平均は乱数の大きな変動の大きさを減らすために取られる 。 準乱数は、関心領域を迅速かつ均等にカバーするという点で、純粋な乱数よりも優れています。
有用な応用としては、確率密度関数 の 特性関数 を求めること と、 少量のノイズを含む決定論的関数の 微分関数を求めることが挙げられます。準乱数を用いることで、高次 モーメントを 非常に高速かつ高精度に計算することが可能になります。
ソートを伴わない応用としては、 統計分布の 平均 、 標準偏差 、 歪度 、 尖度を求めることや、難しい決定論的関数の 積分値 や大域的な 最大値と最小値を求めることが挙げられます。準乱数は、 ニュートン・ラプソン反復法 など、局所的にしか機能しない決定論的アルゴリズムの開始点を提供するためにも使用できます 。
準乱数は探索アルゴリズムと組み合わせることもできます。 探索アルゴリズムを 用いることで、準乱数を用いて 統計分布の 最頻値 、 中央値 、 信頼区間 、 累積分布、そして決定論的関数のすべての 局所的最小値 とすべての解を求めることができます。
数値積分における低矛盾列 数値積分 のさまざまな方法は、ある区間（例えば[0,1]）における 関数の積分を、 その区間内の 集合で評価された関数の平均として近似するものとして表現できます。 f {\displaystyle f} { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\} ∫ 0 1 f ( u ) d u ≈ 1 N ∑ i = 1 N f ( x i ) . {\displaystyle \int _{0}^{1}f(u)\,du\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).}
点が として選ばれる場合 、これは 長方形則 です。点がランダム（または 擬似ランダム ）に分布するように選ばれる場合、これは モンテカルロ法 です。点が低乖離数列の要素として選ばれる場合、これは 準モンテカルロ法 です。注目すべき結果である Koksma–Hlawka 不等式 （下記参照）は、このような方法の誤差が 2 つの項の積で制限されることを示しています。2 つの項の積の 1 つは のみに依存し 、もう 1 つは集合 の乖離数です 。 x i = i / N {\displaystyle x_{i}=i/N} f {\displaystyle f} { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\}
要素を含む集合が構築された場合、以前の 要素を再計算する必要がないよう な方法で 集合を構築すると便利です。長方形ルールでは、乖離度が低い点集合を使用しますが、一般的には が増加すると要素を再計算する必要があります。ランダムモンテカルロ法では 、 が増加しても要素を再計算する必要はありませんが、点集合は最小乖離度を持ちません。乖離度が低いシーケンスを使用することで、乖離度が低く、再計算が不要になることを目指しますが、実際には、再計算を一切行わない場合にのみ、乖離度が低いシーケンスは乖離度に関して増分的に改善されます。 { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\} N + 1 {\displaystyle N+1} N {\displaystyle N} N {\displaystyle N} N {\displaystyle N}
不一致の定義 集合の 不一致は 、 ニーダーライターの 記法 を用いて次のように定義される。 P = { x 1 , … , x N } {\displaystyle P=\{x_{1},\dots ,x_{N}}\} D N ( P ) = sup B ∈ J | A ( B ; P ) N − λ s ( B ) | {\displaystyle D_{N}(P)=\sup _{B\in J}\left|{\frac {A(B;P)}{N}}-\lambda _{s}(B)\right|}
ここで 、 は -次元 ルベーグ測度 、 は に含まれる の点の数 、 は -次元の区間またはボックスの 集合であり、 λ s {\displaystyle \lambda _{s}} s {\displaystyle s} A ( B ; P ) {\displaystyle A(B;P)} P {\displaystyle P} B {\displaystyle B} J {\displaystyle J} s {\displaystyle s}
∏ i = 1 s [ a i , b i ) = { x ∈ R s : a i ≤ x i < b i } {\displaystyle \prod _{i=1}^{s}[a_{i},b_{i})=\{\mathbf {x} \in \mathbf {R} ^{s}:a_{i}\leq x_{i}<b_{i}\}\,}
どこ 。 0 ≤ a i < b i ≤ 1 {\displaystyle 0\leq a_{i}<b_{i}\leq 1}
スター ・ディスクレパンシーも 同様に定義されるが、上限は次のような長方形の箱の 集合に適用される。 D N ∗ ( P ) {\displaystyle D_{N}^{*}(P)} J ∗ {\displaystyle J^{*}}
∏ i = 1 s [ 0 , u i ) {\displaystyle \prod _{i=1}^{s}[0,u_{i})}
ここで 、半開区間 [0, 1) 内にあります。 u i {\displaystyle u_{i}}
この2つは
D N ∗ ≤ D N ≤ 2 s D N ∗ . {\displaystyle D_{N}^{*}\leq D_{N}\leq 2^{s}D_{N}^{*}.\,}
注 ：これらの定義では、不一致は一様集合における点密度の最悪のケース、つまり最大の偏差を表します。しかし、他の誤差指標も意味を持ち、異なる定義や変動指標につながります。例えば、 -不一致や修正中心-不一致は、一様点集合の質を比較するために頻繁に用いられます。どちらも、大きな および の場合に計算がはるかに容易です 。 L 2 {\displaystyle L^{2}} L 2 {\displaystyle L^{2}} N {\displaystyle N} s {\displaystyle s}
Koksma-Hlawka の不等式 を -次元単位立方体 とする 。 は ハーディ とクラウス の意味で 有界 変分 を持つとする。すると、 内の任意の に対して 、 I ¯ s {\displaystyle {\overline {I}}^{s}} s {\displaystyle s} I ¯ s = [ 0 , 1 ] × ⋯ × [ 0 , 1 ] {\displaystyle {\overline {I}}^{s}=[0,1]\times \cdots \times [0,1]} f {\displaystyle f} V ( f ) {\displaystyle V(f)} I ¯ s {\displaystyle {\overline {I}}^{s}} x 1 , … , x N {\displaystyle x_{1},\ldots ,x_{N}} I s = [ 0 , 1 ) s = [ 0 , 1 ) × ⋯ × [ 0 , 1 ) {\displaystyle I^{s}=[0,1)^{s}=[0,1)\times \cdots \times [0,1)}
| 1 N ∑ i = 1 N f ( x i ) − ∫ I ¯ s f ( u ) d u | ≤ V ( f ) D N ∗ ( x 1 , … , x N ) . {\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}).} Koksma - Hlawka 不等式は次の意味で鋭い：および任意 の に 設定された点に対して、 有界な変化とを持つ 関数 が存在し 、 { x 1 , … , x N } {\displaystyle \{x_{1},\ldots ,x_{N}\}} I s {\displaystyle I^{s}} ε > 0 {\displaystyle \varepsilon >0} f {\displaystyle f} V ( f ) = 1 {\displaystyle V(f)=1}
| 1 N ∑ i = 1 N f ( x i ) − ∫ I ¯ s f ( u ) d u | > D N ∗ ( x 1 , … , x N ) − ε . {\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 .}
したがって、数値積分則の品質は、差異のみによって決まります 。 D N ∗ ( x 1 , … , x N ) {\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})}
とします 。 を と 書き 、 を で表します。 u に含ま れない座標を で置き換えて x から得られる点を表します 。すると D = { 1 , 2 , … , d } {\displaystyle D=\{1,2,\ldots ,d\}} ∅ ≠ u ⊆ D {\displaystyle \emptyset \neq u\subseteq D} d x u := ∏ j ∈ u d x j {\displaystyle dx_{u}:=\prod _{j\in u}dx_{j}} ( x u , 1 ) {\displaystyle (x_{u},1)} 1 {\displaystyle 1}
1 N ∑ i = 1 N f ( x i ) − ∫ I ¯ s f ( u ) d u = ∑ ∅ ≠ u ⊆ D ( − 1 ) | u | ∫ [ 0 , 1 ] | u | disc ( x u , 1 ) ∂ | u | ∂ x u f ( x u , 1 ) d x u , {\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},}
ここで 、不一致関数です。 disc ( z ) = 1 N ∑ i = 1 N ∏ j = 1 d 1 [ 0 , z j ) ( x i , j ) − ∏ j = 1 d z i {\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}}
その L2 Koksma-Hlawka 不等式のバージョン 積分と和に関するコーシー・シュワルツの不等式を Hlawka-Zaremba恒等式に 適用すると、 コクスマ・Hlawka不等式の次のバージョンが得られる。 L 2 {\displaystyle L^{2}}
| 1 N ∑ i = 1 N f ( x i ) − ∫ I ¯ s f ( u ) d u | ≤ ‖ f ‖ d disc d ( { t i } ) , {\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}\}),}
どこ
disc d ( { t i } ) = ( ∑ ∅ ≠ u ⊆ D ∫ [ 0 , 1 ] | u | disc ( x u , 1 ) 2 d x u ) 1 / 2 {\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}}
そして
‖ f ‖ d = ( ∑ u ⊆ D ∫ [ 0 , 1 ] | u | | ∂ | u | ∂ x u f ( x u , 1 ) | 2 d x u ) 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}.}
L 2 {\displaystyle L^{2}} 不一致は、与えられた点集合に対して高速かつ明示的な計算が可能であるため、実用上非常に重要です。これにより、 不一致を基準とする点集合最適化器を容易に作成できます。 L 2 {\displaystyle L^{2}}
エルデシュ・トゥラン・コクスマの不平等 大規模な点集合の乖離度の正確な値を求めるのは計算上困難です。 エルデシュ ・ トゥラン ・ コクスマ 不等式は上限値を提供します。
を点とし 、 を 任意の正の整数とする。すると x 1 , … , x N {\displaystyle x_{1},\ldots ,x_{N}} I s {\displaystyle I^{s}} H {\displaystyle H}
D N ∗ ( x 1 , … , x N ) ≤ ( 3 2 ) s ( 2 H + 1 + ∑ 0 < ‖ h ‖ ∞ ≤ H 1 r ( h ) | 1 N ∑ n = 1 N e 2 π i ⟨ h , x n ⟩ | ) {\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)}
どこ
r ( h ) = ∏ i = 1 s max { 1 , | h i | } for h = ( h 1 , … , h s ) ∈ Z s . {\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. 次元 のみに依存する 定数が存在し 、
任意の有限点集合 に対してとなります 。 c s {\displaystyle c_{s}} s {\displaystyle s} D N ∗ ( x 1 , … , x N ) ≥ c s ( ln N ) s − 1 N {\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c_{s}{\frac {(\ln N)^{s-1}}{N}}} x 1 , … , x N {\displaystyle {x_{1},\ldots ,x_{N}}}
予想2. のみに依存する 定数が存在し 、次のようになります。 c s ′ {\displaystyle c'_{s}} s {\displaystyle s} D N ∗ ( x 1 , … , x N ) ≥ c s ′ ( ln N ) s N {\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c'_{s}{\frac {(\ln N)^{s}}{N}}}
任意の無限シーケンス の無限数に対して 。 N {\displaystyle N} x 1 , x 2 , x 3 , … {\displaystyle x_{1},x_{2},x_{3},\ldots }
これらの予想は同値であり、 WM Schmidt によって 証明されている 。高次元においては、対応する問題は未解決である。最もよく知られている下限値は、 Michael Lacey と共同研究者によるものである。 s ≤ 2 {\displaystyle s\leq 2}
下限 しましょう 。そして s = 1 {\displaystyle s=1}
D N ∗ ( x 1 , … , x N ) ≥ 1 2 N {\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2N}}}
任意の有限点集合に対して 。 { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\}
WMシュミットは 、 任意 の有限点集合に対して 、 s = 2 {\displaystyle s=2} { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\}
D N ∗ ( x 1 , … , x N ) ≥ C log N N {\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq C{\frac {\log N}{N}}}
どこ
C = max a ≥ 3 1 16 a − 2 a log a = 0.023335 … . {\displaystyle C=\max _{a\geq 3}{\frac {1}{16}}{\frac {a-2}{a\log a}}=0.023335\dots .}
任意の次元に対して 、 KFロスは 以下を証明した。 s > 1 {\displaystyle s>1}
D N ∗ ( x 1 , … , x N ) ≥ 1 2 4 s 1 ( ( s − 1 ) log 2 ) s − 1 2 log s − 1 2 N N {\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}}}
任意の有限点集合 に対して となる 。Jozef Beck [1] は、 この結果の3次元における二重対数改善を確立した。これはD. Bilyk と MT Lacey によって単対数冪に改善された。s > 2 の場合の最もよく知られている境界は、 D . Bilyk、 MT Lacey 、A. Vagharshakyan [2] によるものである。sに依存して a が存在し 、 { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\} t > 0 {\displaystyle t>0} D N ∗ ( x 1 , … , x N ) ≥ t log s − 1 2 + t N N {\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq t{\frac {\log ^{{\frac {s-1}{2}}+t}N}{N}}}
任意の有限点集合に対して 。 { x 1 , … , x N } {\displaystyle \{x_{1},\dots ,x_{N}}\}
低矛盾シーケンスの構築 任意の乱数分布は均一分布にマッピングでき、準乱数も同様にマッピングできるため、この記事では多次元均一分布上の準乱数の生成についてのみ説明します。
となるようなシーケンスの構成が知られています
。 ここで 、 はシーケンスに依存する特定の定数です。予想 2 以降、これらのシーケンスは、可能な限り最良の収束順序を持つと考えられています。以下の例は、 ファンデルコルプシーケンス 、 ハルトンシーケンス 、および ソボルシーケンス です。一般的な制限の 1 つは、構築方法が通常、収束順序を保証できるだけであるということです。実際には、 が十分に大きい場合にのみ低い乖離が達成され、 が大きい場合、この最小値は非常に大きくなる可能性があります。つまり、例えば、低乖離シーケンスジェネレータからの 変数とポイント を使用してモンテカルロ分析を実行しても、 精度の向上はごくわずかです [ 引用が必要 ] 。 D N ∗ ( x 1 , … , x N ) ≤ C ( ln N ) s N . {\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq C{\frac {(\ln N)^{s}}{N}}.} C {\displaystyle C} N {\displaystyle N} N {\displaystyle N} s = 20 {\displaystyle s=20} N = 1000 {\displaystyle N=1000}
乱数 乱数に負の相関を課すことで、準乱数列を乱数から生成することができます。これを行う一つの方法は、以下の式を用いて、乱数集合から一 様 となる 準乱数を構築することです 。 r i {\displaystyle r_{i}} [ 0 , 0.5 ) {\displaystyle [0,0.5)} s i {\displaystyle s_{i}} [ 0 , 1 ) {\displaystyle [0,1)}
s i = r i {\displaystyle s_{i}=r_{i}} 奇数と偶数 の 場合 。 i {\displaystyle i} s i = 0.5 + r i {\displaystyle s_{i}=0.5+r_{i}} i {\displaystyle i}
開始時の乱数を使用してこれを行う 2 番目の方法は、次のようにオフセット 0.5 のランダム ウォークを構築することです。
s i = s i − 1 + 0.5 + r i ( mod 1 ) . {\displaystyle s_{i}=s_{i-1}+0.5+r_{i}{\pmod {1}}.\,}
つまり、前の準乱数を取り、0.5 と乱数を加算し、その結果を1 で割っ た値 をとります 。
複数の次元の場合、適切な次元の ラテン方陣 を使用してオフセットを提供し、ドメイン全体が均等にカバーされるようにすることができます。
単位正方形の被覆率。左側は c = 0.5545497...、0.308517...の加法性準乱数、右側は乱数です。上から下へ、10、100、1000、10000点。
加法的な再帰 任意の無理数に対して 、数列 α {\displaystyle \alpha }
s n = { s 0 + n α } {\displaystyle s_{n}=\{s_{0}+n\alpha \}}
の不一致は に近づく 。このシーケンスは再帰的に定義できることに注意してください。 1 / N {\displaystyle 1/N} s n + 1 = ( s n + α ) mod 1 . {\displaystyle s_{n+1}=(s_{n}+\alpha ){\bmod {1}}\;.}
の値が適切で あれば、一連の独立した均一な乱数よりも差異は少なくなります。 α {\displaystyle \alpha }
この乖離はの 近似指数 によって制限される 。近似指数が であれば 、任意の に対して 、以下の境界が成り立つ： [3] α {\displaystyle \alpha } μ {\displaystyle \mu } ε > 0 {\displaystyle \varepsilon >0}
D N ( ( s n ) ) = O ε ( N − 1 / ( μ − 1 ) + ε ) . {\displaystyle D_{N}((s_{n}))=O_{\varepsilon }(N^{-1/(\mu -1)+\varepsilon }).}
Thue-Siegel-Roth の定理 により、任意の無理 数的数 の近似指数は 2 となり、上記の境界が得られます 。 N − 1 + ε {\displaystyle N^{-1+\varepsilon }}
上記の再帰関係は、低品質の疑似乱数生成器である 線形合同型生成器 で使用される再帰関係に似ています。 [4]
r i = ( a r i − 1 + c ) mod m {\displaystyle r_{i}=(ar_{i-1}+c){\bmod {m}}}
上記の低乖離加法再帰では、 a と m は 1 に選択されます。ただし、これによって独立した乱数は生成されないため、独立性を必要とする目的には使用しないでください。
最も乖離度が低い値は 黄金比 の分数部分である ： [5] c {\displaystyle c}
c = 5 − 1 2 = φ − 1 ≈ 0.618034. {\displaystyle c={\frac {{\sqrt {5}}-1}{2}}=\varphi -1\approx 0.618034.}
ほぼ同等に適切な別の値は、白銀比 の小数部です 。これは、2 の平方根の小数部です。
c = 2 − 1 ≈ 0.414214. {\displaystyle c={\sqrt {2}}-1\approx 0.414214.\,}
多次元の場合、各次元ごとに別々の準乱数が必要です。使用される便利な値のセットは、 2以上の 素数 の平方根で、すべて1を法として計算したものです。
c = 2 , 3 , 5 , 7 , 11 , … {\displaystyle c={\sqrt {2}},{\sqrt {3}},{\sqrt {5}},{\sqrt {7}},{\sqrt {11}},\ldots \,}
しかし、一般化された黄金比に基づいた値のセットは、より均等に分布した点を生成することが示されています。 [6]
擬似乱数生成器のリストには 、 独立した擬似乱数を生成するための手法が列挙されています。 注 ：次元数が少ない場合、再帰的再帰法は高品質の均一集合を生成しますが、次元数が大きい場合 （ など ）は、他の点集合生成器の方がはるかに誤差が少なくなります。 s {\displaystyle s} s > 8 {\displaystyle s>8}
ファン・デル・コルプット配列 させて
n = ∑ k = 0 L − 1 d k ( n ) b k {\displaystyle n=\sum _{k=0}^{L-1}d_{k}(n)b^{k}}
を正の整数の - 進表現 、すなわち と する 。 b {\displaystyle b} n ≥ 1 {\displaystyle n\geq 1} 0 ≤ d k ( n ) < b {\displaystyle 0\leq d_{k}(n)<b}
g b ( n ) = ∑ k = 0 L − 1 d k ( n ) b − k − 1 . {\displaystyle g_{b}(n)=\sum _{k=0}^{L-1}d_{k}(n)b^{-k-1}.}
すると、 のみに依存する 定数 が存在し 、 C {\displaystyle C} b {\displaystyle b} ( g b ( n ) ) n ≥ 1 {\displaystyle (g_{b}(n))_{n\geq 1}}
D N ∗ ( g b ( 1 ) , … , g b ( N ) ) ≤ C log N N , {\displaystyle D_{N}^{*}(g_{b}(1),\dots ,g_{b}(N))\leq C{\frac {\log N}{N}},}
星の不一致 はどこに あります
か 。 D N ∗ {\displaystyle D_{N}^{*}}
ハルトン配列 (2,3)ハルトン列の最初の256点 ハルトン列は、ファン・デル・コルプット列を高次元に自然に一般化したものである。 任意の次元 s と、 1より大きい 互いに素な任意の 整数 b 1 , ..., b sを次のように定義する。
x ( n ) = ( g b 1 ( n ) , … , g b s ( n ) ) . {\displaystyle x(n)=(g_{b_{1}}(n),\dots ,g_{b_{s}}(n)).}
このとき、定数 Cは b 1 , ..., b s のみに依存し 、シーケンス{ x ( n )} n ≥1は s 次元シーケンスと なり、
D N ∗ ( x ( 1 ) , … , x ( N ) ) ≤ C ′ ( log N ) s N . {\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C'{\frac {(\log N)^{s}}{N}}.}
ハンマースリーセット サイズ256の2D Hammersleyセット が互いに素な 1より大きい正の整数 であるとする。 とが与えられた とき 、大きさ の次元 ハマースリー 集合は [7] で定義される。 b 1 , … , b s − 1 {\displaystyle b_{1},\ldots ,b_{s-1}} s {\displaystyle s} N {\displaystyle N} s {\displaystyle s} N {\displaystyle N}
x ( n ) = ( g b 1 ( n ) , … , g b s − 1 ( n ) , n N ) {\displaystyle x(n)=\left(g_{b_{1}}(n),\dots ,g_{b_{s-1}}(n),{\frac {n}{N}}\right)}
のために 。そして n = 1 , … , N {\displaystyle n=1,\ldots ,N}
D N ∗ ( x ( 1 ) , … , x ( N ) ) ≤ C ( log N ) s − 1 N {\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C{\frac {(\log N)^{s-1}}{N}}}
ここで 、 は のみに依存する定数です 。 C {\displaystyle C} b 1 , … , b s − 1 {\displaystyle b_{1},\ldots ,b_{s-1}}
注 ：式から、ハマースリー集合は実際にはハルトン列であることがわかりますが、線形スイープを追加することで1次元が追加されます。これは、 が事前にわかっている場合にのみ可能です。線形集合は、一般に1次元の乖離度が最小となる集合でもあります。残念ながら、高次元では、そのような「乖離度記録集合」は知られていません。 の場合 、ほとんどの低乖離度点集合生成器は、少なくともほぼ最適な乖離度を生成します。 N {\displaystyle N} s = 2 {\displaystyle s=2}
ソボルシーケンス ソボル数列のアントノフ・サレエフ変種は、方向数と呼ばれる特殊な二進分数 の集合から 、長さ の二進分数として0から1までの数値を直接生成します。 、 、 の グレイコード のビットは 、方向数の選択に使用されます。ソボル数列の値を得るには、 のグレイコードの二進値と適切な方向数との 排他的論理 和をとります 。必要な次元数は の選択に影響します 。 w , {\displaystyle w,} w {\displaystyle w} V i , i = 1 , 2 , … , w {\displaystyle V_{i},i=1,2,\dots ,w} i {\displaystyle i} G ( i ) {\displaystyle G(i)} s i {\displaystyle s_{i}} i {\displaystyle i} V i {\displaystyle V_{i}}
ポアソンディスクサンプリング ポアソンディスクサンプリングは 、ビデオゲームでよく用いられ、ランダムに見えるようにオブジェクトを高速に配置する手法ですが、2点間の距離が指定された最小距離以上であることを保証します。 [8] これは（例えばSobol'のように）低い乖離度を保証するものではありませんが、少なくとも純粋なランダムサンプリングよりも大幅に低い乖離度を実現します。これらのサンプリングパターンの目的は、乖離度ではなく、いわゆる「ブルーノイズ」パターンの一種である頻度分析に基づいています。
グラフィック例 以下にプロットされた点は、ソボル型シーケンスの最初の100、1000、10000要素です。比較のために、擬似乱数点シーケンスの10000要素も示されています。この低乖離シーケンスは、 TOMS アルゴリズム659によって生成されました 。[9] このアルゴリズムの Fortran実装は Netlib から入手できます 。
Sobol タイプの低差異シーケンスの最初の 100 ポイント 。 同じシーケンスの最初の1000ポイント。この1000ポイントが最初の100ポイントを構成し、さらに900ポイントが続きます。
同じシーケンスの最初の10000ポイント。この10000ポイントが最初の1000ポイントを構成し、さらに9000ポイントが続きます。 比較のために、一様分布の疑似乱数列の最初の10000点を示します。密度の高い領域と低い領域がはっきりと分かります。
参照
注記 ^ ベック、ヨーゼフ (1989)。 「分布の不規則性における 2 次元のファン・アーデンヌ・エーレンフェストの定理」。 Compositio Mathematica 。 72 ( 3 ) : 269–339。MR 1032337。S2CID 125940424。Zbl 0691.10041 。 ^ Bilyk, Dmitriy; Lacey, Michael T.; Vagharshakyan, Armen (2008). 「全次元におけるスモールボール不等式について」. Journal of Function Analysis . 254 (9): 2470– 2502. arXiv : 0705.4619 . doi : 10.1016/j.jfa.2007.09.010 . S2CID 14234006. ^ カイパースとニーダーライター、2005、p. 123 ^ ドナルド・E・クヌース「第3章 乱数」 『コンピュータプログラミングの芸術 』第2巻。 ^ Skarupke, Malte (2018年6月16日). 「フィボナッチハッシュ：世界が忘れ去った最適化」 黄金比の特性の一つは、任意の範囲をほぼ均等に分割できることです…ただし、事前に何ステップ行うかが分かっていなければの話ですが。 ^ Roberts, Martin (2018). 「準ランダムシーケンスの不合理な有効性」. 2025年3月1日時点のオリジナルよりアーカイブ。 ^ Hammersley, JM; Handscomb, DC (1964). モンテカルロ法 . doi :10.1007/978-94-009-5819-7. ISBN 978-94-009-5821-0 。 ^ ハーマン・タレンケン。 ハーマン、タレンケン（2008 年 3 月）。 「ポアソンディスクサンプリング」。 開発雑誌 。 No. 21。21 ～ 25 ページ。 ^ Bratley, Paul; Fox, Bennett L. (1988). 「アルゴリズム 659」. ACM Transactions on Mathematical Software . 14 : 88–100 . doi : 10.1145/42288.214372 . S2CID 17325779.
参考文献
外部リンク ACM のアルゴリズム集 (アルゴリズム 647、659、および 738 を参照) GNU Scientific Library からの準ランダムシーケンス FinancialMathematics.Com における制約条件付き準ランダムサンプリング Sobol シーケンスの C++ ジェネレータ SciPy QMC API リファレンス: scipy.stats.qmc 
![{\displaystyle {\overline {I}}^{s}=[0,1]\times \cdots \times [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b7b6b45832d30cbe2b66656b80245cb209cb4262)
![{\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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/646d05c4c12cae58e128651816856d90c9a25e51)
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/609a886b91fa44773d2ddd89c752bc1a037309a6)
![{\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}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dee8232a0985af6392e00e77e9bdfa8c4f98fe77)
