855学习记录之概率论样本空间与概率（6）独立性—— 炎泽汐$de$ Blog

文章目录[隐藏]

• 相关概念
• Error Reduction (one-sided case)
• Error Reduction (two-sided case)

受限的独立性

---

相互独立的事件序列一定是两两独立的，反之不一定：

乘积概率空间

---

基本概念

---

定义一个决定性问题：

$$
f:\left\{ 0,1 \right\} ^*=\left\{ 0,1 \right\}
$$

有一个具有单边错误的蒙特卡洛随机算法$\mathscr{A}$，算法满足：

$\forall x\in \left\{ 0,1 \right\} ^*:f\left( x \right) =1\Rightarrow \mathscr{A}\left( x \right) =1$

$\forall x\in \left\{ 0,1 \right\} ^*:f\left( x \right) =0\Rightarrow Pr\left( \mathscr{A}^n\left( x \right) =0 \right) \ge p$

算法$ \mathscr{A}^n$过程为，相互独立地执行$\mathscr{A}$共$n$次，取所有结果的且$\left( \land \right) $进行输出。

进而可以推得算法犯错的概率$P$满足：

$$
P\le Pr\left( \mathscr{A}^n\left( x \right) =1 \right) \le \left( 1-p \right) ^n
$$

故执行$n$次算法以后失败的概率将收敛于任意正数$\varepsilon $，其中$n$的取值为：

$$
\left( 1-p \right) ^n=\varepsilon \Rightarrow e^{-np}\approx \varepsilon \Rightarrow n\approx \frac{1}{p}\ln \left( \frac{1}{\varepsilon} \right)
$$

控制公平的投票

---

基本概念

---

Network Reliability

---