Entropy $$H(X) = - \sum p(x) log p(x)$$ Properties of H $H(X) \geq 0$ $H_b(X) = log_b a H_a(X)$ Conditioning reduces entropy $H(X|Y) \leq H(X)$ (w/ eq. iff X and Y are independet) $H(X_1, X_2, ..., X_n) \leq \sum H(X_i)$ (w/ eq. iff $X_i$ are independent) $H(X) \leq log |X|$ (w/ eq. iff X is uniformly distributed over X) $H(p)$ is concave in $p$ Relative Entropy $$D(p||q) = \sum p(x) log \frac {..

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 바로 직전의 결과만이 현재에 영향을 주는 경우를 말한다. Initial state와 transition matrix가 중요하다는 것을 ..

대수적 균등 분할 원리라 하며, 큰 수의 법칙과 밀접한 관련이 있다. 장기간에 걸쳐 확률적 과정의 결과가 어떻게 나타나는지 다룬다. Convergence of Random Variable $X_i$가 iid이며 $E(X_1)=E(X_2)=...=E(X_n)$을 만족한다고 가정하자. 이때 $\overline{X_n}=\frac{1}{n}(X_1+...+X_n)$이라고 하자. 그러면 대수의 법칙에 의해서 $n→\infty$, $\overline{X_n}→\mu$가 된다. 우리는 그러면 $\overline{X_n}$을 다음을 만족하는 RV라고 생각해볼 수 있다. 두가지 type(strong, weak)으로 수렴이 인식된다. Types of Convergence 수렴의 종류는 구체적으로 4가지로 구분된다. A..

Convex function $x_1, x_2$에 대해서 다음의 조건을 만족하면, 함수 $f$는 convex라고 한다. 또한 2차 미분이 모든 곳에서 양수면 convex이다. Inequality Jensen's Inequality 어떤 $f$가 convex이면, 다음의 조건을 만족한다. 어떤 함수의 기댓값은 기댓값을 취한 후, 함수를 적용하는 것보다 크거나 같음을 의미한다. 또한 $f$가 strictly convex면, $X=E[X]$고 $X$는 constant임을 알 수 있다. (equality가 성립하는 조건) Information Inequality 정보 불평등이라 불리는 이유는 오직 p(x)=q(x)일 경우에만, equality가 성립하기 때문이다. 이 말은 대부분의 경우 p와 q는 다르기 때문에..

Uncertainty Random variable X에 대해서 X가 discrete하거나 continuous한 경우, 다음처럼 확률을 표현할 수 있다. Discrete (pmf) : $P(x) = Pr\{X=x\}$ where $\sum P(x)=1$ Continuous (pdf) : $\int f(x) dx = 1$ cdf = $F(x) = Pr(X \leq x)$ $f(x) = F'(x)$ 확률을 보고 uncertainty를 결정할 수 있다. Low Prob. = High Uncertainty High Prob. = Low Uncertainty 예를 들어서, coin toss를 하는데, head가 나올 P가 1이면, uncertainty는 0이 된다. 확실하니까 Entropy Uncertainty를 ..

Axiomatic Approach, 공리적 접근 수학이론의 응용을 "Measure Theory"라고 한다. 보통 triplet $ (\Omega, F, P) $으로 표현한다. $\Omega$ : sample space / 모든 가능한 outputs $F$ : $\sigma$-algebra / 모든 가능한 events $P$ : 확률 Conditional Probability A와 B가 event이고 $P(A) > 0$이면, $$ P(B|A) = \frac{P(A \cap B)}{P(A)} $$ $$ P(A \cap B) = P(B|A)P(A) = P(A|B)P(B) $$ 위의 관계에서 Bayes rule도 유도할 수 있다. $$ P(A|B) = \frac {P(B|A)P(A)} {P(B)} $$ Tota..

정보량을 수학적으로 수치화하고 분석하려는 학문이다. Shannon에 의해 시작된 학문으로 두가지 fundamental한 요소를 파악하는 것이 목표이다. the entropy H the channel capacity C 위에서 볼 수 있듯이, 통신하는 과정에서 정보 손실을 최소화하는 것이 목표이다. 초기에는 어느정도의 에러로 정보를 전송하는 것이 불가능하다고 여겨졌다. 그런데, Shannon이 error 발생 확률을 거의 0이 될 수 있음을 보임으로써, channel noise로 capacity를 구해 정보량의 손실 없이 통신하는 방법을 제안한다. entropy of source < capacity of channel = error-free