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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.