# Randomized Algorithm with random input

As per the Yao's principle, in order to lower bound the cost of Randomized algorithm it suffices to find an appropriate distribution of difficult inputs, and to prove that no deterministic algorithm can perform well against that distribution.

Suppose we have a boolean function $f:\{0,1\}^n \rightarrow \{0,1\}$ and we are given a distribution over the inputs. I would like to ask whether I can apply Yao's principle when there is already some distribution given over inputs? If yes, then how?

I was reading the paper by Scott Aaronson and could not understand why he simply stated that by Yao's principle we can assume that algorithm is deterministic while there was already a distribution given over the inputs.

• If a randomized algorithm succeeds on a fixed input distribution with probability $p$, then there exists a deterministic algorithm that succeeds with probability $p$ as well. This is a trivial fact that is nothing more than averaging and I would not call it Yao's principle. Dec 10 '14 at 23:33