Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

漸近理論

関係する定理

マルコフの不等式

証明

指示関数I(⋅)I(\cdot)をもちいて

E[X]=E[X{I(X≥c)+I(X<c)}]≥E[XI(X≥c)]≥cE[I(X≥c)]=cP(X≥c)\begin{aligned} E[X] &= E[X \{ I(X \geq c) + I(X < c) \} ]\\ & \geq E[X I(X \geq c) ]\\ & \geq c E[ I(X \geq c) ] = c P(X \geq c) \end{aligned}
(2)

マルコフの不等式は 期待値よりも極端に大きな値を取る確率が低い ことを意味する。

例えばc=5E[X]c = 5 E[X]とおけば

P(X≥5E[X])≤E[X]5E[X]=15P(X \geq 5 E[X]) \leq \frac{E[X]}{5 E[X]} = \frac{1}{5}
(3)
from scipy.stats import expon
mean = 2  # 期待値 E[X] = 2 の指数分布は scale=2
dist = expon(scale=mean)
threshold = 5 * mean # 5 * E[X]
# P(X >= 5 * E[X]) = 1 - CDF(threshold)
prob = 1 - dist.cdf(threshold)
upper_bound = 1 / 5 # マルコフの不等式の上限
print(f"P(X >= 5E[X]) = {prob:.2g}")
print(f"Markov Inequality Upper Bound = {upper_bound:.2g}")
P(X >= 5E[X]) = 0.0067
Markov Inequality Upper Bound = 0.2

チェビシェフの不等式

証明

Y=(X−μ)2Y=(X-\mu)^2とおき、YYにマルコフの不等式

P(X≥c)≤E[X]cP(X \geq c) \leq \frac{E[X]}{c}
(5)

を適用すれば、

P(Y≥c2)≤E[Y]c2=σ2c2P(Y \geq c^2) \leq \frac{E[Y]}{c^2} = \frac{\sigma^2}{c^2}
(6)

ここで Y≥c2⟺∣X−μ∣≥cY \geq c^2 \Longleftrightarrow|X-\mu| \geq c であるから P(Y≥c2)=P(∣X−μ∣≥c)P(Y \geq c^2) = P(|X - \mu| \geq c) となり

P(∣X−μ∣≥c)≤σ2c2P(|X-\mu|\geq c) \leq \frac{\sigma^2}{c^2}
(7)

が成立する

チェビシェフの不等式は 期待値から値が極端に離れる確率が低い ことを意味する。

例えばc=5σc = 5 \sigmaとおけば

P(∣X−μ∣≥5σ)≤σ25σ2=15P(|X-\mu|\geq 5\sigma) \leq \frac{\sigma^2}{5 \sigma^2} = \frac{1}{5}
(8)

例：2シグマ範囲

期待値からの2シグマ範囲には正規分布だと95%が入る。

import numpy as np
from scipy.stats import norm
mu = 0       # 平均
sigma = 1    # 標準偏差
lower = mu - 2 * sigma
upper = mu + 2 * sigma
dist = norm(loc=mu, scale=sigma)
# P(∣X−μ∣ ≤ 2σ) = P(μ−2σ ≤ X ≤ μ+2σ) = cdf(μ+2σ) - cdf(μ-2σ)
p_2sigma = dist.cdf(upper) - dist.cdf(lower) # P(-2σ <= X <= 2σ)
print(f"P(∣X−μ∣ ≤ 2σ) = {p_2sigma:.3f}")
P(∣X−μ∣ ≤ 2σ) = 0.954
Source
import matplotlib.pyplot as plt

# plot
fig, ax = plt.subplots(figsize=[5, 2])
x = np.linspace(-4, 4, 100)
y = dist.pdf(x)
ax.plot(x, y)

# 2σ points
x_2sig = dist.ppf(dist.cdf(2 * sigma))
ax.axvline(mu + x_2sig, color="gray", linestyle="--")
ax.axvline(mu - x_2sig, color="gray", linestyle="--")
ax.text(mu + x_2sig, 0.1, f" μ+2σ", ha="left", color="gray")
ax.text(mu - x_2sig, 0.1, f"μ−2σ ", ha="right", color="gray")

x = np.linspace(mu - x_2sig, mu + x_2sig, 100)
y = dist.pdf(x)
ax.fill_between(x, y, 0, alpha=0.3)

ax.text(0, 0.01, f"P(μ−2σ ≤ X ≤ μ+2σ)\n= {p_2sigma:.3f}", ha="center", color="darkblue")
plt.show()
<Figure size 500x200 with 1 Axes>

チェビシェフの不等式による任意の分布への下限は

