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

CC BY-SA 4.0
2023-01-11T19:59:04.040Z
2023-01-11T21:22:40.893Z
2023-01-11T21:22:40.893Z
Sid Jain
<p>In the simple proof of the johnson lindenstrauss lemma written by Sanjoy Dasgupta, Anupam Gupta that can be found <a href="https://cseweb.ucsd.edu/%7Edasgupta/papers/jl.pdf" rel="nofollow noreferrer">here</a> they state the following (p.<span class="math-container">$62$</span>):</p>
<blockquote>
<p>Repeating this projection <span class="math-container">$O(n)$</span> times can boost the success probability to the desired constant, giving us the claimed randomized polynomial time algorithm.</p>
</blockquote>
<p>My idea is to see that the success probability of a single trial is <span class="math-container">$1/n$</span> thus the success probability of atleast one trial out of <span class="math-container">$n$</span> trials is <span class="math-container">$1 - (1/n)^n$</span> if we then set it to be larger than <span class="math-container">$0.95$</span> we end up with:
<span class="math-container">$0.05 &gt; (1 - 1/n)^n$</span> thus <span class="math-container">$\log(0.05) &gt; n\log(1 - 1/n)$</span> but i think this way of proving it is wrong.</p>
<p>Could someone help me bring some clarity into this?</p>

<machine-learning><randomized-algorithms><data-streams><data-mining>
Boosting the probability of success(random projections, johnson lindenstrauss)
randomizedalgo
# Boosting the probability of success(random projections, johnson lindenstrauss)

(Asked by: username_0 on 2023-01-11)

In the simple proof of the johnson lindenstrauss lemma written by Sanjoy Dasgupta, Anupam Gupta that can be found [here](https://cseweb.ucsd.edu/%7Edasgupta/papers/jl.pdf) 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?

**Tags:** machine-learning, randomized-algorithms, data-streams, data-mining


---

## 1 answers

### Answer by username_1 on 2023-01-11. Score: 3

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.


---

