-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$.
- 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).$
-Consequently,
-$E[\ts^\prime]\leq n (-\frac{1}{2}+\ln(n+1))\leq n\ln(n+1)$.
+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}
+$$
+
+
+It is well known that
+$\sum_{i=1}^{{\mathsf{N}}-1}\frac{1}{i}\leq 1+\ln({\mathsf{N}}-1)$.
+It follows that
+$2+(\mathsf{N}+2)\sum_{i=1}^{{\mathsf{N}}-1}\frac{1}{i}
+\leq
+2+(\mathsf{N}+2)(\ln(\mathsf{N}-1)+1)
+\leq
+(\mathsf{N}+2)(\ln(\mathsf{N})+2)$.