P(X∈[μ−2σ,μ+2σ])=P(∣X−μ∣≤2σ)≥1−P(∣X−μ∣≥2σ)=1−σ24σ2=1−14=34\begin{aligned} P(X \in [\mu-2\sigma, \mu+2\sigma]) = P(|X - \mu| \leq 2\sigma) &\geq 1 - P(|X - \mu| \geq 2\sigma)\\ &= 1 - \frac{\sigma^2}{4\sigma^2}\\ &= 1 - \frac{1}{4}\\ &= \frac{3}{4}\\ \end{aligned}
(9)

となり、正規分布以外でも75%以上あることがわかる

例：期待値からのズレ

nn個のサンプルX1,…,XnX_1,\dots,X_nがi.i.d.であるとする。これらのサンプルの標本平均Xˉ\bar{X}がその期待値E[Xˉ]E[\bar{X}]からどれだけズレるかを見てみる

P(∣Xˉ−E[Xˉ]∣≥c)≤Var⁡[Xˉ]c2P(|\bar{X} - E[\bar{X}]|\geq c) \leq \frac{ \operatorname{Var}[\bar{X}]}{c^2}
(10)

もしc=1c=1なら、標本平均と期待値の差の絶対値が1以上になる確率はその分散が上限になるということ。

P(∣Xˉ−E[Xˉ]∣≥1)≤Var⁡[Xˉ]=Var⁡[X]nP(|\bar{X} - E[\bar{X}]|\geq 1) \leq \operatorname{Var}[\bar{X}] = \frac{ \operatorname{Var}[X] }{ n }
(11)

例えばサンプルが商談から成約したかどうかであり、真の成約率が20%という確率変数X∼Ber(p=0.2)X\sim Ber(p=0.2) の実現値だとすると、E[Xˉ]=0.2,Var⁡[Xˉ]=p(1−p)=0.16E[\bar{X}]=0.2, \operatorname{Var}[\bar{X}] = p(1-p) = 0.16で、このときc=0.1c=0.1とおけば

P(∣Xˉ−0.2∣≥0.1)≤0.16n×0.12=16nP(|\bar{X} - 0.2| \geq 0.1) \leq \frac{0.16}{ n \times 0.1^2 } = \frac{ 16 }{ n }
(12)

となり、仮にn=100n=100なら16%程度の確率が上限（分布によらない上限）になることがわかる

Source
import numpy as np
from scipy.stats import bernoulli
import matplotlib.pyplot as plt
p = 0.2
dist = bernoulli(p=p)
n = 100
c = 0.1
bound = p * (1-p) / n / c**2

n_trials = 1000
x_bars = []
for i in range(n_trials):
    x = dist.rvs(size=n, random_state=i)
    x_bars.append( x.mean() )

fig, ax = plt.subplots(figsize=[4, 3])
ax.hist(x_bars, bins=10)
ax.axvline(p + c, color="gray", linestyle="--")
ax.axvline(p - c, color="gray", linestyle="--")

x_bars = np.array(x_bars)
is_over = np.abs(x_bars - p) >= c

ax.set(
    # title=r"histogram of $\bar{X}$",
    title=r"num of |$\bar{X} - p| \geq c$ =" + f"{is_over.sum()}, num of simulations={n_trials} (→{is_over.sum()}/{n_trials} = {is_over.sum() / n_trials:.1%})",
    xlabel=r"$\bar{X}$",
    ylabel="count"
)
fig.show()
<Figure size 400x300 with 1 Axes>

ヘフディングの不等式

チェビシェフの不等式は幅広い範囲で有用ではあるものの、裾の確率を緩く評価してしまう。

例えば上記の期待値からのズレの例

P(∣Xˉ−0.2∣≥0.1)≤16nP(|\bar{X} - 0.2| \geq 0.1) \leq \frac{ 16 }{ n }
(13)

では、n=1000n=1000であっても「1.6%1.6\%は起こるかもしれない」というかなり安全に寄った評価をしてしまう。これは実際にシミュレーションすると0%になるレベルの稀少な事例にもかかわらず。

Source
import numpy as np
from scipy.stats import bernoulli
import matplotlib.pyplot as plt
p = 0.2
dist = bernoulli(p=p)
n = 1000
c = 0.1
bound = p * (1-p) / n / c**2

n_trials = 1000
x_bars = []
for i in range(n_trials):
    x = dist.rvs(size=n, random_state=i)
    x_bars.append( x.mean() )

fig, ax = plt.subplots(figsize=[4, 3])
ax.hist(x_bars, bins=10)
ax.axvline(p + c, color="gray", linestyle="--")
ax.axvline(p - c, color="gray", linestyle="--")

x_bars = np.array(x_bars)
is_over = np.abs(x_bars - p) >= c

