Minimum number of trials to get >99% chance of getting the median

Question

Context:

An algorithm is given (below); input array A is made of n elements, which are all odd, positive integers.

Algorithm:

Median(A[1, ... , *n*])
1. Uniformly at random pick i ∈ {1, ... , *n*}.
2. c ← 0
3. foreach j ∈ {1, ... , *n*} 
4.     if A[j] < A[i] then c ← c+1

Note: the "if" statement (line 4) is supposed to be nested under the "foreach" statement (line 3).

5. if c = (n-1)/2 then return A[i]
6. else goto line 1

Question:

Assume each execution of line 1 is defined to be a "trial". How many trials are needed to have atleast a 99% chance of returning successfully with the median value as shown in line 5? The answer will have a lower bound, and it will be a function of $n$.

Thoughts:

Let $m$ be the number of trials, and $n$ be the possible values we're looking through. I realised that $\frac{m}{n} = \frac{trials}{elements} = $ the probability of finding the median. Assuming this is right, I go on to deduce that $\frac{m}{n} \geq 0.99$ because we need a probability of atleast 99%. Given this logic, I end up with $m \geq 0.99n$ but when trying to figure out the lower boundary I am getting confused as my approach doesn't seem to lead to a lower boundary.

I'm not sure where I'm going wrong, so any help or hints on helping me understand any mistakes I'm making would be much appreciated!

Answer 1

I suppose $n$ is odd. (Not the elements in the list $A$.) The "median element" is colored in red, all others are black.

The probability to not extract the red number from the list in one step is $$ p = 1-\frac 1n\ . $$ Let $K>0$ be a natural number.

The probability to not extract the red number from the list in $K$ steps is $$ p^K = \left(1-\frac 1n\right)^K\ . $$ For a rather big $n$ we have $$ \left(1-\frac 1n\right)^n\approx \frac 1e=\exp(-1)\ . $$ To get a value $p^K$ under $0.01=\frac 1{100}$, we need to repeat the experiment roughly some $K=n\log 100 =2n\log 10$ times. (So we repeat for instance $K=5n$ times the random extraction, $\log 100$ is numerically 4.60517018598809... .)

For a given $n$ the value of $K$ can be computed explicitly.