Chernoff bound

• Sublinear algorithmに多用されるChernoff boundはランダマイズド・アルゴリズムを用いて確率的にデータマイニングアウトプットをしたときの、そのアウトプットの確度を教えてくれる不等式
• それに関する文書はいろいろみつかるけれど、わかりにくかったので自分用に整理してepub化

Chernoff boundメモ: カメへの餌やりで考える

• Chernoff boundの基礎をなすマルコフの不等式・チェビシェフの不等式についても同じくepub化(そのRmdファイルはこちら)。

確率変数の不等式を視覚的に理解する: マルコフの不等式・チェビシェフの不等式

• 以下はRmd文書

---
title: "カメの餌やりで考えるChernoff bound"
author: "ryamada"
date: "Monday, May 18, 2015"
output: html_document
---

# はじめに

Chernoff boundは確率変数の上下限を教えてくれる不等式の一つである。

より具体的には、確率変数の取る値を足し合わせたものが取る値の上下限を教えてくれる不等式である。

そして、この足し合わせにあたって条件があり、一つ一つの確率変数値は相互に独立である必要がある。

この独立であること条件とすることで、「確率変数の値の和がある値になる確率」が「個々の確率変数がある値を取る確率」の「積」となることを利用することができる。これがChernoff boundの基本を成している。

# Chernoff bound の式で気をつけること

Chernoff boundについて調べると、いろいろな資料に出会うが、書かれている式がかなりばらばらであって、収拾がつかない。
しかも説明に用いられる例は、ものすごく簡単で簡単すぎて何が面白いのかわからないものと、いきなり複雑になってどんな問題設定なのかがこんがらがっているようなものになる。

どちらも困る。

例がわかりにくいのはさて置くとして、式表現が色々なのはかなり困る。
そして、この式表現のバリエーションにも３種類あるので、さらに式の把握がややこしい。

一つ目は、変数文字の使い方はバラバラであること。特に、変数の置き換えも高頻度になされるので混乱している。

二つ目は、同じ式なのだけれど、指数・対数・分子・分母などの書き振りがバラバラであること。

三つ目は、「不等式」であるがために、「この式」も成り立つが、「それをちょっと書き換えたこちらの式」も、『不等式としては正しい』が、「同一の不等式ではない」というものが散在していること。同一の不等式なのかと思ってその一致を確認しようとするとうまくいかずに混乱する。

これらがあるので、以下では、「代表式」を示し、それを使い、末尾にバリエーション例を示すことにする。

# 確率変数の和、とは

まず、Chernoff boundが問題にする、独立な確率変数の和というものを考える。

Chernoff boundでは、確率変数の和の期待値がいくつになるかと、その期待値からのずれの程度とを対象にするので、そのような例を挙げ、「確率変数の和」とはどういうことか、ということを確認する。

k匹のカメを飼っているとする。毎日、全部でa-kgの餌を与えるとする。この総量を1とする。
なるべく均等に与えるために毎日、餌をk等分して与える、というやり方もありだが、いかにも面倒くさい。餌の塊を適当に、n個に分割して(個々の餌片の大きさはまちまち)、それを餌片の大きさに頓着しないで、ランダムにk匹の餌入れに入れるような装置を設置して給餌することとした。

k匹のカメは平均して総量の$\frac{1}{k}$の餌を与えられるのは確かである。与えられる粒数の平均も$\frac{n}{k}$個になる。
しかしながら、ランダムにn粒を割り付けるので、k匹の餌粒数にはバラツキが出るし、その重さを足し合わせた、餌総量にもバラツキが出る。
このバラツキが、あまり大きいのはよくないが、そこそこの範囲ならよいだろうと考えている。
さて、バラツキがどれくらいに収まるものかを考えることにする。

このバラツキの程度の評価として、k匹のうち、もっともたくさんの餌をもらう個体のその量と、逆に最も少なくもらう量が$\frac{1}{k} \pm \Delta = (1 \pm \epsilon ) \frac{1}{k}$以上・以下になる確率の上下限に着目する。

これを考えるのに次のようにする。

n個の餌片のそれぞれは独立に$\frac{1}{k}$の確率でk匹のカメのいずれかに与えられる。

