Table of Contents
Chebyshev inequalityの定理
Theorem
確率変数 $X$ に対して $\mathbb E[X] = \mu, Var(X) = \sigma^2$とおいたとき,
\[\begin{align*} \ \ &Pr(|X - \mu|\geq k\sigma) \leq \frac{1}{k^2}\\ \ \ &\text{where } k > 1 \text{ and constant} \end{align*}\]証明
以下のような確率変数 $D$ を定義する
\[D = \begin{cases} 1 & \text{ if } |X - \mu|\geq k\sigma\\[8pt] 0 & \text{ otherwise} \end{cases}\]すると, 以下の式が常に成り立つ
\[(X - \mu)^2 \geq k^2\sigma^2U\]従って,
\[\begin{align*} \sigma^2 &= Var(X)\\ &= \mathbb E[(X - \mu)^2]\\ &\geq \mathbb E[k^2\sigma^2U]\\ &= k^2\sigma^2\mathbb E[U]\\ \Rightarrow& \frac{1}{k^2} \geq \mathbb E[U] \end{align*}\]定義より, $\mathbb E[U]$は $Pr(|X - \mu| \geq k\sigma)$と同値なので
\[Pr\{|X - \mu|\geq k\sigma\} \leq \frac{1}{k^2}\]証明終了
Cantelli’s inequality
Chebyshev’s inequalityのよりweakerなboundの定理としてCantelli’s inequalityがあります.
Theorem: Cantelli’s inequality
期待値 $\mu$ と分散 $\sigma^2$ を持つ確率変数$X$ について
\[\begin{align*} &Pr(X\geq \mu + t\sigma) \leq \frac{1}{1 + t^2}\\[8pt] &Pr(X\leq \mu - t\sigma) \leq \frac{1}{1 + t^2} \end{align*}\]証明
証明にはMarkov’s inequlityを用います. for any $v>0$,
\[\begin{align*} Pr(X - \mu \geq t) &= Pr(X - \mu + v \geq t + v)\\ &\leq Pr((X - \mu +v)^2 \geq (t + v)^2)\\ &\leq \frac{\mathbb E[(X - \mu +v)^2]}{ (t + v)^2}\\ &= \frac{v^2 + v^2}{(t + v)^2} \end{align*}\]ここで $v = \sigma/t$ とすると
\[\begin{align*} Pr(X \geq \mu + t) &\leq \frac{\sigma^2 + v^2}{(t + v)^2}\\ &= \frac{\sigma^2}{t^2 + \sigma^2} \end{align*}\]さらに $t = t^*\sigma$と変換すると
\[Pr(X \geq \mu + t^*\sigma) \leq \frac{1}{1+t^{*2}}\]証明終了
Chebyshev’s inequalityとの比較
\[\begin{align*} Pr(X - \mu \geq k\sigma) \leq Pr(|X - \mu|\geq k\sigma) \leq \frac{1}{k^2} \end{align*}\]Chebyshev’s inequality
\[Pr(|X - \mu|\geq k\sigma) = Pr(X - \mu\geq k\sigma) + Pr(|X - \mu|\leq -k\sigma) \leq \frac{2}{1+k^2}\]Cantelli’s inequality
従って, two-sidedにおける比較においては$k>1$について常にChebyshev’s inequalityに対して劣るboundであることがわかる.
例題: 合計診察時間の確率計算
Problem
100人の患者を次々と診察する１人医者を考える. 一人あたりの診察時間についての確率変数 $X$について $\mathbb E[X] = 1$, $Var(X) = 0.64$ が事前に知られている.
患者の診察は互いに独立に実施されるとして, 100人全員の診察が完了するまでに要した時間を $T$ としたとき, 平均を中央とした上下区間が下限96%になるような区間を求めよ.
解答
問題文より, $\mathbb E[T] = 100$, $Var(T) = 64$は自明.
Chebyshev inequalityより
\[Pr(|T - 100|< 8k) \geq 1-\frac{1}{k^2} = 0.96\]従って, $k=5$のときを求めればいいので
\[Pr(60 < T < 140) \geq 0.96\]解答終了
Appendix: Markov’s inequlity
Theorem
期待値 $\mu$ のnon-negativeな確率変数 $X$について
\[Pr(X\geq t) \leq \frac{\mu}{t} \ \ \forall t>0\]or
\[Pr(X\geq t\mu) \leq \frac{1}{t} \ \ \forall t>0\]証明
non-negativeな確率変数 $X$について以下は常に成り立つ
\[1\{X\geq t\} = 1\{X/t\geq 1\} \leq X/t\]これについて期待値をとると
\[\begin{align*} \mathbb E[1\{X\geq t\}] &= Pr(X\geq t)\\ &\leq \mathbb E[X/t]\\ &= \frac{\mu}{t} \end{align*}\]証明終了
References
Book
(注意：GitHub Accountが必要となります）