relecture preuve PCH

diff --git a/main.tex b/main.tex
index e10eba456a5520422f238028edb80ec5b5d1c85f..bc8bb20d3a3da600c918d1554c1b22b5e2385cf7 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -126,7 +126,7 @@ may be  updated at each iteration.   At the theoretical level,  we show that
 
 
 
 
 
 

-\section{Stopping Time}
+\section{Random walk on the modified Hypercube}

 \input{stopping}
 
 % Donner la borne du stopping time quand on marche dedans (nouveau). 
 \input{stopping}
 
 % Donner la borne du stopping time quand on marche dedans (nouveau). 

diff --git a/preliminaries.tex b/preliminaries.tex
index de77e127eb5f560c4805cfc970b5cf3769c6c250..9441aab3a586ced9fb98b0b7d799c13e24d4ffed 100644 (file)
--- a/preliminaries.tex
+++ b/preliminaries.tex
@@ -94,57 +94,6 @@ P=\dfrac{1}{6} \left(
 \end{xpl}
 
 
 \end{xpl}
 
 

-
-More generally, let $\pi$, $\mu$ be two distribution on $\Bool^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^n} |\pi(A)-\mu(A)|.$$ It is known that
-$$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$ Moreover, if
-$\nu$ is a distribution on $\Bool^n$, one has
-$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$
-
-Let $P$ be the matrix of a Markov chain on $\Bool^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^n}\tv{P^t(x,\cdot)-\pi}.$$
-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^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
-\Omega^{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$. 
- 
-
-\JFC{Je ne comprends pas la definition de randomized stopping time, Peut-on enrichir ?}
-
-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$:
-$$\P_x(X_\tau=y)=\pi(y).$$
-
-
-\JFC{Ou ceci a-t-il ete prouvé}
-\begin{Theo}
-If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Bool^n}
-\P_x(\tau > t)$.
-\end{Theo}
-

 % % 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:
 % % 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:

diff --git a/stopping.tex b/stopping.tex
index 0a1dbe2dde19eaed5bab16445498ff21313703da..9309221a592846aff32ea71ea94b62ac3fcd632e 100644 (file)
--- a/stopping.tex
+++ b/stopping.tex
@@ -1,36 +1,98 @@
+This section considers functions $f: \Bool^n \rightarrow \Bool^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.
+ 
+
+
+
+
+First of all, let $\pi$, $\mu$ be two distributions on $\Bool^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^n} |\pi(A)-\mu(A)|.$$ It is known that
+$$\tv{\pi-\mu}=\frac{1}{2}\sum_{x\in\Bool^n}|\pi(x)-\mu(x)|.$$ Moreover, if
+$\nu$ is a distribution on $\Bool^n$, one has
+$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}$$

 
 

+Let $P$ be the matrix of a Markov chain on $\Bool^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^n}\tv{P^t(x,\cdot)-\pi}.$$
+It is known that $d(t+1)\leq d(t)$. \JFC{references ? Cela a-t-il 
+un intérêt dans la preuve ensuite.}

 
 

-%% A {\it coupling} with transition matrix $P$ is a process $(X_t,Y_t)_{t\geq 0}$
-%% such that both $(X_t)$ and $(Y_t)$ are markov chains of matric $P$; moreover
-%% it is required that if $X_s=Y_s$, then for any $t\geq s$, $X_t=Y_t$.
-%% A results provides that if   $(X_t,Y_t)_{t\geq 0}$ is a coupling, then
-%% $$d(t)\leq \max_{x,y} P_{x,y}(\{\tau_{\rm couple} \geq t\}),$$
-%% with $\tau_{\rm couple}=\min_t\{X_t=Y_t\}$.

 
 
 
 

