关于Johnson-Lindenstrauss引理简单证明中重复投影提升成功概率的疑问

首先，你一开始的思路里有个关键的小误解：单轮投影的成功概率不是 $1/n$，反过来，单轮的失败概率才是 $O(1/n)$ 量级的——这才是理解这个结论的核心。

让我们一步步理清楚：

• 在Dasgupta和Gupta的JL引理简单证明中，当我们选择合适的投影维度 $d = O(\epsilon^{-2} \log n)$ 时，单轮投影满足“所有向量对的距离误差都控制在 $(1\pm\epsilon)$ 范围内”的成功概率其实是 $1 - \frac{c}{n}$，这里的 $c$ 是某个固定的常数（和你设定的误差 $\epsilon$ 有关，比如可以取 $c=1/2$ 或者其他小常数）。
• 对应地，单轮投影失败的概率就是 $\frac{c}{n}$。

现在我们重复这个投影 $k = tn$ 次（$t$ 是一个和 $c$ 相关的固定常数，也就是 $k=O(n)$），我们要算至少有一次投影成功的概率：
这个概率等于 $1 - $（所有 $k$ 轮投影都失败的概率）。

所有 $k$ 轮都失败的概率是 $\left(\frac{c}{n}\right)^k$，把 $k=tn$ 代入进去：
$$
\left(\frac{c}{n}\right)^{tn} = \left(\frac{c^t}{nt}\right)^n
$$
当 $n$ 足够大时，这个值会指数级趋近于0——比如取 $c=1$，$t=2$，那就是 $\left(\frac{1}{n^2}\right)n = n^{-2n}$，这显然是一个极小的数，远小于你设定的0.05。

那反过来，至少一次成功的概率就是 $1 - $ 这个极小值，自然会大于你想要的常数（比如0.95）。

你之前的错误是把单轮成功概率当成了 $1/n$，其实刚好反过来，单轮失败概率是 $O(1/n)$，这样重复 $O(n)$ 次后，失败概率被压得极低，成功概率就提升到了接近1的常数。

另外补充一点：有时候也会用另一种视角理解——如果单轮成功概率是 $p = 1 - O(1/n)$，重复 $n$ 次后，成功概率是 $1 - (1-p)^n$，而 $(1-p)^n = (O(1/n))^n$，同样是指数级小，所以成功概率会快速趋近于1。

备注：内容来源于stack exchange，提问作者jakobhellander