HDPブックを読む（１）

HDP (High Dimensional Probability)ブック

本はネット上でPDFをダウンロードできる．
https://www.math.uci.edu/~rvershyn/papers/HDP-book/HDP-book.html

ここでは，いくつか問題演習の答えやヒントを書きたい（忘れそうなので）．
とりあえずは，２章まで．

0.0.5

証明したいのは，

$$\left(\frac{n}{m}\right)^m\leq \binom{n}{m} \leq \sum_{k=0}^m\binom{n}{k} \leq \left(\frac{en}{m}\right)^m$$

まず次を証明する．$m < a < n$のとき，$\frac{n}{m} \leq \frac{n-a}{m-a}$．

証明：$m \leq n \Rightarrow ma \leq na \Rightarrow ma - mn \leq na - mn \Rightarrow m(a-n) \leq n(a-m) \Rightarrow n/m \leq (n-a)/(m-a)$．

よって，

$$\left(\frac{n}{m}\right)^m = \frac{n}{m}\cdot \dots \cdot \frac{n}{m} \leq \frac{n}{m} \cdot \frac{n-1}{m-1} \cdot \dots \cdot \frac{n-m+1}{1} = \binom{n}{m}$$

これで一番左側の証明は終わり．
真ん中は自明（$k=m$を総和が含んでいるので）．

最後は一番右．両辺に$(m/n)^m$をかけることで，

$$\left(\frac{m}{n}\right)^m\sum_{k=0}^m \binom{n}{k} \leq e^m$$

を示せばいいことがわかる．ここで左辺について，

$$\sum_{k=0}^m \left(\frac{m}{n}\right)^m \binom{n}{k} \leq \sum_{k=0}^m \left(\frac{m}{n}\right)^k \binom{n}{k} \leq \sum_{k=0}^n \left(\frac{m}{n}\right)^k \binom{n}{k} = \left(1+ \frac{m}{n}\right)^n \leq e^{m/n\cdot n} = e^m$$

よりOK（$m/n<1$と$1+x \leq e^x$に注意）．

0.0.6

Corollary 0.0.4の証明の最後の方で，めちゃくちゃ大雑把に$N^k$みたいなので抑えている部分を，組み合わせの式で抑えて，Exercise 0.0.5を使えばOK.

1.2.3

Lemma 1.2.1を使って積分に置き換えたあと，置換積分で$t^p = u$みたいにすればOK.積分の中の$pt^{p-1}$というのは，置換積分で出てくる微分の部分

2.2.3

$$\cosh x = \sum_{k=0}^\infty \frac{x^{2k}}{(2k)!}$$

である．ここで，$2^kk!\leq(2k)!$に注意．これを代入して整理すれば，とける．

2.2.9

これが容易に解ける人間は普通ではない．

(a)

こっちは簡単．使える情報からも明らかにチェビシェフの不等式を使うんだろうくらいはわかる．チェビシェフの不等式から

$$\Pr \left(\left|\frac{1}{N}\sum X_i - \mu\right| \geq t\right)\leq \frac{\sigma^2}{nt^2}$$

である．したがって，平均が$(\mu-\epsilon, \mu+\epsilon)$の間に落ちない可能性は，

$$\Pr \left(\left|\frac{1}{N}\sum X_i - \mu\right| \geq \epsilon\right)\leq \frac{\sigma^2}{n\epsilon^2}$$

である．ここで知りたいのはこの間に平均が落っこちる可能性なので，

$$1 - \Pr \left(\left|\frac{1}{N}\sum X_i - \mu\right| \geq \epsilon\right) \geq 1 - \frac{\sigma^2}{n\epsilon^2} \geq \frac{3}{4}$$

となるようにすればいい．よって，式を整理して，$n = O(\sigma^2/\epsilon^2)$を得る．

(b)

こっちを解くのは思いつかなければ不可能だと思う．まず，$N = mk$とする．そして，$k$個の確率変数の平均から，$m$個の平均の推定量$\hat{\mu}_1, \dots, \hat{\mu}_m$を得る．これの中央値を$\hat{\mu} = \textrm{median}(\hat{\mu}_1, \dots, \hat{\mu}_m)$としよう．また，新しい確率変数$Y_i = 1(|\hat{\mu}_i - \mu|>\epsilon)$とおく．$m$をいくつ以上にするかだが，(a)に合わせて少なくとも$1/4$の確率で，$\epsilon$ accurateであるようにする（すなわち$m = O(\sigma^2/\epsilon^2)$である．したがって，$\mathbb{E}Y_i\leq 1/4$である．）．すると，

$$\Pr(|\hat{\mu}-\mu| > \epsilon) = \Pr\left(\sum_{i=1}^m Y_i > \frac{m}{2}\right) = \Pr\left(\sum_{i=1}^m(Y_i - \mathbb{E}Y_i) > \frac{m}{2} - m\mathbb{E}Y_i\right)$$

