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

第６章
数え上げ理論と確率
B4
酒井隆行
6.1 数え上げ
数え上げ理論は、実際に列挙することなしに、
“幾つあるか”という問に答えようとするもので
ある。
例
“nビットの数は何個あるか”
“n個の異なる要素の順番付けは何通りある
か”
などなど
和法則と積法則
• 和法則
２つの互いに素な集合の１つからの要素の選
び方の数が、集合のサイズの和に等しい。
すなわち、AとBが共通部分をもたないとき、
AB  A  B
が成り立つ。
• 積法則
順序対の選び方の数が、最初の要素の選び
方の数と２番目の要素の選び方の数との積
に等しい。
すなわち、AとBが２つの有限集合であるとき、
A B  A  B
が成り立つ。
文字列
有限集合Sの上での文字列とは、Sの要素の文字列で
ある。たとえば、長さ３の２進数列は次の８通りある。
000, 001, 010, 011, 100, 101, 110, 111
長さkの文字列のことをk-文字列と呼ぶことがある。文
字列sの部分文字列s’とは、sの連続する要素からなる
順序列をいい、k-部分文字列とは、長さkの部分文字
列のことである。
集合Sの上でのk-部分列は、
だけ存在する。
S
k
順列
有限集合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-順列の数は、
n!
n n  1n  2 n  k  1 
n  k !
で与えられる。
組み合わせ
n-集合のk-組み合わせとは、単にSのk-部分
集合のことである。4-集合{a,b,c,d}の2-組み合
わせは、以下の６通りである。
ab, ac, ad, bc, bd, cd
n-集合のk-組み合わせの数は、
n!
k!n  k !
で与えられる。
２項係数
n
 
k
という記号(nチューズkと発音する)で、n-集合のk-組み
合わせの個数を書くことにする。
n
 n 
n!
  

 
 k  k!n  k !  n  k 
これらの数は2項係数としても知られている。これは、
これらが２項展開の係数として現れるからである。
x  y 
n
 n  k n k
   x y
k 0  k 
n
２項係数の上下界
• 下界
1≤k≤nのとき、次のような下界がある。
 n  n n  1n  2  n  k  1
  
k k  11
k
 n  n  1   n  k  1 
  
 

1
 k  k  1  

n
 
k
k
• 上界
Stirlingの公式から得られる不等式k!≥(k/e)ᵏを
用いると、下のような上界が得られる。
 n  n n  1 n  k  1
  
k k  11
k
nk

k!
 en 
 
 k 
k
すべての0≤k≤nに対して帰納法を用いると次
の上界を証明することができる。
n
n
 
n
   k
n k
 k  k n  k 
ただし、便宜上
0 1
0
と仮定しておく。
k=λnのとき（ただし、0≤λ≤1）、上界は次のように
書き直すことができる。
 n 
nn

 n 
  n n 1   n 1  n


  1    1 1 
   
   1  


 2 nH  
ここで、




n
H   lg   1  lg 1  
は（２進）エントロピー関数であり、便宜上、
0lg0=0と仮定しておく。
6.2 確率
確率は標本空間Sによって定義されるが、こ
れは各要素が根元事象であるような集合で
ある。各根元事象は試行によって起こりうる
結果とみなすことができる。
事象とは、標本空間の部分集合のことである。
事象Sは全事象と呼ばれ、事象Øは空事象と
呼ばれる。A,BがA∩B＝Øを満たす事象のとき、
これらは互いに素であるという。
確率公理
標本空間Sに関する確率分布とは、Sの事象から次の
確率公理を満たす実数への写像である。
1. 任意の事象Aに対してPr{A}≥0である。
2. Pr{S}=1
3. 互いに素な任意の２つの事象Aに対して、
PrA  B  PrA PrB
である。より一般的には、どの２つも互いに素である
任意の事象列A1 , A 2 , に対して
が成り立つ。


Pr  A i    PrA i 
i
 i
離散確率分布
確率分布が有限の標本空間または加算無限の標本
空間上で定義されているとき、離散確率分布という。S
を標本空間としたとき、任意の事象Aに対して
PrA   Prs
sA
が成り立つ。また、Sが有限ですべての根元事象sϵSが
確率分布
1
Prs 
S
をもつとき、Sに関する一様確率分布という。
連続一様確率分布
a≤c≤d≤bであるような任意の閉区間[c,d]に対
して、連続一様確率分布は、事象[c,d]の確率
を
dc
Prc, d  
ba
と定義する。
条件付き確率と独立性
• 条件付き確率
事象Bが起こるという条件の下での事象Aの
条件付き確率はPr{B}≠0のとき、次のように定
義される。
PrA  B
PrA | B 
PrB
• 独立
PrA  B  PrAPrB
または、Pr{B} ≠0のときはこれと等価な条件
PrA | B  PrB
が成り立つとき、事象A,Bは独立であるという。
A1, A2 ,, An を事象の集合とするとき、すべての
1≤i<j≤nに対して
PrA i  A j   PrA i PrA j 
であるとき、これらの事象は対ごとに独立であるという。
この集合のすべてのk-部分集合A i1 , A i 2 ,, A i k が2≤k≤n
と1  i1  i2    ik  n に対して


   
 
