■ - 研究

以下の補題を使いました。

Let
$p_1,\ldots,p_b\,(b\geq2)$
be positive numbers such that
$\sum_{\ell=1}^bp_\ell=1$ ,
and let
$\varepsilon=\frac{1}{\sqrt{b}}\min_\ell\frac{p_\ell}{1-p_\ell}$ .
Then, there is no $e=(e_1,\ldots,e_b)\in R^b$ satisfying the following three conditions,
$\sum_{\ell=1}^b e_\ell^2=1$ , $\sum_{\ell=1}^bp_\ell e_\ell \geq 0$ , $e_\ell<\varepsilon,\, \ell=1,\ldots,b$ .

proof:
We suppose that $e\in R^b$ satisfies the three conditions.
The inequality $\min_\ell p_\ell/(1-p_\ell)\leq 1$ clearly holds, and thus,
$\varepsilon\leq 1/\sqrt{b}$ holds.
The equality constraint $\sum_{\ell=1}^b e_\ell^2=1$ leads the condition that
there exists an $e_i$ such that $|e_i|\geq 1/\sqrt{b}$ . Moreover, we have
$e_1,\ldots,e_b<\varepsilon\leq 1/\sqrt{b}$ , and thus, there is an $e_i$ such that
$e_i\leq -1/\sqrt{b}$ . Hence, we have
$\frac{p_i}{\sqrt{b}} ~\leq~ -p_ie_i ~\leq~ \sum_{\ell\neq i}p_\ell e_\ell ~<~ \sum_{\ell\neq i}p_\ell \frac{1}{\sqrt{b}}\min_k\frac{p_k}{1-p_k} ~=~(1-p_i) \frac{1}{\sqrt{b}}\min_k\frac{p_k}{1-p_k} ~\leq~\frac{p_i}{\sqrt{b}}$ .
We reach the contradiction.

したがって
$\min \{\max_k ~ e_k ~ |~ \sum_{\ell=1}^b e_\ell^2=1,\sum_{\ell=1}^bp_\ell e_\ell\geq 0\} \geq \frac{1}{\sqrt{b}}\min_\ell\frac{p_\ell}{1-p_\ell}$

二者択一の定理のようなものから導出できるのでしょうか? 最適化問題として見ると、ナイーブには凸性が崩れているのが厄介。