B4 八田 直樹
確率的手法は非常に強力なツールである。
たとえば、
であれば、
ということが言える。
について、
有限確率空間(finite probability space)
有限集合
関数 P {
→ [0,1]} s.t.
事象(event)
Subsets
事象の確率はP(A)＝
と定義される。
定義域(domain) または標本空間(smaple space)
確率分布(probability distribution)
P
一様分布(uniform distribution)
補集合(complement)
任意の事象A,Bについて、
たとえば、 ＝｛１，２，…６｝の空間について
A:２の倍数
B：３の倍数
とすると、
条件付き確率
例：一様分布なP
A:要素が２である
B:偶数
P(A|B)=1/3
P(B|A) ＝１
独立(independent)
となる事象A,Bの関係
このとき、条件付き確率の定義より、
独立は、互いに素(disjointness)とは異なる。
たとえば、
であるとき、AとBは互いに素だが、独立ではない。
互いに独立(mutually independent)
事象の集合
が任意の部分集合
について、
であるとき、Aと
は互いに独立である。
独立だが互いに独立でない例
コインを２回投げたとき
：i回目が表
A ：２回の裏表が同じ
とした時、Aと
、Aと
はそれぞれ独立だが、
となり、互いに独立ではない。
有限集合 と、そのランダム部分集合Sを考える。
Sは の中の要素それぞれについて、確率ｐで表が出
るコインを投げて、表ならSに含めるといった方法で構
成する。
このとき、Sの分布は標本空間 ＝ と、
確率分布
であらわされる。
たとえば、
＝｛１，２，３，４，５｝の時、
コイン： ○ × ○ ○ ×
要素 ： １ ２ ３ ４ ５
S = ｛１，３，４｝
ここで、Sが一様に与えられる、つまりｐ＝1/2として、
部分集合Sの集合を族Fとすると、
標本空間 はFとなり、
となる。
＝ であったので、この場合、
部分集合Sの確率分布は
となる。
確率変数X は →R（確率空間内の実数値） という
写像をする関数としてあらわされる。
確率変数Xの分布は →[0,1]である、関数
で定義される。
これは、
となる事象Aの確
率分布と同義である。
確率変数の期待値
例：サイコロの目を確率変数としたときの、期待値
期待値の線形性
が互いに独立である場合、
確率変数の分散(variance)
確率ｐで１をとり、確率１－ｐで０を取る確率変数Xを
ベルヌーイの変数と呼び、期待値はｐである。
２項分布とは確率ｐで１となる、独立なｎ個のベルヌーイ
変数の和、
であらわされ、
と書かれる。
n=5 p=1/3 のとき
k=3になる確率を考える。
コイン： ○ ○ ○ × ×
○ ○ × ○ ×
・
・
× × ○ ○ ○
それぞれの事象が起こる確率は
よって、任意の
について、
通り
期待値
分散
Counting Sieve
複数の事象が互いに素な確率は個々の事象の確率
の和で抑えられる。
もし、
ならば、
Independence Sieve
が互いに独立で、すべての
ならば、
互いに独立なので、
について
期待値の線形性
これは独立に関係なく成り立つ。
また、あるaについて
となるiが存在する。
のとき、
マルコフの不等式
Xを非負の確率変数、 を実数とすると、
証明：
チェルノフの不等式
で、それぞれが互
いに独立である確率変数
は
任意の ＞０について、以下を満たす。
対称性より、
マルコフの不等式を用いて、次のようになる。
ここで、
とすると、以下が得られる。
チェルノフの不等式 その２
確率ｐのｎ個のベルヌーイ変数の和をXとすると、
任意の
について、以下が成り立つ。
先と同様の変形を行う。
ここで、
であることを利用して、
t = ln(m/pn)とおいて計算すると。（
が得られる。
）
とおいてさらに計算。
同様に、以下のようにおいて計算していくと、
となる。
チェビシェフの不等式
Xを確率変数、 を任意の正の実数とすると、
証明：
適用する。
とおいて、マルコフの不等式を
Second Moment Method
チェビシェフの不等式で
以下の式が得られる。
とした場合、
ここで
であるなら、
の確率は定数で抑えられる。
つまり、このとき、XとE[X]はほとんど等しい。
よって、E[X]がわかれば、
となるXが少なくと
も１つ存在することがわかり、さらに
がわかれば、
となるXが多数存在することが
わかる。
ここからは、ツールの紹介をする。
Deletion Method
局所的に「良く」ない「悪い」ものが生じるランダムな設
定に対して、対象が「良く」なるまで「悪い」ところを変
化（削除）し続けることができる。
ラヴァースのふるい
事象
の依存関係をｎ頂点からなるグラフ
Gとしてあらわし、（ と が独立なら
）
その最大次数をｄ、任意のiについて、
の時、
ならば、
独立
２
１
従属
３
６
４
５
このとき、
の最大値ｐ
について、4ep<1なら、
どこにも属さない要素が存在。
エントロピー
確率変数Yがそれぞれ確率
をとりうる時、エントロピーは
でｍ個の値
と定義される。 これは情報量を意味する。
（一様分布）なら
Concentration property
のとき、
となるｂが存在する。
になる。
Subadditivity property
は事象 の要素をYの座標値としてとる、確率変
数で、
は 集合
の要素をと
る確率変数とするとき、
例：
ジョンソンの不等式
を集合、Yをその部分集合とし、 のすべての要
素と
となる事象が互いに独立であるようにす
る。
そして、 を
となる事象とする。
ここで、
を
とし、従属関
係を表す記号とする。
とおくと、以下の不等式が得られる。
ただし、
あずまの不等式
を積確率空間とし、
である２つの要素が一つの座標しか変わ
らないなら、
であるという命題を
満たす確率変数Xをとると、
Xの期待値を
として、
が成り立つ。
これは、チェルノフの不等式の拡張である。
タラグランドの不等式
先と同様に
る。そして、
に対して距離
任意の実ベクトル
となる
小のものをｔとする。
を積確率空間とす
を定義し、
に対して、
が存在するような、最
としたとき、以下の不等
式が成り立つ。
の一様分布とおくと、
は一様分布のn-cube
をとる。
このとき、ｘが
の要素なら、すべての
となり、ｘは からハミング距離
以内に存在す
る。
© Copyright 2024 ExpyDoc
