<p>As you said, it is enough to point out a distribution (this could be any distribution) on which every deterministic algorithm fails. Now, if there is already a distribution given, and you can show that any deterministic algorithm fails on this one, then this provides also a lower bound for randomized algorithms. You can use any distribution in order to apply Yao's principle.  </p>

CC BY-SA 3.0
2014-12-10T21:20:58.150Z
2014-12-10T21:20:58.150Z
Chris
<p>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.</p>

<p>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?</p>

<p>I was reading the <a href="http://www.scottaaronson.com/papers/bqpph.pdf" rel="nofollow">paper</a> 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.</p>

CC BY-SA 3.0
2014-12-10T23:33:34.877Z
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.
Sasho Nikolov
<cc.complexity-theory><complexity-classes><boolean-functions><randomized-algorithms>
Randomized Algorithm with random input
hardik24
# Randomized Algorithm with random input

(Asked by: username_0 on 2014-12-10)

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](http://www.scottaaronson.com/papers/bqpph.pdf) 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.

**Tags:** cc.complexity-theory, complexity-classes, boolean-functions, randomized-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2014-12-10. Score: 1

As you said, it is enough to point out a distribution (this could be any distribution) on which every deterministic algorithm fails. Now, if there is already a distribution given, and you can show that any deterministic algorithm fails on this one, then this provides also a lower bound for randomized algorithms. You can use any distribution in order to apply Yao's principle.


---

