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)$?


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?

| cite | improve this answer | |
  • $\begingroup$ 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}$? $\endgroup$ – Yoyo Feb 21 '15 at 14:15
  • $\begingroup$ 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$. $\endgroup$ – usul Feb 21 '15 at 19:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.