確率不等式

概要と注意(言い訳)

確率不等式はたくさん知っているといざという時便利だと思うのでブログにまとめていこうと思います。徐々に増やしていくつもりです。僕は大学で数学を学んだことがないため(演習程度はあるけど), あまり厳密さには期待しないでください。なにが確率変数かとかも雰囲気で察してください。また, 一般の積分でも成り立つものに関しても期待値として書いているものが多いです。厳密な証明等は元論文とか参照してください。

表記について

関数 $f(x, y)$の$x$に関する偏導関数を$\partial_x f$と書きます。
確率変数$X$の期待値を$\bracket{X}$と書きます。条件付き期待値などややこしい場合は$\bracket{f(X, Y)}_{X \sim p(X|Y)}$ のように右下に書きます。

一覧

Cauchy-Shwarz inequality - AI.doll

Hölder inequality - AI.doll

Minkowski inequality - AI.doll

Lyapunov inequality - AI.doll

Jensen inequality - AI.doll

Cramér-Rao inequality - AI.doll

Bhattacharyya inequality - AI.doll

Chapman-Robbins inequality - AI.doll

f:id:doll_r0:20191211185715p:plain:w0

2019-12-11

Chapman-Robbins inequality

確率不等式

Chapman-Robbins 不等式

$X$値確率変数$x$の確率密度関数を母数$\theta$を用いて$f(x| \theta)$とする. $S(\theta)$を以下のように定義する:

$$ \begin{align} &f(x| \theta) > 0, \;\; a.e.\;x\in S(\theta)\\ &f(x| \theta) = 0, \;\; a.e.\;x\in X-S(\theta). \end{align} $$

$\varphi(x)$を母数$\theta$の不偏推定量であるとする. $S(\theta + h)\subset S(\theta)$となるような$h(\neq 0)$を考えると,

$$ \begin{align} \mathrm{Var}_\theta[\varphi(x)]\geq\frac{1}{\inf_{h} \bracket{J(\theta, h)}_\theta}. \end{align} $$

ただし,

$$ \begin{align} J(\theta, h) = \frac{1}{h^2}\left[\left\{\frac{f(x|\theta+h)}{f(x|\theta)}\right\}^2-1\right]. \end{align} $$

また, 条件を満たすような$h$が存在しない場合でも $\inf_{h} \bracket{J(\theta, h)} _ \theta = \infty $とすれば不等式は成立する. ($\inf $に関してこういうことをするのは割と普通らしい?)

証明

条件を満たす$h$が存在するとき,

$$ \begin{align} &\bracket{(\varphi(x)-\theta)\frac{f(x|\theta+h)-f(x|\theta)}{hf(x|\theta)}}_\theta \\ &= \int_{S(\theta)}dx (\varphi(x)-\theta)\frac{f(x|\theta+h)-f(x|\theta)}{h}\\ &= \frac{1}{h}\left\{\left( \int_{S(\theta+h)}dx \varphi(x)f(x|\theta+h) - \int_{S(\theta)}dx \varphi(x)f(x|\theta) \right) + \theta\left( \int_{S(\theta+h)}dx f(x|\theta+h) - \int_{S(\theta)}dx f(x|\theta+h) \right) \right\}\\ &= \frac{1}{h}\left\{(\theta + h - \theta)+\theta(1-1)\right\}\\ &= 1. \end{align} $$

Cauchy-Schwartz 不等式から,

$$ \begin{align} \bracket{(\varphi(x)-\theta)\frac{f(x|\theta+h)-f(x|\theta)}{hf(x|\theta)}}_\theta^2=1 &\leq \bracket{(\varphi(x)-\theta)^2}_\theta\bracket{\left\{\frac{f(x|\theta+h)-f(x|\theta)}{hf(x|\theta)}\right\}^2}_\theta\\ &=\mathrm{Var}_\theta[\varphi(x)] \frac{1}{h^2}\bracket{\left\{\frac{f(x|\theta+h)}{f(x|\theta)}\right\}^2 - 2\frac{f(x|\theta+h)}{f(x|\theta)}+1}_\theta\\ &=\mathrm{Var}_\theta[\varphi(x)] \frac{1}{h^2}\left[\bracket{\left\{\frac{f(x|\theta+h)}{f(x|\theta)}\right\}^2}_\theta-1\right]. \end{align} $$

