Sekvence Sobol - Sobol sequence

256 bodů z prvních 256 bodů za sekvenci 2,3 Sobol (nahoře) ve srovnání se zdrojem pseudonáhodného čísla (dole). Sekvence Sobol pokrývá prostor rovnoměrněji. (červená = 1, .., 10, modrá = 11, .., 100, zelená = 101, .., 256)

Sobolovy sekvence (také nazývaný LP_τ sekvence nebo (t, s) sekvence v bázi 2) jsou příkladem kvazi náhodného sekvence s nízkou odchylkou. Poprvé je představil ruský matematik Ilya M. Sobol (Илья Меерович Соболь) v roce 1967.^[1]

Tyto sekvence používají základnu dvou k vytvoření postupně jemnějších jednotných oddílů jednotkového intervalu a poté mění pořadí souřadnic v každé dimenzi.

Dobré distribuce v s-dimenzionální jednotka hyperkrychle

Nechat Já^s = [0,1]^s být s-dimenzionální jednotka hyperkrychle a F skutečná integrovatelná funkce Já^s. Původní motivací Sobola bylo sestavit posloupnost X_n v Já^s aby

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

a konvergence bude co nejrychlejší.

Je víceméně jasné, že pro součet konvergovat k integrálu, body X_n by měl vyplnit Já^s minimalizace děr. Další dobrá vlastnost by byla, že projekce X_n na tváři nižší dimenze Já^s také ponechte velmi málo otvorů. Proto homogenní náplň Já^s se nekvalifikuje, protože v nižších dimenzích bude mnoho bodů na stejném místě, proto je pro integrální odhad zbytečné.

Tyto dobré distribuce se nazývají (t,m,s) -sítě a (t,s) -sekvence v základně b. Chcete-li je představit, definujte nejprve elementární s-interval v základně b podmnožina Já^s formuláře

${ displaystyle prod _ {j = 1} ^ {s} left [{ frac {a_ {j}} {b ^ {d_ {j}}}}, { frac {a_ {j} +1} {b ^ {d_ {j}}}} vpravo),}$

kde A_j a d_j jsou nezáporná celá čísla a ${ displaystyle a_ {j}$ pro všechny j v {1, ..., s}.

Vzhledem k tomu, 2 celá čísla ${ displaystyle 0 leq t leq m}$, a (t,m,s) -net v základně b je sekvence X_n z b^m body Já^s takhle ${ displaystyle operatorname {Card} P cap {x_ {1}, ..., x_ {b ^ {m}} } = b ^ {t}}$ pro všechny základní intervaly P v základně b hypervolume λ(P) = b^{t − m}.

Bylo zadáno nezáporné celé číslo t, a (t,s) -sekvence v základně b je nekonečný sled bodů X_n taková, že pro všechna celá čísla ${ displaystyle k geq 0, m geq t}$, sekvence ${ displaystyle {x_ {kb ^ {m}}, ..., x _ {(k + 1) b ^ {m} -1} }}$ je (t,m,s) -net v základně b.

Sobol ve svém článku popsal Π_τ-mesh a LP_τ sekvence, což jsou (t,m,s) -sítě a (t,s) -sekvence v základně 2. Podmínky (t,m,s) -sítě a (t,s) -sekvence v základně b (také nazývané Niederreiterovy sekvence) byly vytvořeny v roce 1988 autorem Harald Niederreiter.^[2] Termín Sobolovy sekvence byl představen v pozdně anglicky mluvících novinách ve srovnání s Halton, Faure a další sekvence s nízkou odchylkou.

Rychlý algoritmus

Efektivnější Šedý kód implementaci navrhli Antonov a Saleev.^[3]

Pokud jde o generování Sobolových čísel, jasně jim pomáhá použití Grayova kódu ${ displaystyle G (n) = n oplus lfloor n / 2 rfloor}$ namísto n pro stavbu n-tý bod remíza.

Předpokládejme, že jsme již vygenerovali všechny čerpané sekvence Sobol n - 1 a uchoval v paměti hodnoty X_n−1,j pro všechny požadované rozměry. Od Šedého kódu G(n) se liší od předchozího G(n - 1) pouze jedním, řekněme k-th, bit (což je bit zcela vpravo) n - 1), vše, co je třeba udělat, je jediný XOR operace pro každou dimenzi za účelem šíření všech X_n−1 na X_n, tj.

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

Další vlastnosti uniformity

Sobol zavedl další podmínky uniformity známé jako vlastnost A a A '.^[4]

