베르누이 과정

3. 형식적 정의

베르누이 과정은 확률 공간의 언어로 형식화될 수 있다. 베르누이 과정은 집합 {0, 1}에 대한 확률 변수 ''X''를 가지는 확률 공간 $(\backslash Omega,\; Pr)$로 표현된다. 모든 $\backslash omega\; \backslash in\backslash Omega$에 대해, 확률 ''p''에서 $X\_i(\backslash omega)=1$이고, 확률 1-''p''에서 $X\_i(\backslash omega)=0$이다.^[1]

베르누이 과정을 더 엄밀하게 정의하기 위해, $2=\backslash \{H,T\backslash \}$의 가산 무한 직접곱을 고려한다. 여기서 H는 앞면, T는 뒷면을 의미한다. 일반적으로 한쪽 집합 $\backslash Omega=2^\backslash mathbb\{N\}=\backslash \{H,T\backslash \}^\backslash mathbb\{N\}$ 또는 양쪽 집합 $\backslash Omega=2^\backslash mathbb\{Z\}$을 조사한다. 이 공간에는 곱 위상이라고 하는 자연스러운 위상이 있다. 이 위상의 집합은 유한 길이의 ''H''와 ''T''의 문자열로, 나머지(무한 길이) 시퀀스는 "상관 없음"으로 간주되는 동전 던지기의 유한 시퀀스이다. 이러한 유한 시퀀스의 집합을 곱 위상에서 원통 집합이라고 한다. 이러한 모든 문자열의 집합은 시그마 대수를 형성하며, 특히 보렐 대수를 형성한다. 이 대수는 일반적으로 $(\backslash Omega,\; \backslash mathcal\{B\})$로 표기되며, 여기서 $\backslash mathcal\{B\}$의 요소는 동전 던지기의 유한 길이 시퀀스(원통 집합)이다.

만약 앞면 또는 뒷면이 나올 확률이 $\backslash \{p,1-p\backslash \}$로 주어진다면, 곱 공간에 자연스러운 측도를 정의할 수 있는데, 이는 $P=\backslash \{p,\; 1-p\backslash \}^\backslash mathbb\{N\}$으로 주어진다(또는 양방향 과정의 경우 $P=\backslash \{p,\; 1-p\backslash \}^\backslash mathbb\{Z\}$로 주어진다). 다시 말해, 이산 확률 변수 ''X''가 매개변수 ''p''를 갖는 ''베르누이 분포''를 가지고 (여기서 0 ≤ ''p'' ≤ 1), 그 확률 질량 함수는 다음과 같이 주어진다.

:$pX(1)=P(X=1)=p$ 및 $pX(0)=P(X=0)=1-p$.

이 분포를 Ber(''p'')로 표기한다.^[1]

원통 집합, 즉 시간 $1,2,\backslash cdots,n$에서 특정 동전 던지기 결과 시퀀스 $[\backslash omega\_1,\; \backslash omega\_2,\backslash cdots\backslash omega\_n]$이 주어지면, 이 특정 시퀀스를 관찰할 확률은 다음과 같다.

:$P([\backslash omega\_1,\; \backslash omega\_2,\backslash cdots\; ,\backslash omega\_n])=\; p^k\; (1-p)^\{n-k\}$

여기서 ''k''는 시퀀스에 ''H''가 나타나는 횟수이고, ''n''−''k''는 시퀀스에 ''T''가 나타나는 횟수이다. 위에는 몇 가지 다른 종류의 표기법이 있는데, 일반적인 표기법은 다음과 같다.

:$P(X\_1=x\_1,\; X\_2=x\_2,\backslash cdots,\; X\_n=x\_n)=\; p^k\; (1-p)^\{n-k\}$

여기서 각 $X\_i$는 아이버슨 괄호 표기법에서 $x\_i=[\backslash omega\_i=H]$를 갖는 이진 값 확률 변수이며, 이는 $\backslash omega\_i=H$이면 $1$이고 $\backslash omega\_i=T$이면 $0$을 의미한다. 이 확률 $P$는 일반적으로 베르누이 측도라고 한다.^[2]

결론적으로, 베르누이 과정은 위에서 정의된 확률 삼중항 $(\backslash Omega,\; \backslash mathcal\{B\},\; P)$로 주어진다.

4. 관련 확률 분포

베르누이 과정에서 파생되는 여러 확률 분포는 다음과 같다.^[1]

