第６章 数え上げ理論と確率 B4 酒井　隆行.

Presentation on theme: "第６章 数え上げ理論と確率 B4 酒井　隆行."— Presentation transcript:

1 第６章 数え上げ理論と確率 B4 酒井　隆行

2 6.1 数え上げ 数え上げ理論は、実際に列挙することなしに、“幾つあるか”という問に答えようとするものである。 例 “nビットの数は何個あるか” “n個の異なる要素の順番付けは何通りあるか” などなど

3 和法則と積法則 和法則 ２つの互いに素な集合の１つからの要素の選び方の数が、集合のサイズの和に等しい。
　 ２つの互いに素な集合の１つからの要素の選び方の数が、集合のサイズの和に等しい。 すなわち、AとBが共通部分をもたないとき、 が成り立つ。

4 積法則 順序対の選び方の数が、最初の要素の選び方の数と２番目の要素の選び方の数との積に等しい。 すなわち、AとBが２つの有限集合であるとき、 が成り立つ。

5 文字列 有限集合Sの上での文字列とは、Sの要素の文字列である。たとえば、長さ３の２進数列は次の８通りある。 000, 001, 010, 011, 100, 101, 110, 111 長さkの文字列のことをk-文字列と呼ぶことがある。文字列sの部分文字列s’とは、sの連続する要素からなる順序列をいい、k-部分文字列とは、長さkの部分文字列のことである。 集合Sの上でのk-部分列は、 だけ存在する。

6 順列 有限集合Sの順列とは、Sの要素をすべて１度ずつ用いて作った順序列をいう。たとえば、 S={a,b,c}のとき、Sの順列は次の６通りである。 abc, acb, bac, bca, cab, cba Sのk-順列とは、Sの中から重複なしにk個の要素をとって並べた列のことである。 集合{a,b,c,d}の2-順列は以下の１２通りである。 ab, ac, ad, ba, bc, bd, ca, cb, cd, da, db, dc n-集合のk-順列の数は、 で与えられる。

7 組み合わせ n-集合のk-組み合わせとは、単にSのk-部分集合のことである。4-集合{a,b,c,d}の2-組み合わせは、以下の６通りである。 ab, ac, ad, bc, bd, cd n-集合のk-組み合わせの数は、 で与えられる。

8 ２項係数 という記号(nチューズkと発音する)で、n-集合のk-組み合わせの個数を書くことにする。 これらの数は2項係数としても知られている。これは、これらが２項展開の係数として現れるからである。

9 ２項係数の上下界 下界 1≤k≤nのとき、次のような下界がある。

10 上界 Stirlingの公式から得られる不等式k!≥(k/e)ᵏを用いると、下のような上界が得られる。

11 すべての0≤k≤nに対して帰納法を用いると次の上界を証明することができる。 ただし、便宜上 と仮定しておく。

12 k=λnのとき（ただし、0≤λ≤1）、上界は次のように書き直すことができる。 ここで、 は（２進）エントロピー関数であり、便宜上、0lg0=0と仮定しておく。

13 6.2 確率 確率は標本空間Sによって定義されるが、これは各要素が根元事象であるような集合である。各根元事象は試行によって起こりうる結果とみなすことができる。 事象とは、標本空間の部分集合のことである。事象Sは全事象と呼ばれ、事象Øは空事象と呼ばれる。A,BがA∩B＝Øを満たす事象のとき、 これらは互いに素であるという。

14 確率公理 標本空間Sに関する確率分布とは、Sの事象から次の確率公理を満たす実数への写像である。 任意の事象Aに対してPr{A}≥0である。
Pr{S}=1 互いに素な任意の２つの事象Aに対して、 である。より一般的には、どの２つも互いに素である任意の事象列　　　　　　　に対して が成り立つ。

15 離散確率分布 確率分布が有限の標本空間または加算無限の標本空間上で定義されているとき、離散確率分布という。Sを標本空間としたとき、任意の事象Aに対して が成り立つ。また、Sが有限ですべての根元事象sϵSが確率分布 をもつとき、Sに関する一様確率分布という。