i番目の餌片が対総量として$Y_i$とすれば、$\sum_i^n Y_i=1;0 \le Y_i \le 1$。

あるカメに与えられる餌の重さの期待値は$\sum_i^n Y_i \times q$。ただし、$q=\frac{1}{k}$でもある。

ここで、確率変数$Z_i$を、確率$q$で値$Y_i$を取り、確率$1-q$で値0を取るようなベルヌーイ確率変数であるとすれば、あるカメの餌の重さは、$n$個の確率変数$\{Z_1,...,Z_n\}$の和という確率変数になる。

この考察は、ある１匹のカメに関することである。
今、知りたいのは、k匹のカメの中で一番多くの餌を与えられた個体の餌の重さについてである。k匹で分け合うとき、各々のカメの餌の多寡は相互に影響し合うので、独立性を仮定できない。

このようなときに使得るのがUnion bound である。

## Union bound

大層な名前がついているが、ある事象が確率pで起きるとき、k回、独立して実施すると、1回以上起きる確率は$1-(1-p)^k$であるが、これは$kp$よりも小さい。

一方、今回のk匹のカメの餌の量の最大値の場合には、k匹のカメの餌の量は独立していないから、$1-(1-p)^k$は使えない。しかしながら、$kp$以下であることは確実である。

このように独立でない事象のいずれか一つ以上が起きる確率は、それぞれの生起確率の和以下になる、と言うのがunion boundである。

Union bound は「複数の事象」について、確率を足し合わせる。
一方、Chernoff boundは確率を掛け合わせる。

掛け合わせる方は「独立なもの」同士、足し合わせるのは「独立ではないもの」同士。

こういう意味で、Chernoff boundは「独立」であることを利用して、掛け合わせを持ち出し、そうすることで範囲をぐっと限局する。
その一方でunion boundは「非独立」であるがためにChernoff boundを使えないときにも使える計算方法である。

相互に補い合って、非独立かもしれない複数の事象に、なるべく限局したboundを与えるために使われる。

後は、この２種類のboundをどのように使いまわすかが腕の見せ所となる。


したがって、このunion boundを使ってk匹の最大量について考えることにすれば、1匹の最大量がいくつになるかの確率を考えればよいことになる。

以下では、ある１匹のカメの餌量の分布について考えることにする。

ある１匹のカメの餌量は、n個の期待値の異なるベルヌーイ事象確率変数の和である。
このn個の確率変数は独立である。

このような「独立した確率変数の和」としての確率変数を扱いますよ、それにはChernoff boundがありますよ、という話。

以下、このChernoff boundについて述べていく。

# Chernoff boundの式、これだけは

Xは「独立した確率変数の和」としての確率変数。
$\mu$は、それぞれの確率変数の期待値の和。
$\epsilon$は、$\mu$からのずれを表すパラメタで、$\epsilon \ge 0$とする。
また、個々の確率変数が取りうる範囲は0-Gとする。
カメの餌の例では、もしn餌片が均等割りならば$G=\frac{1}{n}$であるし、全く自由に分割するならば、Gの最大値はほぼ1であることもある。１個の餌片にほとんどすべて集中しているような極端場な場合のことである。

このとき、あるカメに与えられる餌量Xについて、以下であることが知られている。
$$
p[X \ge (1+\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2+\epsilon}\mu\frac{1}{G}}\\
p[X \le (1-\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2}\mu\frac{1}{G}}\\
$$

この式の構成要素を確認しよう。

期待値$\mu$は必要だ。それ以外は$\epsilon$と$G$とが使われている。それだけである。


この式で着目するべきことの一つは、平均からのずれの正負によって、確率の上限の式が異なること。

これは、確率というものが0-1の範囲で収まっており、$\mu$が小さいときには、さらにそれより0に近い方にずれるのは、大きい方にずれるのに比べて、『混み混み』であるというような、正負２方向で非対称であることを反映している。
非対称であることに納得がいけば、この方向別の２式を覚えるべく受け入れることはそれほど苦痛ではない。

また、もう一つは各餌片が均質であると$G$は小さくなり、その結果、$p$の上限は小さくなり、餌片の重さに偏りが大きくなると$G$が大きくなり、$p$の上限も大きくなる。

