Suite de Sobol

Les suites de Sobol’ (également appelées suites LP_τ ou suite (t, s) en base 2) sont un exemple de suites quasi-aléatoires de faible discrépance. Elles ont été introduites par le mathématicien russe Ilya M. Sobol’ (Илья Меерович Соболь) en 1967^[1].

 

Les 256 premiers points de la suite de Sobol’ 2,3 (en haut) comparés avec un générateur de nombres pseudo-aléatoire (en bas). La suite de Sobol’ couvre l'espace de manière plus uniforme. (rouge=1,..,10, bleu=11,..,100, vert=101,..,256)

Ces suites utilisent une base deux pour former successivement des partitions de plus en plus fines de l'intervalle [0,1] avant de réorganiser les coordonnées dans chaque dimension.

Bonne distributions dans un hypercube de dimension s

Soit I^s = [0,1]^s l'hypercube de dimension s, et f une fonction réelle intégrable sur I^s. La motivation initiale de Sobol’ était de construire une séquence de x_n dans I^s, telle que

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

avec une convergence aussi rapide que possible.

Il est plus ou moins clair que pour que la somme converge vers l'intégrale, les points de x_n doivent remplir I^s en minimisant les trous. Une autre bonne propriété serait que les projections de x_n sur une face de I^s de dimension plus basse laissent elles également très peu de trous. Ainsi le remplissage homogène de I^s n'est pas satisfaisant, parce que dans les dimensions inférieures de nombreux points se trouvent au même endroit. Cette approche est donc inadéquate pour l'estimation de l'intégrale.

Les bonnes distributions recherchées sont appelés filets-(t,m,s) et suites-(t,s) dans la base b. Pour les présenter, définissons tout d'abord comme s-intervalle élémentaire de la base b un sous-ensemble de I^s de la forme :

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

où a_j et d_j sont des entiers non négatifs, et ${\displaystyle a_{j}<b^{d_{j}}}$ pour tout j dans {1, ...,s}.

Étant donné 2 nombres entiers ${\displaystyle 0\leq t\leq m}$, un filet-(t,m,s) dans la base b est une séquence x_n de b^m points de I^s telle que ${\displaystyle \operatorname {Card} P\cap \{x_{1},...,x_{b^{m}}\}=b^{t}}$ pour tout intervalle élémentaire de P dans la base b de l'hypervolume λ(P) = b^t-m.

Étant donné un entier non négatif t, une suite-(t,s) dans la base b est une suite infinie de points de x_n telle que, pour tout couple d'entiers (k, m) tel que ${\displaystyle k\geq 0,m\geq t}$, la suite ${\displaystyle \{x_{kb^{m}},...,x_{(k+1)b^{m}-1}\}}$ est un filet-(t,m,s) dans la base b.

Dans son article, Sobol’ décrit les grilles-Π_τ et les suites-LP_τ, qui sont les filets-(t,m,s) et les suites-(t,s) de la base 2, respectivement. Les termes filets-(t,m,s) et suites-(t,s) dans la base b (aussi appelés suites de Niederreiter) ont été inventés en 1988 par Harald Niederreiter^[2]. Le terme de suite de Sobol’ a été introduit dans les articles anglais en comparaison avec les suites de Halton, Faure et d'autres suites à faible divergence.

Un algorithme rapide

Une implémentation des codes de Gray plus efficace a été proposée par Antonov et Saleev^[3].

Comme pour la génération de nombres de Sobol’, ils sont clairement aidés par l'utilisation de code de Gray ${\displaystyle G(n)=n\oplus \lfloor n/2\rfloor }$ au lieu de n pour la construction du n-ième point à tirer.

Supposons que nous avons déjà généré toute la suite de Sobol’ jusqu'à n − 1 et conservé en mémoire les valeurs de x_n−1,j pour toutes les dimensions requises. Puisque le code de Gray G(n) diffère du précédent G(n − 1) d'un seul bit, disons le k-ième, tout ce qui doit être fait est une simple opération XOR pour chaque dimension dans le but de propager toutes les valeurs de x_n−1 à x_n, c'est-à-dire

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

Propriétés d'homogénéité supplémentaires

Sobol’ introduit de nouvelles conditions d'uniformité connues comme les propriétés A et A’^[4].

Définition

Une suite de faible divergence est dite satisfaire la Propriété A si pour n'importe quel segment binaire (pas un sous-ensemble arbitraire) de la suite d-dimensionnelle de longueur 2^d , il y a exactement un tirage dans chaque 2^d hypercube résultant de la subdivision par moitié de l'hypercube unité le long de chacune de ses extensions de longueur.

Définition

Une suite de faible divergence est dite satisfaire la Propriété A' si, pour n'importe quel segment binaire (pas un sous-ensemble arbitraire) de la suite d-dimensionnelle de longueur 4^d, il y a exactement un tirage dans chaque 4^d hypercubes résultant de la subdivision en quatre parts égales de l'hypercube unité le long de chacune de ses extensions de longueur.

Il existe des conditions mathématiques qui garantissent les propriétés de A et A'.

Théorème

La suite de Sobol’ d-dimensionnelle possède la Propriété A si et seulement si

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

où V^d est la matrice binaire d × d définie par

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

avec v_k,j,m désignant le m-ième chiffre après le point binaire du nombre de direction v_k,j = (0.v_k,j,1v_k,j,2...)₂.

Théorème

La suite de Sobol’ d-dimensionnelle possède la Propriété A' si et seulement si

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

où U^d est le 2d × 2d matrice binaire définie par

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

avec v_k,j,m désignant le m-ième chiffre après le binaire point du nombre de direction v_k,j = (0.v_k,j,1v_k,j,2...)₂.

