확률에서 가장 유명한 문제들로 시작하고자 한다.
다시 단순하지 않은 정의에 대한 내용으로 돌아가 보자.
먼저 이것은 확률을 공부한다면 익숙해져야 하는 문제이다. 생일 문제 birthday problem 이라고 부른다.
매우 흔한 문제이고, 몇몇은 이미 본 적이 있을 거야. 하지만 놀랍게도 대부분이 이 문제의 정답은 처음 본다는 거지.
문제를 이전에 보았더라도, 이 문제를 어떻게 생각해야 하는지 이야기해 보자.
생일 문제는 간단한 내용이다. 문제는 어떤 파티에서 사람들의 그룹이 있다고 할 경우, 2 명의 생일이 같은 확률이 얼마나 되는지에 대한 것이야.
아마도 3명이 생일이 같을 수 있지. 또는 같은 생일을 가진 사람이 여러 쌍 있을 수 있어.
여기서는 최소한 2명의 생일이 같을 확률을 찾는 거야.
매우 많은 사람이 있을 경우, 놀랍지 않을 거야. 하지만 적은 사람일 경우 대부분이 상당히 우연이라고 생각한다.
예를 들어보자.
몇 명의 사람이 있어야 최소한 50% 확률로 2명의 사람이 생일이 동일할까?
이 질문에 대한 답을 찾아보자. 이것을 생일 문제라고 한다.
일반적으로 이 문제는 k명이 있다고 할 때, 2명의 생일이 같을 확률을 찾는 거지.
특정한 2명에 대한 것이 아니야. 단지 이 그룹 내에서 생일이 같은 2명을 찾을 수 있냐는 거지.
문제를 풀기 전에 생일에 대한 몇 가지 가정이 필요하다.
여기에 2월 29일에 태어난 사람이 있는가? 여기서 2월 29일을 제외해도 괜찮을까?
원한다면 윤년을 포함해서 이 문제를 풀 수 있어. 하지만 상당히 귀찮을 거야.
2월 29일은 다른 날에 비해 확률이 낮다. 따라서 1년을 366일로 계산하지 않는 게 좋겠다.
일단 2월 29일은 제외하겠다.
1년을 365일이라고 가정한다. 문제를 간단히 만들기 위해서이지.
그리고 365일이 모두 동일한 확률을 가진다고 가정한다.
여기까지는 충분히 그럴듯한 가정이다.
365일이 모두 같은 확률을 가진다는 것은 꽤 그럴듯하게 들리지.
이것은 경험에 관한 문제인데 수학적으로 이것은 사실일까?
이것에 대한 데이터를 보면 실제로는 정확하지 않다.
계절의 영향이 있기 때문에 차이가 존재한다.
각 나라마다 다른 계절의 영향이 있지. 휴가철 이후인 9월에 아기가 더 많이 태어나고… 왜 그런지는 알고 있지?
큰 차이는 아니지만 어느 정도의 차이가 있다.
하지만, 여기서는 동일한 확률이라고 가정하겠다.
그리고 각각이 독립 indepence 라고 가정할께.
독립의 정의에 대해서는 나중에 자세히 설명하겠다. 여기서는 각 출생에 대한 독립성을 말하는거야.
지금은 직관적인 개념만 설명하겠다. 예를 들어 k명의 사람이 있는 이 그룹에서 쌍둥이가 있다면 결과가 많이 바뀔거야. 여기서는 모든 사람 각자의 생일이 다른 사람의 생일에 영향을 미치지 않는다고 가정하는거지.
여기서 독립의 직관적인 개념은 이렇게 설명할 수가 있다.
여기까지 가정이었고 이제 확률을 계산해보자. 이 강의에서 가장 어려운 점은 패턴과 구조를 찾아내는 일이다.
이 문제가 우리가 처음 시도하는 것처럼 보인다. 하지만, 과제에서 했던 것을 한번 다시 생각해봐야 한다.
이 문제는 강도 문제와 상당히 비슷하다. 다른 응용 방법이고 다른 상황이지만 비슷한 구조를 가지고 있다.
따라서 여러분은 이미 이 문제를 잘 알고 있는 것이다. 빠르게 진행하겠다.
가장 먼저 k 가 365 보다 클 때이다. 그럼, 확률은 1이 될거야.
메모: 366명 중 365명만 먼저 생각해보자. 정말 재수가 좋으면, 365명의 모든 사람들의 생일이 다 다를 수 있다. 하지만, 366번째 사람은? 이중 한 사람과 겹칠 수 밖에 없다. 즉, 반드시 겹치기 때문에 1의 확률이 된다고 말하는거지.
이것을 시각화하기 위해서 공이나 상자같은 것을 생각할 수가 있다.
지난 시간에 표시(labeling)에 대해 이야기했던거 기억나지? 이 사람들을 1부터 k라고 표시한다면 사람들을 구분할 수 없다고 생각하지 않아도 된다. 각각 개인을 구분할 수 있는거지.
그림을 그려보자면 365개의 상자를 그리는데, 여기는 점으로 표시해서 365개를 모두 그리지 않는다.
이것은 1월 1일 상자이다. 여기는 1월 2일, 여기는 12월 31일인거지.
여기 365개의 상자가 있고 그리고 각 사람들은 표시가 추가 되어 있는거야. 지금은 점으로 표시할께.
이 경우는 3명이 1월 1일에 태어난 경우야. 1월 2일엔 1명, 12월 31일에는 2명이지.
여기서는 365명보다 많은 사람이 있고 상자는 365개 뿐이야. 그렇다면 무조건 한 상자에 한 개 이상의 점이 들어가겠지. 직관적으로 잘 이해가 되지? 이 경우는 사람이 상자보다 많은 경우이다.
수학에서 이것을 비둘기 집의 원리(pigeonhole principle) 라고 부르지.
유용하면서 간단하다. 상자보다 점의 개수가 많으면 여러 개의 점이 들어간 상자가 생긴다.
메모: 비둘기집의 원리
https://ko.wikipedia.org/wiki/비둘기집_원리
비둘기집 원리 위키백과, 우리 모두의 백과사전 비둘기집 원리 위키백과, 우리 모두의 백과사전. 이 문서의 내용은 출처 가 분명하지 않습니다. 이 문서를 편집 하여, 신뢰할 수 있는 출처 를 표기해 주세요. 검증 되지 않은 내용은 삭제될 수도 있습니다. 내용에 대한 의견은 토론 문서 에서 나누어 주세요. (2013년 1월) 비둘기집 원리 는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어 있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이며, ‘서랍과 양말’로 비유하여 서랍 원칙 또는 디리클레의 방 나누기 원칙 이라고…
ko.wikipedia.org
그리고 한 가지 더 말하고 싶은 것은 이런 형태의 문제는 전산학에서 굉장히 중요하다. 종종 비슷한 형태의 문제를 만나게 된다.
다른 자료 구조에 정보를 저장할때 좋은 방법을 찾아야 하는거야.
문제는 2가지 내용을 한 곳에 저장하려고 할때 발생한다. 이것을 충돌이라고 부르지. 그리고 이런 충돌이 발생할 확률을 아는게 중요해.
따라서 이 문제는 재미있지만, 전산학에서 다양한 응용이 존재한다. 또는 다양한 공학분야에서도 말이지.
k가 365보다 큰 경우 상당히 쉬웠다.
이제 k가 365보다 작거나 같을 경우를 보자.
몇년 동안 많은 사람들에게 이 문제를 본적 없는 사람에게 답을 추측해보라고 했어.
이 문제를 직관적으로 추측해보자. 생일이 같을 확률이 50% 이려면 몇 명의 사람이 있어야 할까?
일반적으로 150이나 180정도를 추측했다. 365를 2로 나눈건데 100보다는 큰 값이 나왔다.
이 문제를 본적 없는 사람에게 물어봤을 때 항상 100 이상의 수를 선택했다.
대부분이 직관적으로 그렇게 생각한다는거야. 이 내용을 공부하기 전까지는 말이야.
실제 정답은 23명이다.
23명의 사람이 있으면 되는거야. 여기엔(강의실) 수백명의 사람이 있지. 여기서 몇 개의 열만 가지고 할 수 있겠네. 여러분의 생일 조사하기 위해서 20분을 소비할 필요는 없을거야.
하지만, 여기의 몇 열을 보면 분명 생일이 같은 사람이 있을 확률이 높을거야.
이제 이것을 수학적으로 보자. 먼저 수학적으로 어떻게 계산되는지를 보고 이것이 의미하는 것이 무엇인지를 보자. 1년이 365일이라고 할때 어떻게 23명이 나오는지를 말이야.
23명은 365에 비하면 상당히 적은 비율이다. 그런데 어떻게 50%의 확률을 가질 수 있을까?
사실은 50%보다 조금 큰데, 23명의 경우 50.7% 정도이다.
이제 확률을 계산해보자.
일단 계산하기 쉬운 여사건(compliment)을 계산하겠다. 모두의 생일이 같지 않을 확률을 계산해보자. P(no match)
그리고나서 1에서 이것을 빼면, 최소한 한 쌍의 생일이 일치하는 확률을 구할 수 있다.
이런 방법은 자주 사용된다. 이 사건의 확률을 직접 찾는 것이 쉬울지 여사건을 계산하는 것이 쉬울지 생각해봐야 한다.
이 경우는 여사건을 계산하는 것이 더 쉽다. 이렇게 하면 과제 문제와 비슷하기 때문에 빠르게 해보겠다.
확률의 단순한 정의를 사용하겠다. 여기서 모두 동일한 확률이라고 가정했기 때문이다.
분모는 365^k 가 될거야. (메모: 복원추출, 순서 중요한 경우의 수)
곱의 법칙으로 바로 얻을 수 있지. 분자의 경우, 각각의 ID 를 가지는 사람들을 생각해보자.
ID 의 순서대로 한 명씩 파티에 들어오는거야. 이렇게 생각하는 것이 쉬울거야.
첫번째 사람은 365일 중 아무 때나 생일이 될 수 있다. 두 번째 사람은 첫 번째 하고는 다른 생일을 가져야 하니까 364가 될거야. 마찬가지로 곱의 법칙을 사용하는거야.
이미 배웠던 것에서 알 수가 있지. 다음 사람은 이 2 사람을 제외하고 아무 때나 생일을 가질 수가 있어.
363이 될거고 이것들을 모두 곱하면 되지. 여기서 중요한 것은 항의 갯수가 맞는지 잘 확인하는거야.
k 가 1일때, 생일이 같은 사람이 없을 확률은 1이 되겠지. 한 명뿐이기 때문에 생일을 비교할 사람이 없는거야.
이 부분은 365-k+1 이 되는거야. +1을 빼면 매우 복잡해진다. 프로그래밍에서도 자주 일어나는 실수이다.
1을 빼먹거나 항의 갯수를 잘 확인하지 않던가 말이야.
k명이 있다고 가정했기 때문에 총 k개의 항이 있어야 한다.
따라서 여기는 365-k+1 이 되는거야. 따라서 생일이 같을 확률은 1에서 이 값을 뺀 값이 된다.
우리는 이미 이 문제를 해결했다. 따라서 쉽게 해결할 수 있다. 이미 비슷한 것을 해봤기 때문에 빠르게 보여주었다. 이것을 지수함수적으로 근사하는 방법들은 여러가지가 있다. 나중에 이 근사법에 대해서도 이야기해보자.
지금은 이것을 직접 계산하는 것이 어려워 보인다. 따라서 컴퓨터나 계산기를 이용해 계산해야 할거야.
계산해보면 생일이 같을 확률을 얻을 수 있다.
몇몇 경우에 50%보다 약간 큰 값인데, k가 23일때 50.7% 가 된다. 이 경우가 50% 를 넘기는 첫 번째 경우가 된다. 몇 가지를 더 보게 되면…
k=50 이라면, 23의 두 배보다 큰 값인데, 따라서 아마도 확률이 더 높을거야. 얼마나 큰 값이 나올까?
50명의 사람에 대해 계산을 해보면, 97%의 확률이 나온다.
훨씬 높은 값이지. 50명만 있는데도 말이야. 대부분의 사람들은 150명이 필요하다고 생각했었어.
하지만, 이 값은 50%의 확률을 가지지 않아. 150명이 아닌 50명만 있어도 97%의 확률을 가질 수 있다는거야.
이제 100명 이 있다고 가정해보자.
100명은 꽤 큰 숫자이지만, 365에 비하면 작은 수이지. 엄청나게 큰 숫자는 아니라는거야.
100명이 있는 경우, 99.999 %의 확률을 가진다. 99.999% 이상이지. 아마 99.9994% 정도가 될텐데 아마 뒤쪽에 9가 계속 나올거야.
따라서 100명의 경우 99.999%가 된다. 여기까지가 생일 문제의 풀이였다.
수학적으로 이 부분은 반박하기 어려운 부분이다. 반박하고 싶다면 시해보라. 하지만 소용없는 일일 것이다.
이 부분은 아직 직관적으로 받아들일 정도로 느껴지진 않을거야. 이 값들은 올바른 값들이지만 말이야.
100명에 99.999% 임을 어떻게 알 수 있을까? 어떻게 계산할 수 있지?
직관에 대해서 조금 더 이야기해볼거야.
기본적으로는 k 를 직관적인 수로 생각해보는거야. 이 값은 단지 몇 명의 사람이 있는지를 나타내는데, 이 값은 여기서 가장 의미 있는 값은 아니야.
가장 중요한 값은 k 가 아닌 k 에서 2개를 고르는 경우의 수가 된다.
k명이 있을 때 k명 중에서 각 2명씩을 골라야 하기 때문이지. 따라서 이 경우에는 이 값이 더 연관 있는 값이 된다.
k명 중 2명을 고르는 경우는 k(k-1) / 2 가지이다.
예를 들어, 23명 중에서 2명을 고른다면, 23명이 있는 경우 50%확률이 나왔었지.
23명 중 2명을 고르면, 2322/2 가 된다. 그러면 2311이 된다. 11을 쉽게 곱하는 법을 모두 알고 있지?
2와 3을 더해서 가운데에 추가하면 253이 된다. 따라서 23명의 경우 253쌍을 만들수가 있다.
이제 이 값이 상당히 타당한 값으로 보일거야. 23은 작은 수 이지만, 253은 충분히 큰 수이지.
이제 여기서(253) 어느 한 쌍이라도 충분히 생일이 같을만 하지 않을까? 이 값은 거의 365에 근접한 값이 된다.
따라서 이제 이 값이 충분히 타당해 보이지.
나중에 이것보다 더 복잡한 형태에 대해서 다시 보도록 하겠다. 지금은 이 부분은 꽤나 직관적인거다.
이번엔 약간 다른 문제를 푼다고 가정해보자. 우리는 우연한 일에 대해서 이야기하고 있지.
만약 두 사람의 생일이 단 하루가 차이 난다고 하면, 이것도 어떻게 보면 우연의 일치라고 할 수 있어.
같은 생일을 가지는 것보다는 놀랍진 않겠지만, 마치 내 생일이 너 생일 바로 다음 날이야 라고 하는 것과 같다.
이것도 꽤나 흥미로운 일이다. 이전과 동일한 문제이다.
대신 생일이 같거나 하루 차이가 나는 경우도 포함하는거지. 그렇게 되면 23은 14로 줄어들게 될거야.
사람들에게 이것도 상당히 놀라운 사실일거야. 14명만으로 50% 보다 큰 확률이 나온다는거지.
두 명의 생일이 같거나 하루가 차이 날 확률이 말이지.
14라는 이 결과를 증명하는 것은 이것(확률 50%일 경우)보다 훨씬 복잡하다.
직접 해본다면 365 대신에 363, 362,,, 를 넣어볼 수 있다. 생일 당일과 그 전날, 그리고 그 다음 날을 제외시켜야 하기 때문이다.
따라서 여기에 3을 빼는거야. 하지만, 이렇게 하면 틀리게 되지. 그냥 1년을 기준으로 날짜를 채워넣듯 생각해서 차이가 나는거지. 이것을 모두 곱할 수는 없다. 따라서 훨씬 어려운 문제가 된다.
나중에 이렇게 복잡한 문제를 근사하는 방법을 다시 배우게 된다.
여기서 기본적인 개념은 우연에 관한 것이다. 가장 큰 우연은 우연한 일이 전혀 없는 상태일거야.
세상에 존재하는 모든 우연한 일들을 생각해 볼 수 있다. 상상도 하기 어려울 정도로 수 많은 우연한 일들이 있겠지. 그리고 그 중 일부가 실제로 발생하지.
여기서는 23명만 있음에도 불구하고 발생할 수 있는 253가지의 우연이 있는거지.
이건 전혀 놀라운 일이 아니야. 여기까지 생일 문제에 대한 것이였다.
그리고 한 가지 이야기 하자면, 아주 유용한 애플릿이 있다. 이 애플릿의 링크가 강의 웹사이트에 링크가 있어. 스탠포드에서 만든건데, 나중에 한번 해봐라.
그 시뮬레이션을 해보면 직관적으로 이해하는데 도움이 될거야. 또 온라인에서 생일 문제 애플릿을 쉽게 찾을 수 있다. 직접 찾아보고 시뮬레이션을 실행해봐라.
어떻게 생일이 같은 경우가 나오는지 실제로 볼 수 있다. 여기에는 23명뿐이 없지만, 이 방법을 통해 직관적으로 확인할 수가 있다.
이 방법은 여러 방법 중 하나이다.
여기까지 생일문제에 대한 것이었다.
이제 확률의 단순하지 않은 정의로 되돌아가보자.
매우 간단하게 했기 때문에 다시 상기해보자. 두 가지의 정리(axiom) 만 있으면 되지.
먼저 우리가 정의한 표본공간(sample space) 가 있었어. 그리고 함수 P 가 있는데 확률(probability)를 의미했지. 꽤 적절한 표현이야.
두 가지 정리가 있었는데, 첫 번째는 공집합의 확률은 0이고, 전체 표본공간(full sample space)에 대한 확률은 1이지.
그리고 두 번째는, 여기서(첫 번째)는 공집합도 하나의 사건으로 생각한다.
아직 어떻게 사건을 집합으로 생각해야 하는지 이해되지 않는다면 최대한 빨리 이 부분을 이해하고 싶을거야.
공집합도 하나의 사건이다. 하지만, 절대 발생할 수가 없는 사건이지. 따라서 확률은 0 가 된다.
전체 표본공간은 항상 발생하는 사건들이지. 따라서 불가능한 사건은 0의 확률을 가지는거고 확살한 사건에 대해서는 항상 1의 확률을 가지는거야.
그리고 한 가지 정의가 더 있는데. 합사건의 확률에 대한 정의이지.
이 부분은 n이 1부터 무한대가 되더라도 유한사건일 수 있는거야. 이 표현이 일반적이기 때문에 이렇게 적도록 해보겠다. 하지만, 이 부분도 유한 사건이라는 것을 알고 있기를 바란다.
이 값은 n이 1부터 무한대일때 P(An) 의 합이 되는거지. 그리고 매우 중요한 조건이 있는데, A1, A2, ,,, 등이 모두 겹치지 않는 서로소여야 한다는거야. 이것이 중요한 조건이다. (서로소 = disjoint = don’t overlap)
이제 상당히 직관적인데, 벤 다이어그램을 그려보자.
여기 표본공간 S 가 있다. 이 무한대의 사건을 모두 그리지는 않겠어. 세 가지만 그려볼께.
여기 세 개의 동그라미 A1, A2, A3라고 할께. 먼저 직관적으로 확률을 면적으로 생각해보자.
나중에 더 복잡한 방법들을 배우겠지만 지금은 면적으로 생각하는게 좋겠다.
이 직사각형을 보면, 약간 둥근 직사각형이지만 사실 이건 상관없다.
확률을 면적으로 생각하면 이 영역의 면적은 1이 된다.
여기서도(A1) 확률을 면적으로 생각하면, 이 세 가지 사건을 더한 것의 확률은 이 면적과 이 면적, 그리고 이 면적을 더한 것이 된다.
이것만 알고 있으면, 이것을 확장해서 무한대의 사건이 있더라도 같은 방식을 적용하면 된다.
여기까지가 정리애 대한 설명이다. 이 두 조건이 P가 만족해야 할 것들이지.
이 부분은 큰 진전이 있는데, 확률에서 큰 진전은 이것을 집합, 사건, 합집합, 교집합 등으로 생각하게 된 것이었고, 또 다른 수학적 진전이 있었는데 그것이 이 두가지 정리이다.
메모: 확률에서의 커다란 2가지 진전이 있었는데 하나는 사건에 대한 확률을 집합으로 생각해서 합집합, 교집합 등으로 연산할 수 있다는 것과 그리고 2가지 공리 (공집합, 전체 집합에 대한 확률과 개별 사건의 확률의 합)를 전제조건으로 만족시킨다는 것이지.
유명한 수학자인 콜모고로프는 이 정리에 가장 많이 공헌한 사람이다. 이 정리들이 나오기 전에는 확률에서 어떤 것이 맞고 틀린 것인지 판단하기가 어려웠다.
확률의 의미가 무엇인지에 대해 수많은 철학적 논의가 있었다. 그리고 이 논의는 오늘날에도 계속되고 있다.
철학에서의 이 논의는 수 백년간 계속되고 있다. 통계학에서는 기본적인 문제에 대해 생각하는 것이 중요할 것이다. 확률이 실제로 의미하는 것이 무엇인지에 대한 것이야. 실제로 굉장히 중요하지만, 그건 이 강의의 주제가 아니다.
그리고 이것이 이 정리를 이끌어 내는데 큰 도움이 되지 않지.
기본적으로 수학적인 관점에서 표본공간과 이것을 만족하는 함수 P만 있으면, P가 사건을 입력으로 하고 0부터 1까지의 수를 출력하는 함수라는거야. 이 2가지(axiom)를 만족하면서 말이지.
이것들을 만족하기만 하면 P를 확률이라고 할 수 있다. 그리고 확률에 대한 모든 정리를 적용할 수 있게 되는거야.
이것이 실제로 무엇을 의미하는지 신경쓸 필요는 없다는거지. 사람들은 다양한 확률의 해석을 논의하고 있지만 말이야.
여기에서는 이 두 가지를 만족하기만 하면 된다는거야. 이 두 가지 간단한 규칙을 가지고 확률에 관련된 모든 정리들을 유도할 수 있다.
간단한거부터 해볼께. 이 정리를 이용한 간단한 결과들을 만들어보자.
먼저 굉장히 직관적인 부분부터 시작해본다. 이것을 속성(Properties)라고 부를께.
이 정리를 이용해 빠르게 확률의 몇 가지 속성을 유도해보겠다.
첫 번째는 매우 간단하다. P(Ac) = 1 P(A)
우리는 사실 이전에 이미 이것을 사용했다. 이 속성을 단순한 정의에서도 사용했다.
우리는 원하는 결과(outcomes)와 그렇지 않은 결과를 나누었지.
그래서 결과의 총 가짓수는 원하는 결과와 그렇지 않은 결과의 가짓수의 합이었어. 단순한 정의를 사용할 때에도 항상 이것은 참이었다는거지.
이 그림에서 더 확실하게 보이는데, A1 이 A라고 하면 Ac 는 A1 의 바깥쪽이 될것이고 A의 바깥쪽이라고 할 수 있지. 전체 면적이 1이므로 이 값이 0.3 이면 바깥쪽은 0.7 이 된다.
벤 다이어그램이 확실히 직관적이지.
그러면, 이것을 어떻게 증명할까? 증명도 매우 간단하다.
1은 전체 공간의 확률임을 이미 알고 있다. 이것은 첫 번째 정리이지. 그리고 S를 A와 Ac 의 합집합이라고 할 수 있지.
이 부분은 A의 안쪽, 이 부분은 A의 바깥쪽이기 때문에 이 둘을 합치면 전체가 되지.
이제 1 = P(S) = P(A ∪ Ac) = P(A) + P(Ac) 가 된다. 왜냐하면 A와 Ac 는 서로소이기 때문이야.
집합의 표현을 쓰면 교집합이 공집합이라고 할 수 있지. A ∩ Ac = Ø
정의에 의해서 A와 Ac 의 교집합은 공집합이 된다. 따라서 서로소이기 때문에 두 번째 정리(axiom 2)를 사용한 것이지.
이 값은 이 두 값을 더한 값이고 여기 적힌 것처럼 된다. 이 증명은 첫 번째, 두 번째 정리를 이용해 바로 할 수가 있다. 이것이 첫번째 속성이야.
원래 첫 번째 속성이라고 부르지 않지만, 오늘은 그렇게 부르도록 하자.
두 번째 속성도 유용하다.
A가 B에 포함된다면, A와 B는 사건이야. 이 사건 A 는 이 사건 B에 포함되는거지. A ⊆ B
다시 말하면 이 관계가 의미하는 것은 A가 발생했다면 B도 발생했다고 봐도 되는거지.
이 사건(B)이 더 큰 사건이야. 그러면 P(A) 는 P(B) 보다 작거나 같게 된다. P(A) ≤ P(B)
이것도 벤 다이어그램으로 보면 확실히 직관적이다. B는 더 큰 동그라미이고 안에 작은 동그라미를 포함하겠지.
더 큰 면적을 가질거야. 그림을 통해서 확실히 알수 있지. 하지만, 이것이 공식적인 증명은 아니다.
이것을 한번 증명해보도록 하자. 정리를 사용해서 빠르게 이것을 증명해보자.
증명을 위해서 여기에 그림을 다시 그려볼께. 여기 A가 있고 여기 B가 있다.
B는 A를 포함하고 더 큰 크기를 가지지. B를 이제 두 부분으로 나누어볼거야. A와 A가 아닌 부분으로 나누겠다.
B를 분해해서 2개 부분으로 나누는거지.
B를 A 와 고리 부분의 합 사건으로 생각할 수 있는거야.
이 고리는 B에 포함되면서 A가 아닌 부분인데, 따라서 B = A ∪ (B ∩ Ac) 가 되지.
(고리 부분은) B에는 포함되지만, A 에는 포함되지 않는 부분이지. 그리고 이 집합들은 서로소가 된다.
A 는 이것 (B ∩ Ac) 와 서로소라고 할 수 있어. 서로소이기 때문에 P(B) = P(A) + P(B ∩Ac) 가 되는거지.
두 번째 정리에 의해서 이렇게 되는거야. 확률의 정의에 의해서 확률은 음수가 될 수 없기 때문에 음수가 아닌 어떤 값을 더했으므로 이 값은 P(A)보다 큰 값이 된다. P(B) = P(A) + P(B ∩Ac) ≥ P(A)
이렇게 증명이 끝났다.
2번째 정리를 바로 이용해 얻을 수 있지. 질문 있나?
확률이 음수가 아니라는 사실은 어디에서 나온 것인가요? 확률이 음수가 아니라는 것 말이지?
여기에 적지는 않았지만, 어제 이야기했다. 이것도 원한다면 정리라고 부를 수 있다. 0번 정리라고 하면 되겠네.
지난 시간에 설명했는데, 이번에 여기 다시 적지 않았네.
이것을 적지 않은 이유는 이 정리들을 한 문장으로 적을 때, P는 사건으로부터 정의되는 함수이며 0부터 1까지의 값을 가진다고 할 수 있는데, 그것이 이것과 이것이기 때문이지. 물론, 이 정리도 포함시키고 싶다면 그렇게 해도 된다.
확률이 항상 0부터 1사이의 값이라고 가정했기 때문이지.
여기까지 두 가지의 간단한 속성을 보았다.
약간 복잡한 한 가지를 더 보도록 하겠다. 매우 유용할거야.
합사건의 확률은 어떻게 구하는지에 대한 것이다.
세 번째 속성은 합사건의 확률에 대한 것이다.
A와 B가 서로소일때는 그냥 P(A) + P(B) 를 계산하면 되지. 벤 다이어그램을 다시 그려보면, A가 여기 있고 B가 여기 있는데, 그리고 여기는 교집합이지.
직관적으로 A와 B의 면적을 더하게 되면, 교집합 부분이 중복되게 된다.
따라서 이 값을 한 번 빼주어야 한다. 따라서 이것을 이렇게 해도 되는지 증명할거야. 그리고 이것을 사용하는 예시를 보여줄께.
이것은 굉장히 자주 사용될거야. 앞으로 합사건의 확률을 자주 구하게 될 텐데 집합이 서로소일 확률은 그리 높지 않기 때문이다.
따라서 서로소가 아닐 경우 계산하는 법을 알아야 한다.
확률을 이렇게 더하게 되면 교집합 부분이 중복되기 때문에 한 번 빼주어야 한다. 교집합의 확률을 빼주면 되지.
P(A ∪ B) = P(A) + P(B) P(A ∩ B)
이것을 증명해보자. 일단 전략적으로 생각해보는거야. 이것을 어떻게 증명해야 할지 모르기 상태지.
여기서 사용할 전략은 어떻게 이 정리들을 적용할지에 대한 것이다.
두 번째 정리는 매우 중요한 정리이지만, 이 정리는 서로소일 때만 적용할 수 있지.
따라서 이것들을 서로소인 상태로 만들어줘야 할거야. 이런 전략을 사용해보자.
P(A ∪ B)를 다른 방식으로 적어볼꺼야. 여기서는 아직 두 번째 정리를 사용할 수 없는 상태야. 서로소가 아니기 때문이지. 따라서 서로소가 되도록 바꿔 적어보도록 하는거야. 나는 이것을 서로소화라고 부른다.
확실하지는 않지만, 서로소화라는 말은 내가 만들어낸 말 같아. 서로소화를 해보자.
단어가 길지만 여기 적어볼께. disjoinitification
A ∪ B 를 각각 서로소인 상태로 만들어보자. 어떻게 해야 할까? 집합 A와 B에 포함되지만 A에 포함되지 않는 부분을 보겠다.
그래서 A ∪ (B ∩ Ac) 가 되는 것이지. 맞지? 저 부분과 비슷한 형태가 되는거야. 차이점은 여기에서는 A가 B에 포함되어 있다는거야.
여기는 임의의 사건 A와 B에 대해 훨씬 일반적인 상황이지. 따라서 A의 전체 부분과 A에 포함되지 않는 나머지 B의 부분을 사용하는거야. 그래서 이 부분을 제외시킨거야.
이제 이 둘은 서로소가 되기 때문에 두 번째 정리를 사용할 수가 있다. P(A) + P(B ∩ Ac) 가 되지.
아직은 이것이 이 부분과 같은지 확실하지 않다. 여기서 wishful thinking 이라는 또 다른 방법을 사용할거야.
내가 원하는 결과이지. 여기에 물음표를 넣을거야. 여러분이 원하는 결과를 이유없이 등호로 적는건 좋지 않지만, 하지만, 여기에 물을표를 표시한다면 괜찮다.
따라서 나도 여기에 물음표를 넣을거고 P(A) + P(B) P(A ∩ B) 라고 쓰겠다. 나는 이것이 정답이 되기를 바라는거야. 사실 이것이 정답임을 알고 있지만, 아직은 모르는 상태인 것으로 하자.
이제 이것이 맞는지 확인해보도록 하자. 나는 이것이 정답이기를 바라는거야.
이제 이 두 가지를 비교해보겠다.
여기의 P(A) 는 여기 P(A)와 동일하다. 따라서 이 부분이 이 부분이 같다면 이것은 참이 되겠지.
따라서 이 부분을 다시 적으면 이 부분은 이 부분에서 이것을 뺀 것하고 같게 된다. 하지만 빼기 부호 없이 더 쉽게 적기 위해서 P(A ∩ B) 를 이쪽으로 옮기도록 하겠다. 따라서 이렇게 적을 수 있는거지.
P(A ∩ B) + P(B ∩ Ac) = P(B) 가 되는거야.
이것이 참이 되기 위해 여기와 여기가 같아야 된다고 이야기했지. 그래서 이것을 이쪽으로 옮겨서 이렇게 만들었다. 이제 이것이 참인지 확인해볼까?
당연히 이것은 참이지. 두 번째 정리에 의해 참임을 바로 알수가 있어. 왜냐하면 A ∩ B 와 Ac ∩ B 가 서로소이기 때문이지. A와 Ac 에 동일한 원소가 동시에 포함되는 것은 불가능하기 때문이지.
따라서 이 둘은 서로소이고 합사건은 B가 되는거야. 왜냐하면 이것은 B를 둘로 쪼갠거나 다름 없기 때문이야.
A에 포함되는 B의 부분과 A에 포함되지 않는 B의 부분이 되는거지.
따라서 두 가지 서로소인 집합이므로 이렇게 증명되는거야.
이 속성은 포함배제의 원리(Inclusion-Exclusion Principle)라고 부르고 있어. 포함배제의 원리의 더 일반적인 표현을 보자.
그리고 몇 가지 포함배제 원리의 예시를 보도록 하자. 이것이 일반적인 포함배제 원리의 식인데, 깔끔한 형태는 아니지만 개념 자체는 상당히 간단하다.
이것을 두 가지 사건 이상인 경우로 확장시켜 보겠다.
먼저 세 가지 사건의 경우를 해보도록 하자.
P(A∪B∪C) 를 다이어그램을 그려서 나타내보겠다. A, B, C 3개의 사건이 있다. 연결되어 있는 고리처럼 보이지.
그리고 합사건의 확률을 구하려는거야. 방금 전에 했던 것 처럼 해볼께.
각각의 확률을 더한 후에 중복된 것을 제거할거야. 그래서 P(A) + P(B) + P(C) 를 계산한다. 그림을 보면 너무 많이 중복된 것이 보이지. 여러 개가 중복되어 있어.
따라서 이제 교집합 부분을 빼야 한다. 먼저 P(A∩B)를 빼고, 그리고 P(A∩C)를 빼고, P(B∩C)를 빼야 한다.
그런데, 이제 너무 많이 빼버린 것이 되었어. 이 그림을 보면서 다시 생각해보면, 여기 3 부분이 교차하는 부분은 어떻게 될까?
세 집합의 교집합은 세 번 더해졌다가 세 번 뺐지. 따라서 아직 세어지지 않은거야. 세 집합의 교집합 부분을 제외하면 모두 올바르게 포함된 상태이다. 하지만, 세 집합의 교집합 부분은 아직 포함되지 않은거지.
따라서 이것을 다시 더해야지. P(A∩B∩C) 가 되는거야.
여기까지가 포함배제의 원리이다.
이것을 방금 전과 비슷한 방법으로 증명할 수가 있다. 더 복잡하기 때문에 그 과정을 적지는 않을거야.
물론 더 간단한 방법도 있는데 다음에 배우도록 하겠다. 완전히 유사하지만 단지 복잡할 뿐이다.
일반적으로 만들기 위해서 이것을 귀납적(induction)으로 사용할수가 있어. 전체 귀납법을 모두 설명하지는 않을꺼야. 모두 동일한 개념이기 때문이다.
일반적인 경우는 n개 사건에 대한 합사건이 있는 경우인데, 포함배제원리의 일반식이야. P(A1∪A2…∪An)
이것을 외우고 있다면, 이것도 쉽게 적을수가 있다. 깔끔하지는 않지만, 동일한 방식이야.
먼저 각 사건을 더하고, 각 사건들의 교집합을 빼는거야. i가 j보다 작을 때, P(Ai ∩ Aj) 라고 하면 되겠지.
i 가 j 보다 작도록 한 이유는, A1 ∩ A2 와 A2 ∩ A1 이 중복되지 않도록 하기 위한 것이지.
그리고 세 집합의 교집합을 더하는거야. 덧셈과 뺄셈이 교대로 반복되지.
세 집합의 교집합을, i < j < k 일때 Ai ∩ Aj ∩ Ak 를 더하면 되지.
계속 반복되어서, 마지막은 모든 사건의 교집합이 되는거야. 그리고 덧셈 또는 뺄셈이 될거야.
아마 (-1)n+1 이 될거야. n이 2인 경우를 생각해보면 뺄셈에서 끝나지. n이 3일때 덧셈에서 끝났지.
따라서 (-1)n+1 이 되고, 모든 사건의 교집합이 오면 된다. 이제 여러분이 이것을 직관적으로 이해할 수 있기를 바란다.
포함배제 원리라고 불리는 이유에 대해서도 말이지. 이 세 가지 경우로 볼때, 먼저 모든 집합을 포함하면 중복되는 부분이 생기지. 따라서 이 부분을 배제해야 하는거지. 그리고 또 다른 부분을 맞추기 위해 포함과 배제를 반복하는거야. 이제 포함과 배제를 계속 반복하면 되는거지.
여기는 n개가 모두 포함되기 때문에 합을 구하지 않아도 된다.
(맨 마지막 항은) 모두 포함되었기 때문에 한 개만 있으면 되지. 나머지는 모두 합을 계산해야 하지.
포함배제 원리에 대한 유용한 예시를 하나 들어볼꺼야. 이것을 어떻게 문제에 적용할 수 있을지 본다.
매우 오래된 문제이다. 드 몽모르트(de Montmort’s problem)라는 사람에 의해 만들어졌다. 1700년대였던거 같은데 1713년도 정도였던거 같다. 1713년이 맞군.
다른 이름으로 불리기도 하는데, 매칭 문제라고 불리기도 한다. 나도 보통 매칭 문제(match problem)라고 부른다. 또는 몽마르트 문제라고 부르기도 한다.
사실 이 문제의 이름이 무엇인지는 그렇게 중요하지 않아. 개념을 아는 것이 중요하지.
여러 이름으로 불리는 이유는 여러 가지 상황에서 발생하게 되었던 문제였기 때문이야.
이 문제를 설명하는 방법은 여러 가지가 존재한다. 다양한 형태로 설명할 수가 있어.
나는 가장 먼저 나온 형태로 설명을 할거야. 이제 놀랍지 않겠지만 이 문제는 도박에서 처음 나왔다.
몽마르트는 다양한 도박 게임에 관심을 가지고 있었지. 1713년 확률론이 초창기일 때, 그는 몇 가지 도박 게임을 연구했었어. 이것은 도박꾼들에게 실제로 적용될 수 있는거였어.
매우 큰 돈이 걸려 있었기 때문에 상당한 동기 부여가 되었던거지. 그 문제는 카드 게임에 관한 문제야.
카드 뭉치가 있다고 해보자. 각 카드가 스페이드 A나 클로버 7 같은 것들보다 카드가 1부터 n까지 숫자로 표시되어 있다고 해보자. n장의 카드 뭉치가 있을 때, 각 카드가 1부터 n까지 번호를 가지는 것이지.
카드 한 장당 한 개의 숫자이다. 1부터 n까지 표시된 n장의 카드가 있다고 해보자.
이제 이 게임에 대해 설명할거야.
1700년대로 돌아가서 이 게임을 한다고 생각해보자.
먼저 카드를 섞는다. 그리고 카드를 한 장씩 뒤집을거야. 그리고 너희들은 1부터 n까지 숫자를 세는거지.
내가 첫 번째 카드를 뒤집으면 너희들은 1을 세는거야. 두 번째 카드를 뒤집으면 2를 세는거지. 그리고 세 번째 카드를 뒤집고 3까지 세는거야. 이렇게 계속하는거야.
그리고 내가 뒤집은 카드의 숫자가 너희들이 센 숫자와 같으면 너희들이 이기는거지.
그렇지 않으면 지는거지. 이런 게임이야. 여기서 매칭이라고 부르는 이유가 이것이다.
만약 7번째 카드의 숫자가 7이면 너희들이 이기는거야.
카드 뭉치의 7번째 카드에 7이라고 적혀져 있다면 말이야. 모두 이 게임에 대해서 이해했지?
이제 이렇게 될 확률을 구해보자. 최소 한 장의 카드에 적힌 숫자가 카드 뭉치의 위치와 같을 확률이지.
모든 설명을 여기에 적지는 않겠다. 너희들이 이미 게임을 이해 한것으로 생각할거야.
이제 확률을 구해보자. 확률을 계산하기 위해 먼저 사건을 정의해야 한다.
그렇지? 물론 이 문제를 푸는 방법은 여러 가지가 있다. 직접 계산하는 방법도 있지. 포함 배제의 원리를 사용하지 않고 계산하는 것은 꽤나 어려울거야.
불가능한 것은 아니지만 내 생각엔, 포함배제의 원리를 사용하는 것이 가장 쉽다.
따라서 이 문제가 좋은 예시가 된다.
먼저 사건을 정의해보자. Aj 를 사건이라고 해보자. 이 사건을 j번째 카드가 매칭되는 상황이라고 하는거야.
다시 말해서 j번째 카드에는 숫자 j가 쓰여져 있는거야. 따라서 우리가 구해야 하는 것은 합사건의 확률이다.
P(A1 ∪ A2 ∪ … ∪ An) 이게 최소 한 장의 카드가 매칭되는 확률의 수학적 표현이지.
최소 한 장의 카드가 매칭되어서 너희들이 게임을 이길 확률이라는거야.
직접 계산하기에 꽤 어렵다. 그리고 포함배제의 원리를 이용하면 꽤 지저분하게 보일거야.
그래서 나는 이 문제를 풀 때, 처음부터 무조건 포함배제의 원리를 사용하지는 않아.
하지만 여기에선 다른 방법보다 이 방법이 나을 것 같아. (포함배제의 원리는) 합사건의 확률을 계산하는데 매우 유용한 방법이기 때문이지.
포함배제의 원리를 적용해봐야겠지? 이것을 한 번 적어보자.
운이 좋게도 이 문제에는 대칭적인(symmetry) 부분이 많이 있다. 따라서 대칭의 이점을 잘 사용해야 한다.
가장 먼저 이것들의 합을 계산해야 할텐데, 실제로 Aj 의 확률은… 음, 먼저 간단한 형태로 계산을 해보도록 하자.
여기에 하도록 할께. P(Aj) 는 j 번째 카드가 숫자 j 가 써져 있을 확률이지.
이것에 확률의 단순한 정의를 사용할 수가 있어. 이것을 생각하는 방법에는 두 가지 방법이 있지.
한 가지 방법은 분모에 n! 을 넣는거야. 단순한 정의를 사용했을 때 카드의 가능한 모든 순서가 모두 같은 확률로 나온다고 가정했기 때문이지.
이 방법도 괜찮지만, 더 쉬운 방법은 단순히 1/n 으로 생각하는거야. 모든 위치에 대한 확률이 같은 확률이라고 할 때 1/n 이 되는거지. j 번째에 위치할 확률이 모두 같은 경우이다.
그 카드에 j라고 표시되어 있을 확률이지.
만약 52장의 카드가 있고 스페이드 A를 찾는다면 스페이드 A가 어떤 곳에 위치할 확률은 모두 동일하지. 따라서 특정한 위치에 있을 확률은 1/52일거야.
따라서 여기서도 1/n 이 되는 것이지.
물론 단순한 정의를 사용해서 n!을 사용할 수도 있어. (n-1)! / n! 은 결국 이것(1/n)가 같아지는거지.
여기서 이 값은 j에 관한 식이 아니라는 것을 알아야 한다. 이것이 아주 중요한 부분이다.
만약 j와 n에 대한 식이 나온다면 매우 복잡해질거야. 합을 계산해야 하기 때문이지.
메모: j 번째 위치에 j 가 있을 확률은, 두 가지로 생각할 수 있다. 단순하게 생각해서 j 번째에 올수 있는 경우의 수는 n가지가 있고, 그 중 j 는 1개만 있을 수 있으니까 1/n 으로 생각할수도 있고, 다른 방법으로 생각해보면, 카드의 모든 가능한 경우의 수(비복원, 순서 중요)는 n개중 n개를 선택하기 때문에 n! 이 된다. 분자 같은 경우, j 번째를 뺀 나머지에서 모든 가능한 경우의 수(비복원, 순서 중요)는 (n-1)개에서 (n-1)를 선택하기 때문에 (n-1)! 이 된다. 그래서 (n-1)!/n! 이 되는거지. 약분하면 결국은 1/n 과 같아진다.
하지만 j가 없는 경우에는 이것을 n으로 묶을수가 있어. P(Aj) = 1/n
이제 P(A1 ∩ A2) 를 계산해보자. 대칭을 이용할거야.
여기서 Ai ∩ Aj 라고 쓸 수도 있지만, 난 구체적으로 1과 2를 선택했다. 이제 이것을 계산해보자.
먼저 단순한 정의를 사용한다.
카드 뭉치의 순서는 n! 가지가 가능하지. 이 사건 P(A1 ∩ A2) 가 의미하는 것은 카드 뭉치의 맨 위에 1번 카드가 있는 경우와 두 번째 위치에 2번 카드가 있는 경우이다.
그리고 나머지 n-2 장의 카드는 어떤 순서라도 가능하지. 따라서 나머지는 (n-2)! 가 된다.
이것을 이렇게 둘수도 있고 약분을 해버릴수도 있는데, 약분하면 1/n(n-1) 이 된다.
나머지 부분은 모두 약분된거야. 이것을 계속하면 P(A1 ∩ A2 ∩ … ∩ Ak) 는 이건 맨 위부터 k장의 카드가 정확히 1부터 k까지인 상황이 되지.
나머지 n-k 장의 카드는 어떤 순서가 되든지 상관이 없어. 따라서 분모는 n! 이 되고, 분자는 (n-k)! 이 되는거야. 그렇지?
상당히 복잡해 보인다. 하지만, 좋은 점은 이것들이 대칭이라는거야.
메모: 아래 그림에도 있지만, 전체적으로 순서가 중요하고 비복원 추출 방식이기 때문에…
분모는 모든 가능한 경우의 수 n! 이 되고, 분자의 경우는 교집합 갯수의 수만큼 뺀 (n-k)! 이 된다.
P(Aj) = (n-1)!/n! = 1/n
P(A1 ∩ A2) = (n-2)!/n! = 1/n(n-1)
P(A1∩ … ∩ Ak) = (n-k)!/n!
이 식은 여기에 어떤 것을 넣더라도 동일하다는거지.
이제 빠르게 포함배제의 원리를 적용해보겠다.
이것 P(Aj) = 1/n 을 먼저 n개만큼 더하는 것으로 시작한다.
그러면 n*(1/n) 이 되지.
그리고 다음 부분을 더하겠다. 이 부분은 몇 개나 될까? 이 부분은 n개 중 2개를 고르는 경우의 수만큼 있겠지.
이번에는 반대로 뺄셈을 해야해. n개 중 2개를 고르는 경우의 수를 n(n-1)/2 라고 적을께. 그리고 1/n(n-1) 이 되니까 1/2 가 될거야.
하나를 더해보면, 이제 무언가 보일거야. n개중 3개를 고르는 것을 이렇게 적고, n개중 3개를 고르는 것은 n(n-1(n-2) / 3! 이 되지.
(기존 2 대신에) 여기는 사실 2!이라고 적을 수 있어.
그리고 여기와 와야 할것은 n(n-1)(n-2) 가 되겠네. 이제 여기서 멋진 상황을 발견할 수 있지.
여기서 n(n-1)이 나오고 여기선 n이 약분되서 없어지지. n(n-1)이 약분되서 없어지고, 그리고 여기서도 모두 약분되서 없어진다.
숫자만 남게 되는거지. 이제 그 다음 뺄셈등이 계속 될거야.
이것을 계속해보면, 이러한 형태를 발견할 수가 있다. 이것을 근사적으로 계산하면
1 - 1/2! + 1/3! - 1/4! + … 이 될거야. 여기는 등호가 되겠네. 그리고 마지막 항은 -1의 거듭제곱에, 1/n! 을 곱한 것이 될거야. 마지막 부분은 패턴에 따라서 되겠지.
마지막 항이 무엇인지 봐야겠군. (-1)n * 1/n! 이 되는군. 여기와 똑같은 패턴이 된다. (메모: (-1)n 이 아니라 (-1)n+1 이다)
상당히 복잡하지만, 이것이 정답이다. 이미 끝날 시간이 지났는데, 여기까지가 끝인데, 이것이 아마 다들 익숙할거야. 복잡한 식이기도 하지만, 익숙하기도 하지?
이 식이 ex 의 테일러 급수라는 것을 기억해내야 하는거야.
따라서 근사적으로 1 - 1/e 의 값을 가지게 된다. 이 강의에서 앞으로 1/e 를 많이 보게 될거야.
이 문제는 e와 연관이 없어 보이지만 결국 이것을 계산하면 e 가 나오게 된다.