Definice

Sekvence s nízkou odchylkou je považována za uspokojivou Vlastnost A pokud pro libovolný binární segment (nikoli libovolnou podmnožinu) souboru d-rozměrná posloupnost délky 2^d v každé 2 je přesně jedna remíza^d hyperkrychle, které vznikají rozdělením hyperkrychle jednotky podél každé její prodloužení délky na polovinu.

Definice

Sekvence s nízkou odchylkou je považována za uspokojivou Nemovitost A ' pokud pro libovolný binární segment (nikoli libovolnou podmnožinu) souboru d-rozměrná posloupnost délky 4^d v každé 4 je přesně jedna remíza^d hyperkrychle, které vznikají rozdělením hyperkrychle jednotky podél každé její prodloužení délky na čtyři stejné části.

Existují matematické podmínky, které zaručují vlastnosti A a A '.

Teorém

The d-dimenzionální sekvence Sobol má vlastnost A iff

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

kde PROTI^d je d × d binární matice definovaná

${ 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}},}$

s proti_k,j,m označující m-tá číslice za binárním bodem čísla směru proti_k,j = (0.proti_k,j,1proti_k,j,2...)₂.

Teorém

The d-dimenzionální sekvence Sobol má vlastnost A 'iff

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

kde U^d je 2d × 2d binární matice definovaná

${ displaystyle mathbf {U} _ {d}: = { begin {pmatrix} {v_ {1,1,1}} & {v_ {1,1,2}} & {v_ {2,1,1 }} & {v_ {2,1,2}} & { dots} & {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}},}$

s proti_k,j,m označující m-tá číslice za binárním bodem čísla směru proti_k,j = (0.proti_k,j,1proti_k,j,2...)₂.

Zkoušky vlastností A a A 'jsou nezávislé. Je tedy možné zkonstruovat Sobolovu sekvenci, která splňuje obě vlastnosti A a A 'nebo pouze jednu z nich.

Inicializace sobolských čísel

Chcete-li vytvořit Sobolovu sekvenci, sadu směrových čísel proti_i,j je třeba vybrat. Při výběru počátečních čísel směru existuje určitá volnost.^{[poznámka 1]} Proto je možné pro vybrané dimenze přijímat různé realizace Sobolovy sekvence. Špatný výběr počátečních čísel může při použití pro výpočet výrazně snížit účinnost Sobolových sekvencí.

Pravděpodobně nejjednodušší volbou pro inicializační čísla je prostě mít l- nastaven bit úplně vlevo a všechny ostatní bity nulové, tj. m_k,j = 1 pro všechny k a j. Tato inicializace se obvykle nazývá inicializace jednotky. Taková posloupnost však pro vlastnosti A a A 'selže i pro malé rozměry, a proto je tato inicializace špatná.

Implementace a dostupnost

Dobrá inicializační čísla pro různé počty dimenzí poskytuje několik autorů. Například Sobol poskytuje inicializační čísla pro dimenze až 51.^[5] Stejnou sadu inicializačních čísel používají Bratley a Fox.^[6]

Inicializační čísla pro vysoké dimenze jsou k dispozici u Joe a Kuo.^[7] Peter Jäckel poskytuje inicializační čísla do své dimenze 32 ve své knize "Metody Monte Carlo ve financích ".^[8]

Další implementace jsou k dispozici jako rutiny C, Fortran 77 nebo Fortran 90 v Numerické recepty kolekce softwaru.^[9] A zdarma / open-source implementace až v 1111 dimenzích na základě inicializačních čísel Joe a Kuo je k dispozici v jazyce C.^[10]a až 21201 dimenzí v Pythonu^[11] a Julie^[12]. K dispozici je jiná bezplatná / otevřená implementace až v 1111 dimenzích C ++, Fortran 90, Matlab, a Krajta.^[13]

Nakonec jsou komerční generátory sekvencí Sobol k dispozici například v rámci Knihovna NAG,^[14]. Verze je k dispozici v Britsko-ruské agentuře pro rozvoj offshore (BRODA).^[15][16] MATLAB také obsahuje implementaci^[17] jako součást jeho statistického nástroje.

Viz také

• Sekvence s nízkou odchylkou
• Metoda kvazi-Monte Carla

Poznámky

Reference

externí odkazy

• Shromážděné algoritmy ACM (Viz algoritmy 647, 659 a 738.)
• Sbírka programovacích kódů generátorů sekvencí Sobol
• Freewarový generátor C ++ sekvence Sobol