Cartersian product Binary relation a set of oredered pair로 나타낸다. set이기 때문에 set의 연산이 모두 가능하다. Binary relation은 두개의 pair의 관계를 나타낸 것이고 3개면 ternary, 4개면 quaternary라 한다. 표기는 다음처럼 한다. Ternary relation 4개일 때, n-ary일 때 모두 같다. Properties of Binary relations Reflexive relation (a,a)가 R에 있는 경우 Symmetric relation (a,b)가 R에 있으면 (b,a)도 있는 경우 Empty set U={}인 경우에도 성립한다. 대신 reflexive는 만족하지 않는다. S={(a,a)}면 symmet..

Permutation $$n(n-1)(n-2)...(n-r+1)=\frac{n!}{(n-r)!} = P(n,r)$$ #Example 하루에 한과목씩 7일동안 공부하려고 한다. 공부가 필요한 과목은 수학, 화학, 물리, 경제이다. 최소한 7일동안 각 과목을 한번씩 공부할 경우의 수는 얼마인가? A) 한번도 공부하지 않는 경우를 가정해 전체 경우에서 빼주면 된다. 전체의 경우: $4^7$ let $A_1$: 수학 한번도 공부 안하는 경우 $A_2$: 화학 한번도 공부 안하는 경우 $A_3$: 물리 한번도 공부 안하는 경우 $A_4$: 경제 한번도 공부 안하는 경우 그러면 정답은 $4^7 - |A_1 \cup A_2 \cup A_3 \cup A_4|$이다. $|A_1 \cup A_2 \cup A_3 \cup ..

개념적인 이야기가 많아서 그냥 나열해서 설명한다. $X$와 $Y$가 disjoint면, $X \cap Y = \emptyset$ Combinations of sets $P-Q$ : difference $\{a,b,c\}-\{a,b,d\} = \{c\}$ $P \oplus Q$ : symmetric difference $\{a,b,c\} \oplus \{a,c,d\} = \{b,d\}$ P와 Q에 동시에 속하지 않는 element이다. $\overline{Q}$ : complement Q의 여집합 Power set $P(\{a,b\}) = \{\{\}, \{a\}, \{b\}, \{a,b\}\}$ 집합의 크기가 $k$이면, $2^k$의 elements를 가짐 Properties of Sets Finite ..

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..