念のために、記しておく。

期待値からのずれ$\Delta$は

$$
\Delta = \epsilon \mu
$$

である。

# 実験

## 実験１　均等割り

餌塊をn等分した場合に、ある1匹に与えられる餌量の分布と、Chernoff boundとの関係を乱数実験にて確かめてみる。

均等分割なので$G=\frac{1}{n}$である。

```{r}
k <- 10 # no. turtles
n <- 10^2 # no. pieces
n.iter <- 10^5 # no. iterations
# Relative wieght of pieces for every iterations in a matrix form
divs <- matrix(1/n,n.iter,n)
# G
G <- 1/n
# Whether or not each piece is given to the turtle
r <- matrix(sample(0:1,n*n.iter,replace=TRUE,prob=c(1-1/k,1/k)),ncol=n)
x <- divs * r
# Food weight for the turtle per iteration
food <- apply(x,1,sum)
```

餌やりのたびに、与えられる餌量がばらつく。その度数分布は以下の通りである。

```{r}
hist(food,main="Dist of food amount of a turtle")
```

次に、$\epsilon$の値を適当に換えつつ、それに対応する
$$
p[X \ge (1+\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2+\epsilon}\mu\frac{1}{G}}\\
p[X \le (1-\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2}\mu\frac{1}{G}}\\
$$
を算出する。

```{r}
# Chernoff bound parameter
eps.L <- seq(from=0,to=1,length=101)
eps.U <- seq(from=0,to=5,length=501)
# Mean weight
mu <- 1/k
# Chernoff Lower and Upper bound
L <- exp(-eps.L^2/2*mu/G)
U <- exp(-eps.U^2/(2+eps.U)*mu/G)
# Weight of food indicated by eps Chernoff bound parameter
D.L <- mu-eps.L*mu
D.U <- mu+eps.U*mu

# Fraction more/less than Chernoff cut-off values
obs.L <- rep(0,length(D.L))
obs.U <- rep(0,length(D.U))

for(i in 1:length(obs.L)){
  obs.L[i] <- length(which(food <= D.L[i]))/n.iter
}
for(i in 1:length(obs.U)){
  obs.U[i] <- length(which(food >= D.U[i]))/n.iter
}
```

n.iter回のシミュレーションの結果、実際に$\epsilon$で指定した閾値以上・以下になった確率と、Chernoff boundとを併せて示せば、以下のようになる(黒：観測データに基づく割合、赤：Chernoff bound)。

```{r}
# Plot fractions of observation and Chernoff bound against Weight of food
D <- c(D.L,D.U)
ord <- order(D)
LU <- c(L,U)
obs <- c(obs.L,obs.U)
plot(D[ord],LU[ord],type="l",col=2,ylim=c(0,1),xlab="Threshold of Food amount",ylab="Pr >=/<= thres",main="Black:Observeation,Red:Chernoff bound")
points(D[ord],obs[ord],type="l")
```

$\epsilon=0$のとき、Chernoff boundは1であり、そこから両方向に指数関数的に(右方向は若干異なるが)、boundが狭くなっていることがわかる。
観測データの閾値を超えるずれの割合(黒)は赤の閾値線より低くなっていることが視覚的に理解できる。

## 実験２　不均等割り

では、不均等割りをするとどうなるだろうか。
結論から先に言うと、各餌片の重さがバラバラになり、その中の最大のものの重さ$G$は均等割りのときに比べて必ず大きくなる。
$$
p[X \ge (1+\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2+\epsilon}\mu\frac{1}{G}}\\
p[X \le (1-\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2}\mu\frac{1}{G}}\\
$$
にあるように、$G$が大きくなると、$p$も大きくなるから、Chernoff boundは広くなる。
広くなるというのは、不等式として、役に立つ程度が下がるということである。

では、それがどのように広くなるのかを次のようにしてやってみる。

$n$分割を適当に発生させ、その中の最大餌片の重さを$G$として、実際にあるカメに与えられる餌の重さをモンテカルロ発生させる。

その分割と$G$について、Chernoff boundを考える。


