Sobol sekvens

256 poäng från de första 256 poängen för 2,3 Sobol'-sekvensen (överst) jämfört med en pseudoslumptalskälla (nederst). Sobol'-sekvensen täcker utrymmet jämnare. (röd=1,..,10, blå=11,..,100, grön=101,..,256)

Sobol'-sekvenser (även kallade LP _τ- sekvenser eller ( t , s )-sekvenser i bas 2) är ett exempel på kvasi-slumpmässiga lågdiskrepanssekvenser . De introducerades först av den ryske matematikern Ilya M. Sobol' (Илья Меерович Соболь) 1967.

Dessa sekvenser använder en bas av två för att bilda successivt finare enhetliga partitioner av enhetsintervallet och sedan ordna om koordinaterna i varje dimension.

Bra fördelningar i den s -dimensionella enhetens hyperkub

Låt I ^s = [0,1] ^s vara den s -dimensionella enheten hyperkub, och f en verklig integrerbar funktion över I ^s . Den ursprungliga motiveringen för Sobol' var att konstruera en sekvens x _n i I ^s så att

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

och konvergensen vara så snabb som möjligt.

xn fylla _tydligt att för att summan ska konvergera mot integralen bör punkterna I ^s för att minimera hålen. En annan bra egenskap skulle vara att projektionerna av x _n på en lägre dimensionell yta av I ^s lämnar väldigt få hål också. Därför är den homogena fyllningen av I ^s inte kvalificerad eftersom i lägre dimensioner kommer många punkter att vara på samma plats, därför värdelösa för integraluppskattningen.

Dessa goda fördelningar kallas ( t , m , s )-nät och ( t , s )-sekvenser i bas b . För att introducera dem, definiera först ett elementärt s -intervall i bas b en delmängd av I ^s av formen

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

där a _j och d _j är icke-negativa heltal, och $a_{j}<b^{d_{j}}$ för alla j i {1, ...,s}.

Givet 2 heltal $0\leq t\leq m$ , är a ( t , m , s )-net i bas b en sekvens x _n av b ^m punkter av I ^s så att $\operatorname {Card} P\cap \{x_{1},...,x_{b^{m}}\}=b^{t}$ för alla elementära intervall P i bas b av hypervolym λ ( P ) = b ^t−m .

Givet ett icke-negativt heltal t , är a ( t , s )-sekvensen i bas b en oändlig sekvens av punkter x _n så att för alla heltal $k\geq 0,m\geq t$ , sekvensen ${\displaystyle \{x_{kb^{m}},...,x_{(k+1)b^{m}-1}\}} är$ en ( t , m , s )-net i bas b .

I sin artikel beskrev Sobol' Π _τ -maskor och LP _{τ -} sekvenser , som är ( t , m , s )-nät respektive ( t , s )-sekvenser i bas 2. Termerna ( t , m , s )-nät och ( t , s )-sekvenser i bas b (även kallade Niederreiter-sekvenser) myntades 1988 av Harald Niederreiter . Termen Sobol'-sekvenser introducerades i sent engelsktalande tidningar i jämförelse med Halton , Faure och andra sekvenser med låg diskrepans.

En snabb algoritm

En effektivare implementering av Gray-kod föreslogs av Antonov och Saleev.

När det gäller genereringen av Sobol'-nummer är de tydligt hjälpta av användningen av grå kod $G(n)=n\oplus \lfloor n/2\rfloor$ istället för n för att konstruera den n -te punkten.

Antag att vi redan har genererat alla Sobol'-sekvenser upp till n − 1 och sparat värdena x _{n −1, j} för alla nödvändiga dimensioner i minnet. Eftersom den grå koden G ( n ) skiljer sig från den för den föregående G ( n − 1) med bara en singel, säg den k -:te biten (som är en nollbit längst till höger av n − 1), behöver allt som behövs för att göras är en enda XOR- operation för varje dimension för att sprida alla x _{n −1} till x _n , dvs.

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

Ytterligare enhetlighetsegenskaper

Sobol' introducerade ytterligare enhetlighetsvillkor kända som egenskap A och A'.

Definition