Pr A i1  A i 2    A i k  Pr A i1 Pr A i 2  Pr A i k
を満たすとき、これらは相互独立だという。
Bayesの定理
条件付き確率の定義より、確率が0でない２つの事象AとBに対して、次式が
成り立つ。
PrA  B  PrBPrA | B
 PrAPrB | A
これをPr{A|B}に関して解くと、次式を得る。
PrA | B 
PrAPrB | A
PrB
（１）
さらにPr{B}は、次のように書ける。
PrB  PrB  A Pr B  A


 PrAPrB | A PrAPrB | A
これを、（１）式に代入すると、
PrAPrB | A
PrA | B 
PrAPrB | A Pr A Pr B | A
 

6.3 離散確率変数
離散確率変数Xとは、有限または加算無限の標
本空間Sから実数への関数である。確率変数Xと
実数xに対して、事象X=xを{sϵS:X(s)=x}と定義す
る。したがって、
PrX  x 
である。関数
 Prs
sS:X ( s )  x
f (x)  PrX  x
は、確率変数Xの確率密度関数である。
XとYが確率変数であるとき、関数
f x, y  PrX  xかつY  y
をXとYの結合確率密度関数という。yを定数とするとき、
PrY  y   PrX  xかつ Y  y
x
が成り立ち、同様に定数xに対して、
PrX  x   PrX  xかつ Y  y
y
が成り立つ。条件付き確率の定義を用いると、次式を
得る。
PrX  xかつ Y  y
PrX  x | Y  y 
PrY  y
すべてのx,yに対して
PrX  xかつY  y  PrX  xPrY  y
が成り立つとき、XとYは独立であると定義する。
確率変数の期待値
離散確率変数Xの期待値とは、
EX   x PrX  x
x
であり、上の和が有限か絶対収束する場合には
明確に定義される。
２つの確率変数の和の期待値は、それぞれの期
待値の和に等しい。すなわち、E[X],E[Y]が定義さ
れるなら、
EX  Y  EX  EY
である。期待値をμと記すこともある。
Xを任意の確率変数とするとき、任意の関数g(x)
は新たな確率変数g(X)を定義する。g(X)の期待
値が定義されるなら、
EgX    gx  PrX  x
x
である。g(x)=axとして、aを任意の定数とするとき、
EaX  aEX
が成り立つ。したがって、期待値は線形である。
すなわち、
EaX  Y  aEX  EY
が成り立つ。
２つの確率変数X,Yが独立で、それぞれに対して
期待値が定義されているとき、次式が成り立つ。
EXY    xy PrX  xかつ Y  y
x
y
  xy PrX  xPrY  y
x
y




   x PrX  x  y PrY  y
 x
 y

 EX EY 
一般に、n個の確率変数 X1 , X2 ,, Xn が相互独
立ならば、
EX1X2 Xn   EX1 EX2 EXn 
である。
確率変数Xが自然数N={0,1,2,…}からの値をと
るとき、

EX    i PrX  i
i 0

  iPrX  i PrX  i  1
i 0

  PrX  i
i 1
分散と標準偏差
平均がE[X]である確率変数Xの分散は、次のとおりである。
2
Var X  EX  EX 
 EX 2  E 2 X
確率変数Xの分散とaXの分散は次の関係がある。
Var aX  a 2 Var X
XとYが独立な確率変数であるとき、
VarX  Y  VarX  VarY
である。一般に、n個の確率変数X1, X2 ,, Xnが対ごとに独立であ
れば、次式が成り立つ。
n
 n
Var  X i    Var X i 
 i 1  i 1
確率変数Xの標準偏差はXの分散の平方根をとったものである。標
準偏差をσと書いたりする。この記号を用いると分散は 2 と記される。
6.4 幾何分布と２項分布
確率pで起こる成功と、確率q=1-pで起こる失
敗の２通りの結果しかないBernoulli試行を例
にして、幾何分布および２項分布について考
えていく。
• 幾何分布
確率変数Xを成功を得るのに必要な試行回数とすると、
k≥1に対して、
PrX  k  q k1p
が成り立つ。上を満たす確率分布を２項分布という。
幾何分布の期待値は、
EX    kq k 1p
k 1
p 
  kq k
