Probability of finding $ε$-approximate median of an array I'm given an array $A$ = ($a_1, a_2, \cdots a_n$), where n is uneven. For an element $a_i$ we denote its position in the array with $p(a_i)$. This element would be an $ε$-approximate median of the array, if after we sort it, the following inequality holds: 
$$\frac12 ((1 - ε) × n) < p(a_i) \leqslant \frac12 ((1 + ε) × n)$$
For example, the array $1,2,\cdots,9$ would have $4,5,6$ as $\dfrac13$-approximate medians.
My task is to analyze the following randomized algorithm, which finds an $ε$-approximate median of the array in constant time:

Choose $2k + 1$ elements of the array $A$: $b_1, b_2, \cdots, b_{2k+1}$, where each element is chosen uniformly randomly and independently of all the others (it is possible for an element to repeat). Using the algorithm for finding a median of an array in linear time (QuickSelect) output the median of the array the elements $b_1, b_2, \cdots, b_{2k+1}$ form.

I'm also given the following two random variables:
$K$: number of elements in $b_1, b_2, \cdots, b_{2k+1}$, which are smaller or equal to the $\dfrac12 ((1-ε)×n)$-biggest element in the original array 
$A$.
$G$: number of elements in $b_1, b_2, \cdots, b_{2k+1}$, which are bigger than the $\dfrac12 ((1+ε)×n)$-biggest element in the original array $A$.
What I have to do is find the best possible upper bounds for 
$$P(K \geqslant (1 + ε) E(K))$$
and 
$$P(G \geqslant (1 + ε) E(G)),$$
where $E(K)$ and $E(G)$ are the expected values for the random variables. I also have to find a bound for the probability the algorithm will be successful, which depends only on $k$, not on $n$, $E(K)$ or $E(G)$.
What I have done so far: I computed the expected values for the two random variables. I believe they are binomially distributed, so for example for $K$ I have $2k + 1$ events each with probability $\dfrac12(1-ε)$ to happen, so 
$$E(K) = (2k + 1) × \dfrac12 (1 - ε).$$
$E(G)$ turns out to be the same. Then I tried computing the two upper bounds, mentioned above with the Markov, Chebyshev and Chernoff inequalities:
Markov: 
$$P(K \geqslant (1 + ε) E(K)) \leqslant \frac1{1 + ε},$$
Chebyshev (might be false):
$$P(|K - E(K)| \geqslant εE(K)) \leqslant \frac{\operatorname{Var}(K)}{ε^2 × (E(K))^2} = \frac{1}{ε(2k + 1)},$$
Chernoff:
$$P(K \geqslant (1 + ε) E(K)) \leqslant \exp\left( -\frac13 ε^2 E(K) \right).$$
Are these correct? If they are, am I correct that Chebyshev is the best one? How do I continue with finding the probability of success of the algorithm? 
Thank you :)
 A: The literature credits Manku et al. for solving this problem in section 5: "A Sampling based Algorithm" of their paper DOI:10.1145/276304.276342: Approximate Medians and other Quantiles in One Pass and with Limited Memory.
Beware that the OP notes $ε$ the whole confidence interval, whereas Manku et al. note $ε$ only half the confidence interval.
First observation is that if $K$ and $G$ are both less than $\frac{2k+1}2$, then the median of the sample is an ε-approximate median.
Taking $1-δ$ as the wanted level of confidence that the sample is good, then it's enough to ensure that both:
$$
P(K \ge \frac{2k+1}2) \le \fracδ2\\
P(G \ge \frac{2k+1}2) \le \fracδ2
$$
Because $K$ and $G$ are both independent Bernoulli trials of $2k+1$ events, each with probability $\frac{1−ε}2$ to happen, $E(K) = E(G) = (1-ε)\frac{2k+1}2$, therefore:
$$
P(K \ge \frac{2k+1}2) = P(K - E(K) \ge ε\frac{2k+1}2)\\
P(G \ge \frac{2k+1}2) = P(G - E(G) \ge ε\frac{2k+1}2)
$$
Then, by Hoeffding's inequality:
$$
P(K \ge \frac{2k+1}2) \le \exp(\frac{-2ε²(\frac{2k+1}2)²}{2k+1})\\
P(G \ge \frac{2k+1}2) \le \exp(\frac{-2ε²(\frac{2k+1}2)²}{2k+1})
$$
(Here I believe there's a typo in the paper and that $S²$ should be $\frac{S²}S$, hopefully the error is no longer present when the authors determine $S$ from $ε$ and $δ$.)
By the union bound, it's then enough to ensure:
$$
\exp(-ε²\frac{2k+1}2) \le \fracδ2
$$
Then, fixing $δ$ enables to determine a lower-bound for the number of samples, also independent of $n$:
$$
\frac2{ε²}\log(\frac2{δ}) \le 2k+1
$$
As a side note, there's also a related paper DOI: 10.3150/14-BEJ605 by Rémi Bardenet and Odalric-Ambrym Maillard: Concentration inequalities for sampling without replacement, stating that the sampling without replacement enables to improve Hoeffding’s bound with an Hoeffding–Serfling bound depending upon $n$ which is close for a sample size below $\frac{n}2$, but decreases to zero above this point, outperforming Hoeffding’s bound.
