本項では、私が本書を読み解くにあたって用いたリンクや数式を書いていく。

中心極限定理

「標本平均$\hat{\mu} \leq 5%$のときに、真の平均が$\mu=10%$である確率はどれくらいか」という問題を考える。これを中心極限定理を用いて、評価すると

  \lim_{n\rightarrow \infty} P\left[ \frac{\sqrt{n}(\hat{\mu}-\mu)}{\sigma} \leq x \right]
  =
  \Phi (x)
  ,\quad
  \Phi (x)
  =
  \int_{-\infty}^x \frac{1}{\sqrt{2 \pi}} \exp\left( -\frac{t^2}{2} \right)dt

と表すことができる。しかしどうやって標本平均と真の平均のずれ、つまり誤差を評価すればよいのだろうか？ここで絶対誤差と相対誤差について考えてみよう。

  絶対誤差
  =
  観測値-理論値
  ,\quad
  相対誤差
  =
  \frac{観測値-理論値}{理論値}

例えば中心極限定理を用いる。真の生起確率が$0.01%$、絶対誤差が$1%$であったとしよう。このとき相対誤差は

  相対誤差
  =
  \frac{観測値-理論値}{理論値}
  =
  \frac{1\%}{0.01\%}
  =
  100

となってしまうのである。つまり絶対誤差が$1%$であっても、理論値が小さい場合は相対誤差が大きくなってしまう場合があるのである。反対に理論値が大きい場合、例えば真の生起確率が$30%$であるときは

  相対誤差
  =
  \frac{1\%}{30\%}
  =
  0.333\cdots

となり、相対誤差は小さくなる。

低確率で起きる事象の確率を評価

中心極限定理では、高確率で起きる事象の確率を近似する場合は、有効な定理だが、低確率で起きる事象の確率を評価する場合は役に立たない。ここでは「低確率で起きる事象の確率」の一例として、標本平均が真の平均から大幅にずれる確率である裾確率を考え、裾確立をどのようにして評価するかを検討する。

裾確率の評価式として最も単純なのが「へフディングの不等式」である。

互いに独立で同一な分布に従っている$X_i \sim [0,1] $と、任意の$\Delta>0$に対して

  P[\hat{\mu}\leq \mu-\Delta]
  \leq
  e^{-2n\Delta^2}
  \\
  P[\hat{\mu}\geq \mu+\Delta]
  \leq
  e^{-2n\Delta^2}

が成立する($i=1,\cdots,n$)。

この不等式より標本平均$\hat{\mu}$が真の平均$\mu$から$\Delta$だけずれる確率は、指数関数的に減少していくことがわかる。

マルコフの不等式

確率変数$X$が$P(X\geq0)=1$ならば、実数$a>0$に対して

  P(X\geq a) 
  \leq
  \frac{E(X)}{a}

が成立する。

＜証明＞

確率変数が離散型の場合を証明する。$A={ X\geq a},A^c={ X< a}$とする。

\begin{align*}
  E(X) 
  &= 
  \sum_x xf(x)
  \\ &=
  \sum_{x\in A} xf(x) + \sum_{x\in A^c} xf(x)
  \\ &\geq
  \sum_{x\in A} xf(x)
  \\ &\geq
  \sum_{x\in A} af(x)
  \\ &=
  a P(\geq a)
\end{align*}

$X$は常に非負の確率変数なので$ \sum_{x\in A^c} xf(x)>0$である。

チェルノフの不等式

確率変数$Z$と任意の$t>0$に対して以下の不等式が成立。ただし$m_Z(s)$は積率母関数。

  P(Z\geq t)
  \leq
  \min_{s>0} e^{-st}m_Z(s)

＜証明＞

任意の$s>0$とする。

   P(Z\geq t)
   =
   P(sZ\geq st)
   =
   P(e^{sZ}\geq e^{st})

確率変数$e^{sZ}$と$e^{st}$は常に非負であるので、マルコフの不等式を用いて

  P(e^{sZ}\geq e^{st})
  \leq
  \frac{E[e^{sZ}]}{ e^{st}}
  =
  \frac{m_Z(s)}{ e^{st}}

が得られる。ここで全ての$s>0$で、最小となる$e^{-st}m_Z(s)$としても一般性を失わない。

ヘフティングの補題

確率変数$X$を$E(X)=0, P(a\leq X\leq b)=1$であるとする。全ての$s>0$に対して、以下が成立。

  E[e^{sX}]
  \leq
  \exp \left\{ \frac{s^2(b-a)^2}{8} \right\}

＜証明＞

方針として、$E[e^{sX}]$を不等式により上界で押さえる。その上界の最大値を調べて、ヘフティングの補題を得る。

初めに$y\in [a,b]$のとき、関数$f(y)=e^{sy}$として、その関数が下に凸の関数であることを用いると、$0<t<1$となる$t$を用いて

\begin{align*}
  f(ty_1+(1-t)y_2)
  \leq
  tf(y_1)+(1-t)f(y_2)
  \\
  \exp[s(ty_1+(1-t)y_2)]
  \leq
  te^{sy_1}+(1-t)e^{sy_2}