まず、試行ごとに分割を変える。
その結果、最大餌片の重さがどのような値となったかの分布を示したのが次の図である。
均等分割ならば、餌片は$\frac{1}{n}$であるので、不均等分割をしているこの実験では、最大餌片の重さの最小値は$\frac{1}{n}$よりも大きくなっている。
```{r}
library(MCMCpack)
k <- 50 # no. turtles
n <- 10^2 # no. pieces
n.iter <- 10^3 # no. iterations
divs <- as.matrix(rdirichlet(n.iter,rep(0.5,n))) # weight of pieces per iterations
#divs <- matrix(1/n,n.iter,n)
r <- matrix(sample(0:1,n*n.iter,replace=TRUE,prob=c(1-1/k,1/k)),ncol=n)
x <- divs * r
G <- apply(divs,1,max)
range(G) # min and max of the heviest piece
print(1/n) # Weight of food piece when divided equally
hist(G)
```

このように分割がさまざまに変わる条件で、あるカメに与えられた餌量がどのようにばらつくかを以下に示す。
```{r}
food <- apply(x,1,sum)
hist(food)

```
Chernoff boundは、ある閾値以上・以下になる確率を教えるものであるので、指定の確率をもたらすような餌の重さ閾値を、その$G$に対して計算する。
そのうえで、実際に与えられて餌の量が黒点で示され、Chernoff bound 確率に相当する閾値を等高線(等値線)のように描いたのが以下の図である。
黒の点は、分割によって生じた最も重い餌片の重さを横軸値とし、あるカメに与えられた餌の重さを縦軸値としたものである。

赤の複数の曲線は、複数の$\epsilon$値に対する下側のChernoff boundの等値線。
緑は、上側のChernoff bound の等値線。

```{r}
# Various values of G are assumed for calculation
#seq.G <- seq(from=min(G),to=max(G),length=10)
seq.G <- seq(from=min(G),to=1,length=50)
# Chernoff bound probability 
Pr <- seq(from=0.1,to=0.5,by=0.1)
#eps.L <- seq(from=0,to=1,length=101)
#eps.U <- seq(from=0,to=5,length=501)
mu <- 1/k # Mean of food for a turtle
# Epsilon values that should give Pr as Chernoff bound of Lower and Upper, for various G values are to be stocked 
Ls <- matrix(0,length(seq.G),length(Pr))
Us <- matrix(0,length(seq.G),length(Pr))
for(i in 1:length(seq.G)){
  tmpG <- seq.G[i]
  Ls[i,] <- sqrt(-log(Pr)*2*tmpG/mu)
  Us[i,] <- 1/mu * (-tmpG*log(Pr)+sqrt((tmpG*log(Pr))^2-2*mu*tmpG*log(Pr)))
}
```
Gの値が現実的な範囲について描くと次のようになる。
bound probability は0.5,0.4,...,0.1としてある。
めったにboundを超えた点がないので、上下限値として「十分」であることはわかる。

```{r}
plot(G,food,pch=20,cex=0.1,ylim=c(0,1))
for(i in 1:length(Pr)){
  points(seq.G,(1-Ls[,i])*mu,type="l",col=2)
}
for(i in 1:length(Pr)){
  points(seq.G,(1+Us[,i])*mu,type="l",col=3)
}
```

原理的には、Gの値は1近くなるので、その範囲で描くと以下のようになる。
最大重量について全く情報がないときにG=1を想定しなくてはならないわけであるが、そうすると、Chernoff boundはほとんど意味のある情報を提供していないことも併せてわかる。

```{r}
plot(G,food,pch=20,cex=0.1,xlim=c(0,1),ylim=c(0,1))
for(i in 1:length(Pr)){
  points(seq.G,(1-Ls[,i])*mu,type="l",col=2)
}
for(i in 1:length(Pr)){
  points(seq.G,(1+Us[,i])*mu,type="l",col=3)
}
```

## 複数のカメについてUnion boundで足し合わせる

上記にて１匹のカメについて、Chernoff boundを求めた。
個々の餌片がその着目カメに与えられるか否か、という「相互に独立した確率変数」の和についての分布ということで、Chernoff boundが計算された。

これをk匹について合わせるためには、k匹の餌の重さは相互に非独立なので、使えるのはUnion boundである。

具体的には、１匹用に出したChernoff bound値をk倍することになる。

