6. Discrete Probability

6.1. An Introduction to Discrete Probaility

Introduction

Probability theory(확률 이론)은 17세기부터 프랑스 수학자 Blaise Pascal이 주사위를 반복해 굴려 결과를 내는 인기있는 도박의 승산을 계산하는 것으로 시작되었다.

18세기에 도박을 연구한 프랑스 수학자 Laplace가 사건의 확률을 성공적인 결과의 수를 가능한 결과의 수로 나눈 값으로 정의하였다.

정보

Example

주사위를 굴렸을 때 홀수가 나올 확률

가능한 결과 총 6개(1, 2, 3, 4, 5, 6), 성공적인 결과 총 3개(1, 3, 5)이므로 홀수가 나올 확률은 $3/6=\frac{1}{2}$

Finite Probability

Experiment(시행) = Possible outcome set 중 하나를 생성하는 Procedure이다.
Sample space(표본 공간) = Experiment의 Possible outcom set이다.

만약 $S$가 같은 확률을 가진 Finite sample space, $E$가 event($S$의 Subset)일 때 $E$의 Probability는 Notation $p(E)=\frac{|E|}{|S|}$이다.

Notation $\approx$는 값이 대략 같음을 의미한다.

팁

Example

한 항아리에 파란 공 4개, 빨간 공 5개가 들어 있을 때 항아리에서 선택한 하나의 공이 파란 공일 Probability

Sample space $S$의 $|S|$ = 9, 파란 공이 나올 event $|E|$ = 4로 즉 $\frac{|S|}{|E|}=\frac{4}{9}$이다.

팁

Example

1부터 50까지의 공이 들어있는 통에서 11, 4, 17, 39, 23이 통에 공을 다시 넣을 때와 넣지 않을 때의 순서대로 뽑힐 확률

1. 공을 다시 통에 넣는 경우

   이 경우를 Sampling with replacement라고 한다.
   매 번 50개 중 1개가 원하는 값이여야 하므로 Probability는 $\frac{1}{50^5}=\frac{1}{312500000}$이다.

2. 공을 다시 통에 넣지 않을 경우
   이 경우를 Sampling without replacement라고 한다.
   매 번 50개 중 1개, 49개 중 1개, $\cdots$ 46개 중 1개가 원하는 값이여야 하므로 Probability는 $\frac{1}{50\cdot 49\cdot 48\cdot 47\cdot 46}=\frac{1}{254251200}$이다.

The Probability of Combinations of Events

정보

Theorem

Sample space의 Event $E$에 대해 $E$의 Complementary event인 $\overline{E}$에 대해 $p(\overline{E})=1-p(E)$

• Proof
  $\overline{E}$의 Probability를 구하기 위해 $|\overline{E}|=|S|-|E|$임을 이용하여
  $p(\overline{E})=\frac{|S|-|E|}{|S|}=1-\frac{|E|}{|S|}=1-p(E)$로 증명 가능하다.

팁

Example

길이가 10인 Bit string에 대해 Bit value가 0인 Bit가 적어도 하나 이상 있을 Probability

• Solution

  Event $E$를 Bit가 모두 1인 길이가 10인 Bit string의 Probability라고 할 때 $p(E)=\frac{1}{2^{10}}$임을 이용하여 $1-\frac{1}{2^10}=1-\frac{1}{1024}=\frac{1023}{1024}$로 해결 가능하다.

정보

Theorem

Sample space $S$의 Event $E_1$, $E_2$에 대해 $p(E_1\cup E_2)=p(E_1)+p(E_2)-p(E_1\cap E_2)$

• Proof
  Principle of inclusion-exclusion으로 증명 가능하다.
  $p(E_1\cup E_2)=\frac{|E_1\cap E_2|}{|S|}=\frac{|E_1|+|E_2|-|E_1\cap E2|}{|S|}(\because\ Principle\ of\ inclusion-exclusion)=p(E_1)+p(E_2)-p(E_1\cap E_2)$

팁

Example

무작위로 선택된 100 이하의 Positive integer가 2나 5로 나누어 떨어질 Probability

• Solution
  $E_1$을 2로 나누어 떨어지는 Event, $E_2$를 5로 나누어 떨어지는 Event로 둘 경우 $E_1\cap E_2$는 2와 5로 나누어 떨어지는, 즉 10으로 나누어 떨어지는 Event로 둘 수 있다.
  $p(E_1\cup E_2)=\frac{50}{100}+\frac{20}{100}-\frac{10}{100}=\frac{60}{100}=0.6$으로 해결 가능하다.

Probabilistic Reasoning

팁

Example

The Monty Hall Three-Door Puzzle
세 개의 문 중 하나의 문 뒤에만 보상이 있을 때 게임 참가자가 문 세 개 중 하나를 고르면 진행자가 선택하지 않은 문들 중 보상이 없는 문을 열었을 때 참가자가 문을 바꾸는 것이 이득일 지 그대로 유지하는 것이 이득일 지 판단

• Solution
  1. 참가자가 보상이 있는 문을 선택할 Probability는 $\frac{1}{3}$이다.
  이 때 진행자가 보상이 없는 문을 열더라도 선택한 문을 바꾸는 것과 바꾸지 않는 것 둘 다 보상이 있는 문을 선택했을 때 결과는 달라지지 않는다.
  2. 참가자가 보상이 없는 문을 선택할 Probobility는 $\frac{2}{3}$이다.
  이 때 진행자가 보상이 없는 문을 열게 되면 선택한 문을 바꾸었을 때 이 경우 보상이 있는 문을 선택하게 되므로 항상 보상을 받게 된다.
  다른 문을 열고 바꿀 기회를 줄 경우 바꾸었을 때 보상을 받을 Probability는 $\frac{2}{3}$로 바꾸는 것이 더 이득이다.

6.2. Probability Theory

Assigning Probabilities

Sample space $S$가 Finite하거나 Countable한 Outcome을 가진 공간이라고 가정할 때, 각 Outcome set $s$에 대한 Probability $p(s)$를 할당할 수 있으며 이 때 두 조건이 충족되어야 한다.

1. $0\leq p(s) \leq 1\ for\ each\ s\in S$
2. $\sum_{s\in S}p(s)=1$

위 조건 1은 각 Outcome의 Probability가 0이상 1이하의 Nonnegative integer라는 뜻이고 조건 2는 각 Outcome $s$의 Probability의 합이 1이 되어야 한다는 뜻이다.
단 Sample space가 Infinite인 경우 $\sum_{s\in S}p(s)$는 1에 수렴하는 Infinite series이다.
Sample space $S$의 모든 Outcome set에서 Function $p$는 Probability distribution(확률 분포)라고 한다.

