ajout du dossier talk

[hdrcouchot.git] / annexePreuveStopping.tex

L'objectif principal de cette section est de démontrer le théorème~\ref{theo:tmps:mix} rappelé en fin de section.


Un résultat classique est

$$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$


Soit $(X_t)_{t\in \mathbb{N}}$ une suite de  variables aléatoires de 
$\Bool^{\mathsf{N}}$.
Une variable aléatoire $\tau$ dans $\mathbb{N}$ est un  
\emph{temps d'arrêt} pour la suite
$(X_i)$ si pour chaque $t$ il existe $B_t\subseteq
(\Bool^{\mathsf{N}})^{t+1}$ tel que 
$\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. 
En d'autres termes, l'événement $\{\tau = t \}$ dépend uniquement des valeurs 
de  
$(X_0,X_1,\ldots,X_t)$, et non de celles de $X_k$ pour $k > t$. 
 

Soit $(X_t)_{t\in \mathbb{N}}$ une chaîne de Markov et 
$f(X_{t-1},Z_t)$  une représentation fonctionnelle de celle-ci. 
Un \emph{temps d'arrêt aléatoire} pour la chaîne de 
Markov  est un temps d'arrêt pour 
$(Z_t)_{t\in\mathbb{N}}$.
Si la chaîne de Markov  est irréductible et a $\pi$
comme distribution stationnaire, alors un 
\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
(qui peut dépendre de la configuration initiale $X$),
tel que la distribution de $X_\tau$ est $\pi$:
$$\P_X(X_\tau=Y)=\pi(Y).$$
Un temps d'arrêt  $\tau$ est qualifié de  \emph{fort} si  $X_{\tau}$ 
est indépendant de  $\tau$.  

On rappelle le théorème suivant~\cite[Proposition 6.10]{LevinPeresWilmer2006}.

\begin{theorem}\label{thm-sst}
Si $\tau$ est un temps d'arrêt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}}
\P_X(\tau > t)$.
\end{theorem}


Soit $E=\{(X,Y)\mid
X\in \Bool^{\mathsf{N}}, Y\in \Bool^{\mathsf{N}},\ X=Y \text{ ou } X\oplus Y \in 0^*10^*\}$.
En d'autres mots, $E$ est l'ensemble des tous les arcs du   
${\mathsf{N}}$-cube. 
Soit $h: \Bool^{\mathsf{N}} \to [{\mathsf{N}}]$ 
qui mémorise pour chaque n{\oe}ud $X \in \Bool^{\mathsf{N}}$ quel
arc est supprimé à partir du cycle hamiltonien,
\textit{i.e.} quel bit dans  $[{\mathsf{N}} ]$ 
ne peut pas être inversé.



On définit ensuite  l'ensemble $E_h = E\setminus\{(X,Y)\mid X\oplus Y =
0^{{\mathsf{N}}-h(X)}10^{h(X)-1}\}$. C'est l'ensemble de tous les arcs 
appartenant à l'hypercube modifié, 
\textit{i.e.}, le ${\mathsf{N}}$-cube où le cycle hamiltonien $h$ 
a été enlevé.

On définit la matrice de Markov $P_h$ pour chaque ligne $X$ et  
chaque colonne $Y$  comme suit:
\begin{equation}
\left\{
\begin{array}{ll}
P_h(X,X)=\frac{1}{2}+\frac{1}{2{\mathsf{N}}} & \\
P_h(X,Y)=0 & \textrm{si  $(X,Y)\notin E_h$}\\
P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{si $X\neq Y$ et $(X,Y) \in E_h$}
\end{array}
\right.
\label{eq:Markov:rairo}
\end{equation} 





Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction 
telle que pour $X \in \Bool^{\mathsf{N}} $, 
$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. 
La fonction $\ov{h}$ est dite  {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
$\ov{h}(\ov{h}(X))\neq X$. 


%Let $\Bool^n$ be the set of words of length $n$. 

\begin{lemma}\label{lm:h}
Si $\ov{h}$ est bijective et anti-involutive, alors
$h(\ov{h}^{-1}(X))\neq h(X)$.
\end{lemma}

\begin{proof}
Soit $\ov{h}$  bijective. 
Soit $k\in \llbracket 1, {\mathsf{N}} \rrbracket$ t.q. $h(\ov{h}^{-1}(X))=k$.
Alors $(\ov{h}^{-1}(X),X)$ appartient à  $E$ et
$\ov{h}^{-1}(X)\oplus X = 0^{{\mathsf{N}}-k}10^{k-1}$.
Supposons $h(X) = h(\ov{h}^{-1}(X))$. Dans un tel cas, $h(X) =k$.
Par définition  $\ov{h}$, $(X, \ov{h}(X)) \in E $ et
$X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1} = 0^{{\mathsf{N}}-k}10^{k-1}$.
Ainsi $\ov{h}(X)= \ov{h}^{-1}(X)$, ce qui entraîne $\ov{h}(\ov{h}(X))= X$ et 
qui contredit le fait que $\ov{h}$ est anti-involutive.
\end{proof}

Soit $Z$ une variable aléatoire suivant une distribution uniforme sur 
$[ {\mathsf{N}}] \times \Bool$.
Pour $X\in \Bool^{\mathsf{N}}$, on définit avec  $Z=(i,b)$,  
\[
\left\{
\begin{array}{ll}
f(X,Z)=X\oplus (0^{{\mathsf{N}}-i}10^{i-1}) & \text{ si } b=1 \text{ et } i\neq h(X),\\
f(X,Z)=X& \text{sinon.} 
\end{array}\right.
\]

La chaîne de Markov est ainsi définie par 
\[
X_t= f(X_{t-1},Z_t).
\]




Un entier $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ est  \emph{équitable} 
 au temps $t$ s'il existe  $0\leq j <t$ tel que $Z_{j+1}=(\ell,\cdot)$ et $h(X_j)\neq \ell$. En d'autres mots, il existe une date $j$ antérieure à  $t$ 
où le premier élément de la variable aléatoire  $Z$ est $l$ 
(\textit{i.e.}, la stratégie vaut $l$ à la date $j$) 
et où le n{\oe}ud $X_j$ permet de traverser l'arc  $l$.  
 
Soit $\ts$ le premier temps où tous les éléments de $\llbracket 1, {\mathsf{N}} \rrbracket$ 
sont  équitables.  On a le lemme suivant:%L'entier $\ts$ est un temps d'arrêt pour la chaîne de Markov $(X_t)$.


\begin{lemma}
L'entier $\ts$ est un temps stationnaire fort.
\end{lemma}

\begin{proof}
Soit $\tau_\ell$ la première date où $\ell$ est équitable.
La variable aléatoire $Z_{\tau_\ell}$ est de la forme  $(\ell,b)$ %with $\delta\in\{0,1\}$ and
et telle que 
$b=1$ avec la probabilité $\frac{1}{2}$ et $b=0$ avec la probabilité 
$\frac{1}{2}$. Comme $h(X_{\tau_\ell-1})\neq\ell$,
la valeur du $\ell^{\textrm{ème}}$
bit de $X_{\tau_\ell}$ 
est $0$ ou $1$ avec la même probabilité  ($\frac{1}{2}$).

A chaque étape, le $l^{\textrm{ème}}$ bit  est inversé de $0$ à $1$ ou de $1$ à $0$, chaque fois avec la même 
probabilité. Ainsi,  pour $t\geq \tau_\ell$, le
$\ell^{\textrm{ème}}$ bit de $X_t$ est $0$ ou $1$ avec la même probabilité,
et ce indépendamment de la valeur des autres bits.
\end{proof}







Pour chaque $X\in \Bool^{\mathsf{N}}$ et $\ell\in [{\mathsf{N}}]$, 
soit $S_{X,\ell}$ une variable aléatoire qui compte le nombre d'itérations
tel qu'en démarrant de la configuration  $X$ on en atteigne une où 
$\ell$  est équitable. Plus formellement, 
$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ et }Z_t=(\ell,.)\text{ et } X_0=X\}.$$
On peut majorer l'espérance de cette variable aléatoire comme suit.


\begin{lemma}\label{prop:lambda}
Soit $\ov{h}$ un fonction bijective et anti-involutive. Alors pour tout 
 $X\in \Bool^{\mathsf{N}}$ et $\ell\in [{\mathsf{N}}]$, 
l'inégalité $E[S_{X,\ell}]\leq 8{\mathsf{N}}^2$ est établie.
\end{lemma}

\begin{proof}
Montrons tout d'abord que pour chaque $X$ et chaque  $\ell$, on a  $\P(S_{X,\ell})\leq 2)\geq
\frac{1}{4{\mathsf{N}}^2}$. Soit  $X_0= X$.

\begin{itemize}
\item Si $h(X)\neq \ell$, alors
$\P(S_{X,\ell}=1)=\frac{1}{2{\mathsf{N}}}\geq \frac{1}{4{\mathsf{N}}^2}$. 
\item Sinon, $h(X)=\ell$, alors
$\P(S_{X,\ell}=1)=0$. Dans ce cas, intuitivement, il est possible de passer de $X$ à $\ov{h}^{-1}(X)$ 
(avec la probabilité $\frac{1}{2N}$). De plus, dans la configuration
$\ov{h}^{-1}(X)$, le $l^{\textrm{ème}}$ bit peut être inversé.
Plus formellement, puisque $\ov{h}$ est anti-involutive,
$\ov{h}(X)=\ov{h}(\ov{h}(\ov{h}^{-1}(X)))\neq \ov{h}^{-1}(X)$. On en déduit
que $(X,\ov{h}^{-1}(X))\in E_h$. On a ainsi
$P(X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$. 
D'après le  lemme~\ref{lm:h},
$h(\ov{h}^{-1}(X))$ est différent de $h(X)$. 
Ainsi, $\P(S_{x,\ell}=2\mid X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$, 
prouvant ainsi que  $\P(S_{x,\ell}\leq 2)\geq
\frac{1}{4{\mathsf{N}}^2}$.
\end{itemize}




Ainsi, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{4{\mathsf{N}}^2}$. Par induction, on a,
pour chaque $i$, $\P(S_{X,\ell}\geq 2i)\leq
\left(1-\frac{1}{4{\mathsf{N}}^2}\right)^i$.
De plus,
puisque $S_{X,\ell}$ est positive, on sait~\cite[lemme 2.9]{proba} que
\[
E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i).
\]
Puisque $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, on a 
\[
E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i)\leq
\P(S_{X,\ell}\geq 1)+\P(S_{X,\ell}\geq 2)+2 \sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq 2i).\]
Ainsi,
$$E[S_{X,\ell}]\leq 1+1+2
\sum_{i=1}^{+\infty}\left(1-\frac{1}{4{\mathsf{N}}^2}\right)^i=2+2(4{\mathsf{N}}^2-1)=8{\mathsf{N}}^2,$$
ce qui conclut la preuve du lemme.
\end{proof}