• 처음 ''n''번의 시행에서 성공 횟수는 이항 분포 B(''n'', ''p'')를 따른다.
• ''r''번의 성공을 얻는 데 필요한 실패 횟수는 음이항 분포 NB(''r'', ''p'')를 따른다.
• 한 번의 성공을 얻는 데 필요한 실패 횟수는 기하 분포 NB(1, ''p'')를 따르며, 이는 음이항 분포의 특수한 경우이다.

5. 큰 수의 법칙과 중심 극한 정리

큰 수의 법칙에 따르면, 베르누이 시행에서 수열의 평균 $\backslash bar\{X\}\_\{n\}:=\backslash frac\{1\}\{n\}\backslash sum\_\{i=1\}^\{n\}X\_\{i\}$는 거의 확실하게 기댓값에 접근한다. 즉, 앞면이 나올 확률($p$)에 수렴하지 않는 사건은 확률이 0이다. 각 시행의 기댓값은 다음과 같다.

:$\backslash mathbb\{E\}[X\_i]=\backslash mathbb\{P\}([X\_i=1])=p,$

''n''번의 베르누이 시행에서 ''k''번 성공할 확률은 이항 분포로 주어지며, 다음과 같이 나타낼 수 있다.

:$N(k,n)\; =\; \{n\; \backslash choose\; k\}=\backslash frac\{n!\}\{k!\; (n-k)!\}$

:$\backslash mathbb\{P\}([S\_n=k])\; =\; \{n\backslash choose\; k\}\; p^k\; (1-p)^\{n-k\}\; ,$

여기서 $S\_n=\backslash sum\_\{i=1\}^\{n\}X\_i$이다.

스털링 근사를 사용하여 팩토리얼을 근사하고 위의 식에 대입하면 정규 분포를 얻는다. 이것은 중심 극한 정리의 가장 간단한 예시이다.

큰 수의 법칙과 중심 극한 정리를 조합하면 점근적 등분할 속성이 도출된다. 베르누이 과정에서 발생하는 가능한 무한히 긴 문자열 집합은 확률 1로 발생하는 문자열과 확률 0으로 발생하는 문자열로 분할된다. 이 분할은 콜모고로프 0-1 법칙이라고 한다.

이 집합의 크기는 베르누이 과정의 엔트로피와 관련이 있다. 길이 ''n''인 모든 문자열 집합의 크기는 $2^n$이고, 이 중 특정 하위 집합의 크기는 $H\backslash le\; 1$에 대해 $2^\{nH\}$이다. 스털링 근사를 사용하여 엔트로피를 계산하면 다음과 같다.

:$H=-p\backslash log\_2\; p\; -\; (1-p)\backslash log\_2(1-p)$

이 값은 베르누이 과정의 베르누이 엔트로피이다.

6. 에르고딕 시스템

베르누이 과정은 여러 가지 방식으로 에르고딕 시스템의 예시이자 특히 측도 보존 역학계의 예시로서, 역학계로 이해될 수 있다. 한 가지 방법은 시프트 공간으로, 다른 방법은 오도미터로 이해하는 것이다.

7. 베르누이 수열

베르누이 과정에서 각 $\omega$에 대해 $X_n(\omega) = 1$인 정수 $n$의 수열을 베르누이 수열이라고 한다.^[1] 예를 들어, $x$가 동전 던지기 시퀀스를 나타낸다면, 관련된 베르누이 수열은 동전 던지기 결과가 앞면인 자연수 또는 시간 지점의 목록이다. 이와 같이 정의된 베르누이 수열 $\mathbb{Z}^x$는 인덱스 집합인 자연수 $\mathbb{N}$의 무작위 부분 집합이다. 대부분의 베르누이 수열 $\mathbb{Z}^x$는 에르고딕 수열이다.

8. 무작위성 추출

어떤 베르누이 과정에서든, 폰 노이만 추출기를 통해 ''p'' = 1/2인 베르누이 과정을 도출할 수 있으며, 이는 균등한 무작위성을 추출한다.^[5]

입력 스트림을 0과 1의 시퀀스로 나타내고, 연속된 비트의 겹치지 않는 쌍으로 묶는다. (예: (11)(00)(10)...) 그런 다음 각 쌍에 대해 다음과 같이 처리한다.

• 비트가 같으면 버린다.
• 비트가 같지 않으면 첫 번째 비트를 출력한다.

예를 들어, 8비트 입력 스트림 ''10011011''은 ''(10)(01)(10)(11)''로 묶인다. 이 쌍들은 위의 표에 따라 (1)(0)(1)() = ''101''로 변환된다.