\end{align*}{}

が得られる。ここで$a\leq y \leq b$なので

  0
  \leq
  \frac{y-a}{b-a}
  \leq
  1

であり、$t=(y-a)/(b-a)$とすると$1-t$は

  1-t
  =
  \frac{b-y}{b-a}

となる。先ほどの不等式に$y_1=b, y_2=a$を代入すると

  \exp\left[ s\left( \frac{y-a}{b-a}b+\frac{b-y}{b-a}a \right) \right]
  =
  e^{sy}
  \leq
  \frac{y-a}{b-a}e^{sb}+\frac{b-y}{b-a}e^{sa}

$y$を確率変数$X$に置き換え、期待値を取ると

\begin{align*}
  e^{sX}
  &\leq
  \frac{X-a}{b-a}e^{sb}+\frac{b-X}{b-a}e^{sa}
  \\
  E[e^{sX}]
  &\leq
  \frac{E(X)-a}{b-a}e^{sb}+\frac{b-E(X)}{b-a}e^{sa}
  \\
  E[e^{sX}]
  &\leq
  \frac{b}{b-a}e^{sa}-\frac{a}{b-a}e^{sb}
\end{align*}{}

となる。ここで上界に$\log$をとって新たしい関数$\phi(u)$を導入し、また$p=b/(b-a), u=(b-a)s$とすると

\begin{align*}
  \phi(u)
  &=
  \log \left(pe^{sa}+(1-p)e^{sb} \right)
  \\&=
  u(p-1) +\log \left(p+(1-p)e^{u} \right)
\end{align*}{}

となる。この関数の最大値を考える。$\phi(u)$をテイラー展開すると、以下の式を満たす$\zeta=\zeta(u)$が存在する。

  \phi(u)
  =
  \phi(0)+\phi'(0)u+\frac{1}{2}\phi''(\zeta)u^2

まず$\phi(0)=0$は明らかであり、$\phi(u)$を$u$で微分して$0$を代入すると

\begin{align*}
  \phi'(u)
  &=
  (p-1)+1-\frac{p}{p+(1-p)e^u}
  \\
  \phi'(0)
  &=
  0
\end{align*}{}

となる。さらに$\phi''(u)$の最大値を考えるために、$\phi```(u)$を求めて$=0$とおく。

\begin{align*}
  \phi''(u)
  &=
  \frac{p(1-p)e^u}{(p+(1-p)e^u)^2}
  \\
  \phi```(u)
  &=
  \frac{p(1-p)e^u}{(p+(1-p)e^u)^3}(p-(1-p)e^u)
  \quad(=0)
\end{align*}{}

$\phi''(u)$が最大値となる値を求めると

\begin{align*}
  p-(1-p)e^u
  &=
  0
  \\
  e^u
  =
  \frac{p}{1-p}
\end{align*}{}

となる。ここで増減表を書くと確かに$e^u=p/(1-p)$で最大値となる。そのため$\phi''(u)$に$e^u=p/(1-p)$となる$u$を代入すると

  \phi''\left( \log \frac{p}{1-p} \right)
  =
  \frac{1}{4}

となる。$E[e^{sX}]$の上界の話に戻り、$\phi(u)$の最大値の結果を用いると

