『情報理論』第３章の勉強メモです。
情報源のモデル
離散的$M$元情報源を扱う。
定められた時点ごとに１つずつ情報源記号を発生する。
情報源記号は$M$個の情報アルファベットの集合$A=\lbrace a_1,a_2,\ldots,a_m\rbrace$。
情報源の統計的表現
情報源アルファベットを$A=\lbrace a_1,a_2,\ldots,a_m\rbrace$で表し、
時点$i$の情報源の出力を$X_i\ (i=0,1,2,\ldots)$で表す。
時点$n-1$までの情報源系列$X_0X_1\cdots X_{n-1}$の統計的性質は、結合確率分布
$P_{X_0X_1\cdots X_{n-1}}(x_0,x_1,\cdots,x_{n-1})=[X_0=x_0,X_1=x_1,\cdots,X_{n-1}=x_{n-1}となる確率]$
が与えられれば定まる。
無記憶定常情報源
無記憶情報源
各時点における情報源記号の発生が、ほかの時点と独立であるとき、この情報源を無記憶情報源という。
$P(x_n|x_0,x_1,\cdots,x_{n-1})=P(x_n)$
無記憶定常情報源
無記憶情報源において、各時点における情報源記号の発生が同一の確率分布に従うとき、無記憶定常情報源または独立同一分布情報源という。
$P_{X_0\cdots X_{n-1}}(x_0,\cdots,x_{n-1})=\Pi_{i=0}^{n-1}P_X(x_i)$
定常情報源とエルゴード情報源
定常情報源
時間をずらしても統計的性質が変わらない情報源を定常情報源という。
$P_{X_0X_1\cdots X_{n-1}}(x_0,x_1,\cdots,x_{n-1})=P_{X_iX_{i+1}\cdots X_{i+n-1}}(x_0,x_1,\cdots,x_{n-1})$
ここで、任意の正数$n,i$
エルゴード情報源
十分長い情報源系列に、その情報源の統計的性質が完全に現れている定常情報源をエルゴード情報源という。
定常分布が$P_X(x)$である定常情報源の出力$X$を変数とする任意の関数$f(X)$について、その平均値は
$\overline{f(X)}=\sum_{x\in A}f(x)P_X(x)$
となる。これは、$f(X)$の集合平均と呼ばれる。
１つの情報源からの出力系列$x_0x_1x_2\cdots$について、$f(X)$の時間平均は
$<f(X)>=\lim_{n\to\infty}\frac{1}{n}\sum_{i=0}^{n-1}f(x_i)$
となる。
任意の関数$f(X)$について、$\overline{f(X)}=<f(X)>$が成立するとき、エルゴード情報源という。
大数の法則
確率変数$\lbrace X_n\rbrace$は独立同一分布に従い、その平均を$E[X_n]=\mu$とする。
確率変数の標本平均を$\bar{X_n}=\frac{1}{n}(X_1+X_2+\cdots +X_n)$とする。
大数の弱法則とは、$n\to\infty$のもとで標本平均$\bar{X_n}$が平均$\mu$に確率収束すること。
$\forall\epsilon>0,\ \lim_{n\to\infty}P(|\bar{X_n}-\mu|>\epsilon)=0$
大数の強法則とは、$n\to\infty$のもとで標本平均$\bar{X_n}$が平均$\mu$に概収束すること。
$P(\lim_{n\to\infty}X_n=\mu)=1$
エルゴード理論
マルコフ情報源
マルコフ情報源の定義
任意の時点の出力の確率分布を、その直前の$m$個の出力だけから決めることができる情報源を$m$重マルコフ情報源という。
$P_{X_i|X_{i-1}\cdots X_{i-n}}(x_i|x_{i-1},\ldots,x_{i-n})=P_{X_i|X_{i-1}\cdots X_{i-m}}(x_i|x_{i-1},\ldots,x_{i-m})\ \ (n\geq m)$
状態の分類
ある状態$s_j$から推移を始めた時、いつかはその状態$s_j$に戻ってくる確率を回帰確率$f_{jj}$とする。
- $f_{jj}<1$、すなわち、戻らないことがある状態を過渡状態
- $f_{jj}=1$、すなわち、必ず戻ってくる状態を再帰状態
$s_j$から出発して$k$回推移後に初めて$s_j$に戻る確率$f_{jj}^{(k)}$は
$f_{jj}^{(k)}=P(x_0=s_j,x_k=s_j)-f_{jj}^{(1)}P(x_0=s_j,x_{k-1}=s_j)-f_{jj}^{(2)}P(x_0=s_j,x_{k-2}=s_j)-\cdots -f_{jj}^{(k-1)}P(x_0=s_j,x_{1}=s_j)$
となる。これより、
$f_{jj}=\sum_{k=1}^{\infty}f_{jj}^{(k)}$
また、再帰状態は3に分類される。
- 吸収状態：$P(x_0=s_j,x_{1}=s_j)=1$
- エルゴード的状態：$P(x_0=s_j,x_n=s_j)\neq 0$となる$n$の最大公約数が$1$である状態
- 周期的状態：$P(x_0=s_j,x_n=s_j)\neq 0$となる$n$の最大公約数が$2$以上である状態
一つの再帰状態からなるマルコフ情報源を既約マルコフ情報源という。さらに、エルゴード的状態であるときを正規マルコフ情報源という。
極限分布と定常分布
$N$個の状態$s_0,s_1,\ldots,s_{N-1}$をもつマルコフ情報源について考える。
状態$s_i$にあるとき、次の時点で状態$s_j$に遷移する確率は
$p_{ij}=P(s_j|s_i)$
となる。マルコフ情報源の遷移確率という。この遷移確率$p_{ij}$を$(i,j)$要素とする$N\times N$行列を遷移確率行列という。
ここで、状態$s_i$から出発して、$t$時点後に$s_j$に到達する確率を$p_{ij}^{(t)}$とする。
正規マルコフ情報源は、ある正数$t_0$に対して、$p_{ij}^{(t_0)}>0$となるような情報源である。
時点$t$において状態$s_j$にいる確率を$w_j^{(t)}$として、
$w_t=(w_0^{(t)},w_1^{(t)},\ldots,w_{N-1}^{(t)})$
という$N$次元ベクトルを定義する。$w_t$は時点$t$における状態の確率分布を表すので状態確率分布ベクトルという。遷移確率行列$\Pi$を用いて、
$w_t=w_0\Pi^t$
とできる。ここで、$w_0$は初期分布という。
$w_t$の$t\to\infty$とした状態を極限分布という。正規マルコフ情報源では初期分布によらない極限分布が存在する。
また、$w\Pi = w$をみたす状態分布を定常分布という。
正規マルコフ情報源は、定常分布がただ一つ存在し、極限分布と一致する。
一般のマルコフ情報源は、少なくとも一つ以上の定常分布が存在する。
通信路のモデル
通信路の統計的記述
通信路は各時点において、一つの記号が入力され、一つの記号が出力される。入力記号は入力アルファベットの元であり、出力記号は出力アルファベットの元である。入力アルファベットと出力アルファベットが一致するとき、アルファベットの属する記号の数$r$を用いて、$r$元通信路という。
任意の長さの入力系列$X_0X_1\cdots X_{n-1}$が与えられたとき、それに対応する出力系列$Y_0Y_1\cdots Y_{n-1}$とする。通信路の統計的性質は、確率
$P_{Y_0\cdots Y_{n-1}|X_0\cdots X_{n-1}}(y_0,\ldots,y_{n-1}|x_0,\ldots,x_{n-1})$
がわかればよい。
無記憶定常通信路
各時点の出力の現れ方が、その時点の入力には関係するが、それ以外の時点の出力・入力に独立となるとき、無記憶通信路という。この通信路が時間をずらしても統計的性質が変わらないとき、無記憶定常通信路という。
無記憶定常通信路の統計的性質は
$P_{Y_0\cdots Y_{n-1}|X_0\cdots X_{n-1}}(y_0,\ldots,y_{n-1}|x_0,\ldots,x_{n-1})=\Pi_{i=0}^{n-1}P_{Y_i|X_i}(y_i|x_i)$
となる。
入力アルファベットを$A=\lbrace a_1,a_2,\ldots,a_r\rbrace$、出力アルファベットを$B=\lbrace b_1,b_2,\ldots,b_s\rbrace$とし、$p_{ij}=P_{Y|X}(b_j|a_i)$とおく。$p_{ij}$を$(i,j)$要素とした$r\times s$行列$T$を通信路行列という。
2元対称通信路
入出力アルファベットが$2$元$\lbrace 0,1\rbrace$で、定常無記憶で、対称性が成り立つ通信路モデルを$2$元対象通信路（BSC）という。
2元消失通信路
通信路上で発生したノイズによって受信信号を復調することが困難で、記号を判定できないとき、消失という。
$2$元対称通信路において、入力が消失になることがある通信路モデルを$2$元消失通信路（BEC）という。
通信路の誤りによる表現
通信路に誤り$E$が加わると出力は$Y=X+E$となる。
この誤り源の統計的性質が入力とは独立であるものを加法的通信路という。
誤りの発生がほかの時点の誤りの発生と独立であるとき、ランダム誤りという。
加法的白色ガウス雑音通信路
入出力アルファベットが連続地の集合となるアナログ通信路モデルにおいて、誤り源が独立で平均$0$の正規分布に従うとき、加法的白色ガウス雑音通信路（AWGN通信路）という。
バースト誤り通信路
誤りが一度生じると、その後しばらく誤りが続いて生じることをバースト誤りという。
バースト誤りの最初から最後まですべての記号が誤っているものをソリッドバースト誤りという。
ギルバートモデル
通信路の誤り率が極めて低い$2$元対象通信路（$G$状態）と比較的高い$2$元対象通信路（$B$状態）の二つの状態をマルコフ過程で遷移する通信路モデル。
バースト誤り通信路を表した簡単なモデル。
フリッチマンモデル
ギルバートモデルの一般化で、より複雑なバースト誤り通信路に適合したモデル。
複数の$G$状態$(G_1,\ldots,G_n)$が存在し、任意の$G_i$状態と$B$状態は互いに遷移可能だが、$G_i$状態と$G_j$状態は遷移不可能となる。