6.6 Dimensions supérieures
89
6.5 Une inégalité de concentration
Complétons les résultats sur le comportement de X n par une inégalité
de concentration valable pour tout n 1 (à la différence du théorème de
convergence en loi qui n’est qu’asymptotique).
Théorème 6.10 (Concentration). Pour tout n 1 et tout r > 0,
P
|X n |
n
r
2 exp
−
3n
2 r
2
8(n + 1)
.
Démonstration. Par définition de la martingale (M n ) n0 définie dans le
lemme 6.9, pour tout r > 0,
P
|X n |
n
r
P(|M n | n(n + 1)r).
La martingale (M n ) n0 a des accroissements borné car pour tout n 1,
|M n − M n−1 | = |(n + 1)X n − nX n−1 | n|X n − X n−1 | + |X n | 2n
puisque |X n − X n−1 | = 1 et |X n | n. D’après l’inégalité de concentration
d’Azuma-Hoeffding du lemme 20.3, pour tout λ > 0, on a
P(|M n | λ) 2 exp
−
λ
2
2
n
k=1 (2k) 2
.
Grâce à la comparaison série-intégrale
n
k=1
(2k)
2
4
n+1
1
x
2 dx =
4
3
(n + 1)
3 ,
il reste à remplacer λ par n(n + 1)r pour obtenir l’inégalité souhaitée.
6.6 Dimensions supérieures
On se place à présent sur Z
d avec d > 1. Comme en dimension 1, on
s’attend à ce que la forme limite de l’ensemble aléatoire devienne relativement régulière puisque la marche aléatoire issue de l’origine aura tendance à
atteindre l’ensemble aléatoire A
c
n en des points qui ont beaucoup de voisins
dans A n . La figure 6.1 fournit une réalisation de A(1000) en dimension 2.
Pour tout r 0 notons x la norme euclidienne d’un point x ∈ R
d et
B(0, r) =
y ∈ R
d : y < r
et B(0, r) = B(0, r) ∩ Z
d .
Le cardinal d’un ensemble Λ de Z
d est noté |Λ|. Fixons un entier n et considérons l’ensemble aléatoire A(|B(0, n)|). Le rayon (aléatoire) de la plus grande
boule incluse dans cet ensemble est