[05] Entropy Rates

AEP 덕분에 $X_i$가 iid인 경우에, $nH(X)$ bit만 있으면 데이터를 표현할 수 있었다. 그런데 RV가 iid가 아니거나 stationary RV라면 어떻게 될까?

 

우선 프로세스는 크게 Stochastic process와 Stationary process로 나뉜다.

 

Stochastic process

Joint distribution으로 표현 가능한 경우이다.

 

가령 Entropy의 stochastic process는 다음처럼 나타낼 수 있다.

 

Stationary process

시간에 따라 distribution이 변하지 않는 경우이다.

 

Markov Chain

바로 직전의 결과만이 현재에 영향을 주는 경우를 말한다.

정의

Joint pmf

 

Initial state와 transition matrix가 중요하다는 것을 알 수 있다. Markov chain에는 두가지 종류가 있다.

• Irreducible Markov Chain : 유한하게 한 state에서 아무 state로 갈 수 있는 경우
• Aperiodic Markov Chain : 1번 roundtrip이 있는 경우

*roundtrip= state a에서 a로 가기

 

Markov Chain and Stationary distribution

Markov chain에서 former과 latter 확률 사이의 관계는 다음처럼 나타낼 수 있다.

$$p(x_{n+1}) = \sum p(x_n, x_{n+1}) = \sum p(x_n)p(x_{n+1}|x_n) = \sum p(x_n) P_{x_n x_{n+1}} $$

 

이때 distribution이 변하지 않는 경우, 즉 $p(x_n) = p(x_{n+1})$이면 stationary distribution이며 Markov chain이 stationary process라고 말한다.

 

예를 들면 다음과 같이, transition distribution이 주어졌을 때, stationary distribution을 구할 수 있다.

 

이렇게 해서 entropy of state를 구할 수 있다. 이게 entropy rate를 의미하는 것은 아니다.

 

Entropy Rate

시간에 따라 생성되는 정보의 양을 측정하는 개념이다. 특히 과정에서의 단계나 심볼이 평균적으로 기여하는 정보의 양을 나타낸다. 이는 확률적 시퀀스나 데이터 스트림이 얼마나 빠르게 새로운 정보를 생성하는지 측정하는 지표로 볼 수도 있다.

 

예를 들어 다음처럼 구할 수 있다.

 

만약 RV가 iid라면,

하나의 entropy와 같게 된다.

 

또한, independent지만 identically distributed가 아니라면,

*특정 경우에 수렴하지 않을 수도 있다.

 

$H'(X)$ Conditional Entropy of Last RV

이전 모든 사건들에 대한 정보가 주어졌을 때, 마지막 변수의 conditional entropy를 구해볼 수 있다. 만약 이전의 사건들이 수렴한다면 $H'(X)$는 극한값이 된다.

 

두가지 theorem을 유도해볼 수 있다.

• Stationary stochastic process에 대해서, $H(X)$와 $H'(X)$의 극한값이 존재한다면, $$H(X)=H'(X)$$
• Stationary stochastic process에 대해서, $H(X_n|X_{n-1},...,X_1)$이 n에서 nonincreasing이고 $H'(X)$ 극한값을 가진다.

두번째 증명

 

Entropy rate of Markov Chain

다음의 과정을 통해서 구해볼 수 있다.

 

또한 다음과 같은 가정이 있으면,

$X_i$가 stationary markov chain

$\mu$가 stationary distribution

$P_{ij}$가 transition matrix

Entropy rate

 

예를 들어서, 아까 봤던 two state markov chain을 생각해 보자. Entropy rate는 다음과 같다.

아까 entropy state는 다음과 같았다.

 

이를 통해 entropy rate != entropy of state임을 알 수 있다. 이게 중요한 이유는 Entropy Rate는 시퀀스나 데이터 스트림 전체를 통틀어 평균적인 정보의 양을 측정하는 지표이고 Entropy of state는 특정 시점이나 상태에서의 불확실성의 양을 측정하는 지표라는 사실을 구분할 수 있어야 하기 때문이다.

 

Random Walk on Graph

Entropy rate를 고려해볼 수 있는 대표적인 예시중 하나이다. Edge는 $w_{ij}$를 가지며 transition matrix는 $P_{ij} = \frac {w_{ij}} {\sum_k w_{ik}}$이다.

 

노드 $i$에서의 weight 합은 $\sum_j w_{ij}$이다.

 

그럼 전체 노드에서의 weight = $W=\sum_{i,j: i>j} w_{ij}$

($\sum_i w_i=2W$)

 

이 경우에 stationary distribution을 예측해보면 $\mu_i = \frac {w_i} {2W}$라고 할 수 있다. 풀어보면 다음과 같다.

 

Weight가 모두 동일한 경우, $E_i$를 $i$에서 나오는 경우의 수라 하면,

 

Functions of Markov Chain

Stationary Markov chain $X_1, X_2, ..., X_n$이 있고 $Y_i = g(X_i)$라 했을 때,

 

일반적으로 $Y_1, Y_2, ..., Y_n$은 Markov process가 아니다.

 

$Y_1, Y_2, ..., Y_n$가 stationary라 했을 때, entropy rate를 구해보면, 다음과 같다.

 

Entropy rate of Y 계산하기 어렵기 때문에, 일반적으로 boundary를 구해서 해결한다.

• Upper bound
  $H(Y_n|Y_{n-1}, ..., Y_1) \rightarrow H(y)$ 수렴하는 성질을 이용해 구한다.
• Lower bound
  $H(Y_n|Y_{n-1}, ..., Y_1) \leq H(y)$

 

따라서 다음과 같은 boundary와 극한값의 관계를 구할 수 있다.