<p>First, to be precise in your problem statement, we probably are promised that $A$ has at least one index $i$ with $A[i] = 1$.</p>

<p>We want to show that no randomized algorithm can guarantee better than $\Omega(n)$ expected number of queries. In other words, we want to show that for any randomized algorithm, on its worst-case input, it requires $\Omega(n)$ queries.</p>

<p>By the minimax principle, the expected number of steps required by any randomized algorithm on its worst-case input is lower-bounded by the following: for any distribution $D$ on inputs, the expected number of steps of the best deterministic algorithm against that distribution.</p>

<p>Make sure that the preceding paragraph makes sense. <em>Any randomized algorithm against its worst-case input has poorer performance than any randomized input distribution against its best-case deterministic algorithm.</em></p>

<p>So now we have two steps: First, construct a distribution $D$ on inputs; and second, show that the best deterministic algorithm takes $\Omega(n)$ steps in expectation against that distribution.</p>

<p>The nice thing about the argument is that any such $D$ will give you some lower bound. For instance, the distribution on $A$ where $A = (1,0,0,0,...)$ every time is a distribution on inputs. But, the best deterministic algorithm against this distribution just checks the first coordinate first, and always finds a $1$ there, so this gives a lower bound of $1$ query -- pretty terrible.</p>

<p>Another distribution would have $A = (1,0,0,...)$ with probability $0.5$ and $A = (0,1,0,0,...)$ with probability $0.5$. Here, the best any deterministic algorithm can do is either check the first position first and then the second, or check the second and then the first. In either case, the deterministic algorithm finds a $1$ with an expected number of queries $0.5\cdot 1 + 0.5\cdot 2 = 1.5$ (because half the time it finds it on the first try and half the time it finds it on the second try). Still not great.</p>

<p>Now, can you think of a better distribution $A$ to use?</p>

CC BY-SA 3.0
2015-02-21T14:15:53.770Z
Thanks, I guess it should be uniform distrbution over e_1,...,e_n. Is there a more elegant way I can compute the expected number of queries than $\sum_{k=1}^{n}k\cdot\prod_{i=1}^{k-1}\left(\frac{n-i}{n}\right)\cdot\frac{1}{n-k+1}$?
Yoyo
CC BY-SA 3.0
2015-02-21T19:17:11.020Z
Right! And I think the probability of finding it on the $k$th query, for any deterministic algorithm, should just be $\frac{1}{n}$, so the expected number of steps should be $n/2$.
usul
CC BY-SA 3.0
2015-02-21T13:54:41.737Z
2015-02-21T13:54:41.737Z
usul
<p>Consider the basic problem in which the input is an array A of n bits, and we need to output some index i with A[i]=1 (we can read a single bit each time).</p>

<p>Can you give me an example using Yao's minimax principle to lowerbound the complexity of the problem with $\Omega(n)$?</p>

<lower-bounds><randomized-algorithms>
Using Yao's minimax principle
Yoyo
# Using Yao's minimax principle

(Asked by: username_0 on 2015-02-21)

Consider the basic problem in which the input is an array A of n bits, and we need to output some index i with A[i]=1 (we can read a single bit each time).

Can you give me an example using Yao's minimax principle to lowerbound the complexity of the problem with $\Omega(n)$?

**Tags:** lower-bounds, randomized-algorithms


---

## 1 answers

### Answer by username_1 on 2015-02-21. Score: 5 | Accepted answer

First, to be precise in your problem statement, we probably are promised that $A$ has at least one index $i$ with $A[i] = 1$.

We want to show that no randomized algorithm can guarantee better than $\Omega(n)$ expected number of queries. In other words, we want to show that for any randomized algorithm, on its worst-case input, it requires $\Omega(n)$ queries.

By the minimax principle, the expected number of steps required by any randomized algorithm on its worst-case input is lower-bounded by the following: for any distribution $D$ on inputs, the expected number of steps of the best deterministic algorithm against that distribution.

Make sure that the preceding paragraph makes sense. *Any randomized algorithm against its worst-case input has poorer performance than any randomized input distribution against its best-case deterministic algorithm.*

So now we have two steps: First, construct a distribution $D$ on inputs; and second, show that the best deterministic algorithm takes $\Omega(n)$ steps in expectation against that distribution.

The nice thing about the argument is that any such $D$ will give you some lower bound. For instance, the distribution on $A$ where $A = (1,0,0,0,...)$ every time is a distribution on inputs. But, the best deterministic algorithm against this distribution just checks the first coordinate first, and always finds a $1$ there, so this gives a lower bound of $1$ query -- pretty terrible.

Another distribution would have $A = (1,0,0,...)$ with probability $0.5$ and $A = (0,1,0,0,...)$ with probability $0.5$. Here, the best any deterministic algorithm can do is either check the first position first and then the second, or check the second and then the first. In either case, the deterministic algorithm finds a $1$ with an expected number of queries $0.5\cdot 1 + 0.5\cdot 2 = 1.5$ (because half the time it finds it on the first try and half the time it finds it on the second try). Still not great.

Now, can you think of a better distribution $A$ to use?

> **Comments:**
> **username_0**: Thanks, I guess it should be uniform distrbution over e_1,...,e_n. Is there a more elegant way I can compute the expected number of queries than $\sum_{k=1}^{n}k\cdot\prod_{i=1}^{k-1}\left(\frac{n-i}{n}\right)\cdot\frac{1}{n-k+1}$?  
> **username_1**: Right! And I think the probability of finding it on the $k$th query, for any deterministic algorithm, should just be $\frac{1}{n}$, so the expected number of steps should be $n/2$.  

---

