pptx

様々な情報源(4章)
1
情報源の役割
情報
情報源
伝送路
(通信路)
受信者
今回扱う。
☆無記憶情報源
(前の記号に依存しない情報
源。サイコロのような情報源)
☆マルコフ情報源
(前の結果に依存する情報源。
英文等は、こっちの方)
2
情報源モデル
情報源アルファベット
S = {s1, s 2, L , sn }
情報源:
離散的な時刻に従い、
ある記号の集合から、
各時刻に一つの記号
を(ある確率的性格
で)出力する。
t
情報源から発生する記号の
集合
情報源シンボル(記号)
情報源から発生する記号。
情報源アルファベットの要素
記号 st i Î S は、時刻 t i
で発生した情報源記号
st1 s t 2 s t 3 s t 4 L
時間軸
3
情報源例1
サイコロを振る試行
による記号の生成。
情報源アルファベット
D = {1, 2, 3, 4, 5, 6}
st1 = 3 st2 = 5 st 3 = 2
L
t
1回は3の目がでた。
4
情報源例2
英文からアルファ
ベットを拾って記号を
生成。
情報源アルファベット
A = {a, b, c, L , z }
st1 = i st2 = n st 3 = f
L
t
1文字目は”i”だった。
inf ormation ?
5
通報(メッセージ)
定義:通報
情報源から発生する記号系を通報という。
情報源
通報
st1 s t 2 s t 3 s t 4
s
(n )
L
n
t
時間軸
= st 1 s t 2 L s t n
n
s
(n )
t
= st - (n - 1)st - (n - 2) L st
n
6
情報源における記憶
無記憶情報源
st1 s t 2 s t 3 s t 4
記号の生成確率が、
以前の記号に無関係
L
記憶のある情報源
st1 s t 2 s t 3 s t 4
L
記号の生成確率が、
生成した記号で変化する
7
無記憶情報源(独立情報源)
無記憶情報源
, L
ìï s1
S = ïí
ïï P (s1 ) , L
î
st1 s t 2 s t 3 s t 4
üï
ïý
, P (sn )ïï
þ
, sn
記号の生成確率が、
以前の記号に無関係
L
無記憶情報源の1記号あたりの(平均)情報量は、
次式で表される。
n
H (S ) = -
å
P (sk ) log P (sk )
[bit / 記号]
k= 1
8
1記号の発生速度を
r
[記号 / 単位時間]
*
とする。このとき、単位時間あたりの発生平均情報量は、
次式であらわされる。
H * (S ) = r *H (S )
n
= - r * å P (sk ) log P (sk )
[bit / 単位時間]
k= 1
以下に注意する。
左辺=[bit / 単位時間]
右辺=記号
[
/ 単位時間][bit / 記号] = [bit / 単位時間]
9
記憶のある情報源
記号の生成確率が、
以前の記号で変化する
記憶ある情報
S = {s1, s2, L , sn }
1
1
{P (s1), L , P (sn )} {P 2(s1), L , P 2(sn )}
{P
3
3
(s1 ), L , P (sn )}
4
4
P
(
s
),
L
,
P
(sn )}
{ 1
st1 s t 2 s t 3 s t 4
L
10
問題
次の四角に入るアルファベットを求めよ。
(1)
(2)
m
t
m
n
e
t
in
is
m
il
t
at
(3)
speake
teache
manne
11
マルコフ情報源
12
マルコフ情報源
定義:マルコフ情報源
直前のm 個の記号よって、次記号の発生確率が変化する
情報源を(m重)マルコフ情報源という。
発生した記号を条件とする条件付確率で定式化される。
すなわち、次の条件付き確率で定められる情報源である。
" s , s 1, s 2 , L , s m Î S
P (s | s1, s 2 , L , s m )
s
は今度発
生する記号
s 1, s 2 , L , s m
は直
前のm個の記号列。
カンマはANDの意味。
13
(単純)マルコフ情報源
定義:マルコフ情報源
直前の生成された記号よって、次記号の発生確率が変化
する情報源を単純マルコフ情報源という。
発生した記号を条件とする条件付確率で定式化される。
すなわち、
に対して条件付確率
" s, s ' Î S
P (s | s ')
で定められる情報源である。
s
は今度発生する記号
s ' は直前に発
生した記号
14
マルコフ情報源における状態の遷移
S = {s1, L , sn }
P (s1 | s1 )
s1
s1
s2
P (s 2 | s1 )
P (s n | s1 )
P (s1 | s 2 )
s2
P (s 2 | s 2 )
P (sn | s 2 )
sn
s1
s2
sn
sn
15
状態遷移(確率)行列
éP (s1 | s1 ) P (s 2 | s1 )
ê
êP (s | s ) P (s | s )
2
2
ê 1 2
P = ê
ê M
O
ê
êP (s | s )
L
êë 1 n
L
L
O
L
P (s n | s1 ) ù
ú
P (s n | s 2 ) ú
ú
ú=
M ú
ú
P (sn | sn )ú
ú
û
éP1 ù
ê ú
êP ú
ê 2ú
ê ú
ê Mú
ê ú
êPn ú
êë ú
û
行ベクトルはすべて、確率ベクトル(要素は全て0から1
の値を持ち、要素の総和が1)。すなわち、確率ベクトル
p = ( p1, p2 , L , pn ) に対して次式が成り立つ。
1 £ i £ n,
0 £ pi £ 1
n
å
i= 1
pi = 1
16
状態遷移確率行列のイメージ
次の記号
sj
P
前の記号
si
条件付確率
添え字の順
序に注意
pij = P (s j | si )
各行で総和は1
si , s j Î S = {s1, L , sn }
なので正方行列
17
シャノン線図(状態遷移図)
S = {s1, L , sn }
P (s1 | s1 )
S1
P (s 2 | s1 )
P (si | s1 )
P (sn | sn )
P (s n | s1 )
Sn
P (s1 | si )
Si
記号を状態と
みなし、条件
付確率を矢
印で表したも
の。
S2
P (s 2 | s 2 )
S3
P (s 3 | s 3 )
18
マルコフ情報源例(アルファベット)
A = {a, b, c, L , z }
a
P (a | a )
b
a
P (b | a )
P (z | a )
P (a | b)
b
P (b | b)
P (z | b)
z
英単語において、
thやer
が多いことから、
P (h | t ) や P (r | e )
が大きいと考えられる。
a
b
z
z
19
状態遷移行列
éP (a | a ) P (b | a )
ê
êP (a | b) P (b | b)
ê
P= ê
ê M
O
ê
êP (a | z )
L
êë
辞書
L P (z | a ) ù
ú
ú
L P (z | z ) ú
ú=
O
M ú
ú
ú
L P (z | z ) ú
û
a
b
éPa ù
ê ú
êP ú
ê bú
ê ú
ê Mú
ê ú
êPz ú
êë úû
aa
ab
az
20
シャノン線図(アルファベット)
A = {a, b, c, L , z }
z
a
b
c
bÎ A
P (b | a )
aÎ A
P (a | a )
21
マルコフ情報源例(2元単純マルコフ情報源)
生成記号が 生成記号が
B = {0,1}
0の列
P (0 | 0) = 1/ 4
0
0
P (1 | 0) = 3 / 4
P (0 | 1) = 2 / 3
1
P (1 | 1) = 1/ 3
1
0
1
1の列
状態(記号)
が0の行
P =
é1/ 4 3 / 4ù
ê
ú
ê2 / 3 1/ 3 ú
êë
ú
û
状態(記号)
が1の行
22
2元単純マルコフ情報源のシャノン線図
3
4
1
4
1
0
1
3
2
3
23
練習1
次の状態遷移確率行列で表されるマルコフ情報源を、シャ
ノン線図で表せ。
é1/ 2 1/ 4
0
0
0 1/ 4ù
ê
ú
ê1/ 4 1/ 2 1/ 4
ú
0
0
0
ê
ú
ê
ú
ê 0 1/ 4 1/ 2 1/ 4
0
0 ú
ú
P = êê
ú
0
0
1/
4
1/
2
1/
4
0
ê
ú
ê
ú
ê0
0
0 1/ 4 1/ 2 1/ 4ú
ê
ú
ê1/ 4
ú
0
0
0
1/
4
1/
2
êë
ú
û 24
練習2
次のシャノン線図で表されるマルコフ情報源の状態
遷移確率行列を求めよ。
0.5
0.6
0.2
S1
0.2
0.1
0.7
S2
0.8
S4
0.2
0.1
S5
0.4
0.1
S6
0.1
1.0
0.7
S3
0.3
25
練習3
次のようなマルコフ情報源の、
状態遷移確率行列およびシャノン線図を求めよ。
手 = {グー、 チョ キ、 パー}
自分が出した手の次の手は、
・前の手に勝つような手を出す確率が1/2である。
・前の手に引き分ける手を出す確率が1/3である。
・前の手に負ける手を出す確率が1/6である。
26
(参考)無記憶情報源の状態遷移行列
均等なサイコロを振ったときの状態遷移行列
次 出る目
今の目
1
2
3
4
5
6
1 é1/ 6 1/ 6 1/ 6 1/ 6 1/ 6 1/ 6ù
2
P =
3
4
5
6
ê
ê1/
ê
ê
ê1/
ê
ê1/
ê
ê
ê1/
ê
ê1/
êë
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
6 1/ 6 1/ 6 1/ 6 1/ 6 1/
ú
6ú
ú
ú
6ú 条件付
ú 確率
6ú
ú
ú
6ú
ú
6ú
ú
û
27
偶数の出やすいサイコロ(無記憶情報源)
次 出る目
今の目
1
2
3
4
5
6
1 é1/ 12 1/ 4 1/ 12 1/ 4 1/ 12 1/ 4 ù
2
P =
3
4
5
6
ê
ê1/ 12
ê
ê
ê1/ 12
ê
ê1/ 12
ê
ê
ê1/ 12
ê
ê1/ 12
êë
1/ 4 1/ 12 1/ 4 1/ 12 1/
1/ 4 1/ 12 1/ 4 1/ 12 1/
1/ 4 1/ 12 1/ 4 1/ 12 1/
1/ 4 1/ 12 1/ 4 1/ 12 1/
1/ 4 1/ 12 1/ 4 1/ 12 1/
ú
4ú
ú
ú
4 ú 条件付
ú 確率
4ú
ú
ú
4ú
ú
4ú
ú
û
28
練習
(1)コインを振って得られる状態遷移関数を求めよ。
(2)表の出る確率が、裏のでる確率の2倍であるコインを
振って得られる状態遷移関数を求めよ。
29
定常分布
定義:定常分布
情報源アルファベット S = {s1, s 2, L , sn } に対して、
出現確率が時刻 t
と時刻 t + 1 で変化しないよう
な記号の分布を定常分布という。
t
t
P (sn )
P (s1 )
s1
sn
P
t+1
" si Î S
P t (si ) = P t + 1(si )
t
P (si )
(sn )
s1
sn
s2
si Î S
P
t+1
s2
si Î S
P
t+1
(si )
30
(s1 )
定常分布の求め方
定常分布は、状態遷移確率行列から求めることができる。
定常分布をz = (z 1, z 2 , L , z n ) とし、状態遷移確率行列を
P = [pij ] とする。このとき、次式が成り立つ。
時刻 t からt + 1になっても変化しない。
常に一定の出現確率となる。
z = zP
記号の出現確率。
生成した記号の確率と状
態遷移確率積なので、次
の記号の出現確率を表す。
31
z = zP
の意味。
éP (s1 | s1 ) P (s 2 | s1 )
ê
êP (s | s ) P (s | s )
2
2
ê 1 2
ê
(P (s1 ), L , P (sn )) = (P (s1 ), L , P (s n ))
ê M
M
ê
êP (s | s )
L
êë 1 n
L
L
O
L
P (s n | s1 ) ù
ú
M ú
ú
ú
M ú
ú
P (sn | sn )ú
ú
û
情報理論では、慣用的に確率ベクトルは行ベ
クトルで表される。
t
t
t
z = P z
æP (s1 ) ö
÷
çç
÷
ççP (s ) ÷
÷
çç 2 ÷
÷
÷
=
çç
÷
÷
çç M ÷
÷
÷
çç
÷
÷
P
(
s
)
çèç n ø
÷
÷
転置を用いて左式のようにも表せる。
éP (s1 | s1 ) P (s1 | s 2 )
ê
êP (s | s ) P (s | s )
2
2
ê 2 1
ê
ê M
M
ê
êP (s | s )
L
êë n 1
L
L
O
L
P (s1 | s n ) ùæ
P (s1 ) ö
÷
ç
úç
÷
÷
ç
ú
M úççP (s 2 ) ÷
÷
÷
ç
÷
úç
÷
ç
ú
M ç M÷
÷
÷
úçç
÷
÷
ú
÷
P (sn | sn )úèççP (sn )ø
÷
÷
ûç
32
定常分布例
情報源アルファベットB = {0,1} に対する2元マルコフ情報
源の状態遷移確率関数が次式で与えられている。
é1/ 4 3/ 4ù
ê
ú
P = ê
ú
êë2/ 3 1/ 3 ú
û
このとき、定常分布 z = (z 0, z 1 ) = (P (0), P (1)) を求めよ。
解)
é1/ 4 3/ 4ù
ú
(z 0, z 1 ) = (z 0, z 1 ) êê
ú
2/
3
1/
3
êë
ú
û
より、
æz 0 ÷
ö
çç ÷=
çèz 1 ÷
÷
ø
é1/ 4 2 / 3ùæz 0 ö
ê
úç ÷
÷
ç
ê3 / 4 1/ 3 úçz 1 ÷
è ÷
ø
êë
ú
û
33
ìï 3
2
ïï z 0 = z 1
3
\ ïí 4
ïï 2
3
z
=
z0
ïï 1
4
î3
\ 9z 0 = 8z 1
一方、z
全ての行ベクトルが確率ベクトルなので遷移
確率行列は正則でなく逆行列を持たない。
よって、このように必ず不定の解になる。
は確率ベクトルなので、
前のスライドとこの式か
ら求める。
z 0 + z1 = 1
が成り立つ。
9
\ z0 + z0 = 1
8
8
\ z0 =
17
9
\ z1 =
17
検算
é1/ 4 3 / 4ù
ú
8 / 17 9 / 17 êê
ú
2
/
3
1/
3
êë
ú
û
(
(
= (8 / 17
)
= 2 / 17 + 6 / 17 6 / 17 + 9 / 17
9 / 17
)
34
)
練習
次の状態遷移確率行列で表される情報源の定常分布を求めよ。
(1)
(2)
é2/ 5 3/ 5ù
ê
ú
P1 = ê
ú
êë1/ 2 1/ 2 ú
û
é1/ 2 1/ 2
ù
0
ê
ú
ê
ú
P2 = ê 0 1/ 3 2 / 3ú
ê
ú
ê3 / 4
ú
0
1/
4
êë
ú
û
35
無記憶情報源における定常分布
無記憶情報源における定常分布は、出現確率と一致する。
無記憶情報源が次式で表されているとする。
, L
ìï s1
S = ïí
ïï P (s1 ) , L
î
üï
ïý
, P (sn )ïï
þ
, sn
このとき、状態遷移確率行列は次式で表される。
éP (s1 ) L
ê
êP (s ) L
ê 1
P= ê
ê M
ê
êP (s ) L
êë 1
P (sn )ù
ú
P (sn )úú
ú
Mú
ú
P (sn )úú
û
すべての行が同一な
状態遷移行列。
逆に、このような行列
で表される情報源が
無記憶情報源。
36
(P (s )
1
L
éP (s1 ) L
ê
êP (s ) L
ê 1
P (s n ) ê
ê M
ê
êP (s ) L
êë 1
)
æ
çç
n
= ççP (s1 ) å P (s i ) L
çç
i = 142 4443
144
çè
1
(
= P (s1 ) L
P (s n )
P (s n )ù
ú
P (s n )úú
ú
Mú
ú
ú
P (s n )ú
û
ö÷
n
÷
÷
P (s n ) å P (s i )÷
÷
÷
i144
= 142 4443÷
÷
ø
1
)
37
マルコフ情報源の随伴(無記憶)情報源
定義:随伴情報源
マルコフ情報源 S の定常分布を確率分布とするような
無記憶情報源を元のマルコフ情報源の随伴情報源 S
という。
例
情報源アルファベット B
遷移確率行列が
= {0,1}
é1/ 4 3/
PB = êê
êë2/ 3 1/
で表されるマルコフ情報源を S
このとき、随伴情報源
B
SB
を持ち、状態
4ù
ú
ú
3ú
û
とする。
は次式で表される。
ìï 0
,
1 ü
ï
ï
ïý
SB = í
ïï 8 / 17 , 9 / 17ïï
î
þ
38
マルコフ情報源のエントロピー
定義:マルコフ情報源のエントロピー
S
マルコフ情報源
付きエントロピー
トロピーという。
H (S | S ) =
に対して、
H (S
å
S
| S)
S
を条件とする
の条件
をマルコフ情報源のエン
P (s i )H (S | s i )
si Î S
= -
å
si Î S
= -
P (s i )å P (s j | s i ) log P (s j | s i )
sj Î S
å
P (s i )P (s j | s i ) log P (s j | s i )
å
P (s j , s i ) log P (s j | s i )
si ,s j Î S
= -
si ,s j Î S
39
マルコフ情報源のエントロピー例
状態遷移確率行列
PB =
é1/ 4 3/ 4ù
ê
ú
ê2/ 3 1/ 3 ú
êë
ú
û
で定まるマルコフ情報源 S B のエントロピーを求める。
まず、定常分布
z
は以下で与えられる。
æ8 9 ÷
ö
z = (P (0), P (1)) = çç , ÷
è17 17 ø
状態0におけるエントロピー(0を条件とする条件付きエントロピー)
H (S B | 0) および状態1におけるエントロピー H (S B | 1)
を求める。
40
H (S B | 0) = - P (0 | 0) log P (0 | 0) - P (1 | 0) log P (1 | 0)
æ1 ÷
ö
= H ç
÷
ç
è4 ø
; 0.811
0の時のエントロピー
H (S B | 1) = - P (0 | 1) log P (0 | 1) - P (1 | 1) log P (1 | 1)
æ1 ö
÷
= H ç
ç
è3 ÷
ø
; 0.918
1の時のエントロピー
\ H (S B | S B ) = P (0)H (S B | 0) + P (1)H (S B | 1)
8
æ1 ö
9
÷
=
H ç
+
H
÷
ç
è 4 ø 17
17
; 0.382 + 0.486
= 0.868
æ1 ö
÷
ç
÷
ç
è3 ø
マルコフ情報源のエントロピー
41
マルコフ情報源のエントロピーの意味
1
4
P (0)
P (1)
0状態の一種の
存在確率
1状態の一種の
存在確率
0
3
4
H (S B | 0)
2
3
0状態において、
記号出力に注目し
た平均情報量
1
1
3
H (S B | 1)
1状態において、
記号出力に注目し
た平均情報量
42
イメージ
0を取ったら次は0の箱から取り、1を取ったら次は1の箱からと
る。取った玉は元に戻す。(前のスライドに対応する。)
マルコフ情報源
0
1
1
1
SB
0
0
1
43
練習
次の状態遷移確率行列で表される情報源のエントロピーを求めよ。
(1)
(2)
é2/ 5 3/ 5ù
ê
ú
P1 = ê
ú
êë1/ 2 1/ 2 ú
û
é1/ 2 1/ 2
ù
0
ê
ú
ê
ú
P2 = ê 0 1/ 3 2 / 3ú
ê
ú
ê3 / 4
ú
0
1/
4
êë
ú
û
44
マルコフ情報源のエントロピーの性質
S
S
マルコフ情報源
に対して、随伴情報源を
とす
る。このとき、随伴情報源のエントロピーは、マルコフ情報源
のエントロピー以上である。すなわち、次式が成り立つ。
H (S | S ) £ H (S )
出現確率は同じでも、マルコフ情報源の方は記号の
現れ方に制限がある。(すなわち、記号の出現の予測
が無記憶情報源比べて行いやすい。)したがって、
マルコフ情報源の方が平均情報量が少なくなる。
45
随伴情報源のエントロピー例
é1/ 4 3/ 4ù
ú
PB = êê
ú
の随伴情報源は
2/
3
1/
3
êë
ú
û
ìï 0
,
1 ü
ïï
ï
SB = í
ý
ïï 8 / 17 , 9 / 17ïï
î
þ
である。
したがて、エントロピー H (S B ) は次式で求められる。
æ8 ö
H (S B ) = H çç ÷
; 0.997
÷
è17 ø
\ 0.868 ; H (S B | S B ) £ H (S B ) ; 0.997
46
練習
(1)
(2)
次の状態遷移確率行列で現されるマルコフ情報源
の随伴情報源のエントロピーを求めよ。
é2/ 5 3/ 5ù
ê
ú
P1 = ê
ú
êë1/ 2 1/ 2 ú
û
é1/ 2 1/ 2
ù
0
ê
ú
ê
ú
P2 = ê 0 1/ 3 2 / 3ú
ê
ú
ê3 / 4
ú
0
1/
4
êë
ú
û
47
情報源の分類
48
情報源の分類図
情報源
無記憶
情報源
記憶のある情報源
マルコフ情報源
エルゴード
マルコフ情報源
正規マル
コフ情報
源
周期的
情報源
を含む
過渡的な情
報源を含む
49
様々なマルコフ情報源
エルゴード
マルコフ情報源
a1
b1
a2
c1
b2
a3
a4
過渡的な情
報源
b4
b3
周期的
情報源
c3
c2
非周期的情
報源
矢印には0より大きい確率が割り当てられている。
50
エルゴード性
定義:エルゴード性
集合平均と時間平均が等しい性質をエルゴード性という。
[集合平均]=[時間平均]
エルゴード性を持つ情報源をエルゴード情報源という。
集合平均
時間軸
t1
時間平均
t1
t2
t3
51
サイコロ D i を振ったときの目を情報源と考えると、
エルゴード性を満たす。
t1
t2
L
tj
L
tT
D1
3
2
L
6
L
1
D2
2
4
L
1
L
5
M
M M
Di
5
M
M M
Dn
2
3
1
M
L
6
M
L
M
L
4
1
時間平均:
1つのサイ
コロを何回
も振ったと
きの平均
M
L
3
集合平均:1回に多数のサイ
コロを振ったときの平均
52
状態遷移行列による判別
ép11
ê
êp21
P = êê
êM
êp
êë n 1
ép (t )11
ê
ê (t )
êp 21
t
P = êê
ê M
ê (t )
êp n 1
ë
p1n ù
ú
p2 n ú
ú
Múú
pnn úú
û
p12 L
p22 L
O
O
L
L
p (t )12 L
p (t )22 L
O
O
L
L
p (t )1n ù
ú
(t ) ú
p 2n ú
ú
Mú
ú
ú
(t )
p nn ú
û
pij = P (s j | si )
前の記号 s i のときに次の
記号 s j を生成する確率。
添え字の順序に注意する。
t
P = P
gP42gL444
gP
1444
43
t個
遷移を t 回繰り返すときの
遷移確率。
53
過渡的なマルコフ情報源
定義:過渡的な情報源
十分な時間経過の後に、生成確率がすべて0に収束するよ
うな状態を持つマルコフ情報源を過渡的な情報源という。
過渡的な情報源
$ j , " i,
a1
a2
a3
t ® ¥
é0
ê
ê0
ê
P = ê
ê0
ê
ê0
ë
Þ
p12
p13
0
p23
p32
0
0
0
0 ù
ú
p24 ú
ú
p4 ú
ú
ú
p44 ú
û
pij (t ) ® 0
é0
ê
ê0
ê
t
P = ê
ê0
ê
ê0
ë
0
0
0
0
0
0
0
0
0ù
ú
0ú
ú
0ú
ú
ú
1ú
û
a4
過渡的
54
エルゴードマルコフ情報源
定義:エルゴード情報源
過渡的でない情報源をエルゴード情報源という。エルゴード
情報源はエルゴード性を満たす。
エルゴード情報源
" i, j , $ t ij ,
b1
b4
b2
b3
é0
ê
êp21
ê
P = ê
ê0
ê
êp41
ë
pij
p12
0
0
p23
0
0
0
p43
0 ù
ú
0 úú
p34 úú
ú
0 ú
û
周期的
( t ij )
P
> 0
é0
ê
ê ( to )
êp 21
= ê
ê0
ê
ê (t )
êp o 41
ê
ë
to
P
te
ép ( te )11
ê
ê
ê0
= ê
êp ( te )
ê
31
ê
ê0
ê
ë
p ( to )12
0
0
p (to )23
p ( to ) 32
0
0
p (to ) 43
0
p ( t 3 )13
p (te )22
0
0
p ( te ) 33
p (te ) 42
0
p ( to )14 ù
ú
ú
0
ú
ú
p ( to ) 34 ú
ú
ú
ú
0
ú
û
ù
ú
ú
( te )
p 24 ú
ú
ú
0
ú
ú
p (te ) 44 ú
ú
û
0
55
正規マルコフ情報源
定義:エルゴード情報源
十分な時間経過後、各状態からすべての状態への遷移確率
が0より大きいマルコフ情報源を正規マルコフ情報源という。
正規マルコフ情報源
pij (t ) > 0
" i, j , $ t ,
ép
ê 11
ê
P = êp21
ê
êp31
êë
c1
c3
c2
p12
0
p32
0ù
ú
ú
p23 ú
ú
0ú
ú
û
ép (t )
ê 11
ê (t )
t
P = êp 21
ê
ê (t )
êëp 31
p (t )12
p (t )22
p (t ) 32
p (t )13 ù
ú
ú
(t )
p 23 ú
ú
(t ) ú
p 33 ú
û
全ての確率は非零
56
練習
次の遷移行列で表わされるマルコフ情報源の種類が、
過渡的、周期的、正規マルコフ情報源のいずれかを答えよ。
(1)
(2)
é0
ê
ê0.2
ê
P = ê
ê0
ê
ê0.5
ë
é0.3
ê
ê0.6
ê
P = ê
ê0
ê
ê0
ë
0.6 0.1 0.3ù
ú
0
0.5 0 ú
ú
ú
0.7 0
0.3ú
ú
0
0.5 0 ú
û
0.5 0.2 0 ù
ú
0
0
0.4 ú
ú
ú
0
0.7 0.3 ú
ú
0
0.5 0.5 ú
û
57