Bounding spot-checking sublinear algorithm candidate for detecting a sorted array The source to the piece of an abstract listed below: Sublinear algorithms.
So I have a homework assignment connected to bounding the amount of array accessings of a sublinear algo that tries to guess whether the input array is sorted or not.
Here is a piece of an abstract I can't make sense of:

Input: a list $x_1,...,x_n$ of arbitrary numbers
Goal: an $\epsilon$-tester for sortedness (monotonicity) of the list with running time $O({logn \over \epsilon})$
Testers that do not work:


*

*..

*Proposed test: Pick random $i<j$ and reject if $x_i>x_j$.
Counterexample:
$$1~\color{blue}0~2~\color{blue}1~3~\color{blue}2~4~\color{blue}3~5~\color{blue}4~6~\color{blue}5$$
The Hamming distance of this list to the property "sortedness" is $\geq {1 \over 2}$ because for each black/blue consecutive pair ((1,0), (2,1). etc.) at least one of the two numbers has to be changed to make the first list sorted. But any other pair is correctly ordered. This implies, by Birthday Paradox, that we need to select $s=\Omega(\sqrt(n))$ numbers to find a pair of numbers that is out of order with probability $\geq {2 \over 3}$.



So what I can't understand is an application of a Birthday Paradox in this case as well as interconnection of $\epsilon$ with an amount of times the sampling of a pair $i,j$ should be done. Here is some additional information toghether with my thoughts:
So Hamming distance in this case is expressed as $\epsilon n$, where $n$ is an amount of items in an input array and $\epsilon \in (0,1]$. Together it indicates an amount of modifications that we are "tolerating" assuming that the input array is sorted if it less then $\epsilon n$-far from the totally sorted array.
Given the "worst-case" input from the above, the probability of sampling a pair of $i,j$ that would allow the algorithm to determine that the input array is not sorted is:
$$P(return~"not~sorted")~=~ {n \over 2 {\binom n2}} = {1 \over {n-1}}$$
The intuition behind the above formula is that we have exactly ${n \over 2}$ pair that would allow us to determine that array is not sorted and in total there are $\binom n2$ possible pairs from the $n$ items in the array.
Multiplying the above probability with an amount of iteration of sampling $i,j$ (denoting it $k$) I got the lower bound on $k$ of getting an error (returning sorted for an above obviously unsorted array) with probability at most ${2 \over 3}$:
$$k \geq {{2(n-1)} \over 3}$$
The property ${{2(n-1)} \over 3} = \Omega(\sqrt n)$ seems to hold. But what can I do with Birthday Paradox and how does $\epsilon$ influence the $k$?
Help is appreciated! (hope the problem statement is understandable) 
 A: *

*First of all: in this counterexample, $\varepsilon$ is set to be a constant, namely $\varepsilon = \frac{1}{2}$. The goal here is to show that the proposed tester has a bad dependence on the main parameter, $n$, without bothering about the dependence on $\varepsilon$ for now.

*Then, to see why the Birthday paradox box up: you have $\frac{n}{2}$ "slots" $B_1,\dots, B_{n/2}$ of consecutive elements, where $B_k=\{a_{2i-1}, a_{2i}\}$. To detect a violation, you need to sample two elements in the same slot (as two elements $x,y$ from different slots will not give you any violation of sortenedness: if $x \in B_k$ and $y\in B_\ell$ with $k < \ell$, then $x\leq y$).
So, when sampling two elements $i,j$ independently and uniformly at random and checking if the pair $(i,j)$ is a violation,you need that both $i$ and $j$ fall in the same $B_k$. This is where the Birthday paradox pops in:

To get at least two people out of $m$ having their birthday on the same day (out of $\frac{n}{2}$ days, assuming everyone's birthday is independently and uniformly chosen among the $n/2$ days), you need $m=\Omega(\sqrt{n})$.

Another intuitive view is that the probability that two distinct indices $(i,j)$ with $i< j$ end up in the same block $B_k$ is $p_{i,j} = \frac{1}{n/2} = \frac{1}{n-1}$. By linearity of expectation, if you take $m$ indices uniformly at random (and thus have $\binom{m}{2}$ such pairs), the expected number of collisions you will see is 
$$
\binom{m}{2}\cdot \frac{2}{n} = \frac{m(m-1)}{n} \leq \frac{m^2}{n}
$$
so you need $m=\Omega(\sqrt{n})$ samples to (on expectation) see at least one such collision (and be able to detect unsortedness).

*If you are concerned about the dependence on $\varepsilon$: you will see later a "good" tester for this property with query complexity $O\left(\frac{\log n}{\varepsilon}\right)$, which can be show to be necessary. Moreover, it is not hard to see that for any "reasonable" property (sortedness is one), you will need $\Omega(1/\varepsilon)$ no matter what you do (the idea being: if you take less than that, you will not "hit" any bad point, that is the ones contradicting the property).
As another reference, you can check these lecture notes, e.g. Section 1.2 (p.6) for sortenedness. (Disclaimer: these are by my adviser.)