팁

Example

공정한 동전을 던졌을 때 Outcome set $H$(Heads)와 $T$(Tails)에 어떤 Probability를 부여해야 하는가(1)와 만약 Heads가 Tails보다 두 배 많이 나올 경우의 Probability(2)

• Solution (1)
  $p(H)=p(T)\ and\ p(H)+p(T)=1\ \therefore p(H)=p(T)=\frac{1}{2}=0.5$
• Solution (2)
  $p(H)=2p(T)\ and\ p(H)+p(T)=1\therefore p(T)=\frac{1}{3}\ and\ p(H)=\frac{2}{3}$

Set $S$가 $n$개의 Element를 가진다고 가정할 시 Uniform distribution(균일 분포)는 $S$의 각 Element에 $\frac{1}{n}$의 Probability를 할당한다.

Event $E$의 Probability는 $E$에 포함된 Element들의 Probability의 합이 즉, $p(E)=\sum_{s\in S}p(s)$이다.

팁

Example

주사위가 조작되어 3이 다른 숫자보다 두 배 자주 발생하고, 나머지 다섯 가지 결과는 동등한 Probability로 발생할 때 홀수가 나올 확률

• Solution
  $p(1)=p(2)=p(4)=p(5)=p(6)=\frac{1}{2}p(3)=\frac{1}{7}\therefore p(E)=p(1)+p(3)+p(5)=\frac{4}{7}$

Combinations of Events

Event $E$의 Conplementary event $\overline{E}$는 $p(\overline{E})=1-p(E)$이므로 $\sum_{s\in S}p(s)=1=p(E)+p(\overline{E})$이다.
Sample space $S$에 대해 $E_1$, $E_2$의 Union의 Probability는 Principle of include-exclude에 의해 $p(E_1\cup E_2)=p(E_1)+p(E_2)-p(E_1\cap E_2)$이다.
위 두 Expresssion을 이용하여 $E_1,\ E_2,\ \cdots$가 Sample space $S$의Pairwise disjoint event일 때 $p \left(\underset{i}\bigcup E_i\right)=\underset{i} \sum p(E_i)$임을 알 수 있다.

Conditional Probability

Event $E$, $F$에 대해 $p(F)>0$일 때 $F$가 주어진 $E$의 Conditional probability를 Notation $p(E | F)$로 나타내고 $p(E|F)=\frac{ p(E\cap F)}{p(F)}$를 의미한다.

팁

Example

길이가 4인 Bit string이 무작위로 생성되며 16개의 길이 4인 Bit string이 동일한 Probability로 발생할 때 첫 Bit가 0일 때 Bit string에 최소 두 개의 연속된 0 Bit가 포함될 Probability

• Solution
  $E$가 최소 두 개의 연속된 0 Bit를 포함, $F$가 첫 Bit가 0일 때$E\cap F=\{0000, 0001, 0010, 0011, 0100\}$이므로 $p(E\cap F)=\frac{5}{16}$이다.
  $p(F)=\frac{1}{2}$이므로 $p(E|F)=\frac{5/16}{1/2}=\frac{5}{8}$이다.

Independence

Event $E$, $F$에 대해 두 Event가 Independent(독립적)이라고 할 때 $p(E\cap F)=p(E)p(F)$를 만족한다.

팁

Example

무작위 길이가 4인 Bit string을 생성할 때 Event $E$가 Bit string이 1로 시작, $F$가 1의 개수가 짝수일 때 $E$와 $F$가 Independent인 지 확인

• Solution
  $p(E)=\frac{1}{2}$, $p(F)=\frac{1}{2}$이고 $E\cap F=\{1111, 1100, 1010, 1001\}$이므로 $p(E\cap F)=\frac{4}{16}=\frac{1}{4}$이므로 $p(E\cap F)=p(E)p(F)$를 만족하므로 Independent임을 확인 가능하다.

Bernoulli Trials and the Binomial Distribution

두 Outcome을 가지고 있는 Experiment를 Bernoulli trial(베르누이 시행)이라고 한다.
일반적으로 Bernuolli trial에서 Success의 Probability를 $p$, Failure의 Probability를 $q$로 나타내며 $p+q=1$이다.

정보

Theorem

$n$개의 Mutually independent(상호 독립)인 Bernoulli trial에 대해 $k$번 Success할 Probability $C(n, k)p^kq^{n-k}$

• Proof

  $n$개의 Bernoulli trial이 수행될 때 Outcome은 n-tuple($t_1,\ t_2,\ \cdots ,t_n$)로 표현되며 $t_i=Success$이거나 $t_i=Failure$이다.
  $n$개의 Trial은 Independent이므로 $k$개의 Success와 $n-k$개의 Failure가 발생하므로 각 Trail의 Probability는 $p^kq^{n-k}$이다.
  즉 $k$개의 Success와 $n-k$개의 Failure를 가진 개수는 $C(n, k)$이므로 $k$개의 Success일 Probability는 $C(n,k)p^kq^{n-k}$이다.

Binomial distribution(이항 분포)는 $n$개의Independent Bernoulli trial의 Success probability $p$, Failure probability $q=1-p$일 때 $k$개의 Success인 Probability를 Notation $b(k;n, p)$로나타낸다.
즉, 위 Theorem에 의해 $b(k;n, p)=C(n,k)p^kq^{n-k}$이다.

팁

Example

0 Bit가 발생할 Probability가 0.9, 1 Bit가 발생할 Probability가 0.1일 때 Bit가 Independent하게 생성된 10개의 Bit가 생성될 때 정확히 8개의 0 Bit가 생성될 Probability

• Solution
  $b(8;10,0.9)=C(10,8)(0.9)^8(0.1)^2=\frac{10!}{2!8!}(0.9)^8(0.1)^2=45(0.9)^8(0.1)^2=0.1937102445$로 구할 수 있다.

Random Variables

Random variable(확률 변수)은 Expreiment의 Sample space set에서 Real number로의 Function이다.

경고

Warning

Random variable은 Function이다.
Variable(변수)도, Random(무작위)도 아니다.

Random variable $X$는 Sample space $S$에서 모든 $r\in X(S)$에 대해 $(r, p(X=r))$의 Pair들의 Set으로 정의된다.
$P(X=r)$은 $X$가 Value $r$을 취할 Probability를 나타낸다.
Distribution은 일반적으로 각 $r\in X(S)$에 대해 $p(X=r)$를 지정함으로 설명할 수 있다.

팁

Example

주사위 한 쌍을 던졌을 때 나오는 수의 합을 $X$라고 할 때 첫 번째 주사위의 Value $i$, 두 번째 주사위의 Value $j$에 대한 36개의 Possible outcome $(i,j)$에 대한 Random variable의 Value

