확률

확률(Probability) - 어떤 사건이 일어날 가능성을 수치화한 것이다. 표본 공간에서 어떤 사건이 일어날 가능성이다. 0~1 사이의 값이다.

표본 공간(Sample Space) - 실험의 결과가 될 수 있는 모든 경우의 집합이다. 표본 공간이 무한히 많으면 확률은 0이다. 그래서 표본 공간이 유한하다고 가정한다.

실험(Experiment) - 모든 경우의 수에서 하나를 뽑는 절차이다.

여사건 - 어떤 사건이 일어날 확률을 알면 일어나지 않을 확률도 알 수 있다.

합사건 - 같은 표본 공간에 있는 두 사건이 일어날 확률이다.

 

조건부 확률 - 어떤 사건이 발생했을 때 또 다른 사건이 일어날 확률이다. 사건이 두 번 일어난다.

독립 사건 - 조건부 확률에서 또 다른 사건에 서로 영향을 미치지 않는 경우이다. 영향을 미치지 않으면 최적화가 가능하다.

 

기대값(Expected Value) - 어떤 실험을 무한히 했을 때 나올거라고 믿는 값이다. 보통 평균을 말한다.

확률 변수(Random Variable) - 표본 공간에서 실행한 실험의 결과를 실수로 수치화하는 함수이다.

 

확률 분포(Probability Distribution) - 각 사건이 일어날 확률이 어떻게 분포되어 있는지 알 수 있다.

이산 확률 분포(Discrete) - 확률 변수가 취할 수 있는 값이 유한개인 분포이다.

이산 균등 분포(Discrete Uniform Distribution) - 각 확률 변수의 확률이 모두 같은 값을 가지는 이산 확률 분포이다. 난수, 랜덤 수가 그 예이다.

연속 확률 분포(Continuous) - 확률 변수가 특정 구간 안의 모든 실수값인 분포이다. 확률 분포의 모든 기대값을 더하면 1이다. 즉, 그래프의 면적이 1이므로 적분을 활용해 기대값을 구할 수 있다.

 

베르누이 분포 - 이산 확률 분포의 한 종류로 어떤 실험이 오직 둘 중 하나의 결과만 가지는 것이다. 1회만 할 경우의 확률 분포로 결과는 참 또는 거짓이다.

이항 분포(Binomial Distribution) - 베르누이 시행을 여러번 실행하는 것이다. 실험 횟수가 증가할수록 연속 확률 분포에 가까워진다.

 

결정적 알고리즘(Deterministic) - 알고리즘을 실행하면 언제나 같은 결과가 나온다.

확률적 알고리즘(Probabilistic) - 실행 중에 난수를 뽑아 다음 과정을 결정하는 알고리즘이다. 무작위 알고리즘이라고도 한다. 라스베가스, 몬테카를로 알고리즘이 있다. 속도향상이 가능하다. 무작위로 뽑기 때문에 입력 데이터가 같아도 실행 시간이 다를 수 있다.

라스베가스 알고리즘 - 언제나 올바른 결과를 찾는다. 결정적 알고리즘만큼 시간이 걸릴 수 있다. 무작위 퀵 정렬이 그 예이다.

몬테카를로 알고리즘 - 언제나 결과를 찾기는 하지만 틀릴 가능성도 있다. 어떤 검사를 정해진 횟수만큼 수행한다. 한번 검사할 때마다 무작위로 검사 대상을 뽑는다. 그럼 한번 검사할 때마다 둘 중 하나의 답이 나온다. yes면 정답을 찾아서 더이상 검사를 하지 않아도 되지만 unknown이 나오면 yes일수도 no일수도 있으므로 정확히 알기 위해서는 검사를 다시 해야한다. 정해진 횟수만큼 검사를 모두 진행해도 여전히 unknown이라면 no라고 결론을 내린다. 물론 결론이 틀릴 수도 있지만 그 틀릴 확률을 줄이는 것이 핵심이다. 검사 횟수를 늘릴수록 낮아진다. 제일 문제인 부분은 실제 정답이 yes인데 검사 결론이 no일 때이다.

 

소수(Prime Number) - 자기 자신과 1로만 나머지 없이 나눠지는 수이다. 2, 3, 5, 7, 11...

합성수(Composite Number) - 소수가 아닌 수이다. 다른 소수를 곱해서 만든 수이다.