Boosting the probability of success(random projections, johnson lindenstrauss)

Question

In the simple proof of the johnson lindenstrauss lemma written by Sanjoy Dasgupta, Anupam Gupta that can be found here they state the following (p.$62$):

Repeating this projection $O(n)$ times can boost the success probability to the desired constant, giving us the claimed randomized polynomial time algorithm.

My idea is to see that the success probability of a single trial is $1/n$ thus the success probability of atleast one trial out of $n$ trials is $1 - (1/n)^n$ if we then set it to be larger than $0.95$ we end up with: $0.05 > (1 - 1/n)^n$ thus $\log(0.05) > n\log(1 - 1/n)$ but i think this way of proving it is wrong.

Could someone help me bring some clarity into this?

Answer 1

If the probability of success of an event is $1/n$, then the failure probability is $(1 - 1/n)$. Hence the probability of failure for $n$ independent trials is $(1 - 1/n)^n$. The limit as $n$ goes to infinity is exactly $e^{-1}$. Therefore, thinking of repeating it $n$ times as another subroutine, if we repeat this subroutine $c$ times we get a success probability of $e^{-c}$ which can be made an arbitrarily small constant.