$\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 &lt; \epsilon &lt; 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 &quot;yes&quot;
if $f$ is $\epsilon$ far from monotone, then the algorithm outputs &quot;No&quot; 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 &quot;Yes&quot; for sorted lists, and
given a list which is $\epsilon$-far from being sorted, it returns &quot;No&quot; 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 &quot;Yes&quot;
Return Yes
Else
Return No

which is proven to always return &quot;Yes&quot; 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 &quot;1&quot; to the rightmost &quot;0&quot; 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.
Let $P$ denote the number of pairs of indices $i&lt;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$$
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&lt;j$ uniformly at random and answer &quot;no&quot; if $f(i)&gt;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.