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 divergence. Elles ont été introduites par le mathématicien russe Ilya M. Sobol (Илья Меерович Соболь) en 1967[1].

Pour les articles homonymes, voir Sobol.

 

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 Is = [0,1]s l'hypercube de dimension s, et f une fonction réelle intégrable sur Is. La motivation initiale de Sobol était de construire une séquence de xn dans Is, telle que

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 xn doivent remplir Is en minimisant les trous. Une autre bonne propriété serait que les projections de xn sur une face de Is de dimension plus basse laissent elles également très peu de trous. Ainsi le remplissage homogène de Is 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 Is de la forme :

aj et dj sont des entiers non négatifs, et pour tout j dans {1, ...,s}.

Étant donné 2 nombres entiers , un filet-(t,m,s) dans la base b est une séquence xn de bm points de Is telle que pour tout intervalle élémentaire de P dans la base b de l'hypervolume λ(P) = bt-m.

Étant donné un entier non négatif t, une suite-(t,s) dans la base b est une suite infinie de points de xn telle que, pour tout couple d'entiers (k, m) tel que , la suite 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 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 xn1,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 xn1 à xn, c'est-à-dire

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 2d , il y a exactement un tirage dans chaque 2d 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 4d, il y a exactement un tirage dans chaque 4d 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
Vd est la matrice binaire d × d définie par
avec vk,j,m désignant le m-ième chiffre après le point binaire du nombre de direction vk,j = (0.vk,j,1vk,j,2...)2.
Théorème
La suite de Sobol d-dimensionnelle possède la Propriété A' si et seulement si
Ud est le 2d × 2d matrice binaire définie par
avec vk,j,m désignant le m-ième chiffre après le binaire point du nombre de direction vk,j = (0.vk,j,1vk,j,2...)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 vi,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 mk,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

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’s quasirandom sequence generator". ACM Trans. Math. Software 14: 88–100.
  7. « Sobol sequence generator », University of New South Wales, (consulté le )
  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, (consulté le )
  15. I. Sobol’, D. Asotsky, A. Kreinin, S. Kucherenko, « Construction and Comparison of High-Dimensional Sobol’ Generators », Wilmott Journal, vol. Nov, , p. 64–79 (lire en ligne [PDF])
  16. « Broda », Broda, (consulté le )
  17. sobolset reference page.

Liens externes

  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.