DETAILS FOR THE PROOF OF CLAIM 2.5.2.1

Recall that we have $E[s(X_n)]=0.5+\e$,
and we seek to prove that $Prob[s(X_n)\geq 0.5+\e/2] > \e$.

A DIRECT PROOF (which makes no explicit use of Markov's Inequality,
but includes its underlying logic in the analysis) 
proceeds by noting that $s(X_n) \leq 1$ and so $E[s(X_n)]=0.5+\e$
yields $p\cdot1 + (1-p)\cdot(0.5+\e/2) \geq 0.5+\e$,
where $p\eqdef Prob[s(X_n)\geq 0.5+\e/2]$.
So we get $(1-(0.5+\e/2))\cdot p \geq 0.5+\e - (0.5+\e/2)$,
and $p \geq \frac{\e/2}{0.5-\e/2} > \e$ follows. 

AN INDIRECT PROOF (which uses Markov's Inequality)
proceeds by setting $Z=1-s(X_n)$ and noting that
we seek a lower bound on $Prob[Z \leq 0.5-\e/2]\geq Prob[Z < 0.5-\e/2]$.
Note that $Z\geq0$ and $E[Z]=0.5-\e$. 
Applying Markov's Inequality we get
$$Prob[Z \geq 0.5-\e/2] \leq \frac{0.5-\e}{0.5-\e/2}
  = 1-\frac{\e/2}{0.5-\e/2} < 1-\e$$