ここで,

$$ \begin{align} J(\theta, h) = \frac{1}{h^2}\left[\left\{\frac{f(x|\theta+h)}{f(x|\theta)}\right\}^2-1\right] \end{align} $$

とすれば,

$$ \begin{align} \mathrm{Var}_\theta[\varphi(x)]\geq\frac{1}{\bracket{J(\theta, h)}_\theta} \end{align} $$

ここで, $S(\theta+h)\subset S(\theta)$を満たせば$h$は任意に取れるのでこの条件の下で$\inf$を取れば,

$$ \begin{align} \mathrm{Var}_\theta[\varphi(x)]\geq\frac{1}{\inf_{h} \bracket{J(\theta, h)}_\theta}. \end{align} $$

補足(お気持ち)

$ \bracket{\frac{f(x|\theta+h)}{f(x|\theta)}}_\theta = 1 $ から,

$$ \begin{align} \bracket{J(\theta, h)}_\theta &= \frac{1}{h^2}\left[\bracket{\left\{\frac{f(x|\theta+h)}{f(x|\theta)}\right\}^2}_\theta -\bracket{\frac{f(x|\theta+h)}{f(x|\theta)}}_\theta^2 \right]\\ &= \frac{1}{h^2}\mathrm{Var}_\theta\left[\frac{f(x|\theta+h)}{f(x|\theta)}\right]. \end{align} $$

$f$の$S$を狭めるような$h$を取ったときの確率密度関数の変わり具合のばらつきが大きいほど右辺は小さくなる. つまり, 母数に対して確率密度関数が敏感なほど推定のばらつきは小さくできる. (分母の$h ^ 2$は母数がいっぱい変われば確率密度関数もいっぱい変わるのでそれを打ち消すような感じ...?)

2019-12-11

Bhattacharyya inequality

確率不等式

注意

MathJaxを使っていて, Covという文字列を式中に含めるとなぜかバグるので$\mathrm{C}$で代用しています. そのうち直せたら修正します。

Bhattacharyya 不等式

$X=(X_1, \ldots, X_n)$の分布が母数$\theta$を用いて$f(X_1, \ldots, X_n|\theta)$と表せて, $\varphi(X)$が$\psi(\theta)$の不偏推定量であるとすると,

$$ \begin{align} \mathrm{Var}[\varphi(X)] \geq C^\mathrm{T} B^{-1} C. \end{align} $$

ただし, $i, j=1, \ldots, K$として

$$ \begin{align} B_{ij} &= \left\langle\frac{\partial_\theta^i f(X|\theta)}{f(X|\theta)} \frac{\partial_\theta^j f(X|\theta)}{f(X|\theta)}\right\rangle\\ C_i &= \partial_\theta^i \psi(\theta) \end{align} $$

で, $B$は正則であるとする.

証明

ベクトル

$$ \begin{align} y=\left(\varphi(X)-\psi(\theta), \frac{\partial_\theta f(X|\theta)}{f(X|\theta)}, \ldots, \frac{\partial_\theta^K f(X|\theta)}{f(X|\theta)}\right) \end{align} $$

の共分散行列を考える. まず, $\bracket{y}=0$を示す. $\bracket{\varphi(X)-\psi(\theta)}=0$は定義から明らかである.

$$ \begin{align} \bracket{\frac{\partial_\theta^k f(X|\theta)}{f(X|\theta)}} &=\int dx f(x|\theta)\frac{\partial_\theta^k f(x|\theta)}{f(x|\theta)}\\ &=\int dx \partial_\theta^k f(x|\theta)\\ &=\partial_\theta^k \int dx f(x|\theta)\\ &=0. \end{align} $$

以上より$y$の期待値は$0$なので, $y$の各要素の積の期待値を取れば共分散がでる. $\bracket{y_1 y_k}$を考えると,

$$ \begin{align} \bracket{y_1 y_k} &= \bracket{(\varphi(X)-\psi(\theta))\frac{\partial_\theta^k f(X|\theta)}{f(X|\theta)}}\\ &= \int dx f(x|\theta)(\varphi(x)-\psi(\theta))\frac{\partial_\theta^k f(x|\theta)}{f(x|\theta)}\\ &= \partial_\theta^k \int dx \varphi(x) f(x|\theta) - \psi(\theta)\partial_\theta^k\int dx f(x|\theta)\\ &= \partial_\theta^k \psi(\theta). \end{align} $$

