First, we prove the above inequality for the probability measure ${\mathbb P_n}$ on the set $\mathcal A^n$ of words with length $n$. The idea is that the number of the runs of “$a$” in a random word with length $n$ is highly concentrated around $n/4$ and that it is easy to estimate the maximum of $n/4$ independent geometrical random variables.

Note that $M_n \ge M_n^a$. Using (\[EQruns\]) and lemma \[Nn\] with $\gamma=1$, we have: $$\begin{aligned}
&& {\mathbb P_n}(M_n \leq y ) \\
& \leq  & {\mathbb P_n}(M_n^a \leq y ) \\
& \leq  & {\mathbb P_n}\left( N_n \leq  \frac{n}{2} \left(
1-n^{-\frac12+\varepsilon} \right)
\right)
+ {\mathbb P_n}\left( X_i \leq y , \; 1 \le i \le  \frac{n}{4} \left(
1-n^{-\frac12+\varepsilon} \right) \right)    \\
& \leq & {\mathbb P_n}\left( N_n \leq  \frac{n}{2} \left(
1-n^{-1/2+\varepsilon} \right)
\right)
+ {\mathbb P_n}\left(Z_i \leq y, \;  1 \le i \le  \frac{n}{4} \left(
1-n^{-\frac12+\varepsilon} \right)  \right) \\
& \leq &  O \left( \exp \left( -C_1 n^{2\varepsilon}
  \right) \right) + (1-2^{\lfloor -y \rfloor})^{\lfloor \frac{n}{4} \left(
1-n^{-1/2+\varepsilon}  \right) \rfloor }
.\end{aligned}$$ To lighten notations, we consider the $\frac{n}{4} \left(
1-n^{-\frac12+\varepsilon} \right)$ first $Z_i$’s rather than the $Z_i$’s corresponding to runs of “$a$”, which would have obliged us to distinguish whether 