ソボルシーケンス

ソボル数列（LP _τ数列または2進数の( t ,  s )数列とも呼ばれる）は、準ランダム低乖離数列の一種である。1967年にロシアの数学者イリヤ・M・ソボル（Илья Меерович Соболь）によって初めて導入された。^[1]

これらのシーケンスは、2 を基数として単位間隔のより細かい均一なパーティションを連続的に形成し、各次元の座標を並べ替えます。

I ^s = [0,1] ^sを s次元単位超立方体とし、f​​ をI ^s上の実積分関数とする。ソボルの当初の動機は、 I ^s上の数列x _{n を}構築して、

${\displaystyle \lim _{n\to \infty }{\frac {1}{n}}\sum _{i=1}^{n}f(x_{i})=\int _{I^{s}}f}$

収束は可能な限り速くなります。

和が積分に収束するためには、点x _nがI ^sを埋めて穴を最小にする必要があることは多かれ少なかれ明らかです。もう 1 つの良い特性は、 x _nをI ^sの低次元面に投影しても穴がほとんど残らないことです。したがって、低次元では多くの点が同じ場所にあるため、積分推定には役に立たず、 I ^{sの均一な充填は適格ではありません。}

これらの良い分布は、基数bの ( t , m , s )-ネットおよび ( t , s )-シーケンスと呼ばれます。これらを導入するには、まず基数bの基本s区間を、次の形式の I ^sのサブセットとして定義します。

${\displaystyle \prod _{j=1}^{s}\left[{\frac {a_{j}}{b^{d_{j}}}},{\frac {a_{j}+1}{b^{d_{j}}}}\right],}$

ここで、a _jとd _{j は}負でない整数であり、すべてのj は{1, ...,s} の範囲内にあります。 ${\displaystyle a_{j}}}$

2 つの整数が与えられたとき、基数bの( t , m , s )-ネットは、 b ^m個のIの点のシーケンスx _nで^あり、超体積の基数bのすべての基本区間Pに対してλ ( P ) = b ^t−mとなります。 ${\displaystyle 0\leq t\leq m}$${\displaystyle \operatorname {Card} P\cap \{x_{1},...,x_{b^{m}}\}=b^{t}}$

負でない整数tが与えられたとき、基数bの( t , s ) シーケンスは、すべての整数に対して、シーケンスが基数bの( t , m , s ) ネットであるような点x _nの無限シーケンスです。 ${\displaystyle k\geq 0,m\geq t}$${\displaystyle \{x_{kb^{m}},...,x_{(k+1)b^{m}-1}\}}$

ソボルは論文の中で、Π _τメッシュとLP _τシーケンスについて説明しました。これらはそれぞれ、基数 2 の( t , m , s ) ネットと ( t , s ) シーケンスです。基数bの ( t , m , s ) ネットと ( t , s ) シーケンス(ニーダーライターシーケンスとも呼ばれる)という用語は、1988 年にHarald Niederreiterによって造られました。^[2]ソボルシーケンスという用語は、後期の英語圏の論文で、ハルトン、フォーレ、その他の低差異シーケンス と比較して導入されました。

より効率的なグレイコードの実装は、アントノフとサレエフによって提案されました。^[3]

Sobol 数の生成に関しては、n番目のポイントの描画を構築するためにn の代わりにグレイ コードを使用することで明らかに支援されています。 ${\displaystyle G(n)=n\oplus \lfloor n/2\rfloor }$

すでにn − 1までのソボルシーケンスの描画をすべて生成し、必要なすべての次元の 値x _{n −1, j}をメモリに保存しているとします。グレイコードG ( n ) は、前のコードG ( n  − 1 ) と 1 つだけ、たとえばk番目のビット ( n − 1の右端のゼロビット) だけ異なるため、 x _{n −1のすべてを}x _nに伝播させるには、各次元に対して1 回のXOR演算を 実行するだけで済みます。つまり 、

${\displaystyle x_{n,i}=x_{n-1,i}\oplus v_{k,i}.}$

ソボルは、特性AとA'として知られる追加の均一性条件を導入した。^[4]

意味

低矛盾シーケンスは、長さ 2 ^dのd次元シーケンスの任意のバイナリセグメント(任意のサブセットではない) に対して、単位ハイパーキューブをその長さの延長に沿って半分に細分化して得られる各 2 ^dハイパーキューブに正確に 1 つの描画が存在する場合に、特性 A を満たすと言われます。

意味

低矛盾シーケンスは、長さ 4 ^dのd次元シーケンスの任意のバイナリセグメント(任意のサブセットではない) に対して、単位ハイパーキューブをその長さの延長に沿って 4 つの等しい部分に細分化して得られる各 4 ^dハイパーキューブに正確に 1 つの描画が存在する場合、特性 A' を満たすと言われます。

特性 A と A' を保証する数学的条件があります。

定理

d次元ソボル列は、次の場合に限り特性Aを持つ 。