q k 0
p
q
 
1 p
2
q 1  q 
分散は、
Var X  q p 2
• ２項分布
確率変数Xをn回の試行中の成功の回数と定
義すると、
 n  k n k
PrX  k   p q
k
が成り立つ。上の式を満たす確率分布を２項
分布という。便宜上、
n k
n k
bk; n, p    p 1  p 
k
という記号を用いる。
Xを２項分布b(k;n,p)に従う確率変数、Xᵢをi回
目の試行における成功回数を表す確率変数
とすると、期待値は
 n

EX   E  X i 
 i 1 
n
  EX i 
i 1
n
 p
i 1
 np
 
E Xi2  EXi   p
より、Xᵢの分散は
Var Xi   p  p 2  pq
であり、
 n

Var X   Var  X i 
 i 1 
n
  Var X i 
i 1
n
  pq
i 1
 npq
を得る。
２項分布b(k;n,p)は、kが0からnまで変化する
につれて平均値npに達するまで増加を続け、
その後減少する。連続する２項の比を取って
みると、
 n  k n k
 p q
k
bk; n , p 


bk  1; n , p   n  k 1 n  k 1

p q
 k  1

n  1p  k
   1
kq
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においてのみ極
大値をとる。
補題6.1
n≥0とし、0<p<1,q=1-p,0≤k≤nとする。このとき、
次式が成り立つ。
k
 np   nq 
bk; n, p     

 k  nk
n k
証明
n
nn
   k
n k
k
  k n  k 
を用いると、
 n  k n k
bk; n, p    p q
k
k
n  n 
  

k nk
k
n k
 np   nq 
  

 k  nk
p k q n k
n k
6.5 ２項分布の両端部分
１回の成功確率をpとするn回のBernoulli試行
において、ちょうどk回成功する確率よりも、少
なくともあるいは高々k回成功する確率のほう
がより興味深い場合が多い。この節では、２
項分布の両端部分について考える。
定理6.2
成功確率pであるn回のBernoulli試行
X：全成功回数を表す確率変数
このとき、0≤k≤nに対して少なくともk回成功す
る確率は
n
PrX  k   bi; n, p 
ik
n k
  p
k
である。
証明
6.1の練習問題から得られた次の不等式を利用する。
 n   n  n  k 

   

k

i
k
i

  

また、
n k
 bi; n  k, p   1
i 0
であるので、
n
n k
ik
i 0
PrX  k   bi; n, p    bk  i; n, p 
 n  k i
p 1  p n k i 
  
i 0  k  i 
n k n
  n  k  k i
p 1  p n k i 
   
i  0  k  i 
n k
 n  k n k  n  k  i
p 1  p n  k i
  p  
 k  i 0  i 
 n  k n k
n
  p  bi; n  k, p    p k
k i
k
系6.3
成功確率pであるn回のBernoulli試行
X:全成功回数を表す確率変数
このとき、0≤k≤nに対して高々k回成功する確率
は
k
PrX  k   bi; n, p 
i 0
 n 
n k
1  p 
 
n  k
n
n k


  1  p 
k
定理6.4
成功確率p,失敗確率q=1-pであるn回の
Bernoulli試行
X:全成功回数を表す確率変数とする。このと
き、0<k<npに対してk回より少なく成功する確
率は
k 1
PrX  k   bi; n, p 
i 0
kq

bk; n, p 
np  k
証明
幾何数列の級数和
k 1
 bi; n, p 
i 0
を評価する。
i=1,2,…,kに対して、次式を得る。
bi  1; n, p 
iq

n  i  1p
bi; n, p 
 i  q 

 
 n  i  p 
 n  q 

 
 n  k  p 
もし、
 n  q 
x 
   1
 n  k  p 
ならば、0<i≤kに対して
bi 1; n, p  xb i; n, p
が成り立つ。この操作を繰り返せば0≤i<kに対
して
bi; n, p  x bk; n, p
ki
が得られる。
よって、
k 1
k 1
i 0
i 0
k i


x

p
,
n
;
i
b
 bk; n, p 


 bk; n , p  x i
i 1
x
bk; n , p 

1 x
kq
bk; n , p 

nq  k
系6.5
成功確率pであるn回のBernoulli試行
X:全成功回数を表す確率変数
このとき、np<k<nに対してk回より多く成功す
る確率は次式で与えられる。
PrX  k 
n
 bi; n, p