Les tests pour les propriétés A et A’ sont indépendants. Ainsi, il est possible de construire une suite de Sobol’ qui satisfasse à la fois les propriétés de A et A’, ou seulement l'une d'entre eux.

L'initialisation des nombres de Sobol’

Pour construire une suite de Sobol’, un ensemble de nombres de direction v_i,j doit être sélectionné. Il y a une certaine liberté dans le choix de l'orientation initiale de ces nombres^{[note 1]}. Par conséquent, il est possible de construire différentes réalisations de la suite de Sobol’ pour des dimensions sélectionnées. Une mauvaise sélection des nombres initiaux peut réduire considérablement l'efficacité des suites de Sobol’ lorsque celles-ci sont utilisées pour des calculs.

Sans doute le choix le plus facile pour les nombres d'initialisation est de fixer le l-ème bit le plus à gauche à 1, et tous les autres bits à zéro, c'est-à-dire m_k,j = 1 pour tout k et tout j. Cette initialisation est généralement appelée initialisation unitaire. Cependant, une telle séquence échoue aux tests des propriétés A et A’, même pour de faibles dimensions, et cette initialisation est donc mauvaise.

Implémentation et disponibilité

De bons nombres d'initialisation pour différentes dimensions sont fournis par plusieurs auteurs. Par exemple, Sobol’ fournit des nombres d'initialisation pour les dimensions allant jusqu'à 51^[5]. Le même ensemble de nombres d'initialisation est utilisé par Bratley et Fox^[6].

Des nombres d'initialisation pour des dimensions élevées sont fournis par Joe et Kuo^[7]. Peter Jäckel fournit des nombres d'initialisation jusqu'à la dimension 32 dans son livre "Les méthodes de Monte-Carlo en finance"^[8].

D'autres implémentations sont disponibles en langage C, Fortran 77 ou Fortran 90 dans la collection de bibliothèques logicielles des Recettes numériques^[9]. Une implémentation libre/open-source, jusqu'à la dimension 1111, basée sur les nombres d'initialisation de Joe et Kuo, est disponible en C^[10], et jusqu'à 21201 dimensions en Python^[11] et Julia^[12]. Une implémentation alternative libre/open-source jusqu'à 1111 dimensions est disponible pour le C++, Fortran 90, Matlab et Python^[13].

Enfin, des générateurs commerciaux de suites de Sobol’ sont disponibles au sein, par exemple, de la bibliothèque NAG^[14]. Une version est disponible via la British-Russian Offshore Development Agency (BRODA)^[15],[16]. MATLAB contient également une implémentation^[17] dans le cadre de sa boîte à outils statistiques.

Voir aussi

• Suite à discrépance faible
• Méthode de Quasi-Monte Carlo

Notes

1. These numbers are usually called initialisation numbers.

Références

1. Sobol’,I.M. (1967), "Distribution of points in a cube and approximate evaluation of integrals". Zh. Vych. Mat. Mat. Fiz. 7: 784–802 (in Russian); U.S.S.R Comput. Maths. Math. Phys. 7: 86–112 (in English).
2. Niederreiter, H. (1988). "Low-Discrepancy and Low-Dispersion Sequences", Journal of Number Theory 30: 51–70.
3. Antonov, I.A. and Saleev, V.M. (1979) "An economic method of computing LP_τ-sequences". Zh. Vych. Mat. Mat. Fiz. 19: 243–245 (in Russian); U.S.S.R. Comput. Maths. Math. Phys. 19: 252–256 (in English).
4. Sobol’, I. M. (1976) "Uniformly distributed sequences with an additional uniform property". Zh. Vych. Mat. Mat. Fiz. 16: 1332–1337 (in Russian); U.S.S.R. Comput. Maths. Math. Phys. 16: 236–242 (in English).
5. Sobol’, I.M. and Levitan, Y.L. (1976). "The production of points uniformly distributed in a multidimensional cube" Tech. Rep. 40, Institute of Applied Mathematics, USSR Academy of Sciences (in Russian).
6. Bratley, P. and Fox, B. L. (1988), "Algorithm 659: Implementing Sobol’ quasirandom sequence generator". ACM Trans. Math. Software 14: 88–100.
7. « Sobol’ sequence generator », University of New South Wales, 16 septembre 2010 (consulté le 20 décembre 2013)
8. Jäckel, P. (2002) "Monte Carlo methods in finance".
9. Press, W.H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. (1992) "Numerical Recipes in Fortran 77: The Art of Scientific Computing, 2nd ed."
10. C implementation of the Sobol’ sequence in the NLopt library (2007).
11. Imperiale, « pyscenarios: Python Scenario Generator »
12. Sobol.jl package: Julia implementation of the Sobol’ sequence.
13. The Sobol’ Quasirandom Sequence, code for C++/Fortran 90/Matlab/Python by J. Burkardt
14. « Numerical Algorithms Group », Nag.co.uk, 28 novembre 2013 (consulté le 20 décembre 2013)
15. I. Sobol’, D. Asotsky, A. Kreinin, S. Kucherenko, « Construction and Comparison of High-Dimensional Sobol’ Generators », Wilmott Journal, vol. Nov,‎ 2011, p. 64–79 (lire en ligne [PDF])
16. « Broda », Broda, 16 avril 2004 (consulté le 20 décembre 2013)
17. sobolset reference page.

Liens externes

• Recueil des algorithmes de l'ACM (voir les algorithmes 647, 659 et 738)
• Collection de codes pour générer des suites de Sobol’ (anglais)
• Générateur de séquence de Sobol’ en C++ (Freeware, anglais)

• Portail des mathématiques