Soit $\ts^\prime$ la variable aléatoire comptant le nombre d'itérations pour avoir exactement
$\mathsf{N}-1$ bits équitables. On peut majorer son espérance.

\begin{lemma}\label{lm:stopprime}
On a  $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{N}}+1).$
\end{lemma}

\begin{proof}
C'est un problème classique de collectionneur de vignettes. Soit $W_i$ la variable aléatoire 
comptant le nombre de déplacements dans la chaîne de Markov pour avoir exactement
$i-1$ bits équitables. On a $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}-1}W_i$.
Dans la configuration $X$ avec $i-1$ bits équitables,
la probabilité d'obtenir un nouveau bit équitable est soit
$1-\frac{i-1}{{\mathsf{N}}}$ si $h(X)$ est équitable,
soit $1-\frac{i-2}{{\mathsf{N}}}$ si $h(X)$ ne l'est pas. 

Ainsi, 
$\P (W_i=k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}}.$
On a par conséquent $\P(W_i\geq k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}-i+1}.$
On en déduit que 
\[
E[W_i]=\sum_{k=1}^{+\infty} \P (W_i\geq k)\leq {\mathsf{N}} \frac{{\mathsf{N}}-i+2}{({\mathsf{N}}-i+1)^2}\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2},
\]
et donc que 