• Solution
  $2=X((1, 1)),\\3=X((1,2))=X((2,1)),\\4=X((1,3))=X((2,2))=X((3,1)),\\5=X((1,4))=X((2,3))=X((3,2))=X((4,1)),\\6=X((1,5))=X((2,4))=X((3,3))=X((4,2))=X((5,1)),\\7=X((1,6))=X((2,5))=X((3,4))=X((4,3))=X((5,2))=X((6,1)),\\8=X((2,6))=X((3,5))=X((4,4))=X((5,3))=X((6,2)),\\9=X((3,6))=X((4,5))=X((5,4))=X((6,3)),\\10=X((4,6))=X((5,5))=X((6,4)),\\11=X((5,6))=X((6,5)),\\12=X((6,6))$으로 확인 가능하다.

The Birthday Problem

The birthday problem은 적어도 두 사람이 같은 생일을 가질 확률이 $\frac{1}{2}$를 초과하기 위해 필요한 최소한의 사람 수를 구하는 문제이다.

팁

Example

The birthday problem을 해결

• Solution
  윤년의 경우 366일이므로 1년을 366으로 가정하고 사람의 생일이 Indepedent할 때 각 생일이 동일한 Probability로 발생할 수 있다.
  $n$명의 사람들이 적어도 두 사람이 같은 생일을 가질 Probability를 구하기 위해 모두 다른 생일을 가질 Probability $P_n$을 계산한다.
  적어도 두 사람이 같은 생일을 가질 Probability을 $1-P_n$으로 두어 $P_n$을 계산하기 위해 $n$명의 사람들의 생일을 고정된 순서로 고려한다.
  첫 번째 사람의 생일은 다음 사람의 생일과 일치하지 않고, 두번째 사람이 첫 번째 사람과 생일이 다를 확률은 $\frac{365}{366}$이다.
  위 과정을 반복하여 $j$번째 사람($2\leq j\leq 366)$이 이미 체크한 $j-1$명의 사람들과 생일이 다를 확률은 $\frac{366-(j-1)}{366}=\frac{367-j}{366}$이다.
  즉 $P_n=\frac{365}{366}\frac{364}{366}\frac{363}{366}\cdots \frac{367-j}{366}$이다.
  구해야 하는 $n$명 중 적어도 두 사람이 같은 생일을 가질 확률이 $\frac{1}{2}$를 초과하기 위해 $1-P_n = 1-\frac{365}{366}\frac{364}{366}\frac{363}{366}\cdots \frac{367-j}{366}$가 $\frac{1}{2}$를 초과하기 위한 계산을 구하면 된다.
  $n=22$일 때 $1-P_n\approx 0.475$이고 $n=23$일 때 $1-P_n\approx 0.506$이므로 정답은 23이다.

팁

Example

Hashing function의 Collision Probability
Hashing function $h(k)$가 Database에 저장될 Record의 Key를 Memory의 저장 위치로 Mapping하는 Function일 때 두 개의 다른 Key가 동일한 Memory location으로 Mapping되는 것을 Collision이라고 함
이 때 Collision이 발생하지 않을 Probability

• Solution
  Probability를 계산하기 위해 무작위로 선택된 Key가 Location에 Mapping될 Probability를 $\frac{1}{m}$ 이라고 가정한다.
  이 때 $m$을 Memory size로 가정하고 Hashing function이 Key를 동일한 Probability로 발생시킨다고 가정한다(Key 발생 Probability가 Independent하다.).
  또한 선택된 Record의 Key가 Key universe에 있는 모든 Element에 대해 Probabiltiy 역시 동일하다(Key들이 Independent하게 발생한다.).
  Key를 $k_1, k_2, \cdots, k_n$으로 가정할 때 $h(k_1)\not =h(k_2)$인 Probability는 $\frac{m-1}{m}$이고, 그 다음 Record는 $\frac{m-2}{m}$으로 진행한다.
  즉, Record가 Collision없이 Mapping 될 Probability는 $j$ 번째 Record일 때 $\frac{m-(j-1)}{m}$이다.
  The birthday problem과 같이 모두 다른 Hash value를 갖는 Probability를 $P_n$으로 두었을 때 $P_n=\frac{m-1}{m}\frac{m-2}{m}\cdots\frac{m-n+1}{m}$이다.

Monte Carlo Algorithms

이전 과정들에서 다룬 Algorithm들은 모두 Deterministic(결정론적)이다.
Deterministic이란 동일한 Input에 따라 항상 동일한 방식으로 진행되어 같은 Output을 가진다는 뜻이다.
반대로 Random choice에 관한 Algorithm, 즉 Probabilistic algorithm을 Monte Carlo algorithm이라 부른다.

Monte Carlo의 어원은 Monaco의 유명한 카지노의 이름에서 따왔으며, Stan Ulam, Enrico Fermi, John von Neumann에 의해 Monte Carlo method가 도입되었다.

Monte Carlo algorithm은 일련의 Test를 사용하며 각 단계에서 가능한 Output(Response, Answer)은 True이며 추가 반복이 필요없거나 알 수 없을 경우 Unknown으로 표현하며 이는 True나 False일 수 있다는 뜻이다.
Monte Carlo algorithm은 Error가 발생할 수 있다.
$p$를 Test의 Output이 True일 Probability라고 가정할 경우 Unknown일 경우의 Probability는 자연히 $1-p$가 된다.
Algorithm이 $n$번 반복할 때 Output이 모두 Unknown일 경우 Error probability는 $(1-p)^n$이 된다.
$p\not =0$일 때 Probability는 Test 수가 증가할 때 마다 0에 접근하고 Algorithm의 답이 True일 때는 Output이 True가 될 Probability는 1에 접근하게 된다.

팁

Example

Manufacturer가 $n$이라는 크기의 Batch로 Processor chip을 주문할 때 Chip maker는 Batch의 모든 Chip이 양호하도록 일부 Batch만 Test하여 Test 중 발견된 Bad chip을 Good chip으로 교체함
Test되지 않은 Batch에서 Bad chip의 Probability가 0.1일 때 PC manufacturer는 Batch의 각 Chip을 Test하여 양호한 지 확인을 함
Test가 $n$번 수행될 때 Test 소요 시간초가 $O(n)$일 때 PC manufacturer가 Chip maker가 Batch를 테스트 했는지 여부를 더 적은 시간에 확인이 가능한 지 파악