ax.set(
    # title=r"histogram of $\bar{X}$",
    title=r"num of |$\bar{X} - p| \geq c$ =" + f"{is_over.sum()}, num of simulations={n_trials} (→{is_over.sum()}/{n_trials} = {is_over.sum() / n_trials:.1%})",
    xlabel=r"$\bar{X}$",
    ylabel="count"
)
fig.show()
<Figure size 400x300 with 1 Axes>

このような裾の確率をより厳しく抑えるのに役立つのが ヘフディングの不等式 (Hoeffding’s inequality)

すべての確率変数XiX_iが区間[0,1][0,1]に値を取る場合はもっと単純に

P(∣Xˉ−E[Xˉ]∣≥c)≤2exp⁡(−2nc2)P(|\bar{X}-E[\bar{X}]| \geq c) \leq 2 \exp( -2 n c^2 )
(15)

となる。

前出の成約率の例だと、n=1000,c=0.1n=1000, c=0.1のとき

P(∣Xˉ−E[Xˉ]∣≥0.1)≤2exp⁡(−2×1000×0.12)=2exp⁡(−20)≈4.122×10−9≈0\begin{aligned} P(|\bar{X}-E[\bar{X}]| \geq 0.1) &\leq 2 \exp( -2 \times 1000 \times 0.1^2 )\\ &= 2 \exp( -20 )\\ &\approx 4.122 \times 10^{-9} \approx 0 \end{aligned}
(16)

となり、観測結果に近くなる。

しかしn=100,c=0.1n=100, c=0.1のとき

P(∣Xˉ−E[Xˉ]∣≥0.1)≤2exp⁡(−2×100×0.12)=2exp⁡(−2)≈0.27\begin{aligned} P(|\bar{X}-E[\bar{X}]| \geq 0.1) &\leq 2 \exp( -2 \times 100 \times 0.1^2 )\\ &= 2 \exp( -2 )\\ &\approx 0.27 \end{aligned}
(17)

とだいぶ大きく評価することもある様子…？

確率収束

平均2乗収束

チェビシェフの不等式を使うと「確率変数列がある確率変数に平均2乗収束するならば確率収束する」という命題が導かれる → 大数の法則

例：大数の法則

証明

ε>0\varepsilon > 0を任意の定数とする。E[Xˉn]=μ,Var[Xˉn]=σ2/nE[\bar{X}_n] = \mu, \mathrm{Var}[\bar{X}_n] = \sigma^2/nであるから、Xˉ\bar{X}にチェビシェフの不等式を適用すれば

P(∣Xˉn−μ∣≥ε)≤σ2nε2P(|\bar{X}_n-\mu| \geq \varepsilon) \leq \frac{\sigma^2}{n \varepsilon^2}
(23)

となる。ここでn→∞n \to \inftyとおけば右辺は0に収束するから

∀ε>0,lim⁡n→∞P(∣Xˉn−μ∣≥ε)=0\forall \varepsilon > 0, \quad \lim_{n\to \infty} P(|\bar{X}_n-\mu| \geq \varepsilon) = 0
(24)

例：推定量の一致性

推定量θ^\hat{\theta}が真のパラメータθ\thetaに確率収束

θ^→pθ\hat{\theta} \overset{p}{\to} \theta
(25)

するとき、その推定量は一致性（consistency）を持つという

概収束

分布収束

例：中心極限定理

確率変数列{Xn}n=1∞\{X_n\}_{n=1}^{\infty}はi.i.d.で平均μ:=E[Xi]\mu:=E[X_i]と分散σ2:=Var(Xi)\sigma^2:=Var(X_i)が存在するとする。このとき、以下の分布収束が成り立つ

n(Xˉ−μ)→dN(0,σ2),n→∞\sqrt{n} (\bar{X} - \mu) \overset{d}{\to} N(0, \sigma^2) ,\hspace{1em} n\to\infty
(29)

ここでN(0,σ2)N(0, \sigma^2)をXˉ\bar{X}の漸近分布（asymptoticd distribution）という。

（※なお、N(0,σ2)N(0, \sigma^2)は正規分布を表す記号ではなく、正規分布に従う確率変数を意味するので注意。ややこしい記法だが標準的でよく見られる書き方である）

なお、上の式は

Xˉ−μ→d1nN(0,σ2)=N(0,σ2n)\bar{X} - \mu \overset{d}{\to} \frac{1}{\sqrt{n}} N(0, \sigma^2) = N\left(0, \frac{\sigma^2}{n}\right)
(30)

のように整理できる。

（σ2\sigma^2は未知だが標本分散を用いてもこの関係性が成り立つ）

統計学
漸近理論
統計学
漸近オーダーの表記法