I am interested in proving lower bounds for AM-like languages. The usual techniques for lower bounds in non-probabilistic machines don't work for probabilistic machines.
Intuitively, when I think about showing lower bounds I usually think about showing for any algorithm $A$ some "bad input" that would contradict either its correctness or would take more time than the bound we want to show. But for randomized algorithms, a "bad input" for $A$ might still be correct and within the time bound, but only with some probability. This confuses me on how I should approach proving such lower bounds, as it looks much harder to show that the "bad input" is "bad" with high probability, and not only "bad" for one specific coin toss.
I would be glad if you could give me an example of a language with such a lower bound, and how to prove it.