確率・情報理論基礎

確率・情報理論基礎
2001年度
情報ネットワーク学専攻
伊藤秀一
講義の概要
• 確率と統計学の基礎
• 情報理論の基礎
– 情報源符号化
– 通信路符号化
• その他・行く先不明
参考書など
• W.Feller: An Introduction to Probability
Theory and Its Applications, John Wiley
(翻訳有り 確率論とその応用)
• T.Cover, J.Thomas: Elements of
Information Theory, John Wiley
• 橋本: 情報理論, 培風館
• 韓,小林: 情報と符号化の数理, 培風館
• その他、そのつど紹介する。
講義の進め方
• 例題
• 宿題・レポート
• 期末試験?
数理的な考え方に基づく学問体系とその工
学的な応用に触れ、勉強のおもしろさを発
見してほしい。
第1章 はじめに
情報と通信、情報理論の生立ち、情
報とは、 …
情報と通信
• 情報の伝送
– のろし、半鐘
– 腕木、セマフォ(ナポレオン)
正確さ、距離の限界
• 19世紀ー電気通信の出現
– 産業革命
– 情報革命
エネルギー
大規模なものが可能、いろいろな問題点が明らかになった。
例
• Kelvin の海底電線
– 周波数と時間の関係ーー通信工学のはじまり
• 雑音のある通信路
– 通話が正確に伝わらない
• 「サクラチル」 Y or N, 0, 1
• ゆっくりと話す
ディジタル通信
情報の理論的な取り扱い
• 定量的に扱う必要
• 確率の概念
• 情報と雑音
– Wiener … 予測とろ波、サイバネッティクス
– Shannon … 近代的情報理論
“A mathematical theory of communication,” 1948
情報量、情報源、通信路、通信路容量、符号化基本定理
通信の基本モデル
情報源
符号器
通信路
復号器
• 通信路容量
– 通信路符号化、無誤り伝送の限界
• エントロピー
– 情報源符号化、データ圧縮の限界
受信者
伝送と蓄積
• 通信
– 情報を距離の隔たった場所へ移動する
• 蓄積
– 情報を時間の隔たった時点へ移動する
圧縮技術と誤りに打ち勝つ符号化技術
第2章 確率論の基礎
確率とは何か?
• 正しく作られたサイコロを振る
– 1の目の出る確率は1/6
– 現実の現象を良く説明できる・・・なぜ?
• 開票速報「X氏は90%以上の確率で当選
確実」?
– 既に確定しているはず
– 判断確率
• 公理主義による確率の定義
確率的実験 (試行)
• コイン・トス
– 表か裏が出る
– 表が出るか裏が出るかわからない
– 何度でも実験できる
• ルーレット
– 0から36と00の38の区画、赤と黒(可能な結果)
– 数または数の組み合わせを賭ける (分らない)
– 何度でも繰り返し実験できる
続き
• 30cm定規の長さ
– 製造された物差しの精度を検査
– 29cmから31cmの間
• 電球の寿命
– 選んだ電球の寿命 ・・・ 分らない
– 0から∞の間
ランダム(無作為)実験
• 定義 ランダム実験(試行)
– 実験結果のすべての実現値は事前に既知
– 実験結果はあらかじめ分らない
– 実験は同じ条件の元で何度でも繰り返してで
きる
標本空間(可測空間)
• 定義 ランダム試行の標本空間 (, S )
–
– S
試行の実現値の全集合
 部分集合の族(σ-加法族)
• 説明
– Ωの要素を標本点 (sample point) という
– 集合 A S を事象 (event) という。事象は
標本点の集合である。
– 試行の結果の標本点が A の要素であれば、
その試行により事象 A が生起したという。
– 1つの標本点だけの集合を素事象(単純事
象)という。
– |Ω|が有限 → (, S )は有限標本空間
可算 → 離散標本空間
非可算 → 非可算標本空間
例
• コイン・トス
  H, T 
S   , H , T , H , T 
• 2つのコイン
  H , H , H , T , T , H , T , T 
 , H , H , H , T , T , H ,
S 

 , H , T , T , H , T , T , 
• 「少なくともひとつの表が出る」事象
{( H , H ), ( H , T ), (T , H )}
• サイコロを n 回振る
n
– Ωは 6 個の単純事象をもつ。
– 1を少なくとも1回はもつ事象 A
• 表が出るまでコインを振る
– S はすべての自然数の部分集合の族
• 回転する針
• 長さ l の棒を投げる
r
2l
l

0
r



確率公理
• 確率測度の定義 集合関数 P(S)
• 注1 Ωが離散、有界(高々n)のとき
• 注2 Ωが離散、可算のとき
– 素事象に等確率を割り当てることは出来ない。
– 素事象に確率を割り当てれば十分である。
• 注3 Ωが連続、非可算のとき
– 各素事象に正の確率を割り当てられない。
– 例えば
• 定義: (, S , P ) を確率空間、確率測度空
間という。
• 例
– コイン・トス
Ω={H, T}
– 離散、可算の場合
• 例
Ωが非可算
• 定理1
• 系
• nul 事象
• 確定事象
加法定理
• 定理
– 証明
• 系
ネストした集合列
• 定理
P が下から(上から)の連続性を持つ。
• 上極限
• 下極限
ランダム試行の割り当てる確率
• 例

1
1

A
0.5
A
0
0.5
1
0
1
• Buffon’s Needle
r
2l
l

0
r



• Buffon’s Needle
r
l


Bertrand’s Paradox
条件つき確率
条件つき確率