数列の種類
数学 において 、 低乖離数列 とは、のすべての値に対して 、その部分列の 乖離度 が小さいという 性質を持つ 数列 のことです。
いいえ
{\displaystyle N}
x
1
、 … 、
x
いいえ
{\displaystyle x_{1},\ldots ,x_{N}}
大まかに言えば、任意の集合B に入るシーケンス内の点の割合が B の 測度 にほぼ比例する場合、シーケンスの不一致は低いと言えます。これは、等 分布シーケンス の場合に平均的には (特定のサンプルではそうではないものの) 起こることです。不一致の具体的な定義は、 B の選択 ( 超球 、 超立方体 など) と、すべての B の不一致の計算方法 (通常は正規化) と結合方法 (通常は最悪値を取る) によって異なります。
低乖離数列は、均一に分布する 乱数 の代わりとしてよく使用されるため、 準ランダム数列とも呼ばれます。「準」修飾子は、低乖離数列の値がランダムでも 疑似ランダムで もないことをより明確に示すために使用されますが、このような列はランダム変数のいくつかの特性を共有しており、 準モンテカルロ法 などの特定のアプリケーションでは、 乖離率が低いことが重要な利点となります。
アプリケーション データポイント数の関数としての推定尖度の誤差。「加法準ランダム」は、 c = ( √5 − 1)/2 のときに最大誤差を与えます。「ランダム」は、乱数を 6 回実行した平均誤差 を 与えます。平均は、乱数の変動の大きさを減らすために取られます。 準乱数は、関心領域を迅速かつ均等にカバーするという点で、純粋な乱数よりも優れています。
2 つの便利な用途は、確率密度関数 の 特性関数 を見つけること と、ノイズの少ない決定論 的 関数の微分関数を見つけることです。準乱数を使用すると、高次の モーメントを 非常に高速に高精度に計算できます。
ソートを伴わない応用としては、統計分布の 平均 、 標準偏差 、 歪度 、 尖度を 求めることや、難しい決定論的関数の 積分値 と大域 最大値と最小値を求めることが挙げられます。準乱数は、 ニュートン・ラプソン反復法 など、局所的にしか機能しない決定論的アルゴリズムの開始点を提供するためにも使用できます 。
準乱数は検索アルゴリズムと組み合わせることもできます。検索アルゴリズムを使用すると、準乱数を使用して、 統計分布の モード 、 中央値 、 信頼区間 、 累積分布、および決定論的関数のすべての 局所最小値 とすべての解を見つけることができます。
数値積分における低矛盾シーケンス 数値積分 のさまざまな方法は、ある区間（例えば[0,1]）における 関数の積分を 、その区間内の集合で評価された関数の平均として近似するものとして表現できます 。
ふ
{\displaystyle f}
{
x
1
、 … 、
x
いいえ
}
{\displaystyle \{x_{1},\dots ,x_{N}}\}
∫
0
1
ふ （ あなた ） d あなた ≈
1 いいえ
∑
私 = 1
いいえ
ふ （
x
私
） 。
{\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
私
= 私
/
いいえ
{\displaystyle x_{i}=i/N}
ふ
{\displaystyle f}
{
x
1
、 … 、
x
いいえ
}
{\displaystyle \{x_{1},\dots ,x_{N}}\}
要素を含むセットが構築される場合、以前の 要素を再計算する必要がない ような方法で セットを構築すると便利です。長方形ルールでは、差異の低いポイント セットを使用しますが、一般に 、が増加すると要素を再計算する必要があります。が増加する場合、ランダム モンテ カルロ法で要素を再計算する必要はありません が、ポイント セットには最小の差異がありません。差異の低いシーケンスを使用することで、差異が低く、再計算が不要になることを目指しますが、実際には、再計算を許可しない場合にのみ、差異の低いシーケンスは増分的に良好になります。
{
x
1
、 … 、
x
いいえ
}
{\displaystyle \{x_{1},\dots ,x_{N}}\}
いいえ + 1
{\displaystyle N+1}
いいえ
{\displaystyle N}
いいえ
{\displaystyle N}
いいえ
{\displaystyle N}
不一致の定義 集合の 不一致 は、 ニーダーライターの 記法
を用いて次のように定義される。
ポ = {
x
1
、 … 、
x
いいえ
}
{\displaystyle P=\{x_{1},\dots ,x_{N}}\}
だ
いいえ
（ ポ ） =
すする
B ∈ J
|
あ （ B ; ポ ）
いいえ
−
λ
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}
あ （ B ; ポ ）
{\displaystyle A(B;P)}
ポ
{\displaystyle P}
B
{\displaystyle B}
J
{\displaystyle J}
s
{\displaystyle s}
∏
私 = 1
s
[
1つの
私
、
b
私
） = {
x
∈
R
s
:
1つの
私
≤
x
私
<
b
私
}
{\displaystyle \prod _{i=1}^{s}[a_{i},b_{i})=\{\mathbf {x} \in \mathbf {R} ^{s}:a_{i}\leq x_{i}}\}\,}
どこ 。
0 ≤
1つの
私
<
b
私
≤ 1
{\displaystyle 0\leq a_{i}\leq 1}
スター ・ディスクレパンシーも 同様に定義されるが、上限は次のような長方形の箱の
集合でとられる。
だ
いいえ
∗
（ ポ ）
{\displaystyle D_{N}^{*}(P)}
J
∗
{\displaystyle J^{*}}
∏
私 = 1
s
[ 0 、
あなた
私
）
{\displaystyle \prod _{i=1}^{s}[0,u_{i})}
ここで、 半開区間[0, 1)内にあります。
あなた
私
{\displaystyle u_{i}}
両者の関係は
だ
いいえ
∗
≤
だ
いいえ
≤
2
s
だ
いいえ
∗
。
{\displaystyle D_{N}^{*}\leq D_{N}\leq 2^{s}D_{N}^{*}.\,}
注 : これらの定義では、不一致は、一様集合の最悪ケースまたは最大ポイント密度偏差を表します。ただし、他のエラー測定も意味があり、他の定義と変動測定につながります。たとえば、 -不一致または修正中心-不一致も、一様ポイントセットの品質を比較するために頻繁に使用されます。どちらも、大きい および の場合に計算がはるかに簡単です 。
ら
2
{\displaystyle L^{2}}
ら
2
{\displaystyle L^{2}}
いいえ
{\displaystyle N}
s
{\displaystyle s}
Koksma-Hlawka の不等式 を-次元単位立方体
と します 。 を ハーディ とクラウスの 意味で 有界 変分 とします。すると、
内の任意の に対して 、
私 ¯
s
{\displaystyle {\overline {I}}^{s}}
s
{\displaystyle s}
私 ¯
s
= [ 0 、 1 ] × ⋯ × [ 0 、 1 ]
{\displaystyle {\overline {I}}^{s}=[0,1]\times \cdots \times [0,1]}
ふ
{\displaystyle f}
五 （ ふ ）
{\displaystyle V(f)}
私 ¯
s
{\displaystyle {\overline {I}}^{s}}
x
1
、 … 、
x
いいえ
{\displaystyle x_{1},\ldots ,x_{N}}
私
s
= [ 0 、 1
）
s
= [ 0 、 1 ） × ⋯ × [ 0 、 1 ）
{\displaystyle I^{s}=[0,1)^{s}=[0,1)\times \cdots \times [0,1)}
|
1 いいえ
∑
私 = 1
いいえ
ふ （
x
私
） −
∫
私 ¯
s
ふ （ あなた ） d あなた
|
≤ 五 （ ふ ）
だ
いいえ
∗
（
x
1
、 … 、
x
いいえ
） 。
{\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
いいえ
}
{\displaystyle \{x_{1},\ldots ,x_{N}\}}
私
s
{\displaystyle I^{s}}
ε > 0
{\displaystyle \epsilon >0}
ふ
{\displaystyle f}
五 （ ふ ） = 1
{\displaystyle V(f)=1}
|
1 いいえ
∑
私 = 1
いいえ
ふ （
x
私
） −
∫
私 ¯
s
ふ （ あなた ） d あなた
|
>
だ
いいえ
∗
（
x
1
、 … 、
x
いいえ
） − ε 。
{\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 .}
したがって、数値積分規則の品質は、不一致のみに依存します 。
だ
いいえ
∗
（
x
1
、 … 、
x
いいえ
）
{\displaystyle D_{N}^{*}(x_{1},\ldots,x_{N})}
とし
ましょう 。なぜなら、
だ = { 1 、 2 、 … 、 d }
{\displaystyle D=\{1,2,\ldots ,d\}}
∅ ≠ あなた ⊆ だ
{\displaystyle \emptyset \neq u\subseteq D}
d
x
あなた
:=
∏
じゅう ∈ あなた
d
x
じゅう
{\displaystyle dx_{u}:=\prod _{j\in u}dx_{j}}
そして、 u に 含まれない座標を で置き換えて x から得られる点を で表します 。すると、
（
x
あなた
、 1 ）
{\displaystyle (x_{u},1)}
1
{\displaystyle 1}
1 いいえ
∑
私 = 1
いいえ
ふ （
x
私
） −
∫
私 ¯
s
ふ （ あなた ） d あなた =
∑
∅ ≠ あなた ⊆ だ
（ − 1
）
|
あなた
|
∫
[ 0 、 1
]
|
あなた
|
ディスク （
x
あなた
、 1 ）
∂
|
あなた
|
∂
x
あなた
ふ （
x
あなた
、 1 ） d
x
あなた
、
{\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},}
ここで、 不一致関数です。
ディスク （ ず ） =
1 いいえ
∑
私 = 1
いいえ
∏
じゅう = 1
d
1
[ 0 、
ず
じゅう
）
（
x
私 、 じゅう
） −
∏
じゅう = 1
d
ず
私
{\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}}
エルデシュ・トゥラン・コクスマの不平等 大きな点集合の不一致の正確な値を求めるのは計算上困難です。Erdős – Turán – Koksma不等式 は 上限を提供します。
を点とし 、 を 任意の正の整数とする。すると
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 {\mbox{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] が
存在する ため、
{
x
1
,
…
,
x
N
}
{\displaystyle \{x_{1},\dots ,x_{N}}\}
{
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}}\}
低矛盾シーケンスの構築 任意の乱数分布は一様分布にマッピングでき、準乱数も同様にマッピングされるため、この記事では多次元一様分布上の準乱数の生成についてのみ説明します。
次のような配列の構成が知られている。
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}}.}
ここで、 は シーケンスに依存する特定の定数です。予想 2 以降、これらのシーケンスは、可能な限り最良の収束順序を持つと考えられます。以下の例は、 ファンデルコルプシーケンス 、 ハルトンシーケンス 、および ソボルシーケンス です。一般的な制限の 1 つは、構築方法では通常、収束順序しか保証できないことです。実際には、 が十分に大きい場合にのみ低い乖離が達成され、 が大きい場合、この最小値は非常に大きくなる可能性があります。つまり、たとえば、低乖離シーケンスジェネレータからの 変数とポイント を使用してモンテカルロ分析を実行しても、 精度の向上はごくわずかです [ 引用が必要 ] 。
C
{\displaystyle C}
N
{\displaystyle N}
N
{\displaystyle N}
s
=
20
{\displaystyle s=20}
N
=
1000
{\displaystyle N=1000}
乱数 乱数に負の相関を課すことで、乱数から準乱数のシーケンスを生成できます。これを行う 1 つの方法は、乱数のセットから始めて 、次を使用して 均一な 準乱数を構築することです 。
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.\,}
次元が複数ある場合は、次元ごとに別々の準乱数が必要です。使用される便利な値のセットは、すべて 1 を法としてとった 2 以上の
素数 の平方根です。
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 を 任意の次元とし、 b 1 , ..., b sを 1より大きい
互いに素な任意の整数とする。 定義する。
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ハマースリーセット を互いに素 な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}}
注 : 式から、Hammersley セットは実際には Halton シーケンスであることがわかりますが、線形スイープを追加することで、もう 1 つの次元が無料で得られます。これは、 が事前にわかっている場合にのみ可能です。線形セットは、一般に、1 次元の不一致が最も少ないセットでもあります。残念ながら、より高い次元では、このような「不一致レコード セット」はわかっていません。 の場合 、ほとんどの低不一致ポイント セット ジェネレーターは、少なくともほぼ最適な不一致を生成します。
N
{\displaystyle N}
s
=
2
{\displaystyle s=2}
ソボルシーケンス ソボル数列のアントノフ-サレエフ変形は、方向数と呼ばれる 特別な2進小数 のセットから、長さ の2進小数として0から1までの数値を直接生成します。 、、 の グレイコード のビットは 、方向数を選択するために使用されます。ソボル数列の値を取得するには、適切な方向数で グレイコードの2進値の 排他的論理 和を取ります 。必要な次元の数は、 の選択に影響します 。
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のように）低い差異を保証するものではありませんが、少なくとも純粋なランダムサンプリングよりも大幅に低い差異を保証します。これらのサンプリングパターンの目的は、差異ではなく周波数分析に基づいており、いわゆる「ブルーノイズ」パターンの一種です。
グラフィック例 以下にプロットされた点は、Sobol'タイプのシーケンスの最初の100、1000、10000要素です。比較のために、疑似ランダムポイントのシーケンスの10000要素も示されています。低矛盾シーケンスは、 TOMS アルゴリズム659によって生成されました。 [9] Fortran
でのアルゴリズムの実装は、 Netlib から入手できます 。
参照
注記
^ ベック、ヨーゼフ (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 Functional Analysis . 254 (9): 2470–2502. arXiv : 0705.4619 . doi : 10.1016/j.jfa.2007.09.010 . S2CID 14234006. ^ カイパースとニーダーライター、2005、p. 123 ^ Knuth, Donald E. 「第 3 章 – 乱数」。 コンピュータ プログラミングの芸術 。第 2 巻。 ^ Skarupke、Malte（2018年6月16日）。「フィボナッチハッシュ：世界が忘れた最適化」。 黄金比の特性の1つは、事前に何ステップ行うかがわからない場合でも、任意の範囲をほぼ均等に分割できることです。
^ Roberts, Martin (2018)。「準ランダムシーケンスの不合理な有効性」。 ^ 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.
参考文献 ディック、ヨーゼフ、ピリッヒシャマー、フリードリヒ（2010）。 デジタルネットとシーケンス：不一致理論と準モンテカルロ積分 。ケンブリッジ大学出版局 。ISBN 978-0-521-19159-3 。 カイパーズ、L. Niederreiter, H. (2005)、 配列の均一分布 、 Dover Publications 、 ISBN 0-486-45019-8 Harald Niederreiter (1992)。 乱数生成と準モンテカルロ法 。工業応用数学協会 。ISBN 0-89871-295-5 。 Drmota, Michael; Tichy, Robert F. (1997)。 シーケンス、不一致、およびアプリケーション 。数学の講義ノート。第1651巻 。Springer。ISBN 3-540-62606-9 。 Press, William H.; Flannery, Brian P.; Teukolsky, Saul A.; Vetterling, William T. (1992). Numerical Recipes in C (第 2 版). Cambridge University Press. 低矛盾シーケンスに関する技術的でない説明についてはセクション 7.7 を参照してください 。ISBN 0-521-43108-5 。
外部リンク ACM のアルゴリズム集 (アルゴリズム 647、659、および 738 を参照) GNU 科学ライブラリ からの準ランダムシーケンス 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)
