확률과 통계학에서, 베르누이 과정(Bernoulli process)은, 야콥 베르누이(Jacob Bernoulli)의 이름을 따서 지어졌으며, 이진 확률 변수(random variable)의 유한 또는 무한 수열이므로, 그것은 정식적으로 0과 1의 오직 두 가지 값을 취하는 이산-시간 확률적 과정(discrete-time stochastic process)입니다. 구성 요소 베르누이 변수(Bernoulli variables) Xi는 동일하게 분포되고 독립적입니다. 무미건조하게, 베르누이 과정은 아마도 불공정 동전을 갖는 (하지만 일관된 불공정을 갖는) 반복된 동전 던지기입니다. 수열에서 모든 각 변수 \(X_i\)는 베르누이 시행(Bernoulli trial) 또는 실험과 결합됩니다. 그들 모두는 같은 베르누이 분포(Bernoulli distribution)를 가집니다. 베르누이 과정에 대해 말할 수 있는 것의 대부분은 역시 (육면체 주사위에 대한 과정과 같은) 두 가지 많은 결과로 일반화될 수 있습니다; 이 일반화는 베르누이 스킴(Bernoulli scheme)으로 알려져 있습니다.
오직 제한된 베르누이 시행의 표본이 주어지면, 과정을 결정하는 문제는 동전이 공정한 지를 검사하는 문제라고 불릴 수 있습니다.
Definition
베르누이 과정(Bernoulli process)은 다음임을 만족하는 독립(independent) 확률 변수(random variables) \(X_1, X_2, X_3, ...\)의 유한 또는 무한 수열입니다:
- 각 i에 대해, \(X_i\)의 값은 0 또는 1 중 하나입니다;
- i의 모든 값에 대해, \(X_i=1\)일 확률은 같습니다.
다시 말해서, 베르누이 과정은 독립적인 동일하게 분포된(independent identically distributed) 베르누이 시행(Bernoulli trials)의 수열입니다.
시행의 독립성은 그 과정이 기억-없음(memoryless)임을 의미합니다. 확률 p가 알려진 것으로 주어지면, 과거 결과는 미래 결과에 대한 정보를 제공하지 않습니다. (만약 p가 알려져 있지 않으면, 어쨌든, 과거는 p에 대한 추론을 통해 간접적으로 미래를 알려줍니다.)
만약 그 과정이 무한하다면, 어떤 점에서든 미래 시행은 전체 과정과 동일한 베르누이 과정, 새롭게-시작 속성을 구성합니다.
Interpretation
각 \(X_i=1\)의 두 가지 가능한 값은 종종 "성공"과 "실패"라고 불립니다. 따라서, 숫자 0 또는 1로 표현될 때, 결과는 i번째 "시행"의 성공의 횟수라고 불릴 수 있습니다.
값의 두 개의 다른 공통적인 해석은 "참" 또는 "거짓"과 "예" 또는 "아니오"입니다. 두 값의 임의의 해석 아래에서, 개별 변수 \(X_i=1\)는 매개변수 p를 갖는 베르누이 시행(Bernoulli trials)이라고 불릴 수 있습니다.
많은 응용에서, 지수 i가 증가함에 따라 시행 사이에 시간이 경과합니다. 사실상, 시행 \(X_1,X_2, ..., X_i,...\)는 "시점" 1, 2, ..., i, ...에서 발생합니다. 시간의 경과와 결합된 "과거"와 "미래"의 개념은, 어쨌든, 필요하지 않습니다. 가장 일반적으로, 과정에서 임의의 \(X_i\)와 \(X_j\)는 유한한 경우, {1, 2, ..., n}, 또는, 무한한 경우, {1, 2, 3, ...}에 의해 인덱스된 확률 변수의 집합에서 단순히 두 개입니다.
보통 1과 0으로 인코딩되는, 종종 "성공"과 "실패"라고 참조되는, 오직 두 가지 가능한 결과를 갖는 하나의 실험은 베르누이 분포(Bernoulli distribution)로 모델링될 수 있습니다. 베르누이 외에 여러 확률 변수와 확률 분포는 베르누이 과정에서 다음과 같은 도출될 수 있습니다:
- 처음 n번 시행에서 성공한 횟수, 이는 이항 분포(binomial distribution) B(n, p)를 가집니다.
- r번 성공하는 데 필요한 실패 횟수, 이는 음의 이항 분포(negative binomial distribution) NB(r, p)를 가집니다.
- 한 번 성공하는 데 필요한 실패 횟수, 이는 기하 분포(geometric distribution) NB(1, p), 음의 이항 분포의 특수한 경우를 가집니다.
음의 이항 변수는 무작위 대기 시간(waiting times)으로 해석될 수 있습니다.
Formal definition
베르누이 과정은 앞면 또는 뒷면의 값을 취할 수 있는 확률 변수의 독립적 실현의 무작위 순서로 확률 공간(probability spaces)의 언어로 형식화될 수 있습니다. 개별 값에 대해 상태 공간은 \(2=\{H,T\} \)에 의해 표시됩니다.
Borel algebra
\(2=\{H,T\}\)의 복사본의 셀-수-있는 무한(countably infinite) 직접 곱(direct product)을 생각해 보십시오. 한-측 집합 \(\Omega=2^\mathbb{N}=\{H,T\}^\mathbb{N}\) 또는 두-측 집합 \(\Omega=2^\mathbb{Z}\)를 검사하는 것이 공통적입니다. 이 공간 위에, 곱 토폴로지(product topology)라고 불리는, 자연스러운 토폴로지(topology)가 있습니다. 그 토폴로지에서 집합은 유한한 동전 던짐의 순서열, 즉, H와 T의 유한-길이 문자열이며 (H는 앞면을 나타내고 T는 뒷면을 나타냄), 나머지 (무한하게 긴) 순서열은 "상관하지 않음"으로 취합니다. 이들 유한 순서열의 집합은 곱 토폴로지에서 원기둥 집합(cylinder sets)이라고 참조됩니다. 모든 그러한 문자열의 집합은 시그마 대수(sigma algebra), 특히, 보렐 대수(Borel algebra)를 형성합니다. 이 대수는 그런-다음 공통적으로 \((\Omega, \mathcal{B})\)로 작성되며, 여기서 \(\mathcal{B}\)의 원소는 동전 던짐의 유한-길이 순서열 (원기둥 집합)입니다.
Bernoulli measure
만약 앞면 또는 뒷면 뒤집기의 기회가 확률 \(\{p,1-p\}\)에 의해 주어지면, \(P=\{p, 1-p\}^\mathbb{N}\) (또는 두-측 과정에 대해 \(P=\{p, 1-p\}^\mathbb{Z}\))에 의해 주어진, 곱 공간 위의 자연스러운 측정(measure)을 정의할 수 있습니다. 다시 말해서, 만약 이산 확률 변수(discrete random variable) X가 매개변수 p를 갖는 베르누이 분포를 가지면, 여기서 0 ≤ p ≤ 1이고, 확률 질량 함수(probability mass function)는 다음에 의해 제공됩니다:
\(\quad\displaystyle pX(1)=P(X=1)=p\) and \(pX(0)=P(X=0)=1-p\).
이 분포를 Ber(p)로 표시합니다.
원기둥 집합, 즉, 시간 \(1,2,\cdots,n\)에서 동전 던지기 결과 \([\omega_1, \omega_2,\cdots\omega_n]\)의 특정 순서열이 주어지면, 이 특정 순서열을 관찰할 확률은 다음에 의해 주어집니다:
\(\quad\displaystyle P([\omega_1, \omega_2,\cdots ,\omega_n])= p^k (1-p)^{n-k}\)
여기서 k는 H가 순서열에 나타나는 횟수이고, n−k는 T가 순서열에 나타나는 횟수입니다. 위의 표기법에는 여러 종류가 있습니다; 공통적인 것은 다음과 같이 쓰는 것입니다:
\(\quad\displaystyle P(X_1=x_1, X_2=x_2,\cdots, X_n=x_n)= p^k (1-p)^{n-k}\)
여기서 각 \(X_i\)는 아이버슨 괄호(Iverson bracket) 표기법에서 \(x_i=[\omega_i=H]\)를 갖는 이진-값 확률 변수(random variable)로, \(\omega_i=H\)이면 \(1\), \(\omega_i=T\)이면 \(0\)임을 의미합니다. 이 확률 \(P\)는 공통적으로 베르누이 측정(Bernoulli measure)이라고 불립니다.
임의의 특정, 무한하게 긴 동전 던지기 순서열의 확률은 정확히 영임을 주목하십시오; 이것은 임의의 \(0\le p<1\)에 대해 \(\lim_{n\to\infty}p^n=0\)이기 때문입니다. 확률이 1과 같다는 것은 임의의 주어진 무한 순서열이 측정 영(measure zero)을 가짐을 의미합니다. 그럼에도 불구하고, 동전 던지기의 무한한 순서열의 일부 클래스는 다른 클래스보다 훨씬 더 가능성이 높다고 말할 수 있으며, 이것은 점근적 등분할 속성(asymptotic equipartition property)에 의해 제공됩니다.
형식적 정의를 결론짓기 위해, 베르누이 과정은 위에서 정의된 대로 확률 세-쌍 \((\Omega, \mathcal{B}, P)\)에 의해 제공됩니다.
Law of large numbers, binomial distribution and central limit theorem
\( H \)가 1로 표시되고 \( T \)가 0으로 표시되는 정식의 과정을 가정해 보십시오. 큰 숫자의 법칙(law of large numbers)에 따르면 순서열의 평균, 즉, \( \bar{X}_{n}:=\frac{1}{n}\sum_{i=1}^{n}X_{i} \)는 기댓값(expected value)에 거의 확실히 근접할 것입니다. 즉, 이 극한을 만족시키지 않는 사건은 영 확률을 가집니다. 뒤집힌 ''머리''의 기댓값은 1로 표시되는 것으로 가정되고 \(p\)로 지정됩니다. 사실, 베르누이 과정을 구성하는 무한 순서열의 베르누이 시행(Bernoulli trials) 중 임의의 주어진 확률 변수 \(X_i\)에 대해. 다음을 가집니다:
\(\quad\displaystyle \mathbb{E}[X_i]=\mathbb{P}([X_i=1])=p,\)
사람들은 종종 n번 동전 던지기 순서열에서 H를 얼마나 자주 관찰할지 알고 싶어합니다. 이것은 단순히 세는 것으로써 제공됩니다: n번의 연속적인 동전 던지기가 주어지면, 즉, 길이 n의 모든 가능한 문자열(strings)의 집합이 주어지면, H의 k번 나타나는 문자열의 숫자 N(k,n)은 이항 계수(binomial coefficient)에 의해 제공됩니다:
\(\quad\displaystyle N(k,n) = {n \choose k}=\frac{n!}{k! (n-k)!}\)
만약 앞면이 뒤집힐 확률이 p로 주어지면, k번 앞면을 갖는 길이 n의 문자열을 볼 확률의 총합은 다음과 같습니다:
\(\quad\displaystyle \mathbb{P}([S_n=k]) = {n\choose k} p^k (1-p)^{n-k} , \)
여기서 \(\displaystyle S_n=\sum_{i=1}^{n}X_i \)입니다. 이렇게 정의된 확률 측정은 이항 분포(Binomial distribution)로 알려져 있습니다.
위 공식에서 알 수 있듯이, n=1이면 이항 분포가 베르누이 분포로 바뀔 것입니다. 따라서 베르누이 분포는 n이 1과 같을 때 정확히 이항 분포의 특별한 경우임을 알 수 있습니다.
특히 흥미로운 것은 충분히 긴 동전 던지기 순서열, 즉, 극한 \(n\to\infty\)에 대한 \(S_{n}\)의 값의 문제입니다. 이 경우에서, 팩토리얼에 대한 스털링의 근사(Stirling's approximation)를 사용할 수 있고, 다음과 같이 쓸 수 있습니다:
\(\quad\displaystyle n! = \sqrt{2\pi n} \;n^n e^{-n} \left(1 + \mathcal{O}\left(\frac{1}{n}\right)\right)\)
이것을 P(k,n)에 대한 식에 대입하면, 정규 분포(Normal distribution)를 얻습니다; 이것이 중심 극한 정리(central limit theorem)의 내용이고, 이것이 그것의 가장 간단한 예제입니다.
큰 숫자의 법칙과 중심 극한 정리의 조합은 흥미롭고 아마도 놀라운 결과: 점근적 등분할 속성(asymptotic equipartition property)으로 이어집니다. 비공식적으로 말하면, 예, 많은 동전 던지기에서 H가 정확하게 시간의 p 부분을 관찰하고, 이것이 가우스의 정점과 정확하게 일치한다는 점에 주목합니다. 점근적 등분할 속성은 본질적으로 이 정점이 무한하게 날카롭고 어느 한쪽에서 무한히 감소함을 나타냅니다. 즉, 베르누이 과정에서 발생하는 H와 T의 모든 가능한 무한하게 긴 문자열의 집합이 주어지면, 이 집합은 확률 1로 발생하는 문자열과 확률 0으로 발생하는 문자열의 두 가지로 분할됩니다. 이 분할은 콜모고로프 0-1 법칙(Kolmogorov 0-1 law)으로 알려져 있습니다.
이 집합의 크기도 흥미롭고, 또한, 명시적으로 결정할 수 있습니다: 그것의 로그는 정확히 베르누이 과정의 엔트로피(entropy)입니다. 다시 한번, 길이 n의 모든 문자열 집합을 생각해 보십시오. 이 집합의 크기는 \(2^n\)입니다. 이들 중 특정 부분집합만 가능성이 있습니다; 이 집합의 크기는 \(H\le 1\)에 대해 \(2^{nH}\)입니다. 스털링의 근사를 사용하여, P(k,n)에 대한 식에 대입하여, 정점의 위치와 너비를 풀고, 마지막으로 \(n\to\infty\)를 취함으로써 다음임을 찾습니다:
\(\quad\displaystyle H=-p\log_2 p - (1-p)\log_2(1-p)\)
이 값은 베르누이 과정의 베르누이 엔트로피(Bernoulli entropy)입니다. 여기서, H는 엔트로피를 의미합니다; 머리를 나타내는 같은 기호 H와 혼동하지 마십시오.
존 폰 노이만(John von Neumann)은 베르누이 과정에 대해 흥미로운 질문을 제기했습니다: 동역학 시스템의 동형이라는 의미에서 주어진 과정이 또 다른 과정과 동형적(isomorphic)일 수 있습니까? 그 질문은 오랫동안 분석을 거부했지만, 마침내 오른슈타인 동형 정리(Ornstein isomorphism theorem)로 완전히 답을 얻었습니다. 이 돌파구는 베르누이 과정이 고유하고 보편적(universal)이라는 이해를 가져왔습니다; 어떤 의미에서, 그것은 가능한 한 가장 무작위 과정입니다; 베르누이 과정보다 '더' 무작위적인 것은 없습니다 (비록 비공식적 명제에 주의해야 함에도 불구하고; 확실하게, 혼합되는 시스템은 어떤 의미에서 단순히 에르고딕하지만 혼합되지는 않는 베르누이 과정보다 '강력'합니다. 어쨌든, 그러한 과정은 독립적인 확률 변수로 구성되지 않습니다: 실제로, 많은 순수하게 결정론적이고, 비-무작위 시스템이 혼합될 수 있습니다).
Dynamical systems
베르누이 과정은 역시 에르고딕 시스템의 예제로서 동역학적 시스템(dynamical system)과, 특히 여러 다른 방법 중 하나에서 측정-보존하는 동역학적 시스템(measure-preserving dynamical system)으로 이해될 수 있습니다. 한 가지 방법은 미는 공간(shift space)이고, 다른 하나는 주행거리계(odometer)입니다. 이것들은 아래에서 검토됩니다.
Bernoulli shift
베르누이 과정에서 동역학적 시스템을 생성하기 위해 한 가지 방법은 미는 공간(shift space)입니다. 미는 연산자(shift operator)에 의해 주어진 곱 공간 \(\Omega=2^\mathbb{N}\) 위에 자연스러운 평행이동 대칭이 있습니다:
\(\quad\displaystyle T(X_0, X_1, X_2, \cdots) = (X_1, X_2, \cdots)\)
위에 정의된 베르누이 측정은 평행이동-불변입니다; 즉, 임의의 원기둥 집합 \(\sigma\in\mathcal{B}\)가 주어지면, 다음을 가집니다:
\(\quad\displaystyle P(T^{-1}(\sigma))=P(\sigma)\)
그리고 따라서 베르누이 측정(Bernoulli measure)은 하르 측정(Haar measure)입니다; 그것은 곱 공간 위에 불변 측정(invariant measure)입니다.
확률 측정 \(P:\mathcal{B}\to\mathbb{R}\) 대신, 어떤 임의적인 함수 \(f:\mathcal{B}\to\mathbb{R}\)를 생각해 보십시오. \(\left(f\circ T^{-1}\right)(\sigma) = f(T^{-1}(\sigma))\)에 의해 정의된 다음 밂(pushforward)은
\(\quad\displaystyle f\circ T^{-1}\)
다시 어떤 함수 \(\mathcal{B}\to\mathbb{R}\)입니다. 따라서, 맵 \(T\)는 모든 함수 \(\mathcal{B}\to\mathbb{R}\)의 공간 위에 또 다른 맵 \(\mathcal{L}_T\)를 유도합니다. 즉, 일부 \(f:\mathcal{B}\to\mathbb{R}\)가 주어지면, 다음을 정의합니다:
\(\quad\displaystyle \mathcal{L}_T f = f \circ T^{-1}\)
맵 \(\mathcal{L}_T\)는 (분명히) 함수 \(f,g\)와 상수 \(a\)에 대해 \(\mathcal{L}_T(f+g)= \mathcal{L}_T(f) + \mathcal{L}_T(g)\)와 \(\mathcal{L}_T(af)= a\mathcal{L}_T(f)\)를 가질 때 선형 연산자(linear operator)입니다. 이 선형 연산자는 전송 연산자(transfer operator) 또는 Ruelle–Frobenius–Perron operator라고 불립니다. 이 연산자는 스펙트럼, 즉, 고유-함수(eigenfunctions)와 해당 고윳값의 모음을 가집니다. 가장 큰 고윳값은 프로베니우스–페론 고윳값(Frobenius–Perron eigenvalue)이고, 이 경우에서, 그것은 1입니다. 결합된 고유-벡터는 불변 측정입니다: 이 경우에서, 그것은 베르누이 측정입니다. 즉, \(\mathcal{L}_T(P)= P\)이다.
만약 \(\mathcal{L}_T\)를 다항식 위에 작용하도록 제한하면, 고유-함수는 (이상하게도) 베르누이 다항식(Bernoulli polynomials)입니다! 이 이름의 우연은 아마도 베르누이에게 알려지지 않았을 것입니다.
The 2x mod 1 map
위의 것은 더 정확하게 만들 수 있습니다. 이진 자릿수 \(b_0, b_1, \cdots\)의 무한한 문자열이 주어지면, 다음을 씁니다:
\(\quad\displaystyle y=\sum_{n=0}^\infty \frac{b_n}{2^{n+1}}.\)
결과 \(y\)는 단위 구간 \(0\le y\le 1\)의 실수입니다. 미는 \(T\)는 단위 구간 위에 \(T\)라고도 불리는 준동형(homomorphism)을 유도합니다. \(T(b_0, b_1, b_2, \cdots) = (b_1, b_2, \cdots)\)이므로, \(T(y)=2y\bmod 1\)임을 쉽게 알 수 있습니다. 이 맵은 이원적 변환(dyadic transformation)이라고 불립니다; 비트 \(\Omega=2^\mathbb{Z}\)의 이중으로-무한 순서열 대해, 유도된 준동형은 베이커의 맵(Baker's map)입니다.
이제 \(y\)에서 함수의 공간을 생각해 보십시오. 일부 \(f(y)\)가 주어지면, 다음임을 쉽게 찾을 수 있습니다:
\(\quad\displaystyle \left[\mathcal{L}_T f\right](y) = \frac{1}{2}f\left(\frac{y}{2}\right)+\frac{1}{2}f\left(\frac{y+1}{2}\right)\)
연산자 \(\mathcal{L}_T\)의 동작을 다항식 위에 있는 함수로 제한하면, 다음에 의해 주어진 이산 스펙트럼(discrete spectrum)을 가짐을 찾습니다:
\(\quad\displaystyle \mathcal{L}_T B_n= 2^{-n}B_n\)
여기서 \(B_n\)은 베르누이 다항식(Bernoulli polynomials)입니다. 실제로, 베르누이 다항식은 다음 항등식을 따릅니다:
\(\quad\displaystyle \frac{1}{2}B_n\left(\frac{y}{2}\right)+\frac{1}{2}B_n\left(\frac{y+1}{2}\right) = 2^{-n}B_n(y)\)
The Cantor set
다음 합이 전통적으로 정의된 대로 칸토어 함수(Cantor function)를 제공함을 주목하십시오:
\(\quad\displaystyle y=\sum_{n=0}^\infty \frac{b_n}{3^{n+1}}\)
이것이 집합 \(\{H,T\}^\mathbb{N}\)이 때때로 칸토어 집합(Cantor set)이라고 불리는 이유 중 하나입니다.
Odometer
동역학적 시스템을 만들기 위한 또 다른 방법은 주행기록계(odometer)를 정의하는 것입니다. 비공식적으로, 이것은 정확히 다음과 같이 들리는 것입니다: 첫 번째 위치에 단지 "1을 추가"하고, 주행거리계가 "롤 오버"될 때 캐리 비트(carry bits)를 사용함으로써 주행거리계가 "롤 오버"되도록 합니다. 이것은 무한 문자열의 집합에 대한 밑수-2 덧셈에 지나지 않습니다. 덧셈은 그룹을 형성하고, 베르누이 과정은 위에서 이미 토폴로지를 제공하기 때문에, 이것은 토폴로지적 그룹(topological group)의 간단한 예제를 제공합니다.
이 경우에서, 변환 \(T\)는 다음에 의해 제공됩니다:
\(\quad\displaystyle T\left(1,\dots,1,0,X_{k+1},X_{k+2},\dots\right) = \left(0,\dots,0,1,X_{k+1},X_{k+2},\dots \right).\)
그것은 \(p=1/2\) ("공정한 동전")의 특수한 경우에만 베르누이 측정을 불변으로 남깁니다; 그렇지 않으면 아닙니다. 따라서, \(T\)는 이 경우에서 동역학적 시스템을 보존하는 측정이고, 그렇지 않으면, 그것은 단지 보존 시스템(conservative system)입니다.
Bernoulli sequence
베르누이 수열(Bernoulli sequence)이라는 용어는 종종 베르누이 과정의 실현(realization)을 참조하기 위해 비공식적으로 사용됩니다. 어쨌든, 그 용어는 아래와 같이 완전히 다른 형식적 정의를 가지고 있습니다.
형식적으로 단일 확률 변수로 정의된 베르누이 과정을 가정합니다 (이전 섹션 참조). 동전 던지기의 모든 각 무한 수열 x에 대해, 베르누이 과정과 결합된 베르누이 베르누이 수열(Bernoulli sequence)이라고 불리는 다음과 같은 정수의 수열(sequence)이 있습니다:
\(\quad\displaystyle \mathbb{Z}^x = \{n\in \mathbb{Z} : X_n(x) = 1 \} \, \)
예를 들어, 만약 x가 동전 던지기의 수열을 나타내면, 결합된 베르누이 수열은 동전 던지기 결과가 앞면인 자연수 또는 시간-점의 목록입니다.
이렇게 정의된, 베르누이 수열 \(\mathbb{Z}^x\)은 인덱스 집합, 자연수 \(\mathbb{N}\)의 무작위 부분집합이기도 합니다.
거의 모든(Almost all) 베르누이 수열 \(\mathbb{Z}^x\)은 에르고딕 수열(ergodic sequences)입니다.
Randomness extraction
임의의 베르누이 과정에서 폰 노이만 추출기(von Neumann extractor)에 의해 p = 1/2을 갖는 베르누이 과정을 유도할 수 있으며, 이는 실제로 균등 무작위성을 추출하는 최초의 무작위성 추출기(randomness extractor)입니다.
Basic von Neumann extractor
관찰된 과정을 0과 1 또는 비트의 수열로 나타내고, 해당 입력 스트림을 (11)(00)(10)...과 같이 연속 비트의 겹치지 않는 쌍으로 그룹화합니다. 그런-다음 각 쌍에 대해,
- 만약 비트가 같으면, 버립니다;
- 만약 비트가 같지 않으면, 첫 번째 비트를 출력합니다.
이 테이블은 계산을 요약합니다.
| input | output |
| 00 | discard |
| 01 | 0 |
| 10 | 1 |
| 11 | discard |
예를 들어, 8비트 10011011의 입력 스트림은 (10)(01)(10)(11)으로 쌍으로 그룹화됩니다. 그런-다음 위의 테이블에 따라, 이들 쌍은 절차의 출력: (1)(0)(1)() (=101)으로 변환됩니다.
출력 스트림에서, 0과 1은 확률이 동일하며, 10과 01은 원래에서 확률이 같고, 둘 다 확률 p(1−p) = (1−p)p를 가집니다. 이러한 균등 무작위성의 추출은 입력 시행이 독립적일 필요는 없으며, 단지 비-상관적(uncorrelated)이어야 합니다. 보다 일반적으로, 그것은 비트의 임의의 교환-가능한 수열(exchangeable sequence)에 대해 작동합니다: 유한 재배열인 모든 수열은 같은 가능성이 있습니다.
폰 노이만 추출기는 2개의 입력 비트를 0 또는 1 출력 비트를 생성하기 위해 사용하므로, 출력은 적어도 2의 인수만큼 입력보다 짧습니다. 평균적으로, 계산은 입력 쌍(00와 11)의 비율 \(p^2+(1-p)^2\)을 버리며, 이는 p가 0 또는 1에 가까울 때 1에 가깝고, 원래 과정에 대해 p = 1/2일 때 1/4에서 최소화됩니다 (이 경우에서 출력 스트림 길이는 평균적으로 입력 스트림의 1/4 길이입니다).
폰 노이만 (고전적) 주요 연산 유사-코드(pseudocode):
if (Bit1 ≠ Bit2) {
output(Bit1)
}
Iterated von Neumann extractor
이러한 효율성 감소, 또는 입력 스트림에 존재하는 무작위성의 낭비는 입력 데이터에 걸쳐 알고리듬을 반복함으로써 완화될 수 있습니다. 이 방법으로 출력을 "엔트로피 경계에 임의적으로 가깝게" 만들 수 있습니다.
고급 다중-수준 전략(Advanced Multi-Level Strategy, 줄여서 AMLS)로도 알려진 폰 노이만 알고리듬의 반복된 버전은 1992년에 유발 페레스(Yuval Peres)에 의해 도입되었습니다. 그것은 두 가지 원천: 버림/비-버림의 수열에서 "낭비된 무작위성"과 버려진 쌍의 값 (00에 대해 0과 11에 대해 1)을 재활용하여 재귀적으로 작동합니다. 직관적으로, 그것은 이미 생성된 수열이 주어지면, 두 원천 모두 여전히 교환-가능한 비트의 수열이고, 따라서 또 다른 추출 회에 적합하다는 사실에 의존합니다. 그러한 추가 수열의 생성은 모든 사용-가능한 엔트로피를 추출하기 위해 무한하게 반복될 수 있지만, 무한한 계산적 자원의 총량이 요구되며, 따라서 반복의 횟수는 전형적으로 낮은 값으로 고정됩니다 – 이 값은 미리 고정되거나 실행-시간에 계산됩니다.
보다 구체적으로, 입력 수열에서, 알고리듬은 입력 비트를 쌍으로 소비하여, 두 개의 새로운 수열과 함께 출력을 생성합니다:
| input | output | new sequence 1 | new sequence 2 |
| 00 | none | 0 | 0 |
| 01 | 0 | 1 | none |
| 10 | 1 | 1 | none |
| 11 | none | 0 | 1 |
(만약 입력의 길이가 홀수이면, 마지막 비트는 완전하게 폐기됩니다.) 그런-다음 알고리듬은 입력이 비어 있을 때까지 두 개의 새로운 수열 각각에 재귀적으로 적용됩니다.
예제: 위의 입력 스트림, 10011011은 이러한 방법에서 처리됩니다:
| step number | input | output | new sequence 1 | new sequence 2 |
| 0 | (10)(01)(10)(11) | (1)(0)(1)() | (1)(1)(1)(0) | ()()()(1) |
| 1 | (11)(10) | ()(1) | (0)(1) | (1)() |
| 1.1 | (01) | (0) | (1) | () |
| 1.1.1 | 1 | none | none | none |
| 1.2 | 1 | none | none | none |
| 2 | 1 | none | none | none |
1단계부터, 입력은 이 과정에서 앞으로 나아갈 마지막 단계의 새로운 sequence1이 됩니다. 따라서 출력은 (101)(1)(0)()()() (=10110)이므로, 위의 기본 알고리듬을 통해 3비트가 아닌 8비트의 입력에서 5비트의 출력이 생성되었습니다. 회 당 정확하게 2비트의 일정한 출력 (고전적 VN에서 변수 0에서 1비트와 비교)은 역시 타이밍 공격(timing attacks)에 저항하는 일정한-시간 구현을 허용합니다.
폰 노이만-페레스 (반복된) 주요 연산 유사-코드:
if (Bit1 ≠ Bit2) {
output(1, Sequence1)
output(Bit1)
} else {
output(0, Sequence1)
output(Bit1, Sequence2)
}
2016년에는 Sequence2 채널이 많은 처리량을 제공하지 않는다는 관찰 결과와 한정된 수준의 하드웨어 구현이 Sequence1의 더 많은 수준을 처리하는 대가로 더 일찍 폐기함으로써 이점을 얻을 수 있다는 관찰에 기반하여 또 다른 조정이 제시되었습니다.
Further reading
- Carl W. Helstrom, Probability and Stochastic Processes for Engineers, (1984) Macmillan Publishing Company, New York ISBN 0-02-353560-1.
External links