\[
E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]\leq 
4{\mathsf{N}}\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{{\mathsf{N}}-i+2}=
4{\mathsf{N}}\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}.\]

Or $\sum_{i=1}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1)$. On en déduit que 
$1+\frac{1}{2}+\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1).$
Ainsi, on a la majoration suivante
\[
E[\ts^\prime]\leq 
4{\mathsf{N}} (-\frac{1}{2}+\ln({\mathsf{N}}+1))\leq 
4{\mathsf{N}}\ln({\mathsf{N}}+1),
\]
ce qui termine la preuve du lemme.
\end{proof}

Tous les éléments sont en place pour majorer l'espérance de $\ts$. 
\begin{theorem}
\label{prop:stop}
Si $\ov{h}$ est bijective et anti- involutive 
$\ov{h}(\ov{h}(X))\neq X$, alors
$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
\end{theorem}
\begin{proof}
Sans perte de généralité, considérons que le dernier bit 
non équitable est $\ell$. On a 
$\ts=\ts^\prime+S_{X_\tau,\ell}$ et donc
$E[\ts] = E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Ainsi, le théorème 
est une application directe des lemmes~\ref{prop:lambda} et~\ref{lm:stopprime}.
\end{proof}

Montrons alors le théorème~\ref{theo:tmps:mix} rappelé ci-dessous

\theotpsmix*

\begin{proof}
Comme $\tau$ est positive, on peut appliquer l'inégalité de Markov:
\[
\P_X(\tau > t)\leq \frac{E[\tau]}{t}.
\]

En posant $t_n=32N^2+16N\ln (N+1)$, on obtient:  
\[
\P_X(\tau > t_n)\leq \frac{1}{4}.
\] 


D'après la définition de $t_{\rm mix}$ et d'après le théorème~\ref{thm-sst},
on en déduit
\[
t_{\rm mix}\leq 32N^2+16N\ln (N+1)=O(N^2)
\].
\end{proof}