[확률과 통계] 2.1 Counting Methods: Part I

- 본 내용은 "Introduction to Probability, Statistics, and Random Processes" 책 내용을 통해 작성 되었고 [인프런] 확률과 통계 기초(조범희) 강의를 참고해서 작성 되었습니다.

---

 

Counting Method 파트에서는 위와 같은 내용에 대해서 공부하였다. 그중 PART I 부분을 먼저 정리 할 것이다.

 

유한한 sample space에서  모든 sample의 확률이 동등할때 P(A)는 위와 같이 구할 수 있고 |A| 는 A의 cardinality를 의미하기 때문에 단순히 개수를 세는 Couting Problem 이라고 할 수 있다.

---

위와 같은 주사위 문제가 있을때 Sample space는 구할 수 있지만 A는 counting method를 통해서 구할 수 있다.

 

 

n개의 가능한 결과가 있는 r번의 실험을 할때의는 n^r 의 경우의 수가 나오는데 이러한 경우를 Multiplication Principle 이라고 한다.

 

이를 적용하 예를 보자.

위와 같은 문제가 있을때 전체 경우의 수 N은 26^3 x 10^2 가 되고 10^8번 수행한다고 했을때

비밀번호가 맞을 확률은 전체 1 에서 모두 틀릴경우를 빼주면 된다.

 

따라서 1 - (1-1/N)^10^8 이 되게 된다.

 

 

또다른 예로 A가 있을때 A의 Subset의 갯수를 구할때도 각각의 원소가 존재하거나 존재하지 않거나를 따질경우

2^n 이 되게 된다. (공집합을 포함한다.)

---

용어

이렇게 하나의 set에서 element를 고르는 것을 Sampling 이라고 한다.

그중에서 한번 나온게 다시 나오는 경우를 with replacement(복원 추출) 이라고 하고 다시 나오지 않는 경우를 without replacement(비복원 추출) 이라고 한다.

 

또, 순서가 있는 경우는 ordered, 없는 경우는 unordered라고 한다. 위의 예시를 보면 쉽게 이해 할 수 있다.

---

 

위의 예시는 순서가 있는 복원 추출의 경우 예시이다. 이 경우에는 n개의 원소가 있으면 k번의 draw를 할때 n^K의 경우의수가 나오게된다.

 

 

순서가 있지만 복원추출이 아닌경우 without Replacement인 경우는 우리는 Permutation(순열) 이라고 한다.

이경우에는 복원추출이 아니기 때문에 다음 draw 때마다 선택할 수 있는 원소의 개수가 1개씩 줄어들게 된다.

 

Permutation의 notation은 오른쪽과 같이 4개정도 있는데 첫번째 notation을 주로 사용한다.

 

p_k^n 은 분자 분모에 (n-k)(n-k-1)...2x1 을 곱해주면 n! / (n-k)! 으로 쓸수 있다.

 

0!은 1을 의미하고 p_n^n 은 n!을 k가 n보다 클경우의 permutation은 0 k가 0일때는 1이 된다.

 

위 example3은 permutation의 예를 보여준다. 쉽게 풀 수 있다.

 

 

위의 예제는 birthday paradox라는 유명한 문제이다.

50명의 사람이 있을때 적어도 2명의 생일이 같은 확률을 구하는 문제이다.

A가 at least two people have the same birthday의 경우 일때 permutation을 통해서 p(A) = 1 - p(A^c) 로 위와 같이 구할 수 있다

 

K에 50을 대입하게 되면 97%의 확률이 나온다. 보통 사람들의 생각보다 높은 확률이 나오게 되는데 이는 365일중에 하루를 잡아두고 그것과 같은 날일 확률을 구하는게 아니기 때문에 그렇다. 하루를 잡아놓고 그날일 확률을 구하면 모두가 생각햇던것처럼 더 낮은 확률이 나오게 된다.