[ Open Data Structures ] - Randomisation and Probability

Randomisation and Probability

어떤 자료구조를 구현함에 있어서 앞으로 혹은 이전에 랜덤화를 채택하는 일이 있을 것(혹은 있었다)이다. 이 자료구조는 저장되는 자료나 수행되는 작업(Operation)에 대해 독립적인 무작위 선택을 차용한다. 이러한 연유로 같은 작업을 한 번 이상 수행하게 되면 각각 다른 결과를 얻게 된다. 이런 형태의 자료구조를 분석함에 있어서 우리는 이들의 Expected Running Time에 중점을 두게 될 것이다.

딱딱한 표현을 쓰자면 랜덤화 된 자료구조의 Running time은 Random Variable(랜덤 변수)이며 여기서는 그 랜덤 변수의 Expected value에 대한 공부를 하기로 한다. 셀 수 있는 집합 U 안에 있는 이산 랜덤 변수(Discrete Random Variable) X의 Expected Value(E[X], 기댓값이라고도 함)는 다음과 같은 공식으로 표현된다.

여기서 Pr{e}는 Event(사건) e가 일어날 확률을 이르는 말이다.

'Outcome' : An outcome of an experiment is any possible observation of that experiment.
'Sample Space' : The sample space of an experiment is the finest-grain, mutually exclusive, collectively exhaustive set of all possible outcomes.
'Event' : An event is a set of outcomes of an experiment.

From Probability and stochastic processes 3th edition by Roy D. Yates and David J. Goodman.

Probablity에서 outcome, sample space, event는 Set algebra에서 각각 Set, universal set, element정도로 바꿔서 사용할 수 있다. 

기댓값의 가장 중요한 성질 중 하나는 linearity of expectation이라고 불리는 것이다. 어떤 랜덤 변수 X와 Y는 다음을 만족한다.

일반화를 하면 임의의 랜덤 변수 X1, X2, X3,...,Xk에 대해서 다음이 성립한다.

Linearity of expectation은 복잡한 랜덤변수를 간단한 랜덤변수들의 합으로 표현할 수 있게 해준다. 또, 반복적으로 보게 될 유용한 기법이 하나 있는데 그것은 indicator random variables를 정의하는 것이다. 이 binary variables들은 무언가를 셀 때 유용하며 다음 예제를 통해 파악하게 될 것이다. 

예제) 동전 던지기를 한다고 가정하자. k번 던질 것이고 이때 동전이 head일 때의 Expected value를 알고 싶다. 직관적으로 답이 k/2이라고 생각은 하지만 엄밀하게 풀어보면 다음과 같다.

사실 여기서 Pr{X=i}와 두 개의 Binomial을 풀 배경지식을 요구하기는 한다. 이때, Indicator variables와 Linearity of expectation을 사용해서 풀면 위의 풀이보다 훨씬 쉽게 풀 수 있다. 1부터 k에 해당하는 각각의 i에 대해서 다음과 같이 indicator variable을 정의하면

이고

이다. 이제 랜덤 변수 X를 

라고 두면

완전히 같은 결과가 도출되었다. 조금 장황하기는 하지만 binomial이라든가 비자명한 확률을 계산할 필요가 없어진다. 더 좋은 것은, 절반에 해당하는 동전이 1/2확률로 head가 나올 것이기 때문에 정확히 절반에 해당하는 동전이 head가 나올 것이라는 직관에 정확하게 일치하는 설명을 한다.