-This is a classical Coupon Collector's like problem. Let $W_i$
-be the time to obtain the $i$-th fair bit
-after $i-1$ fair bits have been obtained.
-One has $\ts^\prime=\sum_{i=1}^{{\mathsf{N}}}W_i$.
-
-At position $X$ with $i-1$ fair bits,
-we do not obtain a new fair if $Z$ is one of the $i-1$ already fair bits
-or if $Z$ is a new fair bit but $h(X)$ is $Z$.
-This occurs with probability
-$p
-= \frac{i-1}{{\mathsf{N}}} + \frac{n-i+1}{\mathsf{N}}.\frac{1}{\mathsf{N}}
-=\frac{i(\mathsf{N}-1) +1}{\mathsf{N^2}}
-$.
-The random variable $W_i$ has a geometric distribution
-\textit{i.e.}, $P(W_i = k) = p^{k-1}.(1-p)$ and
-$E(W_i) = \frac{\mathsf{N^2}}{i(\mathsf{N}-1) +1}$.
-Therefore
-$$E[\ts^\prime]=\sum_{i=1}^{{\mathsf{N}}}E[W_i]
-=\frac{\mathsf{N^2}}{\mathsf{N}(\mathsf{N}-1) +1} + \sum_{i=1}^{{\mathsf{N}}-1}E[W_i].$$
-
-A simple study of the function $\mathsf{N} \mapsto \frac{\mathsf{N^2}}{\mathsf{N}(\mathsf{N}-1) +1}$ shows that it is bounded by $\frac{4}{3} \leq 2$.
-For the second term, we successively have
-$$
-\sum_{i=1}^{{\mathsf{N}}-1}E[W_i]
-= \mathsf{N}^2\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i(\mathsf{N}-1) +1}
-\leq \mathsf{N}^2\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i(\mathsf{N}-1)}
-\leq \frac{\mathsf{N}^2}{\mathsf{N}-1}\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i}
-\leq (\mathsf{N}+2)\sum_{i=1}^{{\mathsf{N}}-1} \frac{1}{i}
-$$
+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,
+$\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}$.
+
