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

Slides:



Advertisements
Similar presentations
北海道大学 Hokkaido University 1 情報理論 講義資料 2016/06/22 情報エレクトロニクス学科共通科目・2年次・第 1 学期〔必修 科目〕 講義「情報理論」第 5 回 第 3 章 情報源のモデル [ 後半 ] 3.5 情報源のエントロピー.
Advertisements

1 小暮研究会2 第1章ベイジアンアルゴリズ ム 2値選択 ベルヌーイ試行 尤度原理 同一性 交換可能性 尤度についてのまとめ 環境情報学部3年 渡邊洋一.
5 章 標本と統計量の分布 湯浅 直弘. 5-1 母集団と標本 ■ 母集合 今までは確率的なこと これからは,確率や割合がわかっていないとき に, 推定することが目標. 個体:実験や観測を行う 1 つの対象 母集団:個体全部の集合  ・有限な場合:有限母集合 → 1つの箱に入っているねじ.  ・無限な場合:無限母集合.
1 線形代数学. 2 履修にあたって 電子情報システム学科 必修 2005 年度1セメスタ開講 担当 草苅良至 (電子情報システム学科) 教官室: G I 511 内線: 2095 質問等は上記のいずれかに行なうこと。 注意計算用のノートを準備すること。
放射線の計算や測定における統計誤 差 「平均の誤差」とその応用( 1H) 2 項分布、ポアソン分布、ガウス分布 ( 1H ) 最小二乗法( 1H )
0章 数学基礎.
第1回 確率変数、確率分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
疫学概論 二項分布 Lesson 9.頻度と分布 §B. 二項分布 S.Harano,MD,PhD,MPH.
疫学概論 ポアソン分布 Lesson 9.頻度と分布 §C. ポアソン分布 S.Harano,MD,PhD,MPH.
確率と統計 平成23年12月8日 (徐々に統計へ戻ります).
統計解析 第7回 第6章 離散確率分布.
確率・統計Ⅰ 第12回 統計学の基礎1 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
確率・統計Ⅰ 第11回 i.i.d.の和と大数の法則 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
統計解析 第8回 第7章 2項分布.
統計学 11/13(月) 担当:鈴木智也.
Microsoft Excel 2010 を利用した 2項分布の確率計算
統計解析 第9回 第9章 正規分布、第11章 理論分布.
Extremal Combinatorics 14.1 ~ 14.2
Extremal Combinatrics Chapter 4
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
放射線の計算や測定における統計誤差 「平均の誤差」とその応用(1H) 2項分布、ポアソン分布、ガウス分布(1H) 最小二乗法(1H)
論理式の表現を数学的に取り扱いやすくするために代数学の助けを借りる.
第2章補足Ⅱ 2項分布と正規分布についての補足
統計解析 第8回 第7章 2項分布.
統計学 11/19(月) 担当:鈴木智也.
第7回 二項分布(続き)、幾何分布 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
9.NP完全問題とNP困難問題.
応用統計学の内容 推測統計学(inferential statistics)   連続型の確率分布   標本分布   統計推定   統計的検定.
Probabilistic Method 6-3,4
A path to combinatorics 第6章前半(最初-Ex6.5)
統計数理 石川顕一 10/17 組み合わせと確率 10/24 確率変数と確率分布 10/31 代表的な確率分布
Probabilistic method 輪講 第7回
(ラプラス変換の復習) 教科書には相当する章はない
5.5 The Linear Arboricity of Graphs (グラフの線形樹化数)
第3回 確率変数の平均 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
確率・統計Ⅰ 第3回 確率変数の独立性 / 確率変数の平均 ここです! 確率論とは 確率変数、確率分布 確率変数の独立性 / 確率変数の平均
形式言語の理論 5. 文脈依存言語.
確率論の基礎 「ロジスティクス工学」 第3章 鞭効果 第4章 確率的在庫モデル 補助資料
Probabilistic Method 2007/11/02 岩間研究室M1 市場孝之.
7.4 Two General Settings D3 杉原堅也.
情報理工学系研究科 数理情報学専攻 数理第四研究室 博士三年 指導教員: 駒木 文保 准教授 鈴木 大慈 2008年8月14日
Basic Tools B4  八田 直樹.
6. ラプラス変換.
第2日目第1時限の学習目標 順列、組み合わせ、確率の入門的知識を学ぶ。 (1)順列とは? (2)組み合わせとは? (3)確率とは?
標本分散の標本分布 標本分散の統計量   の定義    の性質 分布表の使い方    分布の信頼区間 
超幾何分布とポアソン分布 超幾何分布 ポアソン分布.
東北大学 大学院情報科学研究科 応用情報科学専攻 田中 和之(Kazuyuki Tanaka)
25. Randomized Algorithms
Additive Combinatrics 7
様々な情報源(4章).
9.通信路符号化手法1 (誤り検出と誤り訂正の原理)
5 Recursions 朴大地.
A path to combinatorics 第3章後半(Ex3.8-最後)
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
4. システムの安定性.
最尤推定・最尤法 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
第5回 確率変数の共分散 確率・統計Ⅰ ここです! 確率変数と確率分布 確率変数の同時分布、独立性 確率変数の平均 確率変数の分散
疫学概論 ポアソン分布 Lesson 9.頻度と分布 §C. ポアソン分布 S.Harano,MD,PhD,MPH.
解析学 ー第9〜10回ー 2019/5/12.
論理回路 第5回
物理フラクチュオマティクス論 応用確率過程論 (2006年4月11日)
確率と統計2007(最終回) 平成20年1月17日(木) 東京工科大学 亀田弘之.
プログラミング言語論 第10回 情報工学科 篠埜 功.
4.プッシュダウンオートマトンと 文脈自由文法の等価性
コストのついたグラフの探索 分枝限定法 A*アルゴリズム.
Microsoft Excel 2010 を利用した 2項分布の確率計算
第3章 統計的推定 (その2) 統計学 2006年度 <修正・補足版>.
確率統計学 (データ解析学) 書き込み式ノート(Ver.1) 担当教員:綴木 馴.
Time Reversal E-Text: pp.80-83(PDF: pp.49-50) FM08002 太神 諭
Presentation transcript:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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という範囲にある1つの整数値kにおいてのみ極大値をとる。

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

証明 を用いると、

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

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

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

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

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

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

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

よって、

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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