よって,

$$ \begin{align} B_{ij} &= \bracket{\frac{\partial_\theta^i f(X|\theta)}{f(X|\theta)} \frac{\partial_\theta^j f(X|\theta)}{f(X|\theta)}}\\ C_i &= \partial_\theta^i \psi(\theta) \end{align} $$

とすれば,

$$ \begin{align} \mathrm{C} [y] = \begin{pmatrix} \mathrm{Var}[\varphi(X)-\psi(\theta)] & C\mathrm{T}\\\ C & B \end{pmatrix}. \end{align} $$

$B$が正則であると仮定しているので, 次のような行列が定義できる:

$$ \begin{align} S = \begin{pmatrix} 1 & 0\\\ -B^{-1}C & I \end{pmatrix}. \end{align} $$

$B$が対象行列であることに注意して$S, S^\mathrm{T}$を共分散行列の両側からかけると,

$$ \begin{align} S^\mathrm{T} \mathrm{C}[y] S &= \begin{pmatrix} 1 & -C^\mathrm{T}B^{-1}\\\ 0 & I \end{pmatrix} \begin{pmatrix} \mathrm{Var}[\varphi(X)-\psi(\theta)] & C\mathrm{T}\\\ C & B \end{pmatrix} \begin{pmatrix} 1 & 0\\\ -B^{-1}C & I \end{pmatrix}\\ &= \begin{pmatrix} 1 & -C^\mathrm{T}B^{-1}\\\ 0 & I \end{pmatrix} \begin{pmatrix} \mathrm{Var}[\varphi(X)-\psi(\theta)] -C^\mathrm{T}B^{-1}C & C^\mathrm{T}\\\ 0 & B \end{pmatrix}\\ &= \begin{pmatrix} \mathrm{Var}[\varphi(X)-\psi(\theta)] -C^\mathrm{T}B^{-1}C & 0\\\ 0 & B \end{pmatrix}. \end{align} $$

ここで, $S$が正定値であることと共分散行列は半正定値であることから,

$$ \begin{align} \mathrm{Var}[\varphi(X)-\psi(\theta)] -C^\mathrm{T}B^{-1}C \geq 0. \end{align} $$

2019-12-11

Cramér-Rao inequality

確率不等式

Cramér-Rao 不等式

$ X=(X_1, \ldots, X_n)$の分布が母数$ \theta$を用いて$ f(X_1, \ldots, X_n|\theta)$と表せるとする.
$ \varphi(X)$が$ \psi(\theta)$の不偏推定量, つまり$ \left\langle\varphi(X)\right\rangle=\psi(\theta)$のとき,

$$ \begin{align} \mathrm{Var}[\psi(X)] \geq \frac{(\partial_\theta \psi(\theta))^2}{\mathcal{I}(\theta)}. \end{align} $$

特に, $ X_1, \ldots, X_n$がi.i.d. のとき,

$$ \begin{align} \mathrm{Var}[\psi(X)] \geq \frac{(\partial_\theta \psi(\theta))^2}{n\mathcal{I}(\theta)}. \end{align} $$

ただし$ \mathcal{I}(\theta)$はFisher情報量で,

$$ \begin{align} \mathcal{I}(\theta) = \left\langle(\partial_\theta \ln f(X|\theta))^2\right\rangle \end{align} $$

証明

微分$ \partial_\theta$ と積分$ \int dx$は交換可能とすると,

$$ \begin{align} \partial_\theta \psi(\theta) &= \partial_\theta \left\langle\phi(X)\right\rangle\\ &= \int dx \partial_\theta f(x|\theta)\varphi(x)\\ &= \int dx f(x|\theta) \frac{\partial_\theta f(x|\theta)}{f(x|\theta)} \varphi(x)\\ &= \int dx f(x|\theta) \partial_\theta \ln f(x|\theta) \varphi(x)\\ &= \left\langle\varphi(X)\partial_\theta\ln f(X|\theta)\right\rangle. \tag{1} \end{align} $$

