Lets assume we have an array a with $n$ numbers and we want to finde an element $a_i$ of $a$ for which holds that $\frac{1}{3} n < p(a_i) \leq \frac{2}{3} n $. Where $p(a_i)$ denotes the position of the element $a_i$ in the sorted array.
I have already thought about an algorithm for this problem. Now I want to analyze it.
We select $2k + 1$ elements uniformly, independently and randomly from $a$ (so it is possible that the same element is drawn several times from a) and call this array $b$.
We define the random variables $G$ and $K$. Be $s,t$ so $p(a_s) = \frac{n}{3}$ and $p(a_t) = \frac{2n}{3}$. Then $K = |\{i:b_i \leq a_s\}|$ and $G = |\{i:b_i > a_t\}|$. How can I calculate the expected value of K and G and $P[K ≥ k + 1]$ and $Pr[G ≥ k + 1]$?