= Solution
Let $S$ be the number of red vertices in $W$. It has a <binomial distribution> with parameters $r$ and $1/2$, so <independence> gives
$$
\mathbb E e^{t(S-r/2)}=\left(\cosh(t/2)\right)^r.
$$
For $t=1$, the strict inequality $\log\cosh(1/2)<1/8$ follows by integrating $\tanh u<u$ for $u>0$. Hence the <exponential Markov bound> yields
$$
\mathbb P(S>3r/4)
\leq e^{-r/4}\left(\cosh(1/2)\right)^r
<e^{-r/4+r/8}.
$$
Therefore
$$
\boxed{\mathbb P(S>3r/4)<e^{-r/8}.}
$$
This supplies the tail estimate directly, including the strict constant in the requested bound.
Back to article page
