My question is somewhat the converse of this one. Basically, I want to proof that in the Miller-Rabin test the probability of passing the test given that the number n being test is not prime is bounded by $\frac{1}{4^k}$.
I found a proof in this Rabin's paper but I would like to simplify it. So you may assume the following theorem:
If more than a quarter of $b \in \mathbb{Z}_{n}^{*}$ pass Miller-Rabin test then all $b \in \mathbb{Z}_{n}^{*}$ do so.
How can I deduce the previous bound from this statement?
The theorem guarantees that at most $\frac{1}{4}$ of the bases coprime to the number $n$ (which has to be tested) pass the Miller-Rabin-test.
So, if we choose a random base, the probability that it passes the test, is at most $\frac{1}{4}$.
If we choose a random base $k$ times and the choices are independent, the probability is $p^k$, where $p$ is the probability that a single ranom base passes the test.
Since $p\le \frac{1}{4}$, we can conclude $p^k\le(\frac{1}{4})^k$.