En sekvens med låg diskrepans sägs uppfylla egenskap A om det för något binärt segment (inte en godtycklig delmängd) av den d -dimensionella sekvensen med längden 2 ^d finns exakt ett drag i varje 2 ^d hyperkub som är ett resultat av att dela upp enhetens hyperkub längs var och en av dess längdförlängningar till hälften.

Definition

En sekvens med låg diskrepans sägs uppfylla egenskap A' om det för något binärt segment (inte en godtycklig delmängd) av den d -dimensionella sekvensen med längden 4 ^d finns exakt ett drag i varje 4 ^d hyperkuber som är ett resultat av att dela upp enheten hyperkub längs var och en av dess längdförlängningar i fyra lika delar.

Det finns matematiska villkor som garanterar egenskaperna A och A'.

Sats

Den d -dimensionella Sobol'-sekvensen har egenskapen A iff

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

där Vd är den binära matrisen

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

× d definierad av ^d

med v _{k , j , m} betecknar den m -:te siffran efter den binära punkten för riktningsnumret v _{k , j} = (0. v _{k , j ,1} v _{k , j ,2} ...) ₂ .

Teorem

Den d -dimensionella Sobol'-sekvensen har egenskapen A' iff

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

där U ^d är den 2 d × 2 d binära matrisen definierad av

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

med v _{k , j , m} som betecknar den m -:te siffran efter den binära punkten för riktningsnumret v _{k , j} = (0. v _{k , j ,1} v _{k , j ,2} ...) ₂ .

Tester för egenskaperna A och A' är oberoende. Således är det möjligt att konstruera Sobol'-sekvensen som uppfyller både egenskaperna A och A' eller bara en av dem.

Initieringen av Sobols nummer

För att konstruera en Sobol'-sekvens måste en uppsättning riktningsnummer v _{i , j} väljas. Det finns en viss frihet i valet av initiala riktningsnummer. Därför är det möjligt att ta emot olika realiseringar av Sobol'-sekvensen för utvalda dimensioner. Ett dåligt urval av initiala siffror kan avsevärt minska effektiviteten hos Sobol'-sekvenser när de används för beräkning.

Förmodligen är det enklaste valet för initialiseringsnumren bara att ha den l -:e biten längst till vänster inställd _{, , j} och alla andra bitar ska vara noll, dvs mk = 1 för alla k och j . Denna initiering kallas vanligtvis enhetsinitiering . En sådan sekvens klarar emellertid inte testet för egenskap A och A' även för låga dimensioner och därför är denna initiering dålig.

Implementering och tillgänglighet

Bra initialiseringsnummer för olika antal dimensioner tillhandahålls av flera författare. Till exempel tillhandahåller Sobol' initialiseringsnummer för dimensioner upp till 51. Samma uppsättning initialiseringsnummer används av Bratley och Fox.

Initialiseringsnummer för höga dimensioner finns på Joe och Kuo. Peter Jäckel tillhandahåller initialiseringsnummer upp till dimension 32 i sin bok " Monte Carlo-metoder inom finans ".

Andra implementeringar är tillgängliga som C-, Fortran 77- eller Fortran 90-rutiner i samlingen Numerical Recipes av programvara. En med gratis/öppen källkod i upp till 1111 dimensioner, baserad på Joe- och Kuo-initieringsnumren, finns tillgänglig i C och upp till 21201 dimensioner i Python och Julia . En annan gratis/öppen källkod-implementering i upp till 1111 dimensioner är tillgänglig för C++, Fortran 90 , Matlab och Python .

Slutligen finns kommersiella Sobol' sekvensgeneratorer tillgängliga inom till exempel NAG Library . En version finns tillgänglig från British-Russian Offshore Development Agency (BRODA). MATLAB innehåller även en implementering som en del av sin statistikverktygslåda.

Se även

• Sekvenser med låg diskrepans
• Quasi-Monte Carlo-metoden

externa länkar

• Samlade algoritmer för ACM (Se ​​algoritmerna 647, 659 och 738.)
• Samling av programmeringskoder för Sobols sekvensgenerator
• Gratisprogram C++ generator av Sobol' sekvens