-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Random walk on the modified Hypercube}
+%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^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^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$. 
+ 
+
+\JFC{Je ne comprends pas la definition de randomized stopping time, Peut-on enrichir ?}
+
+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$:
+$$\P_x(X_\tau=y)=\pi(y).$$
+
+
+\JFC{Ou ceci a-t-il ete prouvé}
+\begin{Theo}
+If $\tau$ is a strong stationary time, then $d(t)\leq \max_{x\in\Bool^n}
+\P_x(\tau > t)$.
+\end{Theo}
+
+
+%Let $\Bool^n$ be the set of words of length $n$. 
+Let $E=\{(x,y)\mid
+x\in \Bool^n, y\in \Bool^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 
+$n$-cube. 
+Let $h$ be a function from $\Bool^n$ into $\llbracket 1, n \rrbracket$.
+Intuitively speaking $h$ aims at memorizing for each node 
+$x \in \Bool^n$ which edge is removed in the Hamiltonian cycle,
+\textit{i.e.} which bit in $\llbracket 1, n \rrbracket$ 
+cannot be switched.

 
 
 
 

-Let $\Omega=\{0,1\}^N$ be the set of words of length $N$. Let $E=\{(x,y)\mid
-x\in \Omega, y\in \Omega,\ x=y \text{ or } x\oplus y \in 0^*10^*\}$. Let $h$
-be a function from $\Omega$ into $\{1,\ldots,N\}$.

 
 We denote by $E_h$ the set $E\setminus\{(x,y)\mid x\oplus y =
 
 We denote by $E_h$ the set $E\setminus\{(x,y)\mid x\oplus y =

-0^{N-h(x)}10^{h(x)-1}\}$. We define the matrix $P_h$ has follows:
+0^{n-h(x)}10^{h(x)-1}\}$. This is the set of the modified hypercube, 
+\textit{i.e.}, the $n$-cube where the Hamiltonian cycle $h$ 
+has been removed.
+
+We define the Markov matrix $P_h$ for each line $x$ and 
+each column $y$  as follows:

 $$\left\{
 \begin{array}{ll}
 $$\left\{
 \begin{array}{ll}

-P_h(x,y)=0 & \text{ if } (x,y)\notin E_h\\
-P_h(x,x)=\frac{1}{2}+\frac{1}{2N} & \\
-P_h(x,x)=\frac{1}{2N} & \text{otherwise}\\
-
+P_h(x,x)=\frac{1}{2}+\frac{1}{2n} & \\
+P_h(x,y)=0 & \textrm{if  $(x,y)\notin E_h$}\\
+P_h(x,y)=\frac{1}{2n} & \textrm{if $x\neq y$ and $(x,y) \in E_h$}

 \end{array}
 \right.
 $$ 
 
 \end{array}
 \right.
 $$ 
 

-We denote by $\ov{h}$ the function from $\Omega$ into $\omega$ defined
-by $x\oplus\ov{h}(x)=0^{N-h(x)}10^{h(x)-1}.$ 
-The function $\ov{h}$ is said {\it square-free} if for every $x\in E$,
+We denote by $\ov{h} : \Bool^n \rightarrow \Bool^n$ the function 
+such that for any $x \in \Bool^n $, 
+$(x,\ov{h}(x)) \in E$ and $x\oplus\ov{h}(x)=0^{n-h(x)}10^{h(x)-1}$. 
+The function $\ov{h}$ is said {\it square-free} if for every $x\in \Bool^n$,

 $\ov{h}(\ov{h}(x))\neq x$. 
 
 \begin{Lemma}\label{lm:h}
 $\ov{h}(\ov{h}(x))\neq x$. 
 
 \begin{Lemma}\label{lm:h}


@@ -38,16 +100,17 @@ If $\ov{h}$ is bijective and square-free, then $h(\ov{h}^{-1}(x))\neq h(x)$.
 \end{Lemma}
 
 \begin{Proof}
 \end{Lemma}
 
 \begin{Proof}

-
+\JFC{ecrire la preuve}

 \end{Proof}
 
 Let $Z$ be a random variable over
 \end{Proof}
 
 Let $Z$ be a random variable over

-$\{1,\ldots,N\}\times\{0,1\}$ uniformaly distributed. For $X\in \Omega$, we
+$\llbracket 1, n \rrbracket \times\{0,1\}$ uniformly distributed.
+ For $X\in \Bool^n$, we

 define, with $Z=(i,x)$,  
 $$
 \left\{
 \begin{array}{ll}
 define, with $Z=(i,x)$,  
 $$
 \left\{
 \begin{array}{ll}

-f(X,Z)=X\oplus (0^{N-i}10^{i-1}) & \text{if } x=1 \text{ and } i\neq h(X),\\
+f(X,Z)=X\oplus (0^{n-i}10^{i-1}) & \text{if } x=1 \text{ and } i\neq h(X),\\

 f(X,Z)=X& \text{otherwise.} 
 \end{array}\right.
 $$
 f(X,Z)=X& \text{otherwise.} 
 \end{array}\right.
 $$


@@ -60,17 +123,17 @@ The pair $f,Z$ is a random mapping representation of $P_h$.
 %%%%%%%%%%%%%%%%%%%%%%%%%%%ù
 \section{Stopping time}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%ù
 \section{Stopping time}
 

-An integer $\ell\in\{1,\ldots,N\}$ is said {\it fair} at time $t$ if there
+An integer $\ell\in\{1,\ldots,n\}$ is said {\it fair} at time $t$ if there

 exists $0\leq j <t$ such that $Z_j=(\ell,\cdot)$ and $h(X_j)\neq \ell$.
 
  
 exists $0\leq j <t$ such that $Z_j=(\ell,\cdot)$ and $h(X_j)\neq \ell$.
 
  

-Let $\ts$ be the first time all the elements of $\{1,\ldots,N\}$
+Let $\ts$ be the first time all the elements of $\{1,\ldots,n\}$

 are fair. The integer $\ts$ is a randomized stopping time for
 are fair. The integer $\ts$ is a randomized stopping time for

-the markov chain $(X_t)$.
+the Markov chain $(X_t)$.

 
 
 \begin{Lemma}
 
 
 \begin{Lemma}

-The integer $\ts$ is a strong stationnary time.
+The integer $\ts$ is a strong stationary time.

 \end{Lemma}
 
 \begin{proof}
 \end{Lemma}
 
 \begin{proof}


@@ -78,19 +141,19 @@ Let $\tau_\ell$ be the first time that $\ell$ is fair. The random variable
 $Z_{\tau_\ell-1}$ is of the form $(\ell,\delta)$ with $\delta\in\{0,1\}$ and
 $\delta=1$ with probability $\frac{1}{2}$ and $\delta=0$ with probability
 $\frac{1}{2}$. Since $h(X_{\tau_\ell-1})\neq\ell$ the value of the $\ell$-th
 $Z_{\tau_\ell-1}$ is of the form $(\ell,\delta)$ with $\delta\in\{0,1\}$ and
 $\delta=1$ with probability $\frac{1}{2}$ and $\delta=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 $\delta$. By symetry, for $t\geq \tau_\ell$, the
+bit of $X_{\tau_\ell}$ is $\delta$. By symmetry, 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{Theo} \label{prop:stop}
 If $\ov{h}$ is bijective and square-free, then
 $\ell$-th bit of $X_t$ is $0$ or $1$ with the same probability, proving the
 lemma.
 \end{proof}
 
 \begin{Theo} \label{prop:stop}
 If $\ov{h}$ is bijective and square-free, then

-$E[\ts]\leq 8N^2+ N\ln (N+1)$. 
+$E[\ts]\leq 8n^2+ n\ln (n+1)$. 

 \end{Theo}
 
 \end{Theo}
 

-For each $x\in \Omega$ and $\ell\in\{1,\ldots,N\}$, let $S_{x,\ell}$ be the
+For each $x\in \Bool^n$ and $\ell\in\{1,\ldots,n\}$, let $S_{x,\ell}$ be the

 random variable counting the number of steps done until reaching from $x$ a state where
 random variable counting the number of steps done until reaching from $x$ a state where

-$\ell$ is fair. More formaly
+$\ell$ is fair. More formally

 $$S_{x,\ell}=\min \{m \geq 1\mid h(X_m)\neq \ell\text{ and }Z_m=\ell\text{ and } X_0=x\}.$$
 
  We denote by
 $$S_{x,\ell}=\min \{m \geq 1\mid h(X_m)\neq \ell\text{ and }Z_m=\ell\text{ and } X_0=x\}.$$
 
  We denote by


@@ -98,23 +161,23 @@ $$\lambda_h=\max_{x,\ell} S_{x,\ell}.$$
 
 
 \begin{Lemma}\label{prop:lambda}
 
 
 \begin{Lemma}\label{prop:lambda}

-If $\ov{h}$ is a square-free bijective function, then one has $E[\lambda_h]\leq 8N^2.$
+If $\ov{h}$ is a square-free bijective function, then one has $E[\lambda_h]\leq 8n^2.$

 \end{Lemma}
 
 \begin{proof}
 \end{Lemma}
 
 \begin{proof}

-For evey $x$, every $\ell$, one has $\P(S_{x,\ell})\leq 2)\geq
-\frac{1}{4N^2}$. Indeed, if $h(x)\neq \ell$, then
-$\P(S_{x,\ell}=1)=\frac{1}{2N}\geq \frac{1}{4N^2}$. If $h(x)=\ell$, then
+For every $x$, every $\ell$, one has $\P(S_{x,\ell})\leq 2)\geq
+\frac{1}{4n^2}$. Indeed, if $h(x)\neq \ell$, then
+$\P(S_{x,\ell}=1)=\frac{1}{2n}\geq \frac{1}{4n^2}$. If $h(x)=\ell$, then

 $\P(S_{x,\ell}=1)=0$. Let $X_0=x$. Since $\ov{h}$ is square-free,
 $\ov{h}(\ov{h}^{-1}(x))\neq x$. It follows that $(x,\ov{h}^{-1}(x))\in E_h$.
 $\P(S_{x,\ell}=1)=0$. Let $X_0=x$. Since $\ov{h}$ is square-free,
 $\ov{h}(\ov{h}^{-1}(x))\neq x$. It follows that $(x,\ov{h}^{-1}(x))\in E_h$.

-Thefore $P(X_1=\ov{h}^{-1}(x))=\frac{1}{2N}$. Now, 
+Therefore $P(X_1=\ov{h}^{-1}(x))=\frac{1}{2n}$. now, 

 by Lemma~\ref{lm:h},  $h(\ov{h}^{-1}(x))\neq h(x)$. Therefore 
 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}{2N}$, proving that
-$\P(S_{x,\ell}\leq 2)\geq \frac{1}{4N^2}$.
+$\P(S_{x,\ell}=2\mid X_1=\ov{h}^{-1}(x))=\frac{1}{2n}$, proving that
+$\P(S_{x,\ell}\leq 2)\geq \frac{1}{4n^2}$.

 
 

-Therefore, $\P(S_{x,\ell}\geq 2)\leq 1-\frac{1}{4N^2}$. By induction, one
+Therefore, $\P(S_{x,\ell}\geq 2)\leq 1-\frac{1}{4n^2}$. By induction, one

 has, for every $i$, $\P(S_{x,\ell}\geq 2i)\leq
 has, for every $i$, $\P(S_{x,\ell}\geq 2i)\leq

-\left(1-\frac{1}{4N^2}\right)^i$.
+\left(1-\frac{1}{4n^2}\right)^i$.

  Moreover,
 since $S_{x,\ell}$ is positive, it is known~\cite[lemma 2.9]{}, that
 $$E[S_{x,\ell}]=\sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq i).$$
  Moreover,
 since $S_{x,\ell}$ is positive, it is known~\cite[lemma 2.9]{}, that
 $$E[S_{x,\ell}]=\sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq i).$$