• Solution
  Monte Carlo algorithm을 사용(Error 발생 감안)하여 Batch가 Test되었는 지 파악하기 위해 Batch에서 임의의 Chip을 확인하여 Test하는 방식을 활용한다.
  Bad chip이 발견된 경우 Algorithm에서 True를, 그렇지 않은 경우를 Unknown으로 두었을 때 $k$개의 Chip을 확인하여 True라는 답이 나오지 않으면 Algorithm은 False로 종료(Chip maker가 Batch의 모든 Chip을 Test했다고 가정)한다.
  이 Monte Carlo algorithm이 잘못된 Output을 내는 방법은 Test되지 않은 Batch가 Test된 것으로 결론지을 때이다.
  Good chip이나 Test되지 않은 Batch에서 온 경우 $1-0.1=0.9$이므로 k번 Test 할 경우 Batch에서 서로 다른 Chip을 Test하는 Event는 Independent이므로 Test되지 않은 Batch가 주어졌을 때 Algorithm의 $k$ 단계가 Unknown을 Output으로 가질 Probability는 $0.9^k$이다.
  $k$ value가 커질 수록 이 Algorithm의 정확도를 높일 수 있다.
  예시로 66개의 Chip을 확인할 경우 $0.9^{66}$의 Probability로 이 Batch가 Test되었는 지 알 수 있다.

The Probabilistic Method

정보

Theorem

The Proibabilistic Method

어떤 Set $S$의 Element가 특정 Property를 가지지 않을 Probability가 1보다 작을 경우, $S$에는 이 Probability를 가진 Element가 존재한다.

정보

Theorem

만약 Integer $k$가 $k\geq 2$를 만족할 경우 $R(k,k)\geq 2^{\frac{k}{2}}$이다.

• Proof
  이 Theorem이 2와 3에도 성립한다.
  $R(2, 2)=2,\ R(3,3)=6$임을 이전 과정에서 확인하였기 때문이다.
  $k$가 4 이상일 때 Probabilistic method를 사용하여 파티에 $2^{\frac{k}{2}}$미만의 사람이 있을 경우 그 중 $k$명은 서로 친구이거나 서로 적일 가능성이 없음을 보여주어 증명한다.
  즉 $R(k,k)\geq2^{\frac{k}{2}}$임을 나타내어야 한다.
  Probabilistic method를 사용하기 위해 두 사람이 친구일 Probability와 적일 Probability를 $\frac{1}{2}$로 놓고 파티에 $n$명이 존재한다고 가정한다.
  이 파티에서 $k$명의 서로 다른 Set은 $\binom{n}{k}$가 존재하며 이를 $S_1, S_2, \cdots, S_\binom{n}{k}$으로 나열한다.
  $E_i$를 $S_i$의 모든 $k$명의 사람이 서로 친구이거나 적인 Event라고 할 때 그 Probability는 $p(\bigcup_{i=1}^{\binom{n}{k}}E_i)$와 같다.
  $S_i$에는 $k$명 존재하기에 $\binom{k}{2}=\frac{k(k-1)}{2}$ 쌍의 사람들이 존재한다.
  따라서 $S_i$의 모든 $k$명이 모두 서로 친구일 Probability와 적일 Probability는 $2\frac{1}{2}^{ \frac{k(k-1)}{2}}$이다.
  위 식들과 Boole's Inequality를 이용하여 $p(\bigcup_{i=1}^{\binom{n}{k}}E_i\leq \sum_{i=1}^{\binom{n}{k}}p(E_i)=\binom{n}{k}2(\frac{1}{2})^{\frac{k(k-1)}{2}}$이고, $\binom{n}{k}\leq \frac{n^k}{2^{k-1}}$이므로 $\binom{n}{k}2(\frac{1}{2})^{\frac{k(k-1)}{2}}\leq \frac{n^k}{2^{k-1}}2(\frac{1}{2})^{\frac{k(k-1)}{2}}$이고, $n<2^{\frac{k}{2}}$이므로 $k\geq 4$일 때$\binom{n}{k}2(\frac{1}{2})^{\frac{k(k-1)}{2}}<\frac{2^{k(\frac{k}{2})}}{2^{k-1}}2(\frac{1}{2})^{\frac{k(k-1}{2}}=2^{2-(\frac{k}{2})}\leq 1$이다.
  따라서 파티에서 $k$명의 서로 친구이거나 서로 적이 없는 Set이 존재하지 않는 Event의 Probability는 0보다 크다.
  $n<2^{\frac{k}{2}}$일 때 $k$명 중 어떤 Subset도 서로 친구나 적이 아닌 Set이 적어도 하나는 존재한다는 결론이 나오므로 증명 가능하다.

6.3. Bayes' Theorem

Bayes' Theorem

정보

Theorem

Bayes' Theorem

$E, F$가 Sample space $S$의 Event일 때 $p(E)\not =0\ \&\ p(F)\not =0$일 때 $p(F|E)=\frac{p(E|F)p(F)}{p(E|F)p(F)+p(E|\overline{F})p(\overline{F})}$

• Proof
  Conditional probability에 따라 $p(F|E)=\frac{p(E\cap F)}{p(E)}$이고 $p(E|F)=\frac{p(E\cap F)}{p(F)}$이다.
  그러므로 $p(E\cap F)=p(F|E)p(E)$이고 $p(E\cap F)=p(E|F)p(F)$이다.
  두 등식을 이용하여 $p(F|E)p(E)=p(E|F)p(F)$임을 알 수 있고 양 변에 $p(E)$를 나눠 $p(F|E)=\frac{p(E|F)p(F)}{p(E)}$임을 알 수 있다.
  증명을 위해 $p(E)=p(E|F)p(F)+p(E|\overline{F})p(\overline{F})$임을 보이기 위해 $E=E\cap S=E\cap(F\cup \overline{F})$임과 $E\cap F$와 $E\cap \overline{F}$가 Disjoint임을 이용하여 $p(E)=p(E\cap F)+p( E\cap \overline{F})$임을 알 수 있다.
  앞전 식들을 이용하여 $p(F|E)=\frac{p(E|F)p(F)}{p(E|F)p(F)+p(E|\overline{F})p(\overline{F})}$임을 증명할 수 있다.

정보

Theorem

Generalized Bayes' Theorem

$E$가 Sample space $S$의 Event이고, $F_1, F_2,\cdots , F_n$을 서로 Mutually excvlusive event($\bigcup_{i=1}^n F_i=S$)라고 할 때 $p(E)\not = 0, p(F_i)\not =0(for\ i=1,2,\cdots ,n)$일 때 $p(F_j|E)=\frac{p(E|F_j)p(F_j)}{\sum_{i=0}^n p(E|F_i)p(F_i)}$

