こちら

情報ネットワーク学基礎１最終プロジェクトについて
発表日：８月２５日（月）１０時３０から
レポートの目的 :
最終プロジェクトでは，各グループに分かれて確率に関するシミュレーションを行い，グループ内で
の議論やお互いの協力を通じて，確率論に対する理解を深めることを目標とする.
[注意事項] :
最終プロジェクトはでグループ全員で取り組むこと．発表の際にはグループの誰が何を担当したかを
明示すること．使用するプログラミング言語に関しては特に指定しない．ただし，Mathematica や
MATLAB や Maple 等の商用ソフトを用いてはいけない．
必要に応じて他のグループと相談したり，参考書などを参照しても良いが，その場合には相談者や参
考書について明記すること．使用したプログラムを示す必要はない．また，発表に際しては発表スラ
イドを作成し，そのスライド（必要に応じて補助資料）を２０部印刷すること．
擬似乱数発生 :
1. プログラム環境上で利用できる数値ライブラリを用いて，適当に大きな N の値 (1 万から 10 万
程度) に対して，一様分布 U(0, 1) にしたがう確率変数を近似する擬似乱数 z1 , z2 , . . . , zN を発
生させる．用いた擬似乱数発生関数が近似的に一様乱数を生成しているかどうかを目視で確か
めるため，n − 1 個の点 Pk = (zk , zk+1 ), 1 ≤ k < N , を適当なグラフィックツール (例えば，フ
リーソフトの Processing や gnuplot など) を用いて, 平面上の点としてプロットせよ．疑似乱数
の精度がよければ，(0, 1) × (0, 1) ⊂ R2 の平面内に点に偏りがなくまばらに散らばっているはず
である．まずは小さい数（N = 100 程度）から始めて疑似乱数の精度をチェックする．
注意: プログラムにある random 関数について何をしているかを確認すること．また，一様擬似
乱数発生アルゴリズムにも様々なものがあるので，各自調べること．
2. 上記 1 において生成した疑似乱数 z1 , z2 , . . . , zN をもとに，それぞれの割り当てられた問題にし
たがう確率変数を近似する疑似乱数列 x1 , x2 , . . . , xn を発生させる．
3. 上記 2 で生成した擬似乱数列からヒストグラムを作成することにより，期待値や分散を計算し，
理論値と近いかどうかを確認せよ．
[注意事項]:
確率関数や確率密度関数に関する詳細については講義ノートを参照すること．また，ある確率関数や
密度関数に従う疑似乱数を発生させる際には，プログラムのライブラリ等を使用せず，各自で考える
こと．(Hint: 逆関数法とは何か調べてみよ．
）
1
プロジェクト内容
Project A （Monty Hall 問題）
授業および演習問題で扱った Monty Hall 問題について，演習問題 4-2 の場合を考える．部屋の数が
n のとき，ゲストが部屋を変更した方が当たる確率が n − 1 倍になることを解説したうえで，n が３
より大きい場合について，n をいろいろ変えて（例えば，n = 5, 10, 100）数値シミュレーションを行
い，非常に多くの試行から実際に n − 1 倍になることを観察せよ．
Project B （パケット分割問題）
演習問題 10（パケット分割問題）を考える．問題の解答について解説したうえで，指数分布のパラ
メータ α を適当な値に設定し，現実的なパケットサイズ a を用いて数値シミュレーションを行い，α
と a をいろいろ変えて，パケット数と端パケットの大きさの期待値の振る舞いを観察せよ．
Project C （２度ふり試行）
表が出る確率が p であるコインを n 枚ふる．このとき，表の出る枚数は二項分布 B(n, p) に従う．次
に，表が出たコインを再度ふり直す．このとき，１回目にふった際に表が出たコインの数を x および，
２回目にふった際に表が出たコインの数を y とする．X, Y に関する同時確率分布を考え，周辺化に
より，Y が従う確率関数が二項分布 B(n, p2 ) になることを示せ．次に，適当な n > 3 と p をいろいろ
設定し，数値シミュレーションを行い，Y の振る舞いを観察せよ．
Project D（ポアソン分布の再生性）
A 市と B 市において天気の観測を行ったところ，A 市の晴れの日数に対する確率変数 X と，B 市の
晴れの日数に対する確率変数 Y は，それぞれ λA ，λB をパラメータとするポアソン分布に従うこと
が分かった．X と Y が独立のとき，A 市と B 市の晴れの日の合計に対する確率変数 Z = X + Y は
λ = λA + λB をパラメータとするポアソン分布に従うことを確認せよ（7 月 16 日分の演習問題 12 を
参照）．次に，適当な λA や λB を色々設定し，数値シミュレーションを行い，Z の振る舞いを確か
めよ．
Project E（The Asymptotic Equipartition Property:AEP)
n ビットのメッセージを送受信する場合を考える．標本空間 Ω を Ω = {n ビットのメッセージ全
体 } = {0, 1}n とし，Xi を送信するメッセージの i 番目のビット，Yi を受信したメッセージの i 番目の
ビットに対する確率変数とする．2 元対称通信路 (Binary Symmetric Channel; BSC) とは，送信者が i 番
目のビットとして xi ∈ {0, 1} を送信した際に，受信者が yi ∈ {0, 1} を受信する確率 P (Yi = yi |Xi = xi )
が，