${\displaystyle \det(\mathbf {V} _{d})\equiv 1(\mod 2),}$

ここで、V ^{d は}、次のように定義される d  ×  dの2進行列である。

${\displaystyle \mathbf {V} _{d}:={\begin{pmatrix}{v_{1,1,1}}&{v_{2,1,1}}&{\dots }&{v_{d,1,1}}\\{v_{1,2,1}}&{v_{2,2,1}}&{\dots }&{v_{d,2,1}}\\{\vdots }&{\vdots }&{\ddots }&{\vdots }\\{v_{1,d,1}}&{v_{2,d,1}}&{\dots }&{v_{d,d,1}}\end{pmatrix}},}$

ここで、v _{k , j , m}は方向数の2進小数点以下のm番目の桁を表します。v _{k , j} = (0. v _{k , j ,1} v _{k , j ,2} ...) ₂。

定理

d次元ソボル列は、次の場合に限り特性A'を持つ 。

${\displaystyle \det(\mathbf {U} _{d})\equiv 1\mod 2,}$

ここでU ^dは2 d  × 2 dの2進行列であり、次のように定義される。

${\displaystyle \mathbf {U} _{d}:={\begin{pmatrix}{v_{1,1,1}}&{v_{1,1,2}}&{v_{2,1,1 }}&{v_{2,1,2}}&{\ドット}&{v_{d,1,1}}&{v_{d,1,2}}\\{v_{1,2,1}}&{v_{1,2,2}}&{v_{ 2,2,1}}&{v_{2,2,2}}&{\dots }&{v_{d,2,1}}&{v_{d,2,2}}\\{\vdots }&{\vdots }&{\vdots }&{\vdots }&{\ddots }&{\vdots }&{\vdots }\\{v_{1,2d,1}}&{v_{1,2d,2}}&{v_{2,2d,1}}&{v_{2,2d,2}}&{\dots }&{v_{d,2d,1}}&{v_{d,2d,2}}\end{pmatrix}},}$

ここで、v _{k , j , m}は方向数の2進小数点以下のm番目の桁を表します。v _{k , j} = (0. v _{k , j ,1} v _{k , j ,2} ...) ₂。

プロパティ A と A' のテストは独立しています。したがって、プロパティ A と A' の両方、またはいずれか 1 つのみを満たす Sobol' シーケンスを構築できます。

Sobol' シーケンスを構築するには、方向番号v _i、jのセットを選択する必要があります。初期の方向番号の選択にはある程度の自由度があります。^{[注 1]}したがって、選択した次元に対して Sobol' シーケンスの異なる実現を受け取ることができます。初期の番号の選択が適切でないと、計算に使用する際に Sobol' シーケンスの効率が大幅に低下する可能性があります。

おそらく、初期化数の最も簡単な選択は、l番目の左端のビットを設定し、他のすべてのビットを 0 にする、つまり、すべてのkとjに対してm _{k , j} = 1にすることです。この初期化は通常、単位初期化と呼ばれます。ただし、このようなシーケンスは、低次元であってもプロパティ A と A' のテストに失敗するため、この初期化は適切ではありません。

さまざまな次元数に適した初期化番号が複数の著者によって提供されています。たとえば、Sobol'は51次元までの初期化番号を提供しています。 ^[5] BratleyとFoxも同じ初期化番号セットを使用しています。^[6]

高次元の初期化数はJoeとKuoから入手できます。^[7] Peter Jäckelは著書「Monte Carlo methods in finance」で32次元までの初期化数を提供しています。^[8]

その他の実装は、C、Fortran 77、またはFortran 90ルーチンとしてNumerical Recipesソフトウェアコレクションで利用できます。 ^{[9] JoeとKuoの初期化数に基づく最大1111次元の}無料/オープンソース実装は、Cで利用できます。^{[10]また、Python [11] [12]}およびJuliaでは最大21201次元です。^[13]最大1111次元の別の無料/オープンソース実装は、C++、Fortran 90、Matlab、およびPythonで利用できます。^[14]

市販のSobol'シーケンスジェネレータは、例えばNAGライブラリ^[15]から入手できます。BRODA Ltd. ^{[16] [17} ]は、最大次元131072までの追加の均一性プロパティAとA'を備えたSobol'シーケンスジェネレータとスクランブルSobol'シーケンスジェネレータを提供しています。これらのジェネレータはI. Sobol'教授と共同開発されました。MATLAB ^[18]には、統計ツールボックスの一部として次元1111までのSobol'シーケンスジェネレータが含まれています。

• 低矛盾シーケンス – 数学的シーケンスの種類
• 準モンテカルロ法 – 数値積分プロセス

• ACM のアルゴリズム集(アルゴリズム 647、659、および 738 を参照)
• Sobol シーケンス ジェネレーターのプログラミング コードのコレクション
• Sobol シーケンスのフリーウェア C++ ジェネレーター