東京工業大学 情報理工学院 数理・計算科学系 2023年8月実施 概率统计

标签：

• TITech
• Independence-of-Random-Variables
• Expectation-and-Variance

Author

思齐塾, 祭音Myyura

Description

$\mathbb{P}, \mathbb{E}$ はそれぞれ確率，期待値を表すものとする． $n$ を正の整数， $p_1, p_2, \dots, p_n$ を $(0, 1)$ 上の実数として，確率変数 $X_1, X_2, \dots, X_n$ は互いに独立に，

$$\mathbb{P}(X_i = 1) = p_i, \quad \mathbb{P}(X_i = 0) = 1 - p_i, \quad i = 1, 2, \dots, n,$$

を満たすものとする． $S = X_1 + X_2 + \dots + X_n$ として以下の問いに答えよ．

(1) $S$ の期待値 $\mu = \mathbb{E}[S]$ を $p_1, p_2, \dots, p_n$ を用いて表せ．

(2) $t$ を実数として， $S$ のモーメント母関数 $M(t) = \mathbb{E}[e^{tS}]$ を $p_1, p_2, \dots, p_n, t$ を用いて表し，任意の $t \in (-\infty, \infty)$ に対して $M(t) \le \exp(\mu(e^t - 1))$ が成り立つことを示せ．

(3) 任意の $a \ge 0, t > 0$ に対して $\mathbb{P}(S > a) \le e^{-at}M(t)$ が成り立つことを示せ．

(4) 任意の $\epsilon > 0$ に対して $\mathbb{P}(S > (1 + \epsilon)\mu) \le e^{-\delta\mu}$ を満たす $\delta > 0$ が存在することを示せ．

题目描述

以 $\mathbb P$、$\mathbb E$ 分别表示概率和期望。设 $n$ 为正整数，$p_1,\ldots,p_n\in(0,1)$；随机变量 $X_1,\ldots,X_n$ 相互独立，且

$$\mathbb P(X_i=1)=p_i, \qquad \mathbb P(X_i=0)=1-p_i \quad(i=1,\ldots,n).$$

令

$$S=X_1+\cdots+X_n.$$

1. 用 $p_1,\ldots,p_n$ 表示 $\mu=\mathbb E[S]$。
2. 对实数 $t$，用 $p_1,\ldots,p_n,t$ 表示 $S$ 的矩母函数

$$M(t)=\mathbb E[e^{tS}],$$

并证明对每个 $t\in\mathbb R$，

$$M(t)\leq\exp\!\bigl(\mu(e^t-1)\bigr).$$

3. 证明对任意 $a\geq0$、$t>0$，

$$\mathbb P(S>a)\leq e^{-at}M(t).$$

4. 证明对任意 $\epsilon>0$，都存在 $\delta>0$，使

$$\mathbb P\bigl(S>(1+\epsilon)\mu\bigr) \leq e^{-\delta\mu}.$$

Kai

解答

(1)

期待値の線形性から

$$\boxed{\mu=\mathbb E[S]=\sum_{i=1}^n\mathbb E[X_i]=\sum_{i=1}^np_i}.$$

(2)

独立性より

$$\begin{aligned} M(t)&=\mathbb E\left[\prod_{i=1}^ne^{tX_i}\right] =\prod_{i=1}^n\mathbb E[e^{tX_i}]\\ &=\boxed{\prod_{i=1}^n(1-p_i+p_ie^t)} =\prod_{i=1}^n\left(1+p_i(e^t-1)\right). \end{aligned}$$

$1+u\le e^u$ を $u=p_i(e^t-1)$ に適用すると、任意の実数 $t$ について

$$M(t)\le\prod_{i=1}^n\exp(p_i(e^t-1)) =\exp\left((e^t-1)\sum_{i=1}^np_i\right) =\boxed{\exp(\mu(e^t-1))}.$$

(3)

$t>0$ では $x\mapsto e^{tx}$ は単調増加である。非負確率変数 $e^{tS}$ にマルコフの不等式を適用すると

$$\mathbb P(S>a)=\mathbb P(e^{tS}>e^{ta}) \le e^{-at}\mathbb E[e^{tS}] =\boxed{e^{-at}M(t)}.$$

(4)

(2), (3)で $a=(1+\epsilon)\mu$ とすると

$$\mathbb P(S>(1+\epsilon)\mu) \le\exp\left(-\mu\{(1+\epsilon)t-(e^t-1)\}\right).$$

$t=\log(1+\epsilon)>0$ と選び

$$\delta=(1+\epsilon)\log(1+\epsilon)-\epsilon$$

とおく。 $\delta(0)=0$ かつ $\delta'(\epsilon)=\log(1+\epsilon)>0$ なので、 $\epsilon>0$ なら $\delta>0$ である。従って

$$\boxed{ \mathbb P(S>(1+\epsilon)\mu)\le e^{-\delta\mu}, \quad \delta=(1+\epsilon)\log(1+\epsilon)-\epsilon>0 }.$$