476
Solutions
1. On commence par noter que
γ n (1) = E(
n
p=1
1 {X
0 ,...,X
p−1 } (X
p ))
=
(x0,...,xn)∈An
M
(x 0 , x 1 ) . . . M
(x n−1 , x n )
=
(x0,...,xn)∈An
1
2d
× . . . ×
1
2d
=
|A n |
(2d) n
On observe ensuite que
η n (G n ) =
γ n (G n )
γ n (1)
=
γ n (1)
γ n−1 (1)
D’apr` es ce qui pr´ ec´ ede, on obtient
η n (G n ) =
|A n |
(2d) n ×
(2d)
n−1
|A n |
=
1
2d
|A n |
|A n−1 |
2. En utilisant le fait qu’une marche al´ eatoire sans intersection de longueur
(p + q) est n´ ecessairement la concat´ enation d’une marche sans intersection
de longueur p, et d’une de longueur q, on montre que
|A p+q | ≤ |A p | |A q |
Pour v´ erifier le second encadrement, on note qu’une marche ne choisissant
que des vecteurs unitaires de la forme
u = (0, . . . , 0, +1, 0, . . . , 0)
et ignorant les vecteurs unitaires oppos´ es
v = (0, . . . , 0, −1, 0, . . . , 0)
ne peut s’intersecter. On montre ainsi la minoration recherch´ ee
d
n
≤ |A n |
Enfin, une marche sans intersection est un chemin ´ evitant n´ ecessairement
` a chaque ´ etape le dernier point visit´ e. Par exemple, si la marche choisit ` a
un temps donn´ e un vecteur unitaire
u = (1, 0, . . . , 0)
elle ne peut choisir imm´ ediatement apr` es le vecteur oppos´ e
u = (−1, 0, . . . , 0)
On a donc la majoration suivante
|S n | ≤ 2d (2d − 1)
n