I have already seen some threads conjecturing that there is at least one prime between $n$ and $2n$. I am given an exercise, where I have relaxed this conjecture to the assumption that between $n$ and $2n$ there are at least $\frac{n}{3\ln n}$ primes. I am asked to describe a randomized algorithm to find a prime in the range $n$ and $2n$ with probability $1 - \frac{1}{n}$.
The only possible solution, that I could think of is to pick random numbers in the range $n$ and $2n$ and apply Miller-Rabin, until Miller-Rabin returns a probably prime. Problem here is that, probably prime is correct with probability $\frac{3}{4}$, which is too far from $1 - \frac{1}{n}$
Yes, after following the discussion, what I suggested is the right approach. Plus, one needs to repeat RM sufficient number of times to get the desired probability. To determine the number of repetitions, use Chernoff bound, which takes into account the number of primes within the selected range.