16 連続一様確率分布 a≤c≤d≤bであるような任意の閉区間[c,d]に対して、連続一様確率分布は、事象[c,d]の確率を と定義する。

17 条件付き確率と独立性 条件付き確率 事象Bが起こるという条件の下での事象Aの条件付き確率はPr{B}≠0のとき、次のように定義される。

18 独立 または、Pr{B} ≠0のときはこれと等価な条件 が成り立つとき、事象A,Bは独立であるという。 　　　　　　　　を事象の集合とするとき、すべての1≤i<j≤nに対して であるとき、これらの事象は対ごとに独立であるという。この集合のすべてのk-部分集合　　　　　　　　が2≤k≤nと　　　　　　　　　　に対して を満たすとき、これらは相互独立だという。

19 Bayesの定理 （１） 条件付き確率の定義より、確率が0でない２つの事象AとBに対して、次式が成り立つ。
これをPr{A|B}に関して解くと、次式を得る。 　　　　　　　　　　　　　　　　　　　　　（１） さらにPr{B}は、次のように書ける。 これを、（１）式に代入すると、

20 6.3 離散確率変数 離散確率変数Xとは、有限または加算無限の標本空間Sから実数への関数である。確率変数Xと実数xに対して、事象X=xを{sϵS:X(s)=x}と定義する。したがって、 である。関数 は、確率変数Xの確率密度関数である。

21 XとYが確率変数であるとき、関数 をXとYの結合確率密度関数という。yを定数とするとき、 が成り立ち、同様に定数xに対して、 が成り立つ。条件付き確率の定義を用いると、次式を得る。 すべてのx,yに対して が成り立つとき、XとYは独立であると定義する。

22 確率変数の期待値 離散確率変数Xの期待値とは、 であり、上の和が有限か絶対収束する場合には明確に定義される。 ２つの確率変数の和の期待値は、それぞれの期待値の和に等しい。すなわち、E[X],E[Y]が定義されるなら、 である。期待値をμと記すこともある。

23 Xを任意の確率変数とするとき、任意の関数g(x)は新たな確率変数g(X)を定義する。g(X)の期待値が定義されるなら、 である。g(x)=axとして、aを任意の定数とするとき、 が成り立つ。したがって、期待値は線形である。すなわち、 が成り立つ。

24 ２つの確率変数X,Yが独立で、それぞれに対して期待値が定義されているとき、次式が成り立つ。 一般に、n個の確率変数 が相互独立ならば、 である。

25 確率変数Xが自然数N={0,1,2,…}からの値をとるとき、

26 分散と標準偏差 平均がE[X]である確率変数Xの分散は、次のとおりである。 確率変数Xの分散とaXの分散は次の関係がある。 XとYが独立な確率変数であるとき、 である。一般に、n個の確率変数 が対ごとに独立であれば、次式が成り立つ。 確率変数Xの標準偏差はXの分散の平方根をとったものである。標準偏差をσと書いたりする。この記号を用いると分散は と記される。

27 6.4 幾何分布と２項分布 確率pで起こる成功と、確率q=1-pで起こる失敗の２通りの結果しかないBernoulli試行を例にして、幾何分布および２項分布について考えていく。

28 幾何分布 確率変数Xを成功を得るのに必要な試行回数とすると、k≥1に対して、 が成り立つ。上を満たす確率分布を２項分布という。幾何分布の期待値は、 分散は、

29 ２項分布 確率変数Xをn回の試行中の成功の回数と定義すると、 が成り立つ。上の式を満たす確率分布を２項分布という。便宜上、 という記号を用いる。

30 Xを２項分布b(k;n,p)に従う確率変数、Xᵢをi回目の試行における成功回数を表す確率変数とすると、期待値は

31 より、Xᵢの分散は であり、 を得る。

32 ２項分布b(k;n,p)は、kが0からnまで変化するにつれて平均値npに達するまで増加を続け、 その後減少する。連続する２項の比を取ってみると、