• Proof
  $F_i$는 서로 Mutually exclusive이기에 $F_i$끼리는 Disjoint이다.
  즉, $E=\bigcup_{i=1}^n (E\cap F_i)$이다.
  위 Bayes' Theorem을 반복 적용하여 증명 가능하다.

팁

Example

한 사람이 100000명 중 1명 정도의 Probability로 특정한 희귀 병을 앓고 있다고 가정할 때 이 병에 대한 진단 테스트는 질병이 있는 사람에게 시행할 경우 99%의 정확도를 보이며 질병이 없는 사람에게는 99.5%의 정확도를 가지고 있을 때
a. 양성인 사람이 실제로 그 질병을 가질 Probability
b. 음성인 사람이 실제로 그 징병이 없을 Probability

• Solution
  a: $F$를 한 사람이 양성인 Event, $E$를 한 사람의 테스트 결과가 양성인 Event로 놓았을 때 $p(F|E)$를 계산해야 한다.
  Bayes' theorem을 이용해 구하기 위해 $p(E|F), p(E|\overline{F}),p(F), p(\overline{F})$를 구해야 한다.
  $p(F)=\frac{1}{100000}=0.00001, p(\overline{F})=0.99999,p(E|F)=0.99, p(E|\overline{F})=0.995$임을 이용하여 대입하면 $p(F|E)=\frac{(0.99)(0.00001)}{(0.99)(0.00001)+(0.005)(0.99999)}\approx 0.002$로 계산 가능
  b: Bayes' theorem을 이용해 $p(\overline{F}|\overline{E})=\frac{(0.955)(0.99999)}{(0.995)(0.99999)+(0.01)(0.00001)}\approx 0.9999999$로 계산 가

Bayesian Spam Filters

E-amil의 Spam을 걸러내기 위한 도구 중 최초의 도구 중 하나는 Bayes' theorem을 이용하여 만든 Bayesian spam filter이다.
Bayesian spam filter는 특정 단어 $w$에 대해 $w$가 Spam E-mail message에서 나타날 Probability는 Spam으로 알려진 대량의 Message set에서 $w$가 나타나는 횟수와 Spam이 아닌 대량의 Message set에서 $w$가 나타나는 횟수를 통해 추정한다.

Spam인 Message set $B$, Spam이 아닌 Message set $G$에 대해 $B, G$에서 발생하는 단어를 식별하여 각 단어가 포함된 Message 수를 세어 $w$가 포함된 Message 수를 각각 $n_B(w), n_G(w)$라고 할 때 Spam message가 단어 $w$를 포함하는 Probability $p(w)$, Spam이 아닌 Message가 단어 $w$를 포함하는 Probability를 $q(w)$라고 할 때 $p(w)=n_B(w)/|B|$, $q(w)=n_G(w)/|G|$이다.

단어 $w$를 포함하는 새로운 E-mail message를 받았을 때 $S$를 해당 Message가 Spam인 Event, $E$가 Message가 단어 $w$를 포함하는 Event일 때 Bayes' theorem에 따라 $p(S|E)=\frac{p(E|S)p(S)}{p(E|S)p(S)+p(E|\overline{S})p(\overline{S})}$가 Message가 단어 $w$를 포함할 때 Spam일 Probability이다.

Formula 적용을 위해 $p(S)$와 $p(\overline{S})$의 Probability를 추정한다.
단순화를 위해 $p(S)=p(\overline{S})=\frac{1}{2}$일 때 $p(S|E)=\frac{p(E|S)}{p(E|S)+p(E|\overline{S})}$로 단어 $w$를 포함한 Message가 Spam일 Probability를 나타낼 수 있다.
추가적으로 Message가 Spam일 때 단어 $w$가 포함될 Conditional probability $p(E|F)$를 $p(w)$, $p(E|\overline{S})$를 $q(w)$로 추정한다면 Message가 단어 $w$를 포함할 때 해당 Message가 Spam일 Probability $r(w)$는 $r(w)=\frac{p(w)}{p(w)+q(w)}$이다.

팁

Example

"Rolex"라는 단어가 Spam으로 알려진 2000개의 Message 중 250개에서 발생하고 Spam이 아닌 Message 1000개에서 5개가 발생할 때 Message가 단어"Rolex"를 포함할 때 Spam 처리(단, 들어오는 Message가 Spam일 Probability은 $\frac{1}{2}$, Message가 Spam으로 거부될 기준이 0.9)

• Solution
  "Rolex"라는 단어가 Spam, Non-spam message에 나타나는 횟수를 사용해 $p("Rolex")=\frac{250}{2000}=0.125$, $q("Rolex")=\frac{5}{1000}=0.005$, 새 Message가 Spam일 Probability가 $\frac{1}{2}$임을 이용해 $r("Rolex")=\frac{p("Rolex")}{p("Rolex")+q("Rolex")}=\frac{0.125}{0.125+0.005}=\frac{0.125}{0.13}\approx 0.962$이므로 이 Message는 Spam으로 처리된다.

앞전 Generalized Bayes' theorm을 이용하여 다양한 Spam으로 추정하는 단어 $w_i$가 많을 수록 Spam 유무를 정확히 판단할 Probability가 증가한다.
$E_i$가 단어 $w_i$를 포함하는 Event라고 할 때 수신되는 Spam과 Non-spam의 수가 동일할 때 Event $E_i|S$가 Independent일 경우 $p(S|\bigcap_{i=1}^k E_i)=\frac{\prod_{i=1}^k p(E_i|S)}{\prod_{i=1}^k p(w_i)+\prod_{i=1}^k q(w_i)}$이다.
즉, 단순화 하여 $r(w_1, w_2, \cdots, w_k)=\frac{prod_{i=1}^k p(w_i)}{prod_{i=1}^k p(w_i)+\prod_{i=1}^k q(w_i)}$이다.

6.4. Expected Value and Variance

Expected Values

Random variable의 Expected value(기댓값)은 Sample space에 있는 모든 Element에 대해 그 Element의 Probability와 해당 Element에서의 Random variable의 Value를 모두 곱한 Value를 합산한 것이다.
즉, Expected value는 Ramdom value의 Weighted average(가중 평균)이다.

Ramdom variable $X$의 Expected value는 Sample space $S$에 대해 $E(X)=\sum_{s\in S} p(s)X(s)$이다.

팁

Example

주사위의 Expected value

• Solution
  주사위는 총 6개의 Value를 가지고 1에서 6까지이므로 $E(x)=\frac{6(1+6)}{12}=\frac{7}{2}$

정보

Theorem

$X$가 Random variable이고 $p(X=r)$이 $X=r$일 Probability이고, $p(X=r)=\sum_{s\in S,X(s)=r}p(s)$일 때 $E(X)=\sum_{r\in X(s)}p(X=r)r$

