通信複雑性
Pr R [ ∃ ( x , y ) : | p R ′ ( x , y ) − p ( x , y ) | ≥ 0.1 ] ≤ ∑ ( x , y ) Pr R [ | p R ′ ( x , y ) − p ( x , y ) | ≥ 0.1 ] < ∑ ( x , y ) 2 − 2 n = 1 {\displaystyle \Pr _{R}[\exists (x,y):\,|p'_{R}(x,y)-p(x,y)|\geq 0.1]\leq \sum _{(x,y)}\Pr _{R}[|p'_{R}(x,y)-p(x,y)|\geq 0.1]<\sum _{(x,y)}2^{-2n}=1}
最後の等号は、 ( x , y ) {\displaystyle (x,y)} の組み合わせが 2 2 n {\displaystyle 2^{2n}} 個あるからである。全ての ( x , y ) {\displaystyle (x,y)} について以下が成り立つ R 0 {\displaystyle R_{0}} が存在する。
| p R 0 ′ ( x , y ) − p ( x , y ) | < 0.1 {\displaystyle |p'_{R_{0}}(x,y)-p(x,y)|<0.1}
P {\displaystyle P} の最大エラー率は 0.1 であることから、 P R 0 ′ {\displaystyle P'_{R_{0}}} のエラー率は最大で 0.2 となる。