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

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.

• OK, so I take it that "$a$ is $\epsilon$-far from monotone" means "$a$ is $\epsilon$-far from some monotone list $b$"? – j_random_hacker May 22 at 10:10
• @j_random_hacker This means, that given a list, it is ϵ-far from monotone, if at least ϵn indices in it should be changed for it to become monotone – Gulzar May 22 at 10:11
• @j_random_hacker yes this seems equivalent. – Gulzar May 22 at 10:11
• Sorry, I should have written "from every" instead of "from some". (Even a monotone list is at least 0.5-far from either the all-0s list or the all-1s list.) – j_random_hacker May 22 at 10:18
• Alg 1 won't reliably report "Yes" if there are duplicates in the list. – j_random_hacker May 22 at 10:25

Let $$P$$ denote the number of pairs of indices $$i 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 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.

• 1. THANK YOU! 2. please explain: $C(n) \le w(n)$ should mean $2C(n)-w(n) < 0$, and $w(n) \ge 1$ means $-w(n)+1 \le 0$ which leads me to not understand - shouldn't we add a positive number to $3P(n+1)$? What did I miss? – Gulzar May 22 at 19:57
• You want to conclude that $C^2(n+1)\le 3P(n+1)$, so the addition should be negative. – Ariel May 22 at 19:59
• I am at awe at how you got to this. I was literally staring at this for hours, at a completely different direction – Gulzar May 22 at 20:04
• The pair sampling is pretty naive, then you just have to get it to work. You have a guarantee on $C/n$, so it remains to connect this to the number of "bad" pairs somehow. – Ariel May 22 at 20:06
• Let me go over this one (or ten) more time(s) and I will accept – Gulzar May 22 at 20:08