33 k<(n+1)pに対してはb(k;n,p)>b(k-1;n,p)が成り立ち、k>(n+1)pに対してはb(k;n,p)<b(k-1;n,p)が成り立つ。 この分布は、k=(n+1)pが整数の場合はb(k;n,p)=b(k-1;n,p)であり、よってこの分布は、k=(n+1)pとk-1=(n+1)p-1=np-qに二つの極大値を持つ。そうでないときは、np-q<k<(n+1)pという範囲にある１つの整数値kにおいてのみ極大値をとる。

34 補題6.1 n≥0とし、0<p<1,q=1-p,0≤k≤nとする。このとき、次式が成り立つ。

35 証明 を用いると、

36 6.5　２項分布の両端部分 １回の成功確率をpとするn回のBernoulli試行において、ちょうどk回成功する確率よりも、少なくともあるいは高々k回成功する確率のほうがより興味深い場合が多い。この節では、２項分布の両端部分について考える。

37 定理6.2 成功確率pであるn回のBernoulli試行 X：全成功回数を表す確率変数 このとき、0≤k≤nに対して少なくともk回成功する確率は である。

38 証明 6.1の練習問題から得られた次の不等式を利用する。 また、 であるので、

39 系6.3 成功確率pであるn回のBernoulli試行 X:全成功回数を表す確率変数 このとき、0≤k≤nに対して高々k回成功する確率は

40 定理6.4 成功確率p,失敗確率q=1-pであるn回のBernoulli試行 X:全成功回数を表す確率変数とする。このとき、0<k<npに対してk回より少なく成功する確率は

41 証明 幾何数列の級数和 を評価する。 i=1,2,…,kに対して、次式を得る。

42 もし、 ならば、0<i≤kに対して が成り立つ。この操作を繰り返せば0≤i<kに対して が得られる。

43 よって、

44 系6.5 成功確率pであるn回のBernoulli試行 X:全成功回数を表す確率変数 このとき、np<k<nに対してk回より多く成功する確率は次式で与えられる。

45 定理6.6 i=1,2,…,nに対するi番目の試行において成功確率がpᵢ,失敗確率がqᵢ=1- pᵢであるn回のBernoulli試行 X:全成功回数を表す確率変数 μ=E[X]とおくと、r>μに対して次式が成り立つ。

46 証明 任意のα>0に対して関数 はxに関して強い意味で増加関数であるので、 が成り立つ。ここで、 αは後に決定される。Markovの不等式 により、 を得る。

47 i=1,2,…,nに対して Xᵢ:i回目のBernoulli試行が成功なら１、失敗なら０となる確率変数 とすると、 が成り立つ。

48 X-μを置き換え、確率変数Xᵢが相互独立ならば確率変数 は相互独立になることから、 期待値の定義から、 である。

49 であるので、 が成り立つ。よって次式を得る。

50 と選べば次式が成り立つ。

51 系6.7 成功確率p,失敗確率q=1-pであるn回のBernoulli試行 このとき、r>npに対して、 証明 ２項分布に対してE[X]=npが成り立つならばμ=npである。

52 6.6 確率を用いた解析例 この節では３つの例を用いて確率を用いた解析例を示す。 部屋にいるk人のなかで２人が同じ誕生日 である確率 ボールを箱に無作為に入れる場合 硬貨投げにおける連続して表の出る“列”

53 誕生日パラドックス 問題 部屋にいる人のうち２人が同じ日にうまれた確率が1/2を超えるためには部屋に何人の人がいなければならないか? 準備 それぞれの人に整数1,2,…,kの番号をつける。 k:人の数 １年はn=365（簡単のため、うるう年はなし） bᵢ:i番目の人がうまれた日（i=1,2,…,k 1≤bᵢ≤n） 誕生日は１年のn日において一様に分布していると仮定

54 i=1,2,…,kとr=1,2,…,nに対して が成り立つ。 ２人の人間iとjが同じ誕生日である確率は、誕生日の無作為な選択が独立であることに依存する。もし誕生日が独立であるならば、iの誕生日とjの誕生日がある日rである確率は となる。