@@ -123,32 +186,32 @@ $$E[S_{x,\ell}]=\sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq i)\leq
 \P(S_{x,\ell}\geq 1)+2 \sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq 2i).$$
 Consequently,
 $$E[S_{x,\ell}]\leq 1+2
 \P(S_{x,\ell}\geq 1)+2 \sum_{i=1}^{+\infty}\P(S_{x,\ell}\geq 2i).$$
 Consequently,
 $$E[S_{x,\ell}]\leq 1+2

-\sum_{i=1}^{+\infty}\left(1-\frac{1}{4N^2}\right)^i=1+2(4N^2-1)=8N^2-2,$$
+\sum_{i=1}^{+\infty}\left(1-\frac{1}{4n^2}\right)^i=1+2(4n^2-1)=8n^2-2,$$

 which concludes the proof.
 \end{proof}
 
 which concludes the proof.
 \end{proof}
 

-Let $\ts^\prime$ be the first time that there are exactly $N-1$ fair
+Let $\ts^\prime$ be the first time that there are exactly $n-1$ fair

 elements. 
 
 \begin{Lemma}\label{lm:stopprime}
 elements. 
 
 \begin{Lemma}\label{lm:stopprime}

-One has $E[\ts^\prime]\leq N \ln (N+1).$
+One has $E[\ts^\prime]\leq n \ln (n+1).$

 \end{Lemma}
 
 \begin{proof}
 This is a classical  Coupon Collector's like problem. Let $W_i$ be the
 \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}^{N-1}W_i$.