均等分割の例でそれをやってみる。

赤は１匹のChernoff bound、青はk匹分をUnion boundしてk倍したものである。

k倍するとBoundが広くなりすぎて役に立たないところもあるが、指数関数的に減衰している領域については、指数関数的減衰がk倍よりもはるかに強力であるため、意味のあるBoundを提供していることとなっている。

逆に言えば、指数関数的な減衰が有効である範囲においては、Union boundと組み合わせても有用になりうるとも言い換えられる。

```{r}
k <- 10 # no. turtles
n <- 10^2 # no. pieces
n.iter <- 10^5 # no. iterations
# Relative wieght of pieces for every iterations in a matrix form
divs <- matrix(1/n,n.iter,n)
# G
G <- 1/n
# Whether or not each piece is given to the turtle
r <- matrix(sample(0:1,n*n.iter,replace=TRUE,prob=c(1-1/k,1/k)),ncol=n)
x <- divs * r
# Food weight for the turtle per iteration
food <- apply(x,1,sum)
# Chernoff bound parameter
eps.L <- seq(from=0,to=1,length=101)
eps.U <- seq(from=0,to=5,length=501)
# Mean weight
mu <- 1/k
# Chernoff Lower and Upper bound
L <- exp(-eps.L^2/2*mu/G)
U <- exp(-eps.U^2/(2+eps.U)*mu/G)
# Weight of food indicated by eps Chernoff bound parameter
D.L <- mu-eps.L*mu
D.U <- mu+eps.U*mu

# Fraction more/less than Chernoff cut-off values
obs.L <- rep(0,length(D.L))
obs.U <- rep(0,length(D.U))

for(i in 1:length(obs.L)){
  obs.L[i] <- length(which(food <= D.L[i]))/n.iter
}
for(i in 1:length(obs.U)){
  obs.U[i] <- length(which(food >= D.U[i]))/n.iter
}

# Plot fractions of observation and Chernoff bound against Weight of food
D <- c(D.L,D.U)
ord <- order(D)
LU <- c(L,U)
obs <- c(obs.L,obs.U)
plot(D[ord],LU[ord],type="l",col=2,ylim=c(0,1),xlab="Threshold of Food amount",ylab="Pr >=/<= thres",main="Black:Observeation,Red:Chernoff bound")
points(D[ord],obs[ord],type="l")
points(D[ord],LU[ord]*k,type="l",col=4)
```
さて、Chernoff boundについて、基本形の議論はこれで終わりである。

次の節で、よくある変形について確認しておく。

# Chernoff bound のその他の表現いろいろ

基本形を再掲する。

$$
p[X \ge (1+\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2+\epsilon}\mu\frac{1}{G}}\\
p[X \le (1-\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2}\mu\frac{1}{G}}\\
$$

いろんな理由があって色々な表現がある。とてもたくさんある。
そのいくつかを示すことで、色々な表現への対処法のイメージをつかむこととする。

## 限定条件 個々の確率変数の上限値が1の場合

足し合わせる個々の確率変数の取りうる値が0以上G以下であるという前提で上記の基本形は書かれている。

$G=1$を仮定して書いた式も多い。そうすると以下のようになる。

どちらかと言えば、$G=1$の場合の書き方の方が「普通形」とみなされているようである。
$$
p[X \ge (1+\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2+\epsilon}\mu}\\
p[X \le (1-\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2}\mu}\\
$$

## 書き換えてわかりやすくしたもの

$\epsilon$はたいてい1より小さいので、それを前提にすれば以下のように書き換えられる。

$$
p[X \ge (1+\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2+\epsilon}\mu\frac{1}{G}} \le e^{-\frac{\epsilon^2}{3}\mu\frac{1}{G}}\\
p[X \le (1-\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2}\mu\frac{1}{G}}\\
$$

## 上下限を対称にしてしまう

上下限は非対称なのが、対称にした考えたいこともある。
そんなときは、緩い方に合わせればよいから

$$
p[X \ge (1+\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2+\epsilon}\mu\frac{1}{G}} \\
p[X \le (1-\epsilon) \mu] \le e^{-\frac{\epsilon^2}{2+\epsilon}\mu\frac{1}{G}}\\
$$
のようにして、さらに次のように１式にまとめることもできる。