\begin{align*}
  E[e^{sX}]
  &\leq
  \frac{b}{b-a}e^{sa}-\frac{a}{b-a}e^{sb}
  \\&=
  e^{\phi(u)}
  \\&=
  \exp\left\{ \phi(0)+\phi'(0)u+\frac{1}{2}\phi''(\zeta)u^2 \right\}
  \\&\leq
  \exp\left\{0+0+\frac{1}{2}\frac{1}{4}u^2 \right\}
  \\&=
  \exp \left\{ \frac{s^2(b-a)^2}{8} \right\}
\end{align*}{}

よってヘフティングの補題が示された。

ヘフティングの不等式

＜証明＞

  P[\hat{\mu}\geq \mu+\Delta]
  \leq
  e^{-2n\Delta^2}

を証明する。$S_n$を

  S_n
  =
  \sum_{i=1}^nX_i

とすると

\begin{align*}
  P(S_n-E(S_n)\geq t)
  &\leq
  \min_{s>0} \frac{E[\exp\{s(S_n-E(S_n))\}]}{e^{st}}
  \\&=
  \min_{s>0} \frac{1}{e^{st}} \prod_{i=1}^n E[\exp\{s(X_i-E(X_i))\}]
  \\&\leq
  \min_{s>0} \frac{1}{e^{st}} \prod_{i=1}^n \exp\left\{\frac{s^2(b_i-a_i)^2}{8} \right\}
  \\&=
  \min_{s>0} \exp\left\{ -st +\frac{\sum_i(b_i-a_i)^2}{8}s^2 \right\}
  \\&=
  \min_{s>0} \exp\left[ \frac{\sum_i(b_i-a_i)^2}{8}  \left\{ \left( s- \frac{4t}{\sum_i(b_i-a_i)^2} \right)^2 - \left( \frac{4t}{\sum_i(b_i-a_i)^2} \right)^2 \right\} \right]
  \\&=
  \exp\left[ \frac{\sum_i(b_i-a_i)^2}{8}  \left\{  - \left( \frac{4t}{\sum_i(b_i-a_i)^2} \right)^2 \right\} \right]
  \\&=
  \exp\left[ - \frac{2t^2}{\sum_i(b_i-a_i)^2} \right]
\end{align*}{}

が得られる。ただし1つ目の不等式ではチェルノフの不等式、2つ目の不等式ではヘフティングの補題を用いた。この不等式を使い

\begin{align*}{}
  P\left(\sum_iX_i-E\left(\sum_iX_i\right)\geq t\right)
  &\leq
  \exp\left[ - \frac{2t^2}{\sum_i(b_i-a_i)^2} \right]
  \\
  P\left( \hat{\mu} \geq \frac{t}{n}+\mu \right)
  &\leq
  \exp\left[ - \frac{2t^2}{\sum_i(1-0)^2} \right]
  \\
  P[\hat{\mu}\geq \mu+\Delta]
  &\leq
  e^{-2n\Delta^2}
\end{align*}{}

を導く。ただし$\Delta=t/n$と置いた。

以上の証明は、へフディングの不等式を導くためのものである。裾確率をより小さな上界で抑えるものとして、チェルノフ・へフディングの不等式がある。これを説明するために、2つの確率分布の距離の様なものを返す関数を紹介する。

KL情報量

2つの確率分布$P,Q$において、カルバック・ライブラー情報量（ＫＬ情報量）は以下の式で示される。

  D(P||Q)
  =
  \sum_x P(x) \log \frac{P(x)}{Q(x)}

全変動距離

2つの確率分布$P,Q$において、全変動距離は以下の式で示される。

  ||P-Q||_1
  =
  \frac{1}{2} \sum_x |P(x)-Q(x)|

この2つの確率分布間の距離には、以下の関係性が知られている。

  D(P||Q)
  \geq
  ||P-Q||_1

確率変数$X$が、パラメータ$p$のベルヌーイ分布に従っているとき

  X
  \sim
  Ber(p)

と表す。このとき2つのベルヌーイ分布がパラメータ$p,q$をもつとき、KL情報量は

  d(p,q)
  =
  D(Ber(p)||Ber(q))
  =
  p\log \frac{p}{q}+(1-p)\log \frac{1-p}{1-q}

となる。また全変動距離は

  ||Ber(p)-Ber(q)||_1
  =
  \frac{1}{2}\sum_x |Ber(p)-Ber(q)|
  =
  \frac{1}{2}[ |p-q|+|(1-p)-(1-q)| ]
  =
  |p-q|

である。このことを利用してチェルノフ・へフディングの不等式を導く。

チェルノフ・へフディングの不等式

互いに独立で同一の分布に従っている$X_i\in [0,1], i=1,\cdots,n$と任意の定数$0\leq x\leq\mu$に対して

  P(\hat{\mu}\leq x)
  \leq
  e^{-nd(x,\mu)}

及び、任意の定数$\mu \leq x\leq1$に対して

  P(\hat{\mu}\geq x)
  \leq
  e^{-nd(x,\mu)}

がそれぞれ成立する。

＜証明＞

$0\leq x\leq\mu$の場合。2つのベルヌーイ分布がそれぞれパラメータ$x,\mu$を持つとき、ピンスカーの不等式を適用すると

  d(x,\mu)
  \geq
  2||x-\mu||_1^2
  =
  2(x-\mu)^2

となる。また$\mu-x>0$であるため、へフディングの不等式において、$\Delta=\mu-x$とおいて

  P(\hat{\mu}\geq x)
  \leq
  e^{-2n(x-\mu)^2}

であるので最終的に

  P(\hat{\mu}\geq x)
  \leq
  e^{-nd(x,\mu)}

となる。

まとめ

大偏差原理とは、低確率で起きる事象の確率を指数関数で評価する理論を指す。バンディット問題ではこの大偏差原理を利用して、様々な方策を評価していく。

参考文献

この記事を書くにあたり、多くの参考文献やウェブサイトから貴重な情報を収集しました。以下に、特に重要な参考リンクに対して謝意を表明します。

相対誤差と絶対誤差
- https://life-freedom888.com/zettai-gosa/
マルコフの不等式、チェビシェフの不等式、チェルノフの上界、ヘフティングの補題、ヘフティングの不等式
- https://seetheworld1992.hatenablog.com/entry/2017/06/04/150253
テイラー展開
- https://manabitimes.jp/math/1001
凸関数
- https://risalc.info/src/convex-concave-function.html
ピンスカーの不等式
- https://mathwords.net/pinsker
サノフの定理の解説
- https://qiita.com/futakuchi0117/items/5c153aa607e7754faac8

本記事の執筆にあたり、多大なる助けとなった上記の参考文献およびウェブサイトに対し、深く感謝申し上げます。