Suite à discrépance faible

En mathématiques, une suite à discrépance faible est une suite ayant la propriété que pour tout entier N, la sous-suite x₁, ..., x_N a une discrépance basse.

Dans les faits, la discrépance d'une suite est faible si la proportion des points de la suite sur un ensemble B est proche de la valeur de la mesure de B, ce qui est le cas en moyenne (mais pas pour des échantillons particuliers) pour une suite équidistribuée. Plusieurs définitions de la discrépance existent selon la forme de B (hypersphères, hypercubes, etc.) et la méthode de calcul de la discrépance sur B.

Les suites à discrépance faible sont appelées quasi aléatoires ou sous-aléatoires, en raison de leur utilisation pour remplacer les tirages de la loi uniforme continue. Le préfixe « quasi » précise ainsi que les valeurs d'une suite à discrépance faible ne sont pas aléatoires ou pseudo-aléatoires, mais ont des propriétés proches de tels tirages, permettant ainsi leur usage intéressant dans la méthode de quasi-Monte-Carlo.

Définitions

Discrépance

La discrépance ou discrépance extrême^[1] d'un ensemble P = {x₁, ..., x_N} est définie (en utilisant les notations de Niederreiter) par

${\displaystyle D_{N}(P)=\sup _{B\in J}\left|{\frac {A(B;P)}{N}}-\lambda _{s}(B)\right|}$

avec

• λ_s est la mesure de Lebesgue de dimension s,
• A(B; P) est le nombre de points de P appartenant à B,
• J est l'ensemble des pavés de dimension s, de la forme

