Suite à discrépance faible

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}$.

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 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}}}$.

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).

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}.}$

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.

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}.

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}}}$.

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}}}$.

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.

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}}.}$

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.

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.

• 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

• (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