(より詳しい解説は後日ブログで公開します)

「\(N\) 個の事象が互いに独立であること」と，「\(N\) 個の事象のうちどの \(2\) 個も独立であること」は異なる意味であることに注意してください．

\(p_i = \frac{P_i}{100}\) とします．コイン \(i\) が表になる事象を \(X_i\) と書くと，問題文の条件は

• \(\mathrm{Pr}[X_i] = p_i\)
• \(\mathrm{Pr}[X_i \wedge X_j] = p_i p_j\) (\(i \ne j\))

ということです．

\(p_1 \le \cdots \le p_N\) としてよいです．すると，\(\mathrm{Pr}[\overline{X_1} \vee \cdots \vee \overline{X_N}] \le \mathrm{Pr}[\overline{X_1}] + \sum_{i=2}^N \mathrm{Pr}[X_1 \wedge \overline{X_i}] = (1-p_1) + \sum_{i=2}^N p_1(1-p_i) = 1 - p_1 \left(\sum_{i=2}^N p_i - (N-2)\right)\) より，\(\mathrm{Pr}[X_1 \wedge \cdots \wedge X_N] \ge \max\left\{ p_1 \left(\sum_{i=2}^N p_i - (N-2)\right), 0 \right\}\) という答えの下界が得られます．

実は，この値が最小値として必ずとりうることが証明できます．表裏の出方 \(2^N\) 通りに対する確率の割り振りを実際に構成します．

\(\sum_{i=2}^N p_i \ge N-2\) のときを考えます．まず

• \(N\) 枚すべて表：\(p_1 \left(\sum_{i=2}^N p_i - (N-2)\right)\)
• コイン \(i (\ge 2)\) のみ裏で他が表：\(p_1 (1-p_i)\)

と割り振ります．するとコイン \(1\) が裏となる場合について満たしたい条件は

• \(\mathrm{Pr}[\overline{X_1}] = 1-p_1\)
• \(\mathrm{Pr}[\overline{X_1} \wedge \overline{X_i}] = (1-p_1) (1-p_i)\) (\(i \ge 2\))
• \(\mathrm{Pr}[\overline{X_1} \wedge \overline{X_i} \wedge \overline{X_j}] = (1-p_i) (1-p_j)\) (\(i, j \ge 2,\, i \ne j\))

となります．\(p_1 = 0\) のときは確率 \(0\) を割り振ります．そうでないときは，各コイン \(i (\ge 2)\) に対して表なら \(1 - \frac{1-p_i}{1-p_1}\)，裏なら \(\frac{1-p_i}{1-p_1}\) の積をとってさらに \((1-p_1)^2\) 倍した値を割り振ります．ただしコイン \(1\) のみが裏で他が表の場合には残った確率をすべて割り振ることにします．これで条件を満たすことが確認できます．

\(\sum_{i=2}^N p_i < N-2\) のときを考えます．\(\sum_{i=2}^k (1-p_i) \ge 1\) なる最小の \(k\) がとれるのでとります．まず \((p_1, \ldots, p_N)\) の代わりに \((p_1, \ldots, p_{k-1}, \sum_{i=2}^{k-1} (1-p_i))\) という列に対して問題を解き，その分布を \(A\) とします (これは先ほどの場合でカバーされます)．これとは別に，コイン \(1, \ldots, k-1\) は確率 \(p_i\) で，コイン \(k\) は確率 \(0\) で表になり，これらが互いに独立な分布 \(B\) を考えます．すると，\(A\) と \(B\) の線形結合によって \(\mathrm{Pr}[X_k] = p_k\) を満たす分布を作ることができます．これにコイン \(k+1, \ldots, N\) を互いに独立に加えることによって，条件を満たせることが確認できます．