X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/1042ddb8d08dc129da9358b73e723fc5014fb2c8..44a56c5eb4a1dfdf7dc67735c5c00f478cef2ede:/annexePreuveStopping.tex?ds=sidebyside diff --git a/annexePreuveStopping.tex b/annexePreuveStopping.tex index 6bbd41f..75d05e4 100644 --- a/annexePreuveStopping.tex +++ b/annexePreuveStopping.tex @@ -1,381 +1,293 @@ -\section{Quantifier l'écart par rapport à la distribution uniforme} -%15 Rairo +L'objectif principal de cette section est de démontrer le théorème~\ref{theo:tmps:mix} rappelé en fin de section. - - - -Let thus be given such kind of map. -This article focuses on studying its iterations according to -the equation~(\ref{eq:asyn}) with a given strategy. -First of all, this can be interpreted as walking into its iteration graph -where the choice of the edge to follow is decided by the strategy. -Notice that the iteration graph is always a subgraph of -${\mathsf{N}}$-cube augmented with all the self-loop, \textit{i.e.}, all the -edges $(v,v)$ for any $v \in \Bool^{\mathsf{N}}$. -Next, if we add probabilities on the transition graph, iterations can be -interpreted as Markov chains. - -\begin{xpl} -Let us consider for instance -the graph $\Gamma(f)$ defined -in \textsc{Figure~\ref{fig:iteration:f*}.} and -the probability function $p$ defined on the set of edges as follows: -$$ -p(e) \left\{ -\begin{array}{ll} -= \frac{2}{3} \textrm{ if $e=(v,v)$ with $v \in \Bool^3$,}\\ -= \frac{1}{6} \textrm{ otherwise.} -\end{array} -\right. -$$ -The matrix $P$ of the Markov chain associated to the function $f^*$ and to its probability function $p$ is -\[ -P=\dfrac{1}{6} \left( -\begin{array}{llllllll} -4&1&1&0&0&0&0&0 \\ -1&4&0&0&0&1&0&0 \\ -0&0&4&1&0&0&1&0 \\ -0&1&1&4&0&0&0&0 \\ -1&0&0&0&4&0&1&0 \\ -0&0&0&0&1&4&0&1 \\ -0&0&0&0&1&0&4&1 \\ -0&0&0&1&0&1&0&4 -\end{array} -\right) -\] -\end{xpl} - - -% % Let us first recall the \emph{Total Variation} distance $\tv{\pi-\mu}$, -% % which is defined for two distributions $\pi$ and $\mu$ on the same set -% % $\Bool^n$ by: -% % $$\tv{\pi-\mu}=\max_{A\subset \Bool^n} |\pi(A)-\mu(A)|.$$ -% % It is known that -% % $$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$ - -% % Let then $M(x,\cdot)$ be the -% % distribution induced by the $x$-th row of $M$. If the Markov chain -% % induced by -% % $M$ has a stationary distribution $\pi$, then we define -% % $$d(t)=\max_{x\in\Bool^n}\tv{M^t(x,\cdot)-\pi}.$$ -% Intuitively $d(t)$ is the largest deviation between -% the distribution $\pi$ and $M^t(x,\cdot)$, which -% is the result of iterating $t$ times the function. -% Finally, let $\varepsilon$ be a positive number, the \emph{mixing time} -% with respect to $\varepsilon$ is given by -% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ -% It defines the smallest iteration number -% that is sufficient to obtain a deviation lesser than $\varepsilon$. -% Notice that the upper and lower bounds of mixing times cannot -% directly be computed with eigenvalues formulae as expressed -% in~\cite[Chap. 12]{LevinPeresWilmer2006}. The authors of this latter work -% only consider reversible Markov matrices whereas we do no restrict our -% matrices to such a form. - - - - - - - -This section considers functions $f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}} $ -issued from an hypercube where an Hamiltonian path has been removed. -A specific random walk in this modified hypercube is first -introduced. We further detail -a theoretical study on the length of the path -which is sufficient to follow to get a uniform distribution. -Notice that for a general references on Markov chains -see~\cite{LevinPeresWilmer2006} -, and particularly Chapter~5 on stopping times. - - - - -First of all, let $\pi$, $\mu$ be two distributions on $\Bool^{\mathsf{N}}$. The total -variation distance between $\pi$ and $\mu$ is denoted $\tv{\pi-\mu}$ and is -defined by -$$\tv{\pi-\mu}=\max_{A\subset \Bool^{\mathsf{N}}} |\pi(A)-\mu(A)|.$$ It is known that -$$\tv{\pi-\mu}=\frac{1}{2}\sum_{X\in\Bool^{\mathsf{N}}}|\pi(X)-\mu(X)|.$$ Moreover, if -$\nu$ is a distribution on $\Bool^{\mathsf{N}}$, one has -$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$ - -Let $P$ be the matrix of a Markov chain on $\Bool^{\mathsf{N}}$. $P(X,\cdot)$ is the -distribution induced by the $X$-th row of $P$. If the Markov chain induced by -$P$ has a stationary distribution $\pi$, then we define -$$d(t)=\max_{X\in\Bool^{\mathsf{N}}}\tv{P^t(X,\cdot)-\pi}.$$ - -and - -$$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ -One can prove that +Un résultat classique est $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ - - -% It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il -% un intérêt dans la preuve ensuite.} - - - -%and -% $$t_{\rm mix}(\varepsilon)=\min\{t \mid d(t)\leq \varepsilon\}.$$ -% One can prove that \JFc{Ou cela a-t-il été fait?} -% $$t_{\rm mix}(\varepsilon)\leq \lceil\log_2(\varepsilon^{-1})\rceil t_{\rm mix}(\frac{1}{4})$$ - - - -Let $(X_t)_{t\in \mathbb{N}}$ be a sequence of $\Bool^{\mathsf{N}}$ valued random -variables. A $\mathbb{N}$-valued random variable $\tau$ is a {\it stopping - time} for the sequence $(X_i)$ if for each $t$ there exists $B_t\subseteq -(\Bool^{\mathsf{N}})^{t+1}$ such that $\{\tau=t\}=\{(X_0,X_1,\ldots,X_t)\in B_t\}$. -In other words, the event $\{\tau = t \}$ only depends on the values of -$(X_0,X_1,\ldots,X_t)$, not on $X_k$ with $k > t$. +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$. -Let $(X_t)_{t\in \mathbb{N}}$ be a Markov chain and $f(X_{t-1},Z_t)$ a -random mapping representation of the Markov chain. A {\it randomized - stopping time} for the Markov chain is a stopping time for -$(Z_t)_{t\in\mathbb{N}}$. If the Markov chain is irreducible and has $\pi$ -as stationary distribution, then a {\it stationary time} $\tau$ is a -randomized stopping time (possibly depending on the starting position $X$), -such that the distribution of $X_\tau$ is $\pi$: +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$. -A stopping time $\tau$ is a {\emph strong stationary time} if $X_{\tau}$ is -independent of $\tau$. +On rappelle le théorème suivant~\cite[Proposition 6.10]{LevinPeresWilmer2006}. - -\begin{theorem} -If $\tau$ is a strong stationary time, then $d(t)\leq \max_{X\in\Bool^{\mathsf{N}}} +\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} -%Let $\Bool^n$ be the set of words of length $n$. -Let $E=\{(X,Y)\mid -X\in \Bool^{\mathsf{N}}, Y\in \Bool^{\mathsf{N}},\ X=Y \text{ or } X\oplus Y \in 0^*10^*\}$. -In other words, $E$ is the set of all the edges in the classical +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. -Let $h$ be a function from $\Bool^{\mathsf{N}}$ into $\llbracket 1, {\mathsf{N}} \rrbracket$. -Intuitively speaking $h$ aims at memorizing for each node -$X \in \Bool^{\mathsf{N}}$ which edge is removed in the Hamiltonian cycle, -\textit{i.e.} which bit in $\llbracket 1, {\mathsf{N}} \rrbracket$ -cannot be switched. +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é. -We denote by $E_h$ the set $E\setminus\{(X,Y)\mid X\oplus Y = -0^{{\mathsf{N}}-h(X)}10^{h(X)-1}\}$. This is the set of the modified hypercube, -\textit{i.e.}, the ${\mathsf{N}}$-cube where the Hamiltonian cycle $h$ -has been removed. +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é. -We define the Markov matrix $P_h$ for each line $X$ and -each column $Y$ as follows: +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{if $(X,Y)\notin E_h$}\\ -P_h(X,Y)=\frac{1}{2{\mathsf{N}}} & \textrm{if $X\neq Y$ and $(X,Y) \in E_h$} +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} -We denote by $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ the function -such that for any $X \in \Bool^{\mathsf{N}} $, -$(X,\ov{h}(X)) \in E$ and $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. -The function $\ov{h}$ is said {\it square-free} if for every $X\in \Bool^{\mathsf{N}}$, + + + + +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} -If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(X))\neq h(X)$. +Si $\ov{h}$ est bijective et anti-involutive, alors +$h(\ov{h}^{-1}(X))\neq h(X)$. \end{lemma} \begin{proof} -Let $\ov{h}$ be bijective. -Let $k\in \llbracket 1, {\mathsf{N}} \rrbracket$ s.t. $h(\ov{h}^{-1}(X))=k$. -Then $(\ov{h}^{-1}(X),X)$ belongs to $E$ and +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}$. -Let us suppose $h(X) = h(\ov{h}^{-1}(X))$. In such a case, $h(X) =k$. -By definition of $\ov{h}$, $(X, \ov{h}(X)) \in E $ and +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}$. -Thus $\ov{h}(X)= \ov{h}^{-1}(X)$, which leads to $\ov{h}(\ov{h}(X))= X$. -This contradicts the square-freeness of $\ov{h}$. +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} -Let $Z$ be a random variable that is uniformly distributed over -$\llbracket 1, {\mathsf{N}} \rrbracket \times \Bool$. -For $X\in \Bool^{\mathsf{N}}$, we -define, with $Z=(i,b)$, -$$ +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{if } b=1 \text{ and } i\neq h(X),\\ -f(X,Z)=X& \text{otherwise.} +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. -$$ +\] -The Markov chain is thus defined as -$$ -X_t= f(X_{t-1},Z_t) -$$ +La chaîne de Markov est ainsi définie par +\[ +X_t= f(X_{t-1},Z_t). +\] -%%%%%%%%%%%%%%%%%%%%%%%%%%%ù -%\section{Stopping time} -An integer $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ is said {\it fair} -at time $t$ if there -exists $0\leq j <t$ such that $Z_{j+1}=(\ell,\cdot)$ and $h(X_j)\neq \ell$. -In other words, there exist a date $j$ before $t$ where -the first element of the random variable $Z$ is exactly $l$ -(\textit{i.e.}, $l$ is the strategy at date $j$) -and where the configuration $X_j$ allows to traverse the edge $l$. +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$. -Let $\ts$ be the first time all the elements of $\llbracket 1, {\mathsf{N}} \rrbracket$ -are fair. The integer $\ts$ is a randomized stopping time for -the Markov chain $(X_t)$. +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} -The integer $\ts$ is a strong stationary time. +L'entier $\ts$ est un temps stationnaire fort. \end{lemma} \begin{proof} -Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable -$Z_{\tau_\ell}$ is of the form $(\ell,b)$ %with $\delta\in\{0,1\}$ and -such that -$b=1$ with probability $\frac{1}{2}$ and $b=0$ with probability -$\frac{1}{2}$. Since $h(X_{\tau_\ell-1})\neq\ell$ the value of the $\ell$-th -bit of $X_{\tau_\ell}$ -is $0$ or $1$ with the same probability ($\frac{1}{2}$). - - Moving next in the chain, at each step, -the $l$-th bit is switched from $0$ to $1$ or from $1$ to $0$ each time with -the same probability. Therefore, for $t\geq \tau_\ell$, the -$\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the -lemma.\end{proof} - -\begin{theorem} \label{prop:stop} -If $\ov{h}$ is bijective and square-free, then -$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. -\end{theorem} +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} + -For each $X\in \Bool^{\mathsf{N}}$ and $\ell\in\llbracket 1,{\mathsf{N}}\rrbracket$, -let $S_{X,\ell}$ be the -random variable that counts the number of steps -from $X$ until we reach a configuration where -$\ell$ is fair. More formally -$$S_{X,\ell}=\min \{t \geq 1\mid h(X_{t-1})\neq \ell\text{ and }Z_t=(\ell,.)\text{ and } X_0=X\}.$$ -% We denote by -% $$\lambda_h=\max_{X,\ell} S_{X,\ell}.$$ + + + + +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} -Let $\ov{h}$ is a square-free bijective function. Then -for all $X$ and -all $\ell$, -the inequality -$E[S_{X,\ell}]\leq 8{\mathsf{N}}^2$ is established. +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} -For every $X$, every $\ell$, one has $\P(S_{X,\ell})\leq 2)\geq -\frac{1}{4{\mathsf{N}}^2}$. -Let $X_0= X$. -Indeed, +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 if $h(X)\neq \ell$, then +\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 otherwise, $h(X)=\ell$, then -$\P(S_{X,\ell}=1)=0$. -But in this case, intuitively, it is possible to move -from $X$ to $\ov{h}^{-1}(X)$ (with probability $\frac{1}{2N}$). And in -$\ov{h}^{-1}(X)$ the $l$-th bit can be switched. -More formally, -since $\ov{h}$ is square-free, -$\ov{h}(X)=\ov{h}(\ov{h}(\ov{h}^{-1}(X)))\neq \ov{h}^{-1}(X)$. It follows -that $(X,\ov{h}^{-1}(X))\in E_h$. We thus have -$P(X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$. Now, by Lemma~\ref{lm:h}, -$h(\ov{h}^{-1}(X))\neq h(X)$. Therefore $\P(S_{x,\ell}=2\mid -X_1=\ov{h}^{-1}(X))=\frac{1}{2{\mathsf{N}}}$, proving that $\P(S_{x,\ell}\leq 2)\geq +\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} -Therefore, $\P(S_{X,\ell}\geq 3)\leq 1-\frac{1}{4{\mathsf{N}}^2}$. By induction, one -has, for every $i$, $\P(S_{X,\ell}\geq 2i)\leq +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$. - Moreover, -since $S_{X,\ell}$ is positive, it is known~\cite[lemma 2.9]{proba}, that -$$E[S_{X,\ell}]=\sum_{i=1}^{+\infty}\P(S_{X,\ell}\geq i).$$ -Since $\P(S_{X,\ell}\geq i)\geq \P(S_{X,\ell}\geq i+1)$, one has -$$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).$$ -Consequently, +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,$$ -which concludes the proof. +ce qui conclut la preuve du lemme. \end{proof} -Let $\ts^\prime$ be the time used to get all the bits but one fair. +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} -One has $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{N}}+1).$ +On a $E[\ts^\prime]\leq 4{\mathsf{N}} \ln ({\mathsf{N}}+1).$ \end{lemma} \begin{proof} -This is a classical Coupon Collector's like problem. Let $W_i$ be the -random variable counting the number of moves done in the Markov chain while -we had exactly $i-1$ fair bits. One has $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}-1}W_i$. - But when we are at position $X$ with $i-1$ fair bits, the probability of - obtaining a new fair bit is either $1-\frac{i-1}{{\mathsf{N}}}$ if $h(X)$ is fair, - or $1-\frac{i-2}{{\mathsf{N}}}$ if $h(X)$ is not fair. - -Therefore, +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}}}.$ -Consequently, we have $\P(W_i\geq k)\leq \left(\frac{i-1}{{\mathsf{N}}}\right)^{k-1} \frac{{\mathsf{N}}-i+2}{{\mathsf{N}}-i+1}.$ -It follows that $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}$. - - +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 -It follows that -$E[W_i]\leq \frac{4{\mathsf{N}}}{{\mathsf{N}}-i+2}$. Therefore -$$E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]\leq +\[ +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}.$$ +4{\mathsf{N}}\sum_{i=3}^{{\mathsf{N}}+1}\frac{1}{i}.\] -But $\sum_{i=1}^{{\mathsf{N}}+1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}+1)$. It follows that +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).$ -Consequently, -$E[\ts^\prime]\leq +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)$. +4{\mathsf{N}}\ln({\mathsf{N}}+1), +\] +ce qui termine la preuve du lemme. \end{proof} -One can now prove Theorem~\ref{prop:stop}. - +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} -Since $\ts^\prime$ is the time used to obtain $\mathsf{N}-1$ fair bits. -Assume that the last unfair bit is $\ell$. One has -$\ts=\ts^\prime+S_{X_\tau,\ell}$, and therefore -$E[\ts] = E[\ts^\prime]+E[S_{X_\tau,\ell}]$. Therefore, -Theorem~\ref{prop:stop} is a direct application of -lemma~\ref{prop:lambda} and~\ref{lm:stopprime}. +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} -Notice that the calculus of the stationary time upper bound is obtained -under the following constraint: for each vertex in the $\mathsf{N}$-cube -there are one ongoing arc and one outgoing arc that are removed. -The calculus does not consider (balanced) Hamiltonian cycles, which -are more regular and more binding than this constraint. -In this later context, we claim that the upper bound for the stopping time -should be reduced. +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}