$\epsilon$-approximation Sub-linear time monotonicity testing

Question

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

1. Pick a uniformly random position $i$ between $1$ and $n$.
2. let $v_i$ be the value at position $i$ in the list.
3. Use binary search to look for the value $v_i$ in the list.
4. If the binary search reported $i$ as the position of $v_i$ then
5. return Yes
6. else
7. 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

1. Let $ h \leftarrow \lceil \frac{2}{\epsilon} \rceil $
2. Execute $h$ independent copies of Alg1 on the input list.
3. If all the copies answer "Yes"
4. Return Yes
5. Else
6. 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.

Answer 1

Let $P$ denote the number of pairs of indices $i<j$ such that $f(i)=1$ and $f(j)=0$, and let $C$ be the minimal number of flips required to make $f$ monotone. First, we show by induction on $n$ that for every function $f$ defined on $[n]$ it holds that $C^2\le 3P$.

Suppose that the claim holds for $n$ and let $f$ be a function defined on $[n+1]$. We denote by $C(n),P(n)$ the number of corrections and monotonicity violating pairs for $f|_{[n]}$ correspondingly. Finally, let $w(n)$ denote the weight of $f$, i.e. $w(n)=\big|f^{-1}(\{1\})\cap[n]\big|$. Observe that if $f(n+1)=1$ then $C(n)=C(n+1)$ and the claim clearly holds, it thus suffices to focus on the $f(n+1)=0$ case. If $f(n+1)=0$ then $P(n+1)=P(n)+w(n)$ and $C(n+1)\le C(n)+1$. Applying the inductive hypothesis $C^2(n)\le 3P(n)$ we have:

$$C^2(n+1)\le C^2(n)+2C(n)+1\le 3P(n)+2C(n)+1=\\3P(n+1)+2(C(n)-w(n))- w(n)+1 \le 3P(n+1),$$

since $C(n)\le w(n)$ and $w(n)\ge 1$ (the claim is trivial for the constant zero function). This concludes the proof.

The above inequality yields a simple algorithm for testing monotonicity. Sample a pair $i<j$ uniformly at random and answer "no" if $f(i)>f(j)$. Let $q$ denote the probability that $i,j$ is such a pair, then $q\ge \frac{P}{n^2}\ge \frac{C^2}{3n^2}\ge \frac{\epsilon^2}{3}$. By repeating this procedure $\approx q^{-1}$ times, you obtain an $O\left(\frac{1}{\epsilon^2}\right)$ algorithm for separating the monotone from the $\epsilon$-far from monotone case.