Suite à discrépance faible

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, une suite à discrépance faible est une suite numérique ayant la propriété que pour tout entier N, la sous-suite x1, ..., xN 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[modifier | modifier le code]

Discrépance[modifier | modifier le code]

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

 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
 \prod_{i=1}^s [a_i, b_i) = \{ \mathbf{x} \in \R^s : a_i \le x_i < b_i \} \,

avec  0 \le a_i < b_i \le 1 .

Discrépance à l'origine et discrépance isotrope[modifier | modifier le code]

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 :

 D_N^*(P) = \sup_{B\in J^*}  \left|  \frac{A(B;P)}{N} - \lambda_s(B)  \right|

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

 \prod_{i=1}^s [0, u_i)

ui est l'intervalle semi-ouvert [0, 1).

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

 J_N(P) = \sup_{C\in \mathcal{C}^*}  \left|  \frac{A(C;P)}{N} - \lambda_s(C)  \right|

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

On a les résultats suivants

0\le D^*_N \le D_N \le J_N \le 1, \,
D^*_N \le D_N \le 2^s D^*_N, \,
D_N \le J_N \le 4s (D_N)^{\frac1s}. \,

Propriétés[modifier | modifier le code]

L'inégalité de Koksma–Hlawka[modifier | modifier le code]

On note Īs le cube unitaire de dimension s,

\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 x1, ..., xN dans Is = [0, 1) × ... × [0, 1),

 \left| \frac{1}{N} \sum_{i=1}^N f(x_i)- \int_{\bar I^s} f(u)\,du \right|\le 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 x1,...,xN dans Is et tout \epsilon>0, il existe une fonction f à variation bornée telle que V(f)=1 et

\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(x1,...,xN).

L'inégalité de Erdös-Turán-Koksma[modifier | modifier le code]

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

Soit x1,...,xN des points sur Is et H un entier positif. Alors

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

r(h)=\prod_{i=1}^s\max\{1,|h_i|\}\quad\mbox{pour}\quad h=(h_1,\ldots,h_s)\in\Z^s.

Conjectures sur la minoration des valeurs de la discrépance[modifier | modifier le code]

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

D_{N}^{*}(x_1,\ldots,x_N)\geq c_s\frac{(\ln N)^{s-1}}{N}

pour tout ensemble fini de points {x1,...,xN}.

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

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 x1,x2,x3,....

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

Minorations connues[modifier | modifier le code]

Soit s = 1. Alors

D_N^*(x_1,\ldots,x_N)\geq\frac{1}{2N}

pour tout N et toute suite de valeurs {x1, ..., xN}.

Soit s = 2. W. M. Schmidt a prouvé que pour tout ensemble fini de points {x1, ..., xN}, on a


D_N^*(x_1,\ldots,x_N)\geq C\frac{\log N}{N}

avec

C=\max_{a\geq3}\frac{1}{16}\frac{a-2}{a\log a}=0.023335\dots

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


D_N^*(x_1,\ldots,x_N)\geq\frac{1}{2^{4s}}\frac{1}{((s-1)\log2)^\frac{s-1}{2}}\frac{\log^{\frac{s-1}{2}}N}{N}

pour tout ensemble fini de points {x1, ..., xN}.

Construction de suites à discrépance faible[modifier | modifier le code]

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


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[modifier | modifier le code]

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 [0,0.5) et construire des nombres sous-aléatoires s_i réparties de façon uniforme sur [0,1) par :

  • s_i = r_i si i impair et s_i = 0.5 + r_i si i pair
  • s_i = s_{i-1} + 0.5+ r_i \pmod 1. \,

Par récurrence additive[modifier | modifier le code]

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

r_i = a r_{i-1} + c \pmod m

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

r_i = r_{i-1} + 1 \pmod m

Suites de Sobol[modifier | modifier le code]

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, 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[modifier | modifier le code]

Soit

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 ≤ dk(n) < b. On pose


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 (gb(n))n ≥ 1 vérifie


D^*_N(g_b(1),\dots,g_b(N))\leq C\frac{\log N}{N}.

Suite de Halton[modifier | modifier le code]

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 b1, ..., bs des nombres premiers entre eux supérieurs à 1. Alors


x(n)=(g_{b_1}(n),\dots,g_{b_s}(n)).

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


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 b1, ..., bs.

Suite de Hammersley[modifier | modifier le code]

Ensemble 2D de la suite de Hammersley de taille 256

Soit b1,...,bs-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


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

Elle vérifie


D^*_N(x(1),\dots,x(N))\leq C\frac{(\log N)^{s-1}}{N}

C est une constante ne dépendant que de b1, ..., bs−1.

Références[modifier | modifier le code]

  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. Donald E. Knuth The Art of Computer Programming Vol. 2, Ch. 3

Bibliographie[modifier | modifier le code]

Théorie[modifier | modifier le code]

  • Josef Dick and Friedrich Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, Cambridge, 2010, ISBN 978-0-521-19159-3
  • Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-295-5
  • Michael Drmota and 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[modifier | modifier le code]

  • William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling. Numerical Recipes in C. Cambridge, UK: Cambridge University Press, second edition 1992. ISBN 0-521-43108-5 (see Section 7.7 for a less technical discussion of low-discrepancy sequences)

Liens externes[modifier | modifier le code]