• Proof
  $X$가 Range $X(S)$를 가진 Random variable이라고 가정할 때 $p(X=r)$이 Random variable $X$가 Value $r$을 가질 확률이라고 할 때 $p(X=r)$는 $X(s)=r$인 Outcome $s$의 Sum이다.
  따라서 $E(X)=\sum_{r\in X(S)} p(X=r)r$이 성립한다.

팁

Example

공정한 주사위 한 쌍을 던졌을 때 나오는 숫자의 합의 Expected value

$X$를 두 주사위 Value의 sum의 Random variable이라고 할 때 총 36개($6\times 6$)의 Outcome에 의해 $X$의 Range는 $\{2,3,4,5,6,7,8,9,10,11,12\}$가 된다.
$p(X=2)=p(X=12)=\frac{1}{36},\\p(X=3)=p(X=11)=\frac{2}{36},\\p(X=4)=p(X=10)=\frac{3}{36},\\p(X=5)=p(X=9)=\frac{4}{36},\\p(X=6)=p(X=8)=\frac{5}{36},\\p(X=7)=\frac{6}{36}$이므로$E(X)=\frac{(2+12)+2(3+11)+3(4+10)+4(5+9)+5(6+8)+6*7}{36}=\frac{14*15+6*7}{36}=7$이다.

정보

Thoerem

$n$개의 Independent Bernoulli trial을 수행할 때 Success probability가 $p$일 경우 Sucess의 Expected number는 $np$이다.

• Proof
  $X$를 $n$번의 trial에서 Success number에 해당하는 Random variable일 때 $p(X=k)=C(n,k)p^kq^{n-k}$이기에
  $E(X)=\sum_{k=1}^nkp(X=k)\\=\sum_{k=1}^nkC(n,k)p^kq^{n-k}\\=\sum_{k=1}^nnC(n-1, k-1)p^kq^{n-k}\\=np\sum_{k=1}^nC(n-1, k-1)p^{k-1}q^{n-k}\\=np\sum_{j=0}^{n-1}C(n-1,j)p^jq^j{n-1-j}\\=np(p+q)n-1\\=np$

Linearity of Expectations

Expected value는 Linear(선형적)이다.

정보

Theorem

$X_i(i=1,2,\cdots,n)$가 $S$의 Random variable이고 $a, b$가 Real number일 때
1. $E(X_1+X_2+\cdots +X_n)=E(X_1)+E(X_2)+\cdots +E(X_n)$
2. $E(aX+b)=aE(X)+b$

• Proof
  $n=2$일 때 (1)은 쉽게 증명된다.
  $E(X_1+X_2)=\sum_{s\in S}p(s)(X_1(s)+X_2(s))\\=\sum_{s\in S}p(s)X_1(s)+\sum_{s\in S}p(s)X_2(s)\\=E(X_1)+E(X_2)$
  비슷한 방법으로 (2)도 전개하여 해결한다.
  $E(aX+b)=\sum_{s\in S}p(s)(aX(s)+b)\\=a\sum_{s\in S}p(s)X(s)+b\sum_{s\in S}p(s)\\=aE(X)+b \because \sum_{s\in S}p(s)=1$

팁

Example

공정한 주사위 한 쌍을 던졌을 때 나오는 숫자의 합의 Expected value(이전에 해결한 Example이나 앞전 Theorem을 이용하여 해결)

• Solution
  Random variable $X_1, X_2$를 $X_1(i,j)=i, X_2=(i,j)=j$로 설정하여 $X_1$은 첫 주사위, $X_2$는 두 번째 주사위에서 나타나는 숫자로 가정한다.
  $E(X_1)=E(X_2)=\frac{7}{2}$이므로 두 주사위를 굴렸을 때 나오는 숫자의 합의 Expected value는 $X_1+X_2=7$로 해결 가능하다.

팁

Example

직원이 식당에서 $n$명의 손님의 모자를 확인하였으나, 모자에 번호를 남기는 것을 깜빡하였을 때 손님들이 모자를 찾으러 왔을 때 무작위로 반환된 모자 중 정확히 반환되는 모자의 Expected value

• Solution
  $X$를 올바른 모자를 받은 사람 수의 Random variable로 설정한다.
  $X_i$는 $i$번째 사람이 올바른 모자를 받으면 1, 그렇지 않다면 0인 Random variable이 되며 $X=X_1+X_2+\cdots +X_n$이 된다.
  $i$번째 사람이 올바른 모자를 받을 Probability는 $\frac{1}{n}$이므로 6.4의 첫 번째 Theorem에 의해 모든 $i$에 대해$E(X_i)=1*p(X_i=1)+0*p(X_i=0)=1*\frac{1}{n}+0=\frac{1}{n}$이고 6.4의 세 번째 Theorem에 의해 $E(X)=E(X_1)+E(X_2)+\cdots +E(X_n)=n*\frac{1}{n}=1$로 해결 가능하다.

팁

Example

주어진 Permutation에서 $(i,j)$라는 Ordered pair는 $i<j$이나 Permutation에서 $j$가 $i$보다 앞에 배치되는 경우 inversion이라고 함
첫 $n$개의 Positive integer의 임의의 Permutation에서 Inversion 개수의 Expected value

• Solution
  $I_{i,j}$를 첫 $n$개의 Positive integer의 Permutation의 Oredered pair $(i,j)$에 대해 $i\leq j$이면 0, $i>j$이면 1일 때 $X$를 Permutation의 Inversion 개수에 해당하는 Random variable로 둘 경우 $X=\sum_{1\leq i<j\leq n}I_{i,j}$가 된다.
  $i\leq j$와 $i>j$는 동일한 Probability를 가지므로 모든 Pair $(i,j)$에 대해 $E(I_{i,j})=1*p(I_{i,j}=1)+0*p(I_{i,j}=0)=1*\frac{1}{2}+0=\frac{1}{2}$이다.
  $\binom{n}{2}$개의 $(i,j)$ Pair가 존재하므로 $1\leq i<j\leq n$을 만족하는 Expected valuesms $E(X)=\sum_{1\leq i<j\leq n}I_{i,j}=\binom{n}{2}*\frac{1}{2}=\frac{n(n-1)}{4}$로 첫 $n$개의 Positive integer를 사용하는 Permutation에서 평균적으로 $\frac{n(n-1)}{4}$개의 Inversion이 존재함을 확인할 수 있다.

Average-Case Computational Complexity

