Basic Tools B4 　八田　直樹.

Presentation on theme: "Basic Tools B4 　八田　直樹."— Presentation transcript:

1 Basic Tools B4 　八田　直樹

2 確率的手法 確率的手法は非常に強力なツールである。 たとえば、　　　　　　　　　　　　　について、 であれば、 ということが言える。

3 定義 有限確率空間(finite probability space) 有限集合 関数 P { → [0,1]} s.t. 事象(event) Subsets 事象の確率はP(A)＝ と定義される。

4 定義 定義域(domain) または標本空間(smaple space) 確率分布(probability distribution) P 一様分布(uniform distribution) 補集合(complement)

5 任意の事象A,Bについて、 たとえば、 ＝｛１，２，…６｝の空間について A:２の倍数 B：３の倍数 とすると、

6 定義 条件付き確率 例：一様分布なP A:要素が２である B:偶数 P(A|B)=1/3 P(B|A) ＝１

7 定義 独立(independent) となる事象A,Bの関係 このとき、条件付き確率の定義より、 独立は、互いに素(disjointness)とは異なる。 たとえば、 であるとき、AとBは互いに素だが、独立ではない。 A:偶数　B:奇数

8 互いに独立(mutually independent) 事象の集合 が任意の部分集合 について、 であるとき、Aと は互いに独立である。 独立だが互いに独立でない例 コインを２回投げたとき ：i回目が表 A ：２回の裏表が同じ とした時、Aと 、Aと はそれぞれ独立だが、 となり、互いに独立ではない。

9 部分集合と確率 有限集合 と、そのランダム部分集合Sを考える。 Sは の中の要素それぞれについて、確率ｐで表が出 るコインを投げて、表ならSに含めるといった方法で構 成する。 このとき、Sの分布は標本空間 ＝ と、 確率分布 であらわされる。 たとえば、 ＝｛１，２，３，４，５｝の時、 コイン：　○　×　○　○　× 要素　：　１　 ２ 　３ 　４　 ５ S = ｛１，３，４｝

10 ここで、Sが一様に与えられる、つまりｐ＝1/2として、 部分集合Sの集合を族Fとすると、 標本空間 はFとなり、 となる。 ＝ であったので、この場合、 部分集合Sの確率分布は となる。

11 定義 確率変数X は →R（確率空間内の実数値） という 写像をする関数としてあらわされる。 確率変数Xの分布は →[0,1]である、関数 で定義される。 これは、 となる事象Aの確 率分布と同義である。

12 定義 確率変数の期待値 例：サイコロの目を確率変数としたときの、期待値

13 期待値の性質と分散 期待値の線形性 が互いに独立である場合、 確率変数の分散(variance)

14 ２項分布 確率ｐで１をとり、確率１－ｐで０を取る確率変数Xを ベルヌーイの変数と呼び、期待値はｐである。 ２項分布とは確率ｐで１となる、独立なｎ個のベルヌーイ 変数の和、 であらわされ、 と書かれる。

15 コイン： ○ ○ ○ × × ○ ○ × ○ × ・ × × ○ ○ ○ 通り
n=5 p=1/3 のとき k=3になる確率を考える。 それぞれの事象が起こる確率は よって、任意の について、 コイン：　○　○　○　×　× 　 ○　○　×　○　× ・ 　 ×　×　○　○　○ 通り

16 期待値　 分散

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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