i  k 1

n  k p

bk; n, p 
k  np
定理6.6
i=1,2,…,nに対するi番目の試行において成功
確率がpᵢ,失敗確率がqᵢ=1- pᵢであるn回の
Bernoulli試行
X:全成功回数を表す確率変数
μ=E[X]とおくと、r>μに対して次式が成り立つ。
 e 
PrX    r   
 r 
r
証明
x
e
任意のα>0に対して関数はxに関して強い
意味で増加関数であるので、
  X  
r
PrX    r  Pre
e 
が成り立つ。ここで、 αは後に決定される。
Markovの不等式
PrX  t  EX t
により、
を得る。


PrX    r  E eX  er
i=1,2,…,nに対して
Xᵢ:i回目のBernoulli試行が成功なら１、失敗な
ら０となる確率変数
とすると、
n
X   Xi
i 1
n
X     X i  p i 
i 1
が成り立つ。
X-μを置き換え、確率変数Xᵢが相互独立ならば確
率変数 e  X  p  は相互独立になることから、
i
i

E e   X  

 n  Xi  pi  
 E  e

 i 1


n
  E e  X i  pi 

i 1
期待値の定義から、


E e  X i  pi   e  1 pi p i  e  1 pi q i
 p i e q i  q i e  p i
 pi e  1

 exp p i e 
である。

n
   pi
i 1
であるので、



n
E e  X     exp p i e 
i 1

 
 exp e

が成り立つ。よって次式を得る。

PrX    r  exp e  r

  ln r 
と選べば次式が成り立つ。


 r ln r  
PrX    r  exp e
 exp r  r ln r  
ln  r  
er

r  r
 e 
 
 r 
r
系6.7
成功確率p,失敗確率q=1-pであるn回のBernoulli
試行
このとき、r>npに対して、
n
PrX  np  r   bk; n, p 
k  np r 
 npe 


 r 
r
証明
２項分布に対してE[X]=npが成り立つならばμ=np
である。
6.6 確率を用いた解析例
この節では３つの例を用いて確率を用いた解析
例を示す。
6.6.1
部屋にいるk人のなかで２人が同じ誕生日
である確率
6.6.2
ボールを箱に無作為に入れる場合
6.6.3
硬貨投げにおける連続して表の出る“列”
6.6.1 誕生日パラドックス
問題
部屋にいる人のうち２人が同じ日にうまれた確率が1/2を
超えるためには部屋に何人の人がいなければならない
か?
準備
それぞれの人に整数1,2,…,kの番号をつける。
k:人の数
１年はn=365（簡単のため、うるう年はなし）
bᵢ:i番目の人がうまれた日（i=1,2,…,k 1≤bᵢ≤n）
誕生日は１年のn日において一様に分布していると仮定
i=1,2,…,kとr=1,2,…,nに対して
Prbi  r  1 n
が成り立つ。
２人の人間iとjが同じ誕生日である確率は、
誕生日の無作為な選択が独立であることに
依存する。もし誕生日が独立であるならば、i
の誕生日とjの誕生日がある日rである確率は
Prbi  rかつ b j  r  Prbi  rPrb j  r
 1 n2
となる。
よって、部屋にいる２人の人間の誕生日が同じ
になる確率は
Prb i  b j    Prb i  rかつ b j  r
n
r 1
n
 1 n
2
r 1
1 n
である。
k人のうちの少なくとも２人の誕生日が同じにな
る確率は補事象を考えることにより解析できる。
K人が異なった誕生日である事象は
k 1
Bk   A i
i 1
である。ここで、Aᵢはi+1の誕生日がすべてのj≤iに対し
てjの誕生日と異なる事象である。すなわち、
A i  bi 1  b j : j  1,2,..., i
である。
Bk  Ak1  Bk1
と書くことができるので、漸化式
PrBk   PrBk1PrAk1 | Bk1
をえる。ここで、初期条件として
とする。
PrB1  1
b1, b2 ,..., bk1 が異なるならばn日から選ばれない
n-(k-1)日が存在するので、i=1,2,…,k-1に対して
bk  bi となる条件確率は(n-k+1)/nである。
先ほどの漸化式を繰り返し適用することにより、
PrBk   PrB1PrA1 | B1PrA 2 | B2  PrA k 1 | Bk 1
 n  1  n  2   n  k  1 
 1 



 n  n   n 
 1  2   k  1 
 1 1  1   1 

n 
 n  n  
を得る。
1  x  ex
により
 kk 1 2n  ln 1 2
のとき次式を得る。
PrB k   e 1 n e  2 n  e  k 1 n
i n

