대학에서는 쓸모 있는 내용으로 넘어가기 전에 확률론을 아주 오랫동안 공리화합니다. 지금부터 그 이유를 보여 드리겠습니다.
원에 내접하는 정삼각형을 생각해 봅시다. 원의 현을 무작위로 하나 고릅니다. 고른 현이 삼각형의 한 변보다 길 확률은 얼마입니까?
알고 보면, 이 문제를 푸는 방법을 적어도 세 가지는 생각해 낼 수 있는데, 모두 타당해 보이지만 서로 다른 답을 냅니다.
원 위에서 임의로 두 점을 고르고 그 두 점을 지나는 현을 그읍시다. 구하는 확률을 계산하기 위해, 삼각형의 한 꼭짓점이 현의 끝점과 일치하도록 삼각형이 회전되어 있다고 생각합시다. 현의 다른 끝점이 삼각형의 나머지 두 꼭짓점 사이의 호 위에 있으면 현의 길이가 삼각형의 변의 길이보다 길다는 것에 주목하십시오. 이 호의 길이는 원 둘레의 3분의 1이므로, 구하는 확률은 $\frac13$입니다.
원의 반지름 하나를 고정하고, 그 반지름 위의 점 하나를 임의로 고릅시다. 고른 점을 지나고 고정한 반지름에 수직인 현을 그립시다. 구하려는 확률을 계산하기 위해, 삼각형의 한 변이 고정한 반지름에 수직이 되도록 삼각형을 회전했다고 생각합시다. 현의 중점이 삼각형과 고정한 반지름의 교점보다 원의 중심에 더 가까우면, 현은 삼각형의 변보다 깁니다. 삼각형의 변은 반지름을 이등분하므로, 삼각형의 변보다 긴 현을 고를 확률은 $\frac12$입니다.
원 내부에서 임의의 점을 무작위로 선택하고, 선택한 점을 중점으로 하는 현을 그립시다. 선택한 점이 삼각형에 내접하는 원 내부에 있으면 현은 정삼각형의 변보다 깁니다. 내접원의 넓이는 큰 원 넓이의 $\frac14$이므로, 구하려는 확률은 $\frac14$입니다.
앞에서 보았듯이, 답은 “무작위 현"의 형식적 정의에 직접적으로 좌우됩니다. 수학의 역사에서 이처럼 모순을 낳는 역설이 나타날 때마다 수학자들은 당황하여 모든 것을 형식화하고 공리화하기 시작합니다. 확률론은 이렇게 탄생했습니다.
공리 체계
확률 변수(random variable) 또는 확률량은 여러 값을 무작위로 취하는 변수를 말합니다. 확률 변수 자체는 가능한 상태들을 기술할 뿐입니다. 확률 변수는 각 상태가 얼마나 일어날 법한지를 나타내는 확률 분포와 연결되어야 합니다.
예를 들어, 육면체 주사위를 던진 결과에 해당하는 확률 변수를 도입할 수 있습니다. 이 확률 변수는 확률 공간 $\Omega = {1, 2, 3, 4, 5, 6}$의 값을 취하며, 각 값의 확률은 모두 같습니다: $p(x=i) = \frac{1}{6}$.
연속 분포
확률 변수는 이산적일 뿐만 아니라 연속적일 수도 있습니다. 예를 들어, 0부터 1 사이의 무작위 수라는 변수를 도입할 수 있습니다.
확률 밀도.
기댓값과 분산
정규 분포
생일 역설
조건부 확률
정보 이론
확률 변수는 이산형일 수도 있고 연속형일 수도 있습니다. 이산 변수는 유한한(주사위 던지기) 또는 가산 개의 상태를 가지며, 연속 변수는 연속체 위의 값을 가집니다.
함수 X : \Omega \to R를 확률 변수라고 부르겠습니다. 이 함수는
각 근원사건 x \in \Omega에 어떤 수를 대응시킵니다.
예를 들어, 육면체 주사위를 던졌을 때의 결과에 대한 확률 변수를 도입할 수 있습니다.
확률 변수는 이산적이거나 연속적일 수 있습니다. 이산 변수는 유한하거나 셀 수 있는 개수의 상태를 가집니다. 연속 변수는 실숫값을 가집니다.
확률 공간 $\Omega$란 근원사건들로 이루어진 어떤 집합을 말합니다. 이것은 사실상 어떤 집합이든 될 수 있습니다. 예를 들어, ${1, 2, 3, 4, 5, 6}$은 주사위 하나를 던졌을 때의 결과이고, ${(x, y) | 1 \leq x, y \leq 6}$은 주사위 두 개를 차례로 던졌을 때의 결과입니다.
이 공간에서 사건 $A$란 확률 공간 $\Omega$의 어떤 부분집합을 말합니다. 예를 들어 공집합이나 $\Omega$ 자체, 또는 ${1, 2, 3, 4, 5, 6}$의 부분집합인 ${1, 2, 6}$이 사건입니다.
사건은 교집합, 합집합, 여집합을 취할 수 있습니다 — 사건도 결국 부분집합이기 때문입니다.
일부 사건(근원 사건 포함)에 대해 확률이라고 부르는 함수 $P$가 정의됩니다. 이 함수는 다음 조건을 만족합니다:
두 사건이 서로 겹치지 않으면($A \cap B = \emptyset$) $P(A \cup B) = P(A) + P(B)$입니다.
$P(\Omega) = 1$
대부분의 경우(반대를 시사하는 것이 없다면) 근원사건들의 확률은 모두 같습니다 — 이를 균등 분포라고 합니다.
첫 번째 절의 이 모든 문제에서는 풀이할 때 가장 먼저 확률 공간을 기술해야 합니다.
% \subsection{전철의 좌석} % % TODO 어딘가로 옮길 것 % 안드레이, 세료자, 료샤는 돌고프루드니에서 출발하는 전철을 타고 가고 있습니다. 칸막이 구역은 각각 6인석이고, 한 칸에 12개씩 있으며, 객차는 9량입니다. 그들은 세 명이 함께 앉을 수 있는 자리를 찾고 싶어 합니다. 그들은 한 객차를 들여다보았고 그곳에서 빈자리 7개를 보았습니다. 그들은 빈자리를 찾아 열차 안을 돌아다니는 것이 의미가 있는지 알고 싶어 합니다. 그들이 지나가야 하는 객차 수의 기댓값(자리를 찾을 확률?)을 계산하여 그들을 도와주십시오.
\subsection{동전} % TODO: 답이 1/2이 되도록 숫자 중 하나를 수정해야 합니다 안드레이와 세료자가 게임을 합니다. 그들은 동전을 $N$번 던집니다. 앞면이 $K$번 이상 나오면 안드레이가 이깁니다. 그렇지 않으면 세료자가 이깁니다(무승부는 없습니다). 세료자가 이길 확률은 얼마입니까?
a) N = 3, K = 2
b) N = 99, K = 50
c) N = 100, K = 50
\subsection{오일러 원을 그리십시오} 캠프에 참가한 모든 학생은 Java, Python, C++ 세 가지 언어 중 적어도 하나를 배웁니다. 무작위로 선택한 학생이 Java, Python, C++를 배울 확률은 각각 $0.4$, $0.5$, $0.6$입니다. 학생이 Java와 Python을 배울 확률은 $0.2$입니다. 학생이 Python과 C++를 배울 확률은 $0.3$입니다. 학생이 C++와 Java를 배울 확률은 $0.2$입니다.
학생이 세 가지 프로그래밍 언어를 모두 배울 확률을 구하십시오. 학생이 C++만 배울 확률을 구하십시오.
\subsection{수 10의 분할*} 페탸는 수 10을 세 항(0보다 큰 정수)의 합으로 무작위로 분할합니다. 확률 공간을 기술하고, 항들 가운데 수 4가 있을 확률을 계산하십시오. 분할에서 항의 순서는 중요합니다.
\subsection{룩*} $n \times n$ 크기의 체스판에 $n$개의 룩을 무작위로 배치합니다. 다음 사건들의 확률을 구하십시오:
a) $A = {$룩들이 서로 공격하지 않음$}$
b) $B = {$룩들이 서로 공격하지 않으며 주대각선 위에 어떤 기물도 없음$}$
\subsection{개표*} 두 후보가 출마한 선거에서 첫 번째 후보가 $p$표, 두 번째 후보가 $q \leq p$표를 얻었을 때, 개표가 진행되는 내내 첫 번째 후보가 두 번째 후보를 앞설 확률이 $\frac{p-q}{p+q}$임을 증명하십시오. \newpage \section{기하학적 확률}
이 문제들에서는 멋진 기법이 사용됩니다 — 확률이 어떤 넓이들의 비와 같다는 것입니다.
\subsection{직사각형 안의 점} 임의의 점 $A$는 변의 길이가 $1$과 $2$인 직사각형 안에서 균등 분포를 따릅니다. 다음 사건들의 확률을 구하십시오:
a) 점 $A$에서 직사각형의 모든 변까지의 거리가 $0.1$ 이하입니다
b) 점 $A$에서 직사각형의 가장 가까운 긴 변까지의 거리가 가장 가까운 짧은 변까지의 거리보다 작음.
\subsection{두 수} $X$와 $Y$는 구간 $[0, 1]$에서 균등하게 분포되어 있습니다. $X^2 + Y^2 \leq 1$일 확률은 얼마입니까?
\subsection{페탸와 바샤*} 페탸와 바샤는 12:00부터 13:00 사이에 만나기로 했지만 정확한 시각은 정하지 않았기 때문에, 각자 임의의 시각에 도착하여 10분 동안 기다렸다가 떠나기로 했습니다. 두 사람이 만날 확률은 얼마입니까?
\subsection{두 수*} 길이가 1 이하인 선분 세 개를 무작위로 골랐을 때, 이 선분들로 삼각형을 만들 수 있을 확률을 구하십시오. \newpage \section{조건부 확률과 독립성}
정의에 따라, $B$가 주어졌을 때 $A$의 확률은 $P(A | B) = \frac{P(A \cap B)}{P(B)}$입니다. 이를 조건부 확률이라고 하며, 일상적인 의미로는 사건 $B$가 확실히 일어났다는 것을 이미 알고 있을 때 사건 $A$가 일어날 확률입니다(말하자면 확률 공간을 $B$로 좁히는 것이며, 공식도 여기에서 나옵니다).
정의에 따르면, $P(A \cap B) = P(A) P(B)$이면 $A \perp B$($A$는 $B$와 독립)입니다. 이는 사건의 독립성에 대한 일상적인 개념과 일치합니다. 동전을 여러 번 던질 때, 각 던지기는 서로 독립이라고 간주합니다.
\subsection{전구} 방은 전구 세 개가 달린 등으로 조명됩니다. 전구 하나가 1년 안에 끊어질 확률은 $0.3$입니다. 1년 안에 적어도 하나의 전구가 끊어지지 않을 확률을 구하십시오.
\subsection{베이즈 정리와 전확률 공식} a) 베이즈 정리를 증명하십시오:
$$ P(A|B) = \frac{P(B|A)P(A)}{P(B)} $$의미상 이것은 매우 멋진 공식입니다 — 보통은 어떤 조건에서 사건이 일어날 확률은 알고 있지만, 그 조건들이 성립할 확률은 분명하지 않습니다. 이 공식들을 사용하면 사건들이 일어났다는 조건에서 그 조건들의 확률을 계산할 수 있습니다.
b) 다음 조건
$$ \Omega = B_1 \cup ... \cup B_n (B_i \cap B_j = \emptyset) $$ 에서 전확률 공식 $$ P(A) = P(A|B_1)P(B_1) + ... + P(A|B_n)P(B_n) $$을 증명하십시오.
이것은 중요하면서도 직관적으로 이해하기 쉬운 공식입니다 — 사건을 서로 겹치지 않는 하위 경우들로 나누고, 각 경우에서 사건이 일어날 확률을 구한 뒤, 그 경우들의 확률을 가중치로 하여 평균을 내는 것입니다.
\subsection{베이즈 정리 또는 전확률 공식 문제} 사수 30명 중 12명은 0.6의 확률로, 8명은 0.5의 확률로, 10명은 0.7의 확률로 표적을 맞힙니다. 무작위로 선택된 사수 한 명이 사격하여 표적을 맞혔습니다. 이 사수는 세 그룹 중 어느 그룹에 속했을 가능성이 가장 높습니까? 이 사수가 실제로 표적을 맞혔다는 조건에서 그 그룹에 속할 확률을 구하십시오.
% 이 문제에 대해서는 아무것도 이해하지 못했습니다 % \subsection{출구 조사*} % 여러분은 투표소를 나오는 사람들에게 누가 누구에게 투표했는지 묻습니다. 후보는 모두 두 명으로, A와 B입니다. 여러분은 100명에게 물었고, 그중 55명이 A에게 투표했습니다. 후보 A가 승리할 확률은 얼마입니까?
\subsection{반례*} 다음 등식들이 성립하지 않음을 보여 주는 예를 드십시오.
$$ P(B|A) + P(B|\overline A) = 1 $$ $$ P(B|A) + P(\overline B|\overline A) = 1 $$성립하지 않습니다.
\subsection{또 하나의 반례*} 사건 $A_1$, …, $A_k$는 정의에 따라, 그 임의의 부분집합 $A_{i_1}$, …, $A_{i_t}$에 대해 등식 $P(A_{i_1}, …, A_{i_t}) = P(A_{i_1}) \times … \times P(A_{i_t})$이 성립하면 상호 독립입니다).
쌍별로 독립이지만 전체로서는 독립이 아닌 세 사건의 예를 드십시오.
\subsection{쌍별 독립 사건*} $A$, $B$, $C$가 쌍별 독립이고 확률이 같은 사건이며, $A \cap B \cap C = \emptyset$이라고 합시다. $P(A)$의 가능한 최댓값을 구하십시오. \newpage \section{확률 변수와 분포 함수}
함수 $X: \Omega \rightarrow\mathbb{R}$를 확률 변수라고 부르겠습니다. 확률 변수는 각 근원 사건에 어떤 수를 대응시킵니다. 그러면 $P(X \in A)$도 정의할 수 있습니다. 이는 확률 변수 $X$가 실수의 어떤 부분집합 $A$에 속할 확률이며, $X \in A$는 확률 공간 $\Omega$에서의 사건이기 때문에 정의할 수 있습니다.
$F_X(x) = P(X \leq x)$를 분포 함수라고 합니다.
분포 밀도란 $\rho_X(k) = P(X = k)$ (이산적인 경우) 또는 분포 함수의 도함수인 $\rho_X(x) = F_X(x)’$를 말합니다.
\subsection{분포 함수} 다음 확률 변수들의 분포 함수와 밀도 함수를 구하고 그래프로 그리십시오:
a) $X = 1$
b) $X = \begin{cases} 0, & p \ 1, & 1-p \end{cases} $
c) $X \sim U[0, 1]$ ($X$는 구간 $[0, 1]$에서 균등 분포를 따릅니다)
\subsection{기하 분포} 페탸가 동전을 던집니다. 확률 $p$로 앞면이 나오면 던지기를 멈추고, 확률 $1-p$로 뒷면이 나오면 한 번 더 던집니다. $X$를 던진 횟수라고 합시다. $\rho_X(x)$와 $F_X(x)$를 구하십시오.
% \subsection{푸아송} % % 이것은 그냥 말로 설명하는 편이 낫습니다 % 다리는 최대 $k$대의 자동차를 견딜 수 있습니다. 다리를 건너는 데에는 1시간이 걸립니다. 매우 작은 단위 시간마다 자동차가 $\lambda$의 확률로 다리에 진입합니다. 시간 간격 $t$ 동안 다리가 무너질 확률, 즉 그 시간 동안 다리 위를 $k$대보다 많은 자동차가 지나갈 확률을 구하십시오. \newpage \section{기댓값과 분산} 값 $a_0$, $a_1$, …을 취하는 확률 변수 $X$의 기댓값은 다음과 같이 정의합니다.
$$ E[X] = a_0 P(X = a_0) + a_1 P(X = a_1) + ... = \sum_{x} x p_X(x) $$ X가 셀 수 없이 많은 값을 가지는 경우(예를 들어, 구간 $[0, 1]$에서의 균등분포), 기댓값은 함수 $x$에 밀도를 곱한 것의 적분으로 정의됩니다(적분이란 이 함수의 그래프 아래 넓이라는 것만 이해하면 충분합니다): $$ E[X] = \int\limits_{-\infty}^{\infty} x \rho (x) dx $$분산은 $D[X] = E[(X-E[X])^2]$로 정의되며, 이는 확률 변수가 그 기댓값에서 벗어난 편차의 제곱의 평균입니다.
일상적인 의미에서 기댓값은 — 확률 변수의 평균값입니다. 즉, 독립적이고 동일한 분포를 따르는 확률 변수를 여러 개 취하면, 그 평균은 실제로 기댓값에 수렴하게 됩니다(예를 들어 물리학에서 여러 번 실험을 하고 답을 평균 내는 것도 바로 이 때문입니다).
일상적인 의미에서 분산은 확률 변수가 얼마나 잡음이 많은지를 나타냅니다.
확률론에서 가장 중요한 것은 기댓값이 선형이라는 점입니다.
\begin{align*} E[X+Y] & = \sum_{x, y} (x+y) p(x, y) \ & = \sum_{x, y} x p(x, y) + \sum_{x, y} y p(x, y) \ & = \sum_x x p(x) \sum_y p(y) + \sum_y y p(y) \sum_x p(x) \ & = \sum_x x p(x) + \sum_y y p(y) \ & = E[X] + E[Y] \end{align*}
$X \perp Y$이면(이는 $X \in A$ 형태의 모든 사건이 $Y \in B$ 형태의 모든 사건과 독립이라는 뜻입니다), 곱도 기댓값 밖으로 꺼낼 수 있습니다:
$$ E[X \cdot Y] = E[X] \cdot E[Y] $$% 합, 곱, 상수배의 분산은 어떻게 됩니까?
\subsection{간단한 예제}
다음 확률 변수들의 기댓값과 분산을 구하십시오.
a) $X = 1$
b) $X = \begin{cases} 0, & p \ 1, & 1-p \end{cases} $
c) $X \sim U[0, 1]$ ($X$는 구간 $[0, 1]$에서 균등 분포를 따릅니다)
d) 문제 4.2의 확률변수(기하분포) [10-11학년은 직접 구해야 하며, 8-9학년은 급수의 합이 얼마인지 구글에서 찾아봐도 됩니다. 그 합을 구하려면 미분할 줄 알아야 하기 때문입니다]
\subsection{분산에 대한 간단한 공식}
$$ D[X] = E[X^2] - E[X]^2 $$임을 증명하십시오.
\subsection{지시 확률 변수로 분해하기} 주사위를 $N$번 던졌을 때, 6이 나온 횟수의 기댓값을 구하십시오.
힌트: 확률 변수 $X[$나온 6의 개수$]$는
$$ X = I_1 + ... + I_N $$로 나타낼 수 있습니다. 여기서 $I_k = \begin{cases} 1, & $на k-м кубике выпало $ 6 \ 0, & $иначе$ \end{cases} $입니다. 힌트 2: 그다음 기댓값의 선형성을 사용하십시오.
\subsection{무작위 그래프*} $N$개의 정점을 잡고, 서로 다른 정점의 각 쌍을 확률 $0.5$로 연결했습니다. 다음을 구하십시오.
a) 간선 수의 기댓값
b) 삼각형 개수의 기댓값
\subsection{랜덤 그래프 - 2*} $N$개의 정점을 잡고, 서로 다른 정점의 각 쌍을 확률 $0.5$로 연결했습니다. 다음을 구하십시오.
a) 간선 수의 분산
b) 삼각형 개수의 분산
\newpage \section{정규 분포} % 「직관적인」 증명을 알고 계십니까? % 무엇의 증명입니까? 중심극한정리입니다 % 안 해도 되지 않겠습니까? 다음번에 하면 어떻겠습니까? % 그래도 어떻게든 그것이 옳다는 것을 납득시켜야 합니다 % 거기서 선거와 여론 조사에 대해 이야기합시다 % 제 생각에는 이것은 언급만 하고 증명하지 않아도 됩니다
% 참고로, http://sereja.me/a/pollard 를 확인해 보십시오
%몬테카를로 방법과 그 상대 오차.
훌륭한 정규분포 $N(a, \sigma^2)$가 있습니다 — 이것은 무시무시한 밀도
$$ \rho(x) = \frac{1}{\sigma\sqrt{2\pi}}e^{-{\frac{(x-a)^2}{2\sigma^2}}} $$를 가진 분포입니다. 게다가 그 기댓값은 $a$이고, 분산은 $\sigma^2$입니다.
이 분포가 훌륭한 점은, 임의의 한 분포 $X$를 따르는 독립 확률 변수를 많이 취하면 그 산술 평균의 분포가 대략 $N(E[X], \frac{D[X]}{N})$와 같아진다는 것입니다. 이 사실(물론 더 엄밀한 형태)을 중심 극한 정리라고 합니다.
\subsection{주사위} 다음 각 경우에 N개의 주사위 눈의 합이 어떻게 분포하는지 (밀도 그래프 또는 단순히 밀도 값으로) 그려 보십시오.
a) N = 1
b) N = 2
c) N = 3
d*) N = 5
e*) N = 100
힌트: 5와 100의 경우 프로그램을 작성하여 히스토그램을 그려 볼 수 있습니다.
\subsection{정규 확률 변수의 합} 정규 분포를 따르는 두 확률 변수의 합 역시 정규 분포를 따르는 확률 변수임이 알려져 있습니다. $X \sim N(0, 1), Y \sim N(5, 4)$라고 합시다. 확률 변수 $2X + Y$의 매개변수(기댓값과 분산)를 구하십시오. \newpage \section{알고리즘 실행 시간 추정 및 그 밖의 것들}
무작위 알고리즘에 대해 우리는 “평균적으로 O(n)에 동작한다"라는 말을 매우 자주 했습니다. 이는 연산 횟수 — 가 확률 변수이며, 그 기댓값 — 이 O(n)이라는 뜻입니다.
\subsection{Quicksort} 피벗을 무작위로 선택하는 Quicksort가 임의의 고정된 순열에 대해 평균 $O(n\log{n})$번의 비교로 동작함을 증명하십시오.
힌트 1: 비교 횟수를 단순한 확률 변수들로 분해하고 기댓값의 선형성을 이용하십시오.
힌트 2: 다음 보조정리를 증명하십시오 — 두 수 $x_i$와 $x_j$는 (정렬된 배열에서) 그 사이에 있는 모든 원소 중 처음으로 피벗으로 선택된 원소가 이 두 수 중 하나인 경우에만 비교됩니다.
\subsection{무작위 이진 트리의 높이*} 무작위 이진 트리(예를 들어 트립이 이에 해당합니다), 즉 정점의 우선순위가 동일한 분포를 따르고 우선순위에 대해 트리가 힙을 이루는 트리에서 정점 깊이의 기댓값을 구하십시오.
힌트: 다음 보조정리를 증명하십시오 — 임의의 $i\neq k$에 대해, $x_i$가 $x_k$의 조상일 필요충분조건은 $x_i$가 $x_{min(i, k)}$, $x_{min(i, k) + 1} … x_{max(i, k)} $ 중에서 가장 높은 우선순위를 갖는 것입니다.
\subsection{에라토스테네스*} 수 $k$가 소수일 확률이 $\frac{1}{\ln k}$이라고 가정하고, 일반적인 에라토스테네스의 체가 $O(n \log \log n)$에 동작함을 보이십시오.
% \subsection{골드바흐 추측} % 소수가 앞 문제에서와 같이 분포한다고 가정하고, 골드바흐 추측을 «증명»하십시오.
\subsection{트리 파괴*} 루트가 있는 트리가 주어집니다. 매 반복마다 (남아 있는 모든 정점 중에서 같은 확률로) 정점 하나를 선택하고, 그 정점에 해당하는 서브트리 전체를 삭제합니다. 이 과정이 평균적으로 몇 번의 이동 동안 계속되는지, 즉 트리의 루트가 삭제되는 반복 번호의 기댓값을 구하십시오.
\subsection{대안적인 트립} 두 트리를 병합할 때 우선순위가 더 큰 정점을 루트로 삼아 매다는 대신, 다음과 같이 매단다고 합시다:
\begin{itemize} \item За левое с вероятностью $\frac{L}{L+R}$. \item За правое с вероятностью $\frac{R}{L+R}$. \end{itemize}
여기서 $L$과 $R$은 각 트리의 크기입니다.
각 정점이 여전히 같은 확률로 트리의 루트가 됨을 보이십시오.
% \section{확률 과정}
% \subsection{0에서 1까지*}
% 다음과 같은 코드가 주어집니다:
% % 무언가 작동하지 않습니다. 어떻게 고칩니까? % \begin{lstlisting}[language=Python] % x = 0 % while x < 1: % x += random() % \end{lstlisting}
% x의 기댓값을 구해야 합니다.
% (파이썬의 random은 0부터 1 사이의 임의의 실수를 반환합니다.)
% \subsection{술꾼} % 술꾼이 절벽 가장자리에 서 있습니다(절벽은 왼쪽에 있습니다). 그는 확률 $p$로 오른쪽으로 한 걸음 가고, 확률 $p-1$로 왼쪽으로 한 걸음 갑니다. 술꾼이 언젠가 떨어질 확률을 구하십시오.
% \subsection{카지노*} % 여러분은 $A$달러를 가지고 시작하여 도박을 하며, 매번 1달러를 거는데, 이 베팅은 $p < \frac{1}{2}$의 확률로 2달러를 돌려줍니다. 유니버숨 캠프의 한 기수 참가비를 내기 위해 여러분은 언젠가 $B > A$달러를 모으고자 하며, 그렇게 되는 즉시 게임을 그만둡니다. 여러분이 돈을 가지고 떠날 확률을 구하십시오. 여러분은 $B$달러를 가지고 떠나거나, 아니면 파산합니다. 어쩌면 끝없이 게임을 해야 할 수도 있습니다.
확률 밀도 함수
어떤 확률 변수 $X$가 있다고 합시다. $X$의 확률 밀도란 사건 $X=x$가 일어날 상대적 확률(즉, 다른 모든 가능한 사건에 대한 상대적 확률)을 나타내는 함수 $p(x)$를 말합니다. 예를 들어, 근원 사건의 집합 $\Omega$가 유한한 확률 변수의 경우 $p(x)=P(X=x)$입니다(여기서 $P(A)$는 사건 $A$가 일어날 확률입니다). 일반적으로 확률 밀도 함수는 1로 정규화되어 있다고 가정합니다(즉, 그래프 아래의 넓이가 1입니다). 수치 확률 변수의 분포 함수 $F(x)$란 $X$가 반직선 $(-\infty;,x]$에 속할 확률(또는 $\int_{-\infty}^{x}p(x),dx$)을 말합니다.
기댓값
밀도 함수가 $p(x)$인 확률 수치 변수 $X$가 있다고 가정합시다. 그러면 확률 변수의 기댓값은 가능한 모든 결과 $A$에 대한 $P(A) \cdot A$의 합과 같습니다. TODO
분산
분포를 가장 잘 설명하는 두 수는 무엇입니까?
정규 분포
중심 극한 정리가 이처럼 거창한 이름을 얻은 데에는 충분한 이유가 있습니다.
이 정리에 따르면 각 항에 대해 기댓값과 분산이라는 단 두 개의 수만 알면 충분합니다.
$$ f(x) = \frac{1}{2\sqrt{\pi}} e^{-\frac{(x-\mu)^2}{\sigma^2}} $$이것을 증명하는 것은 매우 어렵습니다. 강력한 정리들을 인용하더라도 증명은 여러 페이지에 걸칩니다. 보통 이 증명은 2학년 중반에 배웁니다.
이것이 분포라는 것, 즉 다음이 성립한다는 것을 증명하는 것조차 어렵습니다.
응용
어떤 나라에 대통령 후보가 두 명 있다고 합시다. 이들을 푸틴과 나발니라고 부르겠습니다.
무작위로 고른 유권자 1000명에게 이진 질문을 했더니, 그중 510명이 푸틴에게 투표하겠다고 답했습니다. 그가 이길 확률은 얼마입니까? 정리에 따르면 득표수는
선형 점화식
다음 문제들을 풀기 위해서는 다음 사실을 이용해야 합니다:
…
증명은 생략합니다.
특히, 이렇게 하면 피보나치 수에 대한 공식을 얻을 수 있습니다.
$$ f_n = \ldots $$이 모든 무리수와 거듭제곱이 서로 약분되어 결국 정수가 나오리라고 누가 생각이나 했겠습니까?..
고전 문제
생일 역설.
이것은 사실 매우 자주 사용되는 결과입니다. 이를 통해 해시 충돌 확률을 계산할 수 있으며, 소수의 분포에 대한 (상당히 타당한) 가정을 사용하는 많은 정수론 알고리즘에서도 사용됩니다.
술주정꾼. 한 사람이 절벽 가장자리에 서 있으며, 확률 p로 절벽 쪽으로 한 걸음 나아갑니다. 그가 언젠가 절벽으로 떨어질 확률은 얼마입니까?
TODO: 미적 즐거움, 도박의 짜릿함, 그리고 카지노에 가는 의미에 관한 이야기. 카지노. 우리는 1000$를 들고 카지노에 와서 다음과 같이 시간을 보냅니다. 파산하거나 1100$를 딸 때까지 1$씩 겁니다. 우리가 돈을 가지고 떠날 확률은 얼마입니까?
생일 역설
23명 이상으로 이루어진 집단에서 적어도 두 사람의 생일이 같을 확률은 50%를 넘습니다.
더 일반적인 명제는 다음과 같습니다: 어떤 두 수가 일치하려면 멀티셋에 1부터 n까지의 무작위 수를 $\Theta(\sqrt{n})$개 추가해야 합니다.
첫 번째 증명 (해석학 애호가를 위한 증명입니다). $f(n, d)$를 $n$명으로 이루어진 그룹에서 생일이 같은 사람이 아무도 없을 확률이라고 합시다. 생일은 $1$부터 $d$까지의 구간에서 독립적이고 균등하게 분포되어 있다고 가정하겠습니다.
$$ f(n, d) = (1-\frac{1}{d}) \times (1-\frac{2}{d}) \times ... \times (1-\frac{n-1}{d}) $$ $f$를 추정해 봅시다: $$ \begin{aligned} e^x & = 1 + x + \frac{x^2}{2!} + \ldots & \text{(ряд Тейлора для экспоненты)} \\ & \simeq 1 + x & \text{(аппроксимация для $|x| \ll 1$)} \\ e^{-\frac{n}{d}} & \simeq 1 - \frac{n}{d} & \text{(подставим $\frac{n}{d} \ll 1$)} \\ f(n, d) & \simeq e^{-\frac{1}{d}} \times e^{-\frac{2}{d}} \times \ldots \times e^{-\frac{n-1}{d}} & \\ & = e^{-\frac{n(n-1)}{2d}} & \\ & \simeq e^{-\frac{n^2}{2d}} & \\ \end{aligned} $$마지막 식으로부터 확률 $\frac{1}{2}$에 $n \approx \sqrt{d}$일 때 도달하며, 이 지점에서 확률이 매우 빠르게 변한다는 것을 어느 정도 알 수 있습니다.
두 번째 증명 (확률론 애호가를 위한 증명). 사람 쌍 $(i, j)$마다 하나씩, 총 $\frac{n(n-1)}{2}$개의 지시 변수를 도입합시다. 각 지시 변수는 두 사람의 생일이 같으면 1이 됩니다. 각 지시 변수의 기댓값과 확률은 $\frac{1}{d}$입니다.
일치하는 생일의 수를 $X$라고 합시다. 그 기댓값은 이 지시 변수들의 기댓값의 합, 즉 $\frac{n (n-1)}{2} \cdot \frac{1}{d}$와 같습니다.
이로부터 $d = \Theta(n^2)$이면 기댓값이 상수가 되고, $d$가 점근적으로 더 크거나 더 작으면 $X$는 각각 0 또는 무한대로 수렴한다는 것을 알 수 있습니다.
참고: 엄밀히 말하면, 이로부터 확률 역시 0과 1로 수렴한다는 사실이 바로 따라 나오지는 않습니다.
보너스: «메타 문제»
임의의 문자열이 주어지며, 이 문자열로부터 문제 출제자만 아는 방식으로 yes/no 답이 생성됩니다. 문제에는 테스트가 100개 있습니다. 여러분에게는 풀이를 제출할 기회가 20번 있습니다. 피드백으로는 각 테스트에 대한 판정 결과를 확인할 수 있습니다. 판정은 OK(답이 일치함)와 WA 두 가지뿐입니다. 0으로 나누기, 테라바이트 단위의 메모리 할당 등의 시도 역시 WA로 간주됩니다.
문제를 «푸십시오».
최대 가능도 원리
엔트로피
엔트로피란 이론적으로 메시지를 압축할 수 있는 최소 비트 수를 말합니다. 이 값이 중요한 이유는, 실제로 이 값을 계산할 수 있다면 그에 해당하는 압축률을 실제로 달성할 수 있기 때문입니다.
잡음이 있는 채널.
1TB의 데이터와 중국산 1테라바이트 디스크 두 개가 있다고 합시다. 각 디스크에는 그만큼의 데이터를 기록할 수 있지만, 각 비트는 10%의 확률로 반대 값으로 기록됩니다. 데이터를 한 번에 손실 없이 저장해야 합니다. 손실이 전혀 없어야 합니다.
게다가 이는 거의 빠듯하게 이루어집니다.
알고리즘 연구자를 위한 확률론
여러분은 마침내 트립이 왜 로그 시간에 동작하는지, 퀵 정렬이 왜 빠른지, 해시에는 어떤 모듈러를 선택해야 하는지, 몬테카를로에는 샘플을 몇 개 뽑아야 하는지 등을 알게 될 것입니다.
다음 코드는 분포를 생성하고 그래프를 그리기 위한 것이니 신경 쓰지 마십시오.
공리 체계
대학에서는 확률론을 무언가 유용한 내용으로 넘어가기 전에 매우 오랫동안 공리화합니다. 이제 그 이유를 설명하겠습니다.
원에 내접하는 정삼각형을 생각해 봅시다. 원의 현을 무작위로 하나 선택합니다. 선택한 현이 삼각형의 변보다 길 확률은 얼마입니까?
그럴듯해 보이지만 모두 서로 다른 답을 내놓는, 이 문제를 푸는 방법을 적어도 세 가지는 생각해 낼 수 있다는 사실이 밝혀졌습니다.
원 위에서 임의로 두 점을 고르고, 그 두 점을 지나는 현을 긋습니다. 구하려는 확률을 계산하기 위해, 삼각형의 꼭짓점 중 하나가 현의 한 끝점과 일치하도록 삼각형이 회전되어 있다고 생각해 봅시다. 현의 다른 끝점이 삼각형의 나머지 두 꼭짓점 사이의 호 위에 있으면, 현의 길이가 삼각형의 변보다 길다는 점에 주목하십시오. 이 호의 길이는 원 둘레의 3분의 1이므로, 구하려는 확률은 $\frac13$입니다.
원의 반지름 하나를 고정하고, 그 반지름 위의 점 하나를 무작위로 고릅니다. 고정한 반지름에 수직이면서 고른 점을 지나는 현을 그립니다. 구하려는 확률을 계산하기 위해, 삼각형의 한 변이 고정한 반지름에 수직이 되도록 삼각형을 회전시켰다고 생각합시다. 현의 중점이 삼각형과 고정한 반지름의 교점보다 원의 중심에 더 가까우면, 현은 삼각형의 변보다 깁니다. 삼각형의 변은 반지름을 이등분하므로, 삼각형의 변보다 긴 현을 고를 확률은 $\frac12$입니다.
원 내부의 임의의 점을 무작위로 선택하고, 선택한 점을 중점으로 하는 현을 그립시다. 선택한 점이 삼각형에 내접하는 원의 내부에 있으면, 현은 정삼각형의 변보다 깁니다. 내접원의 넓이는 큰 원 넓이의 $\frac14$이므로, 구하는 확률은 $\frac14$입니다.
보았듯이, 답은 ‘임의의 현’의 형식적 정의에 직접적으로 좌우됩니다.
수학의 역사에서 이처럼 모순을 낳는 역설이 나타날 때마다 수학자들은 당황하여 모든 것을 형식화하고 공리화하기 시작합니다. 이렇게 해서 확률론이 생겨났습니다(주의: «ти»가 아니라 «тей»입니다).
이제 정의 자체로 넘어갑시다:
함수 $X : \Omega \to R$를 확률 변수라고 부르겠습니다. 확률 변수는 각 근원 사건에 어떤 수를 대응시킵니다.
분포
기하 분포.
생일 역설
$f(n, d)$를 $n$명으로 이루어진 그룹에서 생일이 같은 사람이 아무도 없을 확률이라고 합시다. 생일은 $1$부터 $d$까지의 범위에서 독립적이고 균등하게 분포한다고 가정하겠습니다.
$$ f(n, d) = (1-\frac{1}{d}) \times (1-\frac{2}{d}) \times ... \times (1-\frac{n-1}{d}) $$ $f$를 추정해 봅시다: $$ \begin{align} \begin{aligned} e^x & = 1 + x + \frac{x^2}{2!} + \ldots & \text{(ряд Тейлора для экспоненты)} \\ & \simeq 1 + x & \text{(аппроксимация для $|x| \ll 1$)} \\ e^{-\frac{n}{d}} & \simeq 1 - \frac{n}{d} & \text{(подставим $\frac{n}{d} \ll 1$)} \\ f(n, d) & \simeq e^{-\frac{1}{d}} \times e^{-\frac{2}{d}} \times \ldots \times e^{-\frac{n-1}{d}} & \\ & = e^{-\frac{n(n-1)}{2d}} & \\ & \simeq e^{-\frac{n^2}{2d}} & \\ \end{aligned} \end{align} $$기댓값
값 $x_1, x_2, \ldots$을 취하는 확률 변수 $X$의 수학적 기댓값은 다음과 같이 정의됩니다
$$ E[X] = \sum_{x \in S} p_S(x) \cdot x $$ 우리에게 가장 중요한 성질은 기댓값이 선형이라는 것입니다: $$ \begin{align*} E[X+Y] & = \sum_{x, y} (x+y) p(x, y) \\ & = \sum_{x, y} x p(x, y) + \sum_{x, y} y p(x, y) \\ & = \sum_x x p(x) \sum_y p(y) + \sum_y y p(y) \sum_x p(x) \\ & = \sum_x x p(x) + \sum_y y p(y) \\ & = E[X] + E[Y] \end{align*} $$주목하십시오: $X$와 $Y$가 어떤 것인지는 전혀 중요하지 않습니다. 어쩌면 이들은 매우 복잡하게 연관되어 있을 수도 있지만, 그것은 중요하지 않습니다. 나중에 보게 되겠지만, 이 성질은 매우 복잡한 무언가의 기댓값을 계산하는 일을 크게 단순화해 줍니다.
또한, 특히 기댓값에는 상수를 곱할 수 있습니다.
이제 실전 문제로 넘어갈 수 있습니다.
기하 분포
페탸가 동전을 던집니다. 확률 $p$로 앞면이 나오면 던지기를 멈추고, 확률 $1-p$로 뒷면이 나오면 한 번 더 던집니다. $X$를 던진 횟수라고 합시다. $\rho_X(x)$와 $F_X(x)$를 구하십시오.
순열의 고정점
저자가 МФТИ(모스크바 물리공과대학)에서 첫 영어 수업에 들어갔을 때, 강사는 서로를 알아 가기 위한 다음과 같은 게임을 진행했습니다. 모든 학생을 두 팀으로 나눈 것입니다. 각 팀에서는 자기 팀원들에 관한 사실을 문제로 냅니다. 누군가는 곡예사가 되기를 꿈꿨고, 누군가는 애니메이션을 본다는 식입니다. 상대 팀에게는 이 사실들만 알려 주었고, 상대 팀은 어떤 사실이 누구의 것인지 맞혀야 했습니다. 상대 팀에 관한 사실을 더 많이 맞힌 팀이 이깁니다. 우리는 11명이었는데, 이는 소수여서 결코 같은 크기의 팀으로 나눌 수 없었고, 그래서 한 팀은 5명, 다른 팀은 6명이었습니다. 저자는 궁금해졌습니다. 심리적인 측면을 모두 무시하고 모든 것을 무작위로 한다면, 어느 팀이 이길 확률이 더 높을까요?
다만 정답을 맞힌 질문 수의 기댓값만으로는 어느 팀이 유리한지, 그리고 그 유리함이 어느 정도인지 알아내는 데 그다지 도움이 되지 않는다는 점에 유의해야 합니다.
트립의 높이
트리의 높이. 높이는 평균적으로 로그 수준입니다. 궁금한 분은 증명 비슷한 것을 살펴보셔도 되지만, 꼭 그럴 필요는 없습니다.
정점의 깊이는 부모의 개수입니다(주. 캡틴 오비어스). 지시 확률 변수를 도입합시다. $E[h] = \sum \frac{1}{k} \approx \log n $.
quicksort의 점근적 복잡도
사실 여기서도 트립의 경우와 거의 같습니다. 우리가 관심을 두는 것은 비교의 총횟수입니다. 각 원소 쌍에 대해 그 두 원소가 비교될 확률을 합산합시다.
한 쌍에 대해 이 확률을 어떻게 구할 수 있겠습니까? 정렬된 배열에 있다고 할 때 두 원소 사이에 놓이는 모든 원소를 살펴봅시다.
갑자기 조화급수가 등장하는데, 그다음은 우리가 이미 알고 있습니다.
분산
분산은 정량적 지표입니다. 이것은 학교 확률론 수업에서 들었을 법한 추상적인 개념이 아니라, 온갖 유용한 성질을 한 힙 가득 지닌, 형식적으로 정의된 값입니다.
분산은 확률 변수가 그 기댓값에서 벗어난 편차의 제곱의 평균으로 정의됩니다:
$$ D[X] = E[(X − E[X])^2] $$ 기댓값 안의 제곱을 전개하면 다음과 같은 다른 공식으로 더 쉽게 계산할 수 있습니다: $$ \begin{align} D[X] &= E[(X − E[X])^2] \\ &= E[X^2 - 2 \cdot X \cdot E[X] + E[X]^2] \\ &= E[X^2] - E [\underbrace{2 \cdot E[X]}_{const} \cdot X ] + E[E[X]^2] \\ &= E[X^2] - 2 E[X]^2 + E[X]^2 \\ &= E[X^2] - E[X]^2 \end{align} $$이 공식은 여러 가지 성질을 유도하는 데 사용할 것입니다.
분산에는 매우 멋진 성질이 많이 있습니다.
$$ D[k X] = E[k^2 X^2] - E[k X]^2 = k^2 (E[X^2] - E[X]^2) = k^2 D[X] $$ $X$와 $Y$는 서로 독립이라고 가정합니다. $$ \begin{align} D[X + Y] &= E[(X+Y)^2] - E[X+Y]^2 \\ &= E[X^2 + X Y + Y^2] - (E[X] + E[Y])^2 \\ &= E[X^2] + E[Y^2] - E[X]^2 - E[Y]^2 \\ &= D[X] + D[Y] \end{align} $$기댓값의 성질과의 중요한 차이점은, 분산을 이렇게 간단하게 계산할 수 있는 것은 독립인 확률 변수에 대해서뿐이라는 것입니다.
큰 수의 법칙
큰 수의 법칙은 동일한 실험을 여러 번 수행했을 때의 결과를 설명하는 원리입니다. 이 법칙에 따르면, 고정된 분포에서 뽑은 유한 표본의 평균값은 그 분포의 기댓값에 가깝습니다.
기댓값(상수)의 표준 표기는 $\mu$(뮤)이고, 분산의 표준 표기는 $\sigma$(시그마)입니다.
$$ M_n = \frac{X_1 + \ldots + X_n}{n} $$ $$ E[M_n] = \frac1n E[X_1 + \ldots + X_n] = \mu $$ 이것은 다소 자명한 등식입니다. 이제 우리가 관심을 가지는 것은 이 등식이 실제로 얼마나 정확하게 성립하는가입니다: $$ D[M_n] = \frac{1}{n^2} D[X_1 + \ldots + X_n] = \frac{\sigma}{n} $$한편으로는 평균을 내기 때문에 $\frac{1}[n^2}$이 곱해지고, 다른 한편으로는 합산하기 때문에 $n$이 곱해집니다.
정규 분포
데이터 분석용 라이브러리에서 summary를 보여 달라고 요청하면, 대개 기댓값과 분산이라는 두 숫자를 보게 됩니다.
중심 극한 정리라는 거창한 이름이 붙은 데에는 충분한 이유가 있습니다.
이 정리에 따르면, 각 항에 대해 기댓값과 분산이라는 단 두 개의 수만 알면 충분합니다.
$$ f(x) = \frac{1}{2\sqrt{\pi}} e^{-\frac{(x-\mu)^2}{\sigma^2}} $$이것을 증명하는 것은 매우 어렵습니다. 강력한 정리들을 인용하더라도 증명은 여러 쪽에 걸칩니다. 보통 이 증명은 2학년 중반에 배웁니다.
이것이 분포라는 것, 즉 $\int_{-\inf}^\inf f(x) dx = 1$임을 증명하는 것조차 어렵습니다.
몬테카를로 방법
“여러 무작위 지점에서 값을 계산한 뒤 평균을 내 봅시다” 같은 형태의 알고리즘을 몬테카를로 방법이라고 합니다.
단위 정사각형 하나와 원 수백 개가 있다고 합시다. 정사각형 영역 중 어떤 원에도 덮이지 않는 부분의 비율을 1%의 정확도로 계산해야 합니다.
이렇게 하면 간단합니다. 무작위 점 10000개를 찍어 각 점이 «좋은» 점인지 확인한 다음, $\frac{\text{хорошие}}{\text{хорошие} + \text{плохие}}$를 답으로 출력하면 됩니다.
여기에서 제출할 수 있습니다.
해시 테이블
일반적으로 해시란 어떤 원소에 다른 어떤 원소를 대응시키는 함수입니다. 암호 분석의 관점에서는 역산하기 어려워야 하고, 알고리즘 설계자의 관점에서는 균등하게 분포된 출력값을 생성해야 합니다.
다음과 같이 할 수 있습니다. $n$개의 원소를 저장할 계획이라면 $\Theta(n)$개의 칸을 마련해야 하며, 각 칸은 실제로는 단일 연결 리스트가 됩니다.
무작위성 덕분에 각 칸에는 평균적으로 원소가 하나씩 들어가므로 이 방법은 잘 동작합니다. 하지만 이러한 해법은 상수가 큽니다.
STL의 표준 해시 테이블은 저자도 알 수 없는 이유로 매우 느리게 동작합니다. 많은 문제에서 해시 테이블은 가장 부하가 큰 자료 구조입니다. 해시 테이블은 3~5배 더 빠르게 작성할 수 있습니다.