출력 스트림에서 0과 1은 동일한 확률을 가지며, 이는 원본에서 10과 01이 동일한 확률 ''p''(1−''p'') = (1−''p'')''p''를 갖기 때문이다. 이러한 균일한 무작위성 추출은 입력이 독립적일 필요는 없으며, 상관관계가 없어야(uncorrelated) 한다. 즉, 비트의 모든 교환 가능한 시퀀스에 대해 작동한다.

폰 노이만 추출기는 두 개의 입력 비트를 사용하여 0 또는 1개의 출력 비트를 생성하므로 출력은 입력보다 최소 2배 짧다. 평균적으로 입력 쌍의 ''p''² + (1 − ''p'')² 비율(00 및 11)을 버리는데, 이는 ''p''가 0 또는 1에 가까울 때 1에 가깝고, ''p'' = 1/2일 때 1/4로 최소화된다. (''p'' = 1/2인 경우, 출력 스트림은 평균적으로 입력 스트림 길이의 1/4이다.)

폰 노이만 추출기의 효율성을 개선하기 위해 알고리즘을 입력 데이터에 반복 적용할 수 있다. 이를 통해 출력을 "엔트로피 경계에 임의로 근접"하게 만들 수 있다.^[5]

1992년 유발 페레스가 반복된 폰 노이만 알고리즘(고급 다단계 전략, AMLS)을 소개했다.^[5] 이 알고리즘은 재귀적으로 작동하며, 폐기되지 않은 시퀀스와 폐기된 쌍의 값(00은 0, 11은 1) 두 소스에서 "낭비된 무작위성"을 재활용한다.

입력 시퀀스에서 비트를 쌍으로 소비하여 출력을 생성하고, 두 개의 새로운 시퀀스를 생성한다. 입력의 길이가 홀수이면 마지막 비트는 폐기된다. 그런 다음 알고리즘은 입력이 비어 있을 때까지 두 개의 새로운 시퀀스 각각에 재귀적으로 적용된다.

예를 들어, 입력 스트림 ''11001011101110''은 다음과 같이 처리된다.

최종 출력은 ''1111000111''로, 14비트 입력에서 10비트 출력이 생성된다. 이는 폰 노이만 알고리즘만 사용한 3비트보다 개선된 결과이다. 또한, 비트 쌍당 2비트의 상수 출력을 통해 타이밍 공격에 저항하는 고정 시간 구현이 가능하다.

2016년에는 Sequence2 채널이 많은 처리량을 제공하지 않는다는 점을 바탕으로 개선된 알고리즘이 제시되었다.^[7]

9. 베르누이 맵

각 시행이 두 값 중 하나를 취할 때, 시행의 열은 실수를 이진법으로 나타낸 것으로 볼 수 있다.^[3] 확률 ''p''가 1/2이면, 모든 이진 수열이 동일한 확률로 생성되며, 베르누이 과정의 완전 가법족의 측도는 단위 구간에서의 균등 측도와 등가이다. 즉, 이들 실수는 단위 구간 위에 균등하게 분포한다.

시프트 연산자 ''T''는 각 확률 변수의 다음 확률 변수를 제공한다.

:$TX\_i=X\_\{i+1\}$

이는 다음의 베르누이 맵으로 주어진다.

:$b(z)=2z-\backslash lfloor\; 2z\; \backslash rfloor$

여기서 $z\backslash in[0,1]$는 측정 열을 나타내고, $\backslash lfloor\; z\; \backslash rfloor$는 바닥 함수 (즉, ''z''를 넘지 않는 최대 정수)를 나타낸다. 베르누이 맵은 ''z''를 이진수 표현으로 보았을 때 소수점 이하에 해당한다.

베르누이 맵은 결정적 카오스의 정확한 가해 모델이다. 베르누이 맵의 전송 연산자는 가해적이다. 그 고유값은 1/2의 배수이며, 고유 함수는 베르누이 다항식이다.^[3][4]

10. 베르누이 계

베르누이 계열이라고 부른다.

참조

_[1] 서적 A modern introduction to probability and statistics
_[2] 서적 Probability Theory Springer-Verlag
_[3] 논문 "''r''-adic one-dimensional maps and the Euler summation formula"
_[4] 서적 Fully Chaotic Maps and Broken Time Symmetry Kluwer Academic Publishers
_[5] 간행물 Iterating Von Neumann's Procedure for Extracting Random Bits 1992-03
_[6] 웹사이트 Tossing a Biased Coin http://www.eecs.harv[...] eecs.harvard.edu 2018-07-28
_[7] 간행물 Iterating Von Neumann's post-processing under hardware constraints https://www.esat.kul[...] 2016-05-03