$X$を確率変数とし、その平均を$\mu =\mathbb{E}[X]$とする。このとき、ある正数$\sigma$が存在して

$$\mathbb{E}[e^{\lambda (X-\mu )}]\le e^{{\sigma }^2{\lambda }^2/2}$$

を任意の$\lambda$について満たすとき、$X$はパラメータ$\sigma$のsub-Gaussianであるという。

これが確率変数のsub-Gaussian性です。性の付き方おかしい気がしますが、、。日本語で言うと準ガウス性といったところでしょうか。訳しているところ見たことありませんが。

確率分布$f(x)$に従う乱数を生成したいとする。このとき、次のように一様乱数を用いて目的の乱数を生成する方法を棄却法という。

1. $u_1$を$f(x)$の定義域$[a,b]$上の一様分布とする。
2. $u_2$を$f(x)$の値域$[0,c]$上の一様分布とする。
3. $u_2<f(u_1)$でなければ棄却して以上の手順を繰り返し行う。
4. $u_1,u_2$が上の条件を満たしたとき$u_1$を生成した乱数$x$とする。

棄却法ではこのようにして条件を満たすまで何度も一様分布に従う乱数を生成する。直観的にも採用された乱数列は目的の確率分布$f(x)$に従う。

$U$を一様分布$U(0,1)$に従う乱数とする。このとき、ある確率密度関数$f(x)$に対する累積分布関数$F(x)$の逆関数$F^{-1}$を用いて、乱数$X$を$X=F^{-1}(U)$と定義すると$X$は分布$f(x)$に従う。

マルコフの不等式 （Markov's inequality）

正の値を取る確率変数$X$について

$$\mathbb{P}[X\ge t]\le \frac{\mathbb{E}[X]}{t}$$

が成立する。これをMarkovの不等式という。これを示す。

主張

確率空間$(\mathrm{\Omega },A,\mathbb{P})$ 事象列$A_1,A_2,\dots ,A_n\subset A$ 事象列の上極限を

$$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}{A}_n=\bigcap _{n=1}^{\mathrm{\infty }}\bigcup _{k=n}^{\mathrm{\infty }}{A}_k$$

と定義する。このとき、

$$\sum _{n=1}^{\mathrm{\infty }}\mathbb{P}[A_n]<\mathrm{\infty }\Rightarrow \mathbb{P}[\underset{n\to \mathrm{\infty }}{\mathrm{lim\; sup}}{A}_n]=0$$

が成立。以上が補題の主張。