となる．ここで，中央値を考えるときに真の平均$\mu$からの距離で考えているので，もし$\mu$に近い順に$(\hat{\mu}_1, \dots, \hat{\mu}_m)$を並び替えたときに，インデックスが$m/2$の要素（中央値）が$\epsilon$の範囲を超えていたら，条件を満たさないと考えられることを使って，式変形している．
ここで，Hoeffding's inequalityを使うと，

$$\Pr(|\hat{\mu}-\mu| > \epsilon) \leq \exp\left(-\frac{2}{m}\left(\frac{m}{4} + \left(\frac{1}{4}-\mathbb{E}Y_i\right)\right)^2\right)\leq \exp\left(-\frac{m}{8}\right) = \delta$$

を得るので，結局$m = O(\log(\delta^{-1}))$とすればよく，以上より$N = km = O(\log(\delta^{-1})\sigma^2/\epsilon^2)$である．

2.3.3

ポアソン分布のMGFが，$\exp(\lambda(e^t-1))$であることからすぐ解ける．

グラフあたりの話はやる気にならないので，飛ばす（必要になったらやるかも）．

2.5.4

$\exp(\lambda \mathbb{E}X)\leq \mathbb{E}\exp(\lambda X)\leq \exp(K^2\lambda^2)$ということは，$\lambda \mathbb{E}X \leq K^2\lambda^2$なので，$\lambda(\mathbb{E}X-K^2 \lambda) \leq 0$がすべての$\lambda\in \mathbb{R}$で成り立たねばならない．これは実は，$\mathbb{E}X=0$でないと，満たすことができないので，$\mathbb{E}X=0$である．

2.5.5

(a)

要するになんで$\lambda$はある定数で抑えた範囲にせねばならないのかという話．これは正規分布の場合は，$\lambda \mapsto \mathbb{E}\exp(\lambda^2 X^2) = 2\int_0^\infty e^{x^2\left(\lambda^2-\frac{1}{2}\right)}dx$なので，$\lambda \geq 1/\sqrt{2}$としないと収束しないことからすぐわかる．

(b)

$$\Pr(X \geq t) = \Pr(X^2\geq t^2) = \Pr(e^{\lambda^2X^2}\geq e^{\lambda^2t^2})\leq e^{-\lambda^2 t^2}\mathbb{E}e^{\lambda^2X^2}\leq e^{-\lambda^2 t^2}e^{K\lambda^2} = e^{\lambda^2(K-t^2)}$$

ということは，$t^2>K$のとき，$\lambda$は任意なので，$\Pr(X\geq t)<0$とならねばならず，要するに確率$0$ということ．よって$\|X\|_\infty<\infty$

2.5.7と2.7.11

2.7.11が一般の場合なので，そちらを証明する．これってそんなに簡単なんだろうか．

まず$\|0\|_\psi = 0$は明らか（どんな$t$でも条件を満たすので，その下限は0）．$\|X\|_\psi = 0$のときは，$\lim_{t\to 0} \mathbb{E}\psi(|X|/t)\leq 1$が成立してなければならない．すべての$x$について，$\psi(|x|/t)$は$t$に関して単調減少なので，単調収束定理からほんとん確実に$\lim_{t\to 0} \mathbb{E}\psi(|X|/t) = \mathbb{E}\lim_{t\to 0}\psi(|X|/t)$が成り立つ（厳密なことを言うと，まず適当な定数$T\in \mathbb{R}_+$をとって，$t$の範囲を$t\in (0, T]$に置き換える．次に0に収束する任意の単調減少列$\{t_i\}_{i=1}^\infty \subset (0, T]$について，$\lim_{i\to \infty} \mathbb{E}\psi(|X|/t_i) = \mathbb{E}\lim_{i\to \infty}\psi(|X|/t_i)$が成り立っていることから，$t\to 0$の場合に交換可能なことが示される）．ここでもし，$|X|=0$がほとんど確実に成り立たないと，$\mathbb{E}\lim_{t\to 0}\psi(|X|/t)<\infty$とはならない．なぜなら，$\Pr(|X|\neq 0) > 0$と仮定すると，$|X| \neq 0$のとき，任意の$n\in \mathbb{N}$について，$n < \lim_{t\to 0}\psi(|X|/t)=\infty$でなければならないので，$\mathbb{E}\lim_{t\to 0} \psi(|X|/t) = \mathbb{E}1(|X|\neq 0)\lim_{t\to 0} \psi(|X|/t) > \mathbb{E}1(|X|\neq 0) n = \Pr(|X|\neq 0) n > 0$となる．ここで，任意の$n$について，これが成り立つので，結局$\mathbb{E}\lim_{t\to 0} \psi(|X|/t)$は有界ではない．したがって，$\Pr(|X|\neq 0)=0$でなければならない．よって$|X|=0 (a.s.)$である．

次に$c\in \mathbb{R}$について，$\|c X\|_\psi = |c|\|X\|_\psi$を示す．$\|c X\|_\psi = \inf\{t>0: \mathbb{E}\psi(|cX|/t)\leq 1\}$だが，$t = |c|s$とおくと，$\|c X\|_\psi = \inf\{|c|s>0: \mathbb{E}\psi(|X|/s)\leq 1\}$となって，結局$\|c X\|_\psi = |c| \|X\|$である．