i 1
e

k 1
 e  k k 1 2 n
1 2
k(k-1)≥2nln2のとき、k人すべての誕生日が異なる確率
が1/2以下となる。よって23人以上いれば少なくとも２
人の誕生日が同じになる確率が1/2以上となる。
6.6.2 ボールと箱
同一のボールを1,2,…,bと番号付けられたb個
の箱に無作為に入れるという過程を考える。
ボールを入れるのは独立事象で、それぞれ
のボールはどの箱にも等確率で入れられる。
ボールがある特定の箱に入る確率は1/bであ
る。したがって、ボールを入れる過程は成功
確率1/bのBernoulli試行の列である。
• ある特定の箱に幾つのボールが入るか？
特定の箱に入るボールの数は２項分布
b(k;n,1/b)に従う。もしn個のボールが入れら
れるならば、特定の箱に入るボールの数の期
待値はn/bである。
• ある特定の箱にボールが１つ入るまでに平均
何回ボールをなげなければならないか？
箱にボールが入るまでにボールを投げ入れ
る回数は確率1/bの幾何分布に従うので、成
功までボールを投げ入れる平均回数は
1/(1/b)=bである。
• すべての箱に少なくとも１個のボールが入るまで
何回ボールを投げないといけないか？
空の箱にボールが入れられると“当たり”
b回当たるのに必要なボールの投げ入れ回数の
平均値nを求める。
i番目の段階をi-1回目の当たりの後からi回目の
当たりまでのボールの投げ入れと定義する。
i番目の段階におけるそれぞれのボールの投げ
入れに対して、ボールの入ったi-1の箱とb-i+1の
空の箱が存在する。よって、i番目の段階におけ
るすべてのボールの投げ入れに対して当たる確
率は(b-i+1)/bである。
nᵢ: i番目の段階におけるボールの投げ入れ
回数
b回の当たりを得るために必要な投げ入れ回
数は
b
n   ni
i 1
である。それぞれの確率変数はnᵢは成功確率
(b-i+1)/bの幾何分布をもつので次式を得る。
b
En i  
b  i 1
期待値の線形性から
 b

En   E  n i 
 i 1

b
  En i 
i 1
b

i 1
b
b  i 1
b
1
 b
i 1 i
 bln b  O1
したがって、すべての箱にボールが入るまでに
はおおよそblnb回の投げ入れが必要である。
6.6.3 連続硬貨投げ
公正な硬貨をn回投げるとする。連続して表が出
る最大の列はどの程度になると期待されるかを
考える。
答えは lg n 
まず表が連続する最大列の平均長がO(lgn)であ
ることを証明する。
Aik:i回目の硬貨投げから始めてk回以上表が続
けて出る事象(1≤k≤nかつ1≤i≤n-k+1)
任意の事象 Aik に対してk回すべてが表となる確
率はp=q=1/2の幾何分布である。
PrAik   1 2k
に対して
k  2lg n 


Pr A i , 2 lg n   1 2 2 lg n 
 1 2 2 lg n
 1 n2
である。任意の有限または加算無限の事象列について成り立つ
ブールの不等式
PrA1  A2    PrA1PrA2 
により、事象の和集合の確率は各事象の確率の和を超えないの
で、任意の位置から始めて2 lg n 以上表が続いて起こる確率は
n  2 lg n 1
 n
Pr   A i , 2 lg n    1 n 2
 i 1
 i 1
1 n
となる。
したがって、任意の列が 2lg n  以上の長さを
もつ確率は高々1/nであるので、最大列長
2lg n  より短くなる確率は少なくとも1-1/nであ
る。よって平均長は
2lg n 1  1 n   n1 n   Olg n 
で上から押さえられる。
次に下界 lg n の証明を行う。
長さ lg n  2 の列を見つける。


Pr A i , lg n  2  1 2 lg n  2
1
n
を得る。よって、表が lg n  2以上続く列の位置
がiで始まらない確率は高々1 1 n である。N
個の硬貨投げをそれぞれが lg n  2 回の連続
する硬貨投げからなる少なくとも2n lg n  の
グループに分けることができ、これらは互い
に独立な硬貨投げになる。
これらのグループのそれぞれが長さ lg n  2 の表
が続く列にならない確率は
1  1
n

2 n lg n  

 1 1
e
 2 n
lg n 1 
n

2 n lg n 1
n
 Oe lg n 
 O1 n 
したがって、最大列長がlg n  2 を超える確率は
1 O1 n 
である。最大列長の平均値は少なくとも
lg n  21  O1 n   0  1 n   lg n 
である。

Download Report