How did we arrive at this form of Markov's Inequality in this proof?

62 Views Asked by At

In the book I am reading (complexity and cryptography by Talbot and Welsh, chapter 4), there is a proposition on $\textbf{ZPP}$($ \textbf{ZPP} = \textbf{RP} \cap \textbf{coRP}$-proposition $4.13$), page 80, where I don't understand the following:

By Markov's Inequality:

we know that the probability that any random variable exceeds twice its expected value is at most $\frac {1}{2}$. Thus if $x \in L$ then

$$Pr[\text{M accepts $x$ in time at most 2p(n)}] \ge \frac {1}{2}$$