Algorithm을 Average-case computational complexity(평균 사례 계산 복잡도)를 계산하는 것은 Random variable의 Expected value를 계산하는 것과 같다.
Experiment의 Sample space의 가능한 Input을 $a_j\ j=1,2,\dots,n$으로 놓고 $X$를 Algorithm이 $a_j$를 Input으로 받을 때 사용하는 Operation 개수의 Random variable로 둘 경우 Algorithm의 Average-case computational complexity는 $E(X)=\sum_{j=1}^np(a_j)X(a_j)$이다.

팁

Example

$x$를 각 Element와 순차적 비교해 $x$를 찾을 때 List에 $x$가 있을 Probability를 $p$, $x$가 $n$개의 Element중 어느 것이든 동일한 Probability로 선택될 경우의 Linear search algorithm의 Average-case complexity

• Solution
  이전 과정에서 $x$가 List의 $i$번째 Element와 같은 경우 $2i+1$회의 Operation이 사용됨과 $x$가 List에 없을 경우 $2n+2$만큼의 Operation이 사용됨을 활용하여 $x$가 $a_i$와 같을 Probability는 $\frac{p}{n}$이고 $x$가 List에 없을 Probability는 $q=1-p$이므로 $E=\frac{3p}{n}+\frac{5p}{n}+\cdots+\frac{(2n+1)p}{n}+(2n+2)q\\=\frac{p}{n}(3+5+\cdots+(2n+1))+(2n+2)q\\=\frac{p}{n}((n+1)^2-1)+(2n+2)q\\=p(n+2)+(2n+2)q$이다.
  만약 $x$가 List에 있을 Probability가 $\frac{1}{2}$일 경우 $p=\frac{3}{4}, q=\frac{1}{4}$로 $E=\frac{3(n+2)}{4}+\frac{2n+2}{4}=\frac{5n+8}{4}$가 된다.

팁

Example

$n$개의 Element가 있는 Insertion sort의 Average-case complexity

• Solution
  $X$를 $n$개의 다른 Element로 구성된 List $a_1, a_2,\dots ,a_n$를 Insertion sort로 정렬할 때 사용되는 Operation 수의 Random variable로 둘 경우 $E(X)$는 평균 Operation 수가 된다.
  $X=X_2+X_3+\cdots+X_n$일 때 $E(X)=E(X_2+X_3+\cdots+X_n)=E(X_2)+E(X_3)+\cdots+E(X_n)$이다.
  $p_j(k)$를 List의 처음 $j$개의 Element 중 Max value가 $k$번째 위치에 있을 Probability로 정의할 경우 List의 Element들이 무작위로 분포되어 있으므로 $p_j(k)=\frac{1}{j}$가 된다.
  $X_i(k)$가 $a_i$가 정렬된 후 $k$번째 위치에 삽입될 때 Insertion sort가 사용하는 Operation 수라면 $X_i(k)=k$가 된다.
  $a_i$가 처음 $i$개의 위치 중 어느 곳에나 삽입될 수 있으므로 $E(X_i)=\sum_{k=1}^i p_i(k)*X_i(k)=\sum_{k=1}^i \frac{1}{i}*k=\frac{1}{i}\sum_{k=1}^ik=\frac{i+1}{2}$이다.
  결과적으로 $E(X)=\sum_{i=2}^nE(X_i)=\sum_{i=2}^n\frac{i+1}{2}=\frac{1}{2}\sum_{j=3}^{n+1}j(\because j=i+1)=\frac{1}{2}\frac{(n+1)(n+2)}{2}-\frac{1}{2}(1+2)=\frac{n^2+3n-4}{4}$이므로 Insertion sort가 $n$개의 Element를 정렬하는 데 필요한 평균 Operation 수는 $\frac{n^2+3n-4}{4}$이며 Notation으로 $\Theta(n^2)$이 된다.

The Geometric Distribution

Geometric distribution(기하 분포) = 동일한 Bernoulli distribution(Random variable의 1회 실행 결과가 Binary value로 이루어진 Distribution)을 따르는 Independent 반복에서 처음으로 목표 Value를 갖기까지의 시도 횟수를 Random variable로 갖는 Distribution이다.

정보

Theorem

Random variable $X$가 Parameter $p$를 가진 Geometric distribution을 가진다면 $E(X)=\frac{1}{p}$

팁

Example

동전을 던졌을 때 뒷면이 나올 Probability를 $p$라고 가정할 때 뒷면이 나올 때 까지 동전을 반복해서 던질 때의 Expected value

• Solution
  Sample space는 임의의 수의 앞면($H$)와 제일 뒤에 뒷면($T$)이 오는 Sequence로 구성된다.
  따라서 Sample space $S=\{T,HT,HHT,HHHT,HHHHT,\dots\}$가 된다.
  Sample space의 Element의 Probability를 구하기 위해 동전 던지는 Event가 Independent이며 앞면이 나올 Probability는 $1-p=q$일때 $p(T)=p, p(HT)=pq, p(HHT)=pq^2$이기 때문에 뒷면이 나올때 까지 n번 던지는 Probability는 $pq^{n-1}$이다.
  $X$를 Sample space의 Element에서 던진 횟수와 같은 Random variable이라고 할 때 $X(T)=1, X(HT)=2, X(HHT)=3,\dots$이다.
  즉 $P(X=j)=pq^{j-1}$이므로 $E(X)=\sum_{j=1}^\infty jp*p(X=j)=\sum_{j=1}^\infty jpq^{j-1}=p\sum_{j=1}^\infty j(1-p)^{j-1}=p*\frac{1}{p^2}=\frac{1}{p}$이다.
  따라서 동전이 뒷면이 나올 때까지 던지는 Expected value는 $\frac{1}{p}$이므로 공정한 동전일 경우 $p=\frac{1}{2}$이므로 2이다.

Independent Random Variables

Sample space $S$에서 Random variable $X, Y$가 모든 Real number $r_1, r_2$에 대해$p(X(s)=r_1\ and\ Y(s)=r_2)=p(X(s)=r_1)*p(Y(s)=r_2)$일 때 Independent이다.

정보

Theorem

Sample space $S$의 $X,Y$가 Independent random variable이라면 $E(XY)=E(X)E(Y)$

• Proof
  $X, Y$는 Independent random variable이기에 $E(XY)=\sum_{s\in S}X(s)Y(s)p(s)\\=\sum_{r_1\in X(S),r_2\in Y(s)}r_1r_2*p(X(s)=r_1 and Y(s)=r_2)\\=\sum_{r_1\in X(S),r_2\in Y(s)}r_1r_2*p*(X(s)=r_1)*p(Y(s)=r_2)\\=[\sum_{r1\in X(S)}r_1p(X(s)=r_1)]*[\sum_{r2\in Y(s)}r_2p(Y(s)=r_2)]\\=E(X)E(Y)$
  으로 증명 가능하다.