$$
p[|X-\mu| \ge \epsilon \mu] \le 2 \times e^{-\frac{\epsilon^2}{2+\epsilon}\mu\frac{1}{G}} \\
$$

# 証明に即した表現

Chernoff boundは独立な確率変数の和に関する確率を指数関数に対応づけることで、「指数の和」を「指数関数の積」にすること、さらに、それにMarkovの不等式を適用するというプロセスで導かれる。

その過程が見えるように書いたのが次の表現である。

$E[e^{tX}]$は確率変数Xのt倍を指数とする指数関数値をとる確率変数の期待値のことである。

$$
p[X \ge (1+\epsilon)\mu] = p[e^{tX} \ge e^{1+\epsilon)t\mu}]\\
p[e^{tX} \ge e^{1+\epsilon)t\mu}] \le \frac{E[e^{tX}]}{e^{1+\epsilon)t\mu}\\
E[e^{tX}]=E[e^{t\sum_i X_i}] = \prod_i E[e^{tX_i}]\\
$$

ここで$X_i$が確率$q_i$で1とり、確率$1-q_i$で0をとるとすると、$e^{tX_i}$は確率$q_i$で$e^t$、確率$1-q_i$で$e^0=1$の値を取るから
$$
E[e^{tX_i} = q_i e^t+(1-q_i)=1+q_i(e^t-1)]
$$
となる。

ここで$1 + \alpha \le e^{\alpha}$を使えば
$$
E[e^{tX_i} =1+q_i(e^t-1)\le e^{q_i(e^t-1)}]
$$

結局
$$
E[e^{tX}] = \prod_i E[e^{tX_i}] \le \prod_i e^{q_i(e^t-1)} = e^{\sum_i q_i(e^t-1)}
$$
ここで$\sum_i q_i = \mu$だから
$$
E[e^{tX}] \le e^{(e^t-1)\mu}
$$

これを
$$
p[X \ge (1+\epsilon)\mu]  \le \frac{E[e^{tX}]}{e^{1+\epsilon)t\mu}\\
$$
に入れれば
$$
p[X \ge (1+\epsilon)\mu]  \le \frac{e^{(e^t-1)\mu}}{e^{1+\epsilon)t\mu}
$$
# ごく限定した特別な場合：個々の確率変数が等確率ベルヌーイ事象の場合

この場合は、ちょうど0.5の確率のものが合わさっているだけなので、上下限の非対称性が打ち消し合って対称になる。

さらに基本形と少し違う(特殊条件を用いて証明しているから、だと思われる)。

とても単純な特別形だけれど、これを想定する場合も少なくないから、これを持ちてChernoff boundの説明がなされていることもある。

その説明から入って、一般化をしていくことにメリットがあることも多いけれど、かえって混乱の素になっているのではないか、という印象も強い。

$\mu = \frac{n}{2}$ であるので、

$$
p[X \ge (1+\epsilon) \frac{n}{2}] \le e^{-\frac{\epsilon^2}{2}\frac{n}{2}} \\
p[X \le (1-\epsilon) \frac{n}{2}] \le e^{-\frac{\epsilon^2}{2}\frac{n}{2}}\\
$$

ただし、これがさらに、末尾の指数関数の指数内の$\frac{n}{2}$が$n$に転じて、より強力なboundになっている。
$$
p[X \ge (1+\epsilon) \frac{n}{2}] \le e^{-\frac{\epsilon^2}{2}n} \\
p[X \le (1-\epsilon) \frac{n}{2}] \le e^{-\frac{\epsilon^2}{2}n}\\
$$

この式を、期待値からの逸脱のパラメタ表現を変えて以下のように表すこともできる。boundの関数が単純になっている形式で、bound確率がどれくらいのときに期待値からのずれがどれくらいかを考えるにはこの形式の方がわかりやすいだろう。

$$
p[X \ge \frac{n}{2}+t\frac{\sqrt{n}}{2}] \le e^{-\frac{t^2}{2}}\\
p[X \le \frac{n}{2}-t\frac{\sqrt{n}}{2}] \le e^{-\frac{t^2}{2}}\\
$$