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.

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 :

 

où 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. 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.

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 xn−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 xn−1 à 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’.

 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
 
 où 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
 
 où 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. 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. Le même ensemble de nombres d'initialisation est utilisé par Bratley et Fox.

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

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. 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, et jusqu'à 21201 dimensions en Python et Julia. Une implémentation alternative libre/open-source jusqu'à 1111 dimensions est disponible pour le C++, Fortran 90, Matlab et Python.

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

Voir aussi 

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

Notes

Références

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)

Suite