팁

Example

동전을 두 번 던졌을 때 나오는 앞면의 수를 세는 Random variable $X$와 뒷면의 수를 세는 Random variable $Y$가 Independent random variable인지 확인

• Solution
  간단히 보았을 때 $E(X)=E(Y)=2\frac{1}{4}+1\frac{1}{2}+0\frac{1}{4}=1$로 확인 가능하다.
  $XY$는 양쪽 다 앞면이거나 뒷면일 때 0이 나오므로 $E(XY)=1\frac{1}{2}+0\frac{1}{2}=\frac{1}{2}$이다.
  $E(X)E(Y)\not =E(XY)$이므로 $X,Y$는 Independent random variable이 아니다.

Variance

$X$를 Sample space $S$의 Random variable이라고 할 때 $X$의 Variance(분산)은 Notation $V(X)$로 표기하며 $V(X)=\sum_{s\in S}(X(s)-E(X))^2p(s)$로 정의된다.
$X$의 Standard deviation은 Notation $\sigma(X)$로 표기하고 $\sqrt {V(X)}=\sigma(X)$이다.

정보

Theorem

$X$가 Sample sapce $S$의 Random variable일 때 $V(X)=E(X^2)-E(X)^2$

• Proof
  $V(X)=\sum_{s\in S}(X(s)-E(X))^2p(s)\\=\sum_{s\in S}X(s)^2p(s)-2E(X)\sum_{s\in S}X(s)p(s)+E(X)^2\sum_{s\in S}p(s)\\=E(X^2)-2E(X)E(X)+E(X)^2 \because \sum_{s\in S}p(s)=1 \\=E(X^2)-E(X)^2$
  로 증명 가능하다.

정보

Theorem

$X,Y$가 Sample space $S$에서 두 개의 Independent random variable일 경우 $V(X+Y)=V(X)+V(Y)$

• Proof
  $V(X+Y)=E((X+Y)^2)-E(X+Y)^2\\=E(X^2+2XY+Y^2)-(E(X)+E(Y))^2\\=E(X^2)+2E(XY)+E(Y^2)-E(X)^2-2E(X)E(Y)-E(Y)^2\\=(E(X^2)-E(X)^2)+(E(Y^2)-E(Y)^2)\\=V(X)+V(Y)$
  로 증명 가능하다.
  추가적으로 $X_i, i=1,2,\dots,n$에 해당하는 $V(X_1+X_2+\cdots+X_n)=V(X_1)+V(X_2)+\cdots+V(X_n)$ 역시 성립한다.

팁

Example

두 개의 주사위를 굴렸을 때 Random variable $X$의 Variance와 Standard deviation
단 $X((i, j))=i+j$, ($i, j$는 첫 번째, 두 번째 주사위의 값)

• Solution
  $X_1, X_2$로 나누어 $X_1((i,j))=i, X_2((i,j))=j$인 Random variable로 정의한다.
  이 때 $X=X_1+X_2$이며 $X_1, X_2$는 Independent random variable이다.
  따라서 $V(X)=V(X_1)+V(X_2)$이기에 $V(X_1)=V(X_2)$임을 이용해서 $V(X)=2V(X_1)=2((E({X_1}^2)-E(X_1)^2)=2(\frac{1}{6}(1^2+2^2+3^2+4^2+5^2+6^2)-(\frac{7}{2})^2)=2(\frac{91}{6}-\frac{49}{4})=\frac{35}{6}$
  임을 구할 수 있다.
  따라서 $V(X)=\frac{35}{6}, \sigma(X)=\sqrt{\frac{35}{6}}$이다.

팁

Example

$n$개의 Independent Bernoulli trial이 수행될 때 Success probability $p$에 대한 Success 수의 Variance

• Solution
  $X_i((t_1,t_2,\dots,t_n))=1$이 Success인 Random variable $X_i$에 대해$X=X_1+X_2+\dots+X_n$은 $n$번 수행에 Success의 수이다.
  $V(X_1)=V(X_2)=\cdots=V(X_n)$이고 $V(X_1)=E(X^2)-E(X)^2=p-p^2 (\because X=0\ or\ 1, X^2(t)=X(t))=p(p-1)=pq$
  이므로 $V(X)=npq$이다.

Chebyshev's Inequality

Chebyshev's inquality는 Probability distribution 없이 Average(=Expected value)와 Standard deviation을 이용하여 Random variable $X$가 Average $\mu$에서 $r\sigma$만큼 떨어진 Probability를 구할 수 있다.

정보

Theorem
Chebyshev's inquality
Sample space $S$의 Probability function $p$를 가진 Random variable $X$에 대해 Positive real number $r$에 대해 $p(\vert X(s)\to E(X)\vert \geq r)\leq \frac{V(X)}{r^2}$

• Proof
  Event $A$를 $A=\{s\in S\mid (\vert X(s)-E(X)\vert) \geq r\}$라고 가정했을 때 $p(A)\leq \frac{V(X)}{r^2}$임을 증명하면 된다.
  $V(X)=\sum_{s\in S}(X(s)-E(X))^2p(s)\\=\sum_{s\in A}(X(s)-E(X))^2p(s)+\sum_{s \notin A}(X(s)-E(X))^2p(s)$이고, 각 항이 Nonnegative이므로 두 번째 등식의 합의 뒤 역시 Nonnegative이다.
  $A$의 각 Element $s$에 대해 $(X(s)-E(X))^2\geq r^2$이므로 두 번째 등식의 합의 앞은 최소 $\sum_{s\in A}r^2p(s)$보다 크다.
  따라서 $V(X)\leq \sum_{s\in A}r^2p(s)=r^2p(A)$이므로 $\frac{V(X)}{r^2}\geq p(A)$이기에 성립한다.

팁

Example

공정한 동전을 $n$번 던졌을 때 나오는 뒷면 수에 대한 Chebyshev's inequality

• Solution
  $X$를 Success probability가 $\frac{1}{2}$인 $n$개의 Independent Bernoulli's trial의 Success 수에 해당하는 Random variable이라고 할 때 $E(X)=\frac{n}{2}$이고 $V(X)=npq=\frac{n}{4}$이다.
  이를 Chebyshev's inequality를 이용하여 $p(| X(s)-\frac{n}{2}|\geq \sqrt n)\leq \frac{n}{4} / (\sqrt n)^2 = \frac{1}{4}$로 공정한 동전을 $n$회 던졌을 때 나오는 뒷면의 수는 평균에서 $\sqrt n$만큼 벗어날 확률은 25%를 초과하지 않는다.