55 よって、部屋にいる２人の人間の誕生日が同じになる確率は である。 k人のうちの少なくとも２人の誕生日が同じになる確率は補事象を考えることにより解析できる。

56 K人が異なった誕生日である事象は である。ここで、Aᵢはi+1の誕生日がすべてのj≤iに対してjの誕生日と異なる事象である。すなわち、 である。 と書くことができるので、漸化式 をえる。ここで、初期条件として とする。

57 が異なるならばn日から選ばれない n-(k-1)日が存在するので、i=1,2,…,k-1に対して となる条件確率は(n-k+1)/nである。 先ほどの漸化式を繰り返し適用することにより、 を得る。

58 により のとき次式を得る。 k(k-1)≥2nln2のとき、k人すべての誕生日が異なる確率が1/2以下となる。よって23人以上いれば少なくとも２人の誕生日が同じになる確率が1/2以上となる。

59 ボールと箱 同一のボールを1,2,…,bと番号付けられたb個の箱に無作為に入れるという過程を考える。ボールを入れるのは独立事象で、それぞれのボールはどの箱にも等確率で入れられる。 ボールがある特定の箱に入る確率は1/bである。したがって、ボールを入れる過程は成功確率1/bのBernoulli試行の列である。

60 ある特定の箱に幾つのボールが入るか？ 特定の箱に入るボールの数は２項分布b(k;n,1/b)に従う。もしn個のボールが入れられるならば、特定の箱に入るボールの数の期待値はn/bである。

61 ある特定の箱にボールが１つ入るまでに平均何回ボールをなげなければならないか？
箱にボールが入るまでにボールを投げ入れる回数は確率1/bの幾何分布に従うので、成功までボールを投げ入れる平均回数は1/(1/b)=bである。

62 すべての箱に少なくとも１個のボールが入るまで何回ボールを投げないといけないか？
空の箱にボールが入れられると“当たり” b回当たるのに必要なボールの投げ入れ回数の平均値nを求める。 i番目の段階をi-1回目の当たりの後からi回目の当たりまでのボールの投げ入れと定義する。 i番目の段階におけるそれぞれのボールの投げ入れに対して、ボールの入ったi-1の箱とb-i+1の空の箱が存在する。よって、i番目の段階におけるすべてのボールの投げ入れに対して当たる確率は(b-i+1)/bである。

63 nᵢ: i番目の段階におけるボールの投げ入れ回数 b回の当たりを得るために必要な投げ入れ回数は である。それぞれの確率変数はnᵢは成功確率(b-i+1)/bの幾何分布をもつので次式を得る。

64 期待値の線形性から したがって、すべての箱にボールが入るまでにはおおよそblnb回の投げ入れが必要である。

65 連続硬貨投げ 公正な硬貨をn回投げるとする。連続して表が出る最大の列はどの程度になると期待されるかを考える。 答えは まず表が連続する最大列の平均長がO(lgn)であることを証明する。 :i回目の硬貨投げから始めてk回以上表が続けて出る事象(1≤k≤nかつ1≤i≤n-k+1) 任意の事象 に対してk回すべてが表となる確率はp=q=1/2の幾何分布である。

66 に対して である。任意の有限または加算無限の事象列について成り立つブールの不等式 により、事象の和集合の確率は各事象の確率の和を超えないので、任意の位置から始めて 以上表が続いて起こる確率は となる。

67 したがって、任意の列が 以上の長さをもつ確率は高々1/nであるので、最大列長 より短くなる確率は少なくとも1-1/nである。よって平均長は で上から押さえられる。 次に下界 の証明を行う。

68 長さ の列を見つける。 を得る。よって、表が 以上続く列の位置がiで始まらない確率は高々 である。N個の硬貨投げをそれぞれが 回の連続する硬貨投げからなる少なくとも のグループに分けることができ、これらは互いに独立な硬貨投げになる。

69 これらのグループのそれぞれが長さ の表が続く列にならない確率は したがって、最大列長が を超える確率は である。最大列長の平均値は少なくとも である。