+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}^{n-1}W_i$.

  But when we are at position $x$ with $i-1$ fair bits, the probability of
  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}{N}$ if $h(x)$ is fair,
- or  $1-\frac{i-2}{N}$ if $h(x)$ is not fair. It follows that 
-$E[W_i]\leq \frac{N}{N-i+2}$. Therefore
-$$E[\ts^\prime]=\sum_{i=1}^{N-1}E[W_i]\leq N\sum_{i=1}^{N-1}
- \frac{1}{N-i+2}=N\sum_{i=3}^{N+1}\frac{1}{i}.$$
-
-But $\sum_{i=1}^{N+1}\frac{1}{i}\leq 1+\ln(N+1)$. It follows that
-$1+\frac{1}{2}+\sum_{i=3}^{N+1}\frac{1}{i}\leq 1+\ln(N+1).$
+ obtaining a new fair bit is either $1-\frac{i-1}{n}$ if $h(x)$ is fair,
+ or  $1-\frac{i-2}{n}$ if $h(x)$ is not fair. It follows that 
+$E[W_i]\leq \frac{n}{n-i+2}$. Therefore
+$$E[\ts^\prime]=\sum_{i=1}^{n-1}E[W_i]\leq n\sum_{i=1}^{n-1}
+ \frac{1}{n-i+2}=n\sum_{i=3}^{n+1}\frac{1}{i}.$$
+
+But $\sum_{i=1}^{n+1}\frac{1}{i}\leq 1+\ln(n+1)$. It follows that
+$1+\frac{1}{2}+\sum_{i=3}^{n+1}\frac{1}{i}\leq 1+\ln(n+1).$

 Consequently,
 Consequently,

-$E[\ts^\prime]\leq N (-\frac{1}{2}+\ln(N+1))\leq N\ln(N+1)$.
+$E[\ts^\prime]\leq n (-\frac{1}{2}+\ln(n+1))\leq n\ln(n+1)$.

 \end{proof}
 
 One can now prove Theo~\ref{prop:stop}.
 \end{proof}
 
 One can now prove Theo~\ref{prop:stop}.