Leo's Garage

The Envelope Problem n명의 사람으로 구성된 그룹에 n개의 우편이 그들의 이름이 써있는 채 도착했다. 하지만 누군가 이 우편을 어질러버렸다. 자 여기서 적어도 한 명이 자신에게 온 우편을 받을 확률을 구해보자. Ai를 어떤 i라는 사람이 자신에게 온 편지를 받는 Event라고 가정하면, 우리가 원하는 건 이런 Ai의 합집합이 될 것이다. 그리고 그에 대한 확률을 구하면 되는 것이다. 이 전체 합집합을 inclusion-exclusion의 원리로 전개하면 짝수 Event의 교집합은 빼고 홀수 Event의 교집합은 더하는 식으로 전개할 수 있다. 이 문제의 경우 각 Ai의 확률 P(Ai)는 전부 같다고 볼 수 있고 또한 모든 교집합들도 서로 확률이 같다고 볼 수 있다. 따라서 위와 같이 전개..

The Birthday Problem 생각해보면 이 확률이 굉장히 작을 것 같다. 실제로 그런지 계산해보자 만약에 n명이 전부 생일이 다른 경우의 수를 구한다면 위의 수식과 같이 구할 수 있을 것이다. 그리고 이렇게 전부 생일이 다를 "확률"을 계산해본다면 위의 수식과 같이 구할 수 있다. 그렇다면 적어도 2명의 생일이 같은 확률은 전체확률 1에서 전부 다를 확률을 빼면 된다는 것이다. 만약에 인원이 366명이면 당연히 확률은 1이다. 그렇다면 확률이 0.5이상이 되는 순간의 인원은 몇 명일까? 놀랍게도 23명 이상이면 확률이 0.5 이상이 되고, 인원이 50명인 경우에는 확률이 무려 0.97이 된다. 놀라운 일이 아닐 수 없다.

Permutations vs. Combinations 위와 같은 문제가 있다고 가정하자. 4개는 빨간 대리석이고 2개는 하얀 대리석이다. 이것들을 나열해보자 여기서 문제는 다음과 같다. a. 양 끝이 하얀색 대리석인 경우 b. 양 끝이 하얀색 대리석이 아닌 경우 c. 하얀 대리석이 연속으로 있는 경우 1번 방식은 기본적으로 Permutation을 이용한 방식이다. 중복에 대해서 고려하지 않고 가능한 모든 경우의 수를 나열하는 식으로 전개하고 있다. 하지만 이 방법의 경우에는 음... 계산이 좀 더 길어지고 수가 커진다는 단점이 있다. 2번 방식의 경우에는 좀 더 명확한데 중복 가지수를 빼고 계산할 수 있기 때문에 좀 더 빠르게 답을 얻을 수 있다.

Hypergeometric, Binomial, and Multinomial Problems 2개의 서로 다른 종류의 Object가 있을 때, 이 Object들 중에서 어떤 종류의 Object를 k개 뽑을 확률을 위와 같이 구한다. 그리고 이런 환경에서 어떤 종류의 Object를 k개 뽑는 것에 대해서 어떤 Object의 k 갯수(X)에 대한 Hypergeometric Distribution이라고 한다. Binomial은 Hypergeometric과 거의 유사한데 한 가지 다른 점은 먼저 뽑은 object를 다시 채워넣는다는 점이다. 즉, Hypergeometic의 경우에는 첫번째와 두번째 시도가 확률적으로 다르다. 하지만 Binomial은 모든 시도에서 확률적으로 동일하다. Multinomial Coef..

Counting Techniques: Combinations Combination은 순서에 관계가 없다. Permutation의 경우에는 순서가 중요하다. Binomial Distribution이라는 걸 나중에 배우게 되는데 이 분포는 베르누이 시행을 n번 하여 성공할 횟수를 X라고 하면, 이 X 확률 변수의 모수가 (n, p)이 분포이다. (여기서 p는 성공할 확률을 의미한다.)

Counting Techniques: Permutations n개의 기호를 어떤 순서에 따라 배열한 것을 Permutation이라고 한다. n개 중 r개를 순서에 따라 고르는 것을 Pn,r로 표현한다.

Counting Techniques: Baby Examples 아주 간단한 예제들이다. 한 번씩 훑어보고 지나가자

Finite Sample Space Sample space의 사건들의 확률이 전부 동일할 때 Simple sample space라고 한다.

Basic Probability Results 사건 A의 여집합은 전체집합에서 A집합을 뺀 집합을 의미한다. 전체집합의 여집합은 null로 정의할 수 있다. A 사건의 확률이 0이라고 해서 A가 null 사건이지는 않는다. 일반적으로는 A와 B의 합집합의 확률은 A와 B의 확률의 합에 A와 B의 교집합의 확률을 뺀 값과 같다. 이전에 언급했던 A와 B가 disjoint인 경우는 특별한 케이스이다. n개 사건의 합집합에 대해서 짝수개의 사건의 교집합은 빼고, 홀수개의 사건의 교집합은 더하는 식으로 전개할 수 있다.

What is Probability 어떤 event A의 확률 P(A)는 Sample space에서 event A를 나눈 값으로 표현할 수 있다. 어떤 사건 A의 확률은 0과 1 사이에서 정의된다. P(S) = 1, 왜냐면 전체 사건 집합이므로 만약에 사건 A, B가 서로 disjoint라면 A와 B의 교집합은 null로 표기된다. 이 경우에 P(A U B) = P(A) + P(B)로 표현될 수 있다. 그리고 마지막 식의 경우에는 모든 event가 서로 disjoint라면 그 전체 합이 전체의 합집합과 동일하다고 볼 수 있다. 마지막의 식은 결국, 동전던지기 횟수가 1회 증가할 때마다 확률은 절반씩 줄기 때문에 위와 같이 표현할 수 있다.