Consider a problem over the inputs \mathcal{X}, and let \mathcal{A} be the set of all possible deterministic algorithms that correctly solve the problem.
i.e., the worst-case expected cost of the randomized algorithm is at least the cost of the best deterministic algorithm against input distribution q.