Basic Tools 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は互いに素だが、独立ではない。 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になる確率を考える。 それぞれの事象が起こる確率は よって、任意の について、 コイン：　○　○　○　×　× 　 ○　○　×　○　× ・ 　 ×　×　○　○　○ 通り

期待値　 分散

Elementary tools Counting Sieve 複数の事象が互いに素な確率は個々の事象の確率 の和で抑えられる。 もし、 ならば、

Independence Sieve が互いに独立で、すべての について ならば、 互いに独立なので、 期待値の線形性 これは独立に関係なく成り立つ。 また、あるaについて のとき、 となるiが存在する。

マルコフの不等式 Xを非負の確率変数、 を実数とすると、 証明：

チェルノフの不等式 で、それぞれが互 いに独立である確率変数 は 任意の ＞０について、以下を満たす。 対称性より、 マルコフの不等式を用いて、次のようになる。 ここで、 とすると、以下が得られる。

チェルノフの不等式 その２ 確率ｐのｎ個のベルヌーイ変数の和をXとすると、 任意の について、以下が成り立つ。 先と同様の変形を行う。

ここで、 であることを利用して、 t = ln(m/pn)とおいて計算すると。（ ） が得られる。 とおいてさらに計算。 同様に、以下のようにおいて計算していくと、 となる。

チェビシェフの不等式 Xを確率変数、 を任意の正の実数とすると、 証明： とおいて、マルコフの不等式を 適用する。

Second Moment Method チェビシェフの不等式で とした場合、 以下の式が得られる。 ここで であるなら、 の確率は定数で抑えられる。 つまり、このとき、XとE[X]はほとんど等しい。 よって、E[X]がわかれば、 となるXが少なくと も１つ存在することがわかり、さらに がわかれば、 となるXが多数存在することが わかる。

Advanced tools ここからは、ツールの紹介をする。 Deletion Method 局所的に「良く」ない「悪い」ものが生じるランダムな設 定に対して、対象が「良く」なるまで「悪い」ところを変 化（削除）し続けることができる。

ラヴァースのふるい 事象 の依存関係をｎ頂点からなるグラフ Gとしてあらわし、（ と が独立なら ） その最大次数をｄ、任意のiについて、 の時、 ならば、 このとき、 の最大値ｐ について、4ep<1なら、 どこにも属さない要素が存在。 独立 ２ 従属 １ ３ ６ ５ ４

エントロピー 確率変数Yがそれぞれ確率 でｍ個の値 をとりうる時、エントロピーは と定義される。 これは情報量を意味する。 （一様分布）なら になる。 Concentration property のとき、 となるｂが存在する。 確率が小さければ、エントロピーは増える凸関数

Subadditivity property は事象 の要素をYの座標値としてとる、確率変 数で、 は 集合 の要素をと る確率変数とするとき、 例： N=1で等号成立

ジョンソンの不等式 を集合、Yをその部分集合とし、 のすべての要 素と となる事象が互いに独立であるようにす る。 そして、 を となる事象とする。 ここで、 を とし、従属関 係を表す記号とする。 とおくと、以下の不等式が得られる。 ただし、

あずまの不等式 を積確率空間とし、 である２つの要素が一つの座標しか変わ らないなら、 であるという命題を 満たす確率変数Xをとると、 Xの期待値を として、 が成り立つ。 これは、チェルノフの不等式の拡張である。

タラグランドの不等式 先と同様に を積確率空間とす る。そして、 に対して距離 を定義し、 任意の実ベクトル に対して、 となる が存在するような、最 小のものをｔとする。 としたとき、以下の不等 式が成り立つ。

の一様分布とおくと、 は一様分布のn-cube をとる。 このとき、ｘが の要素なら、すべての となり、ｘは からハミング距離 以内に存在す る。