${\displaystyle \prod _{i=1}^{s}[a_{i},b_{i}[=\{\mathbf {x} \in \mathbb {R} ^{s}:a_{i}\leq x_{i}<b_{i}\}\,}$

avec ${\displaystyle 0\leq a_{i}<b_{i}\leq 1}$.

Discrépance à l'origine et discrépance isotrope

La discrépance à l'origine D^*_N(P) est définie de façon similaire, mis à part que la borne inférieure des pavés de J est fixée à 0 :

${\displaystyle D_{N}^{*}(P)=\sup _{B\in J^{*}}\left|{\frac {A(B;P)}{N}}-\lambda _{s}(B)\right|}$

avec J^* l'ensemble des pavés de dimension s, de la forme

${\displaystyle \prod _{i=1}^{s}[0,u_{i}[}$

où u_i est dans l'intervalle semi-ouvert [0, 1[.

On définit également la discrépance isotrope J_N(P) :

${\displaystyle J_{N}(P)=\sup _{C\in {\mathcal {C}}^{*}}\left|{\frac {A(C;P)}{N}}-\lambda _{s}(C)\right|}$

avec ${\displaystyle {\mathcal {C}}^{*}}$ la famille des sous-ensembles convexes du cube unité fermé de dimension s.

On a les résultats suivants

${\displaystyle 0\leq D_{N}^{*}\leq D_{N}\leq J_{N}\leq 1}$,

${\displaystyle D_{N}^{*}\leq D_{N}\leq 2^{s}D_{N}^{*}}$,

${\displaystyle D_{N}\leq J_{N}\leq 4s(D_{N})^{\frac {1}{s}}}$.

Propriétés

L'inégalité de Koksma-Hlawka

On note Ī^s le cube unitaire de dimension s,

${\displaystyle {\bar {I}}^{s}=[0,1]\times ...\times [0,1]}$.

Soit f une fonction à variation bornée de variation de Hardy-Krause V(f) finie sur Ī^s. Alors pour tout x₁, ..., x_N dans I^s = [0, 1[ × ... × [0, 1[

${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|\leq V(f)\,D_{N}^{*}(x_{1},\ldots ,x_{N})}$.

L'inégalité de Koksma-Hlawka est consistante dans le sens où pour tout ensemble de points x₁,...,x_N dans I^s et tout ε > 0, il existe une fonction f à variation bornée telle que V(f)=1 et

${\displaystyle \left|{\frac {1}{N}}\sum _{i=1}^{N}f(x_{i})-\int _{{\bar {I}}^{s}}f(u)\,du\right|>D_{N}^{*}(x_{1},\ldots ,x_{N})-\epsilon .}$

Ainsi, la qualité du calcul de l'intégrale ne dépend que de la discrépance D^*_N(x₁,...,x_N).

L'inégalité d'Erdös-Turán-Koksma

Le calcul de la discrépance de grands ensembles est souvent compliquée, mais l'inégalité d'Erdös-Turán-Koksma donne une majoration de la valeur.

Soit x₁,...,x_N des points sur I^s et H un entier positif. Alors

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq \left({\frac {3}{2}}\right)^{s}\left({\frac {2}{H+1}}+\sum _{0<\|h\|_{\infty }\leq H}{\frac {1}{r(h)}}\left|{\frac {1}{N}}\sum _{n=1}^{N}e^{2\pi i\langle h,x_{n}\rangle }\right|\right)}$

avec

${\displaystyle r(h)=\prod _{i=1}^{s}\max\{1,|h_{i}|\}\quad {\mbox{pour}}\quad h=(h_{1},\ldots ,h_{s})\in \mathbb {Z} ^{s}.}$

Conjectures sur la minoration des valeurs de la discrépance

Conjecture 1. Il existe une constante c_s dépendant uniquement de la dimension s, telle que

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c_{s}{\frac {(\ln N)^{s-1}}{N}}}$

pour tout ensemble fini de points {x₁,...,x_N}.

Conjecture 2. Il existe une constante c^'_s dépendant uniquement de la dimension s, telle que

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq c'_{s}{\frac {(\ln N)^{s}}{N}}}$

pour au moins un sous-ensemble fini de valeurs de la suite x₁, x₂, x₃....

Ces conjectures sont équivalentes. Si elles ont été prouvées pour s ≤ 2 par Wolfgang Schmidt, la question des dimensions supérieures est encore ouverte.

Minorations connues

Soit s = 1. Alors

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2N}}}$

pour tout N et toute suite de valeurs {x₁, ..., x_N}.

Soit s = 2. Wolfgang Schmidt a prouvé que pour tout ensemble fini de points {x₁, ..., x_N}, on a

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq C{\frac {\log N}{N}}}$

avec

${\displaystyle C=\max _{a\geq 3}{\frac {1}{16}}{\frac {a-2}{a\log a}}=0{,}023335\dots }$

Pour les dimensions s > 1, K. F. Roth a prouvé que

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\geq {\frac {1}{2^{4s}}}{\frac {1}{((s-1)\log 2)^{\frac {s-1}{2}}}}{\frac {\log ^{\frac {s-1}{2}}N}{N}}}$

pour tout ensemble fini de points {x₁, ..., x_N}.

Construction de suites à discrépance faible

On ne donne ici que des exemples de tirages à discrépance faible pour les dimensions supérieures à 1.

On sait construire des suites telles que

${\displaystyle D_{N}^{*}(x_{1},\ldots ,x_{N})\leq C{\frac {(\ln N)^{s}}{N}}.}$

où la constante C dépend de la suite. Par la conjecture 2, ces suites sont supposées avoir le meilleur ordre de convergence possible.

À partir de nombres aléatoires

Des suites de nombres sous-aléatoires peuvent être générées à partir d'un tirage aléatoire en imposant une corrélation négative entre les nombres du tirage. Par exemple, on peut se donner un tirage aléatoire r_i sur ${\displaystyle [0;0,5[}$ et construire des nombres sous-aléatoires s_i réparties de façon uniforme sur ${\displaystyle [0,1[}$ par :

• ${\displaystyle s_{i}=r_{i}}$ si i impair et ${\displaystyle s_{i}=0.5+r_{i}}$ si i pair
• ${\displaystyle s_{i}=s_{i-1}+0.5+r_{i}{\pmod {1}}}$.

Par récurrence additive

Une méthode classique de génération de nombres pseudo-aléatoires est donné par^[2] :

${\displaystyle r_{i}=ar_{i-1}+c{\pmod {m}}}$.

En fixant a et c à 1, on obtient un générateur simple :

${\displaystyle r_{i}=r_{i-1}+1{\pmod {m}}}$.

Suites de Sobol

La variante Antonov–Saleev de la suite de Sobol génère des nombres entre 0 et 1 comme fractions binaires de longueur w, pour un ensemble w fractions binaires spéciales, ${\displaystyle V_{i},i=1,2,\dots ,w}$ sont appelés nombres de direction. Les bits du code de Gray de i, G(i), sont utilisés pour choisir des nombres de direction. Obtenir les valeurs de la suite de Sobol s_i demande le ou exclusif de la valeur binaire du code de Gray de i avec le nombre de direction approprié. Le nombre de dimension a un impact sur le choix de V_i.

Suites de van der Corput

Soit

${\displaystyle n=\sum _{k=0}^{L-1}d_{k}(n)b^{k}}$

la décomposition de l'entier positif n ≥ 1 en base b, avec donc 0 ≤ d_k(n) < b. On pose

${\displaystyle g_{b}(n)=\sum _{k=0}^{L-1}d_{k}(n)b^{-k-1}.}$

Alors il existe une constante C dépendant uniquement de b telle que (g_b(n))_{n ≥ 1} vérifie

${\displaystyle D_{N}^{*}(g_{b}(1),\dots ,g_{b}(N))\leq C{\frac {\log N}{N}}.}$

Suite de Halton

Les 256 points de la suite de Halton (2,3)

La suite de Halton généralise la suite de van der Corput pour les dimensions supérieures à 1. Soit s la dimension du problème et b₁, ..., b_s des nombres premiers entre eux supérieurs à 1. Alors

${\displaystyle x(n)=(g_{b_{1}}(n),\dots ,g_{b_{s}}(n)).}$

Il existe une constante C dépendant uniquement de b₁, ..., b_s, telle que {x(n)}_n≥1 vérifie

${\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C'{\frac {(\log N)^{s}}{N}}.}$

Dans la pratique, on utilise les s premiers nombres premiers pour b₁, ..., b_s.

Suite de Hammersley

Ensemble 2D de la suite de Hammersley de taille 256

Soit b₁,...,b_s-1 des nombres premiers entre eux supérieurs à 1. Pour s et N donnés, la suite de Hammersley de taille N est donnée par

${\displaystyle x(n)=(g_{b_{1}}(n),\dots ,g_{b_{s-1}}(n),{\frac {n}{N}})}$

Elle vérifie

${\displaystyle D_{N}^{*}(x(1),\dots ,x(N))\leq C{\frac {(\log N)^{s-1}}{N}}}$

où C est une constante ne dépendant que de b₁, ..., b_s−1.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Low-discrepancy sequence » (voir la liste des auteurs).

1. Discrepancy en anglais, voir par exemple (Lapeyre et Pagès 1989) et (Thiémard 2000), pour une référence de la traduction.
2. (en) Donald E. Knuth, The Art of Computer Programming, vol. 2, chap. 3.

Bibliographie

Théorie

• Eric Thiémard, Sur le calcul et la majoration de la discrépance à l'origine (Thèse de doctorat), École polytechnique fédérale de Lausanne, 2000 (lire en ligne)
• (en) Josef Dick et Friedrich Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, Cambridge, 2010, (ISBN 978-0-521-19159-3)
• (en) L. Kuipers et H. Niederreiter, Uniform distribution of sequences, Dover Publications, 2005, 416 p. (ISBN 0-486-45019-8)
• (en) Harald Niederreiter, Random Number Generation and Quasi-Monte Carlo Methods, SIAM, 1992 (ISBN 0-89871-295-5)
• (en) Michael Drmota et Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math., 1651, Springer, Berlin, 1997 (ISBN 3-540-62606-9)
• Bernard Lapeyre et G. Pagès, « Familles de suites à discrépance faible obtenues par itération de transformations de [0, 1] », Note aux CRAS, Série I, vol. 17,‎ 1989, p. 507-509

Simulations numériques

• (en) William H. Press, Brian P. Flannery, Saul A. Teukolsky et William T. Vetterling, Numerical Recipes in C, Cambridge University Press, 2^e éd., 1992 (ISBN 0-521-43108-5) (voir Section 7.7 pour une discussion moins technique)
• Quasi-Monte Carlo Simulations, http://www.puc-rio.br/marco.ind/quasi_mc.html

Liens externes

• (en) Collected Algorithms of the ACM (voir les algorithmes 647, 659 et 738)
• (en) GNU Scientific Library Quasi-Random Sequences

• Portail des mathématiques