I have the following exercise I have been staring at for several hours to no avail.
Question:
Testing the monotonicity of a function - the case of bits: Given a function $f: [n] \rightarrow \{0,1\}$ and a parameter $0 < \epsilon < 1$, show an algorithm that runs in $O(\frac{1}{poly(\epsilon)})$ queries to $f$, with the following behavior:
- if $f$ is monotone (i.e $\forall x, y \in [n]$ if $x \le y$ then $f(x) \le f(y)$, then the algorithm always outputs "yes"
- if $f$ is $\epsilon$ far from monotone, then the algorithm outputs "No" with probability at least $\frac {3}{4}$.
Definition of $\epsilon$-far:
A list $a$ is $\epsilon$-far from a list $b$, both of length $n$ iff they differ in more than $\epsilon n$ indices.
I will greatly appreciate help, and show my (stale) thought process.
My thoughts:
Consider the following algorithms
Alg1
- Pick a uniformly random position $i$ between $1$ and $n$.
- let $v_i$ be the value at position $i$ in the list.
- Use binary search to look for the value $v_i$ in the list.
- If the binary search reported $i$ as the position of $v_i$ then
- return Yes
- else
- return No
which is proven to always return "Yes" for sorted lists, and
given a list which is $\epsilon$-far from being sorted, it returns "No" with probability at least $\epsilon$.
Alg 2
- Let $ h \leftarrow \lceil \frac{2}{\epsilon} \rceil $
- Execute $h$ independent copies of Alg1 on the input list.
- If all the copies answer "Yes"
- Return Yes
- Else
- Return No
which is proven to always return "Yes" for sorted lists, and
given a list which is $\epsilon$-far from being sorted, Algorithm 3 detects it is not sorted, with probability at least $\frac{2}{3}$
It is also proven to be of (query) complexity
$h lon(n) = \lceil \frac{2}{\epsilon} \rceil O(log(n)) = O(\epsilon ^{-1} log(n))$
What to do with all that?
I thought I could use Alg 2 for the case of the binary function $f$, and to find out if it is non-decreasing.
The problem is, binary search has too many queries.
So I have to skip the search, and probably use some kind of sampling.
Let's say I uniformly sample $k$ indices of the list, and later force $k=o(\frac{1}{\epsilon})$.
I will then test monotonicity on the sample, and return an answer accordingly.
I haven't the slightest idea if this holds the required probability constraint, or how to augment so it does.
I thought maybe it would make prooving easier if I were to use the number of indices in the sample, between the leftmost "1" to the rightmost "0" as a proxy for the probability bound, but this is as far as I went.
I will appreciate direction to this, or even a solution at this point.