$$ \begin{align} \left\langle\partial_\theta\ln f(x|\theta)\right\rangle &= \int dx f(x|\theta)\frac{\partial_\theta f(x|\theta)}{f(x|\theta)}\\ &= \int dx \partial_\theta f(x|\theta)\\ &= \partial_\theta \int dx f(x|\theta)\\ &= \partial_\theta 1\\ &= 0. \tag{2} \end{align} $$

(1)$-$(2)$ \times\left\langle\varphi(X)\right\rangle$より,

$$ \begin{align} \partial_\theta \psi(\theta) = \left\langle(\varphi(X)-\left\langle\varphi(X)\right\rangle)\partial_\theta\ln f(X|\theta)\right\rangle. \end{align} $$

両辺を2乗して,

$$ \begin{align} (\partial_\theta \psi(X))^2 &= \left\langle(\varphi(X)-\left\langle\varphi(X)\right\rangle)\partial_\theta \ln f(X|\theta)\right\rangle^2\\ &\leq \left\langle(\varphi(X)-\left\langle\varphi(X)\right\rangle)^2\right\rangle\left\langle(\partial_\theta \ln f(X|\theta))^2\right\rangle\;(\because \mathrm{Cauchy-Schwartz\;不等式}). \end{align} $$

$ X_1, \ldots, X_n$がi.i.d.のとき,

$$ \begin{align} \partial_\theta \ln f(X|\theta) = \sum_{i=1}^n \partial_\theta \ln f(X_i|\theta). \end{align} $$

$ i\neq j$とすると,

$$ \begin{align} \left\langle\partial_\theta \ln f(X_i|\theta)\partial_\theta\ln f(X_j|\theta)\right\rangle &= \left\langle\partial_\theta \ln f(X_i|\theta)\right\rangle\left\langle\partial_\theta\ln f(X_j|\theta)\right\rangle \\ &= 0 \end{align} $$

であることに注意すれば,

$$ \begin{align} \left\langle(\partial_\theta\ln f(X|\theta))^2\right\rangle = n\left\langle(\partial_\theta\ln f(X_1|\theta))^2\right\rangle . \end{align} $$

2019-12-11

Jensen inequality

確率不等式

Jensen 不等式

$g$ を凸関数とすると $\left\langle g(X)\right\rangle\geq g(\left\langle X\right\rangle)$ .

証明

$\begin{aligned} \varphi(x) = \frac{g(x)-g(\left\langle X\right\rangle)}{x-\left\langle X\right\rangle} \end{aligned}$

とすると, $\varphi(x)$ は単調非減少である. よって,

$\begin{aligned} \sup_{x<\left\langle X\right\rangle} \varphi(x) \leq \Phi \leq \inf_{x>\left\langle X\right\rangle}\varphi(x) \end{aligned}$

を満たす $\Phi$ が存在する. $\sup, \inf$ の範囲に注意して $(x-\left\langle X\right\rangle)$ をかけると,

$\begin{aligned} (x-\left\langle X\right\rangle)\Phi \leq g(X) - g(\left\langle X\right\rangle). \end{aligned}$

両辺の期待値をとって,

$\begin{aligned} (\left\langle X\right\rangle-\left\langle X\right\rangle)\Phi = 0 \leq \left\langle g(X)\right\rangle - g(\left\langle X\right\rangle). \end{aligned}$

2019-12-11

Lyapunov inequality

確率不等式

Lyapunov不等式

$s>r>1$ のとき, $\left\langle|X|^r\right\rangle^{1/r}\leq\left\langle|X|^s\right\rangle^{1/s}$ .

証明

Hölderの不等式で $Y=1$ とすると,

$\begin{aligned} \left\langle|X|^r|1|\right\rangle\leq\left\langle|X|^{rp}\right\rangle^{1/p}\left\langle|1|^q\right\rangle^{1/q}, \frac{1}{p}+\frac{1}{q} = 1. \end{aligned}$

$p=\frac{s}{r}$ とできるので,

$\begin{aligned} \left\langle|X|^r\right\rangle \leq \left\langle|X|^s\right\rangle^{r/s}. \end{aligned}$

両辺を $1/r$ 乗すると,

$\begin{aligned} \left\langle|X|^r\right\rangle^{1/r} \leq \left\langle|X|^s\right\rangle^{1/s}. \end{aligned}$

2019-12-11

Minkowski inequality

確率不等式

Minkowski 不等式