1 − p if x = y
i
i
P (Yi = yi |Xi = xi ) =
p
otherwise
で表される通信路である．上記における p を反転確率 (crossover probability) と呼ぶ．
いま，X1 , X2 , . . . , Xn を i.i.d. とする (このとき，Y1 , Y2 , . . . , Yn も i.i.d. となる）．送信者がメッセー
ジを送信する際に，i 番目のビットにおいて 0 を送る確率を PXi (0) = 32 ，1 を送る確率を PXi (1) = 31
とする．このとき，受信者が i 番目のビットにおいて 0 を受け取る確率 PYi (0) と 1 を受け取る確率
PYi (1) は，反転確率 p の関数として求める事ができる．
確率変数 Yi のエントロピー H(Yi ) は．対数の底を 2 として
∑
H(Yi ) =
PYi (yi ) log PYi (yi )
yi
= −PYi (0) log PYi (0) − PYi (1) log PYi (1)
= E[− log P (Yi )]
2
で定義される．仮定より Y1 , Y2 , . . . , Yn は i.i.d なので，確率変数 log PY1 (y1 ), log PY2 (y2 ), . . . , log PYn (yn )
も i.i.d. となる．よって，大数の弱法則を用いると，
(
)
n
1∑
1
log PYi (yi ) = − log PY1 ,Y2 ,...,Yn (y1 , y2 , . . . , yn )
−
n
n
i=1
は n → ∞ で H(Y1 ) に確率収束する．そのことを，数値シミュレーションを用いて確かめよ．
ここで，大数の弱法則をもう一度思い出してみよう．
定理 1 (大数の弱法則, weak law of large numbers) n 個の確率変数 X1 , X2 , · · · , Xn が独立同一分布
に従うとき，E[X12 ] < ∞ であれば，以下が成り立つ．
}
{ n
1 ∑
∀ε > 0, lim Pr Xi − E[X1 ] > ε = 0
(1)
n→∞
n
i=1
また，数列の極限は以下のように定義される．
極限の復習
数列 {an } において
lim an = α
n→∞
であるとは ∀δ > 0, ∃Mδ ∈ N such that ∀n ≥ Mδ , |an − α| < δ が成り立つことである 1 ．
よって，式 (1) は任意の（微小な）ε > 0 を選んで固定したとき，
{ n
}
1 ∑
∀δ > 0, ∃n > Mδ,ε ∈ N such that ∀n ≥ Mδ,ε , Pr Xi − E[X1 ] > ε < δ
n
i=1
が成り立つことを意味する．
つまり，ある数列の十分大きな n での振る舞い，特に極限値に収束する様子を見たい場合には δ > 0 を
小さくしたときにも必ず n を大きくすると an の値が a に十分近く，i.e., |an − a| < δ ，成り立っているこ
とを様々な δ と n で確かめることになる．
この論理式は，∀δ > 0, ∃Mδ ∈ N, ∀n ≥ Mδ , |an − α| < δ や ∀δ > 0, ∃Mδ ∈ N (∀n ≥ Mδ ⇒ |an − α| < δ) や
∀δ > 0, ∃Mδ ∈ N, ∀n ∈ N (n ≥ Mδ ⇒ |an − α| < δ) とも書かれる．
1
3

Download Report