最後に，三角不等式$\|X + Y\|_\psi \leq \|X\|_\psi + \|Y\|_\psi$を示す．書くのが面倒なので，ノルムの$\psi$を省略．次に注目する．

$$\psi\left(\frac{|X + Y|}{\|X\| + \|Y\|}\right) \leq \psi \left(\frac{|X| + |Y|}{\|X\| + \|Y\|}\right) = \psi \left(\frac{1}{\|X\| + \|Y\|}\left( \|X\|\frac{|X|}{\|X\|} + \|Y\|\frac{|Y|}{\|Y\|} \right)\right)$$

ここで，Jensenの不等式から，

$$\psi\left(\frac{|X + Y|}{\|X\| + \|Y\|}\right) \leq \frac{\|X\|}{\|X\| + \|Y\|} \psi\left( \frac{|X|}{\|X\|} \right) + \frac{\|Y\|}{\|X\| + \|Y\|} \psi\left( \frac{|Y|}{\|Y\|} \right)$$

である．ここで$\psi(|X|/\|X\|)\leq 1$と，$\psi(|Y|/\|Y\|)\leq 1$が成り立つことに注意（Orliczノルムの定義から明らか）．よって，

$$\psi\left(\frac{|X + Y|}{\|X\| + \|Y\|}\right) \leq 1$$

である．ここから，$t = \|X\| + \|Y\|$とと取れば，$\inf\{t>0: \mathbb{E}\psi(|X+Y|/t)\leq 1\}$は少なくとも存在することがわかる．よって，$X+Y$もまたOrlicz空間に属していることがわかる．また，明らかに$\|X\| + \|Y\| \geq \inf\{t>0: \mathbb{E}\psi(|X+Y|/t)\leq 1\} = \|X + Y\|$である．

2.5.10

解けなくて絶望

2.6.5

$\|a\|=\left(\sum_{i=1}^N a_i^2\right)^{1/2}$とする．これで全体を割れば，

$$1\leq \left\|\sum_{i=1}^N (a_i/\|a\|)X_i\right\|_{L^P} \leq CK\sqrt{p}$$

をえる．ここで，$\alpha = a/\|a\|$とすれば，

$$1\leq \left\|\sum_{i=1}^N \alpha_i X_i\right\|_{L^P} \leq CK\sqrt{p}$$

が示すべきもの．まず左辺を示す．こういうときはJensenで無理やり$p$を消す．すなわち

$$\left\|\sum_{i=1}^N \alpha_i X_i\right\|_{L^P} = \left(\mathbb{E}\left| \sum_{i=1}^N \alpha_i X_i \right|^p\right)^{1/p}=\left[\mathbb{E}\left( \left( \sum_{i=1}^N \alpha_i X_i \right)^2 \right)^{p/2}\right]^{1/p}\geq \left[\left( \mathbb{E}\left( \sum_{i=1}^N \alpha_i X_i \right)^2 \right)^{p/2}\right]^{1/p} = \left( \mathbb{E}\left( \sum_{i=1}^N \alpha_i X_i \right)^2 \right)^{1/2}$$

とする．ここで分散1と仮定されているので，

$$\left\|\sum_{i=1}^N \alpha_i X_i\right\|_{L^P} \geq 1$$

をえる．次に上界だが，そもそも$\sum_{i=1}^N \alpha_i X_i$もsub-gaussianなので，(ii)の性質が成り立って，$\|\sum_{i=1}^N \alpha_i X_i\|_{L^P}\leq C \|\sum_{i=1}^N \alpha_i X_i\|_{\psi_2} \sqrt{p}\leq C \sum_{i=1}^N \alpha_i \|X_i\|_{\psi_2} \sqrt{p} \leq C \max_i \|X_i\|_{\psi_2} \sqrt{p}$である．

2.6.6

これをヒントなしで解ける人間は，神である．まず，Holderの不等式から，確率変数$Z$について，$\|Z\|_{L^2} = \|Z\|_{L^1}^{1/4} \|Z\|_{L^3}^{3/4}$がなりたつ．ここで，$Z = \sum_i \alpha_i X_i$としよう．すると，左辺は分散が1なので，$\|Z\|_{L^2} = 1$となる．よって，

$$1 = \left\|\sum_i \alpha_i X_i \right\|_{L^1}^{1/4}\left\|\sum_i \alpha_i X_i \right\|_{L^3}^{3/4}$$

ここで，$L^3$側に2.6.5のKhintchine's inequalityが適用できることに気がつくと，

$$1\leq \frac{1}{\left\|\sum_i \alpha_i X_i \right\|_{L^1}} \leq CK\sqrt{3}$$

える．あとはいい感じに式を整理すれば証明完了．

2.6.7

おそらくHolderの不等式を使うときに，p, qに入れる値を変えればいいんだと思われるが，面倒なので証明するのは諦め．

2.7.2

これは本当にそのままProposition 2.5.2の証明をパクればできる．作業ゲー

飽きた．全部解くのは大変なので2章までに関しては，これぐらいで終わり．