$p\geq 1$ のとき, $\left\langle|X+Y|^p\right\rangle^{1/p}\leq\left\langle|X|^p\right\rangle^{1/p}+\left\langle|Y|^p\right\rangle^{1/p}$ .

証明

$p=1$ のときは三角不等式になり明らかに成り立つので $p>1$ を考える.

$\begin{aligned} \left\langle|X+Y|^p\right\rangle &\leq \left\langle(|X|+|Y|)|X+Y|^{p-1}\right\rangle\\ &= \left\langle|X||X+Y|^{p-1}\right\rangle+\left\langle|Y||X+Y|^{p-1}\right\rangle. \end{aligned}$

$q=\frac{p}{p-1}$ とすると, Hölder不等式から

$\begin{aligned} \left\langle|X||X+Y|^{p-1}\right\rangle+\left\langle|Y||X+Y|^{p-1}\right\rangle &\leq \left\langle|X|^p\right\rangle^{1/p} \left\langle|X+Y|^{(p-1)q}\right\rangle^{1/q}+\left\langle|Y|^p\right\rangle^{1/p} \left\langle|X+Y|^{(p-1)q}\right\rangle^{1/q}\\ &= \left(\left\langle|X|^p\right\rangle^{1/p}+\left\langle|Y|^p\right\rangle^{1/p}\right)\left\langle|X+Y|^p\right\rangle^\frac{p-1}{p}. \end{aligned}$

よって,

$\begin{aligned} \left\langle|X+Y|^p\right\rangle^{1-\frac{p-1}{p}} = \left\langle|X+Y|^p\right\rangle^{1/p} \leq \left\langle|X|^p\right\rangle^{1/p}+\left\langle|Y|^p\right\rangle^{1/p}. \end{aligned}$

2019-12-11

Hölder inequality

確率不等式

Hölder 不等式

$p, q>0$ が $\frac{1}{p}+\frac{1}{q}=1$ を満たすとき

$\begin{aligned} \left\langle |XY| \right\rangle \leq \left\langle |X|^p \right\rangle ^{\frac{1}{p}} \left\langle |Y|^q \right\rangle ^{\frac{1}{q}}. \end{aligned}$

証明

① まずはYoung inequalityと呼ばれる以下の不等式を示す. $a, b>0$ に対して,

$\begin{aligned} \frac{1}{p}a^p +\frac{1}{q}b^q \geq ab. \end{aligned}$

$b$ を定数とみなして,

$\begin{aligned} g(a) = \frac{1}{p}a^p + \frac{1}{q}b^q - ab \end{aligned}$

の最小値を調べる. ただし $g(x)$ は凸関数なので1階微分のみ調べればよい.

$\begin{aligned} g^\prime(a) = a^{p-1} - b. \end{aligned}$

よって $g$ を最小とする $a$ は $a=b^{\frac{1}{p-1}}$

$\begin{aligned} g(b^{\frac{1}{p-1}}) &= \frac{1}{p}b^{\frac{p}{p-1}}+\frac{1}{q}b^q - b^{\frac{p}{p-1}}\\ &= \frac{1}{q}b^q - \left(1-\frac{1}{p}\right)b^{\frac{1}{1-\frac{1}{p}}}\\ &= 0. \end{aligned}$

よって $g(a)\geq 0$ .
② $\left\langle |X|\right\rangle=0$ または $\left\langle |Y|\right\rangle=0$ のときは明らかに成り立つのでそれ以外の場合を考える.
①で, $a=\frac{|X|}{\left\langle|X|^p\right\rangle^{1/p}}$ , $b=\frac{|Y|}{\left\langle |Y|^q\right\rangle ^{1/q}}$ とすると,

$\begin{aligned} \frac{1}{p}\frac{|X|^p}{\left\langle |X|^p\right\rangle} + \frac{1}{q}\frac{|Y|^q}{\left\langle |Y|^q\right\rangle} \geq \frac{|X||Y|}{\left\langle |X|^p\right\rangle^{1/p}\left\langle |Y|^q\right\rangle^{1/q}}. \end{aligned}$

両辺の期待値を考えると,

$\begin{aligned} \frac{1}{p} + \frac{1}{q} = 1 \geq \frac{\left\langle |X||Y|\right\rangle}{\left\langle |X|^p\right\rangle^{1/p}\left\langle |Y|^q\right\rangle^{1/q}}. \end{aligned}$