Bernoulli process

확률과 통계학에서, 베르누이 과정(Bernoulli process)은, 야콥 베르누이(Jacob Bernoulli)의 이름을 따서 지어졌으며, 이진 확률 변수(random variable)의 유한 또는 무한 수열이므로, 그것은 정식적으로 0과 1의 오직 두 가지 값을 취하는 이산-시간 확률적 과정(discrete-time stochastic process)입니다. 구성 요소 베르누이 변수(Bernoulli variables) X_i는 동일하게 분포되고 독립적입니다. 무미건조하게, 베르누이 과정은 아마도 불공정 동전을 갖는 (하지만 일관된 불공정을 갖는) 반복된 동전 던지기입니다. 수열에서 모든 각 변수 X_i는 베르누이 시행(Bernoulli trial) 또는 실험과 결합됩니다. 그들 모두는 같은 베르누이 분포(Bernoulli distribution)를 가집니다. 베르누이 과정에 대해 말할 수 있는 것의 대부분은 역시 (육면체 주사위에 대한 과정과 같은) 두 가지 많은 결과로 일반화될 수 있습니다; 이 일반화는 베르누이 스킴(Bernoulli scheme)으로 알려져 있습니다.

오직 제한된 베르누이 시행의 표본이 주어지면, 과정을 결정하는 문제는 동전이 공정한 지를 검사하는 문제라고 불릴 수 있습니다.

Definition

베르누이 과정(Bernoulli process)은 다음임을 만족하는 독립(independent) 확률 변수(random variables) X₁, X₂, X₃, ...의 유한 또는 무한 수열입니다:

각 i에 대해, X_i의 값은 0 또는 1 중 하나입니다;
i의 모든 값에 대해, X_i = 1일 확률은 같습니다.

다시 말해서, 베르누이 과정은 독립적인 동일하게 분포된(independent identically distributed) 베르누이 시행(Bernoulli trials)의 수열입니다.

시행의 독립성은 그 과정이 기억-없음(memoryless)임을 의미합니다. 확률 p가 알려진 것으로 주어지면, 과거 결과는 미래 결과에 대한 정보를 제공하지 않습니다. (만약 p가 알려져 있지 않으면, 어쨌든, 과거는 p에 대한 추론을 통해 간접적으로 미래를 알려줍니다.)

만약 그 과정이 무한하다면, 어떤 점에서든 미래 시행은 전체 과정과 동일한 베르누이 과정, 새롭게-시작 속성을 구성합니다.

Interpretation

각 X_i의 두 가지 가능한 값은 종종 "성공"과 "실패"라고 불립니다. 따라서, 숫자 0 또는 1로 표현될 때, 결과는 i번째 "시행"의 성공의 횟수라고 불릴 수 있습니다.

값의 두 개의 다른 공통적인 해석은 "참" 또는 "거짓"과 "예" 또는 "아니오"입니다. 두 값의 임의의 해석 아래에서, 개별 변수 X_i는 매개변수 p를 갖는 베르누이 시행(Bernoulli trials)이라고 불릴 수 있습니다.

많은 응용에서, 지수 i가 증가함에 따라 시행 사이에 시간이 경과합니다. 사실상, 시행 X₁, X₂, ... X_i, ...는 "시점" 1, 2, ..., i, ...에서 발생합니다. 시간의 경과와 결합된 "과거"와 "미래"의 개념은, 어쨌든, 필요하지 않습니다. 가장 일반적으로, 과정에서 임의의 X_i와 X_j는 유한한 경우, {1, 2, ..., n}, 또는, 무한한 경우, {1, 2, 3, ...}에 의해 인덱스된 확률 변수의 집합에서 단순히 두 개입니다.

보통 1과 0으로 인코딩되는, 종종 "성공"과 "실패"라고 참조되는, 오직 두 가지 가능한 결과를 갖는 하나의 실험은 베르누이 분포(Bernoulli distribution)로 모델링될 수 있습니다.^[1] 베르누이 외에 여러 확률 변수와 확률 분포는 베르누이 과정에서 다음과 같은 도출될 수 있습니다:

처음 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)는 다음에 의해 제공됩니다:

pX(1)=P(X=1)=p

and

pX(0)=P(X=0)=1-p

.

이 분포를 Ber(p)로 표시합니다.^[1]

원기둥 집합, 즉, 시간 $1,2,\cdots ,n$ 에서 동전 던지기 결과 $[\omega _{1},\omega _{2},\cdots \omega _{n}]$ 의 특정 순서열이 주어지면, 이 특정 순서열을 관찰할 확률은 다음에 의해 주어집니다:

P([\omega _{1},\omega _{2},\cdots ,\omega _{n}])=p^{k}(1-p)^{n-k}

여기서 k는 H가 순서열에 나타나는 횟수이고, n−k는 T가 순서열에 나타나는 횟수입니다. 위의 표기법에는 여러 종류가 있습니다; 공통적인 것은 다음과 같이 쓰는 것입니다:

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)이라고 불립니다.^[2]

임의의 특정, 무한하게 긴 동전 던지기 순서열의 확률은 정확히 영임을 주목하십시오; 이것은 임의의 $0\leq 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}$ 에 대해. 다음을 가집니다:

\mathbb {E} [X_{i}]=\mathbb {P} ([X_{i}=1])=p,

사람들은 종종 n번 동전 던지기 순서열에서 H를 얼마나 자주 관찰할지 알고 싶어합니다. 이것은 단순히 세는 것으로써 제공됩니다: n번의 연속적인 동전 던지기가 주어지면, 즉, 길이 n의 모든 가능한 문자열(strings)의 집합이 주어지면, H의 k번 나타나는 문자열의 숫자 N(k,n)은 이항 계수(binomial coefficient)에 의해 제공됩니다:

N(k,n)={n \choose k}={\frac {n!}{k!(n-k)!}}

만약 앞면이 뒤집힐 확률이 p로 주어지면, k번 앞면을 갖는 길이 n의 문자열을 볼 확률의 총합은 다음과 같습니다:

\mathbb {P} ([S_{n}=k])={n \choose k}p^{k}(1-p)^{n-k},

여기서 $S_{n}=\sum _{i=1}^{n}X_{i}$ 입니다. 이렇게 정의된 확률 측정은 이항 분포(Binomial distribution)로 알려져 있습니다.

위 공식에서 알 수 있듯이, n=1이면 이항 분포가 베르누이 분포로 바뀔 것입니다. 따라서 베르누이 분포는 n이 1과 같을 때 정확히 이항 분포의 특별한 경우임을 알 수 있습니다.

특히 흥미로운 것은 충분히 긴 동전 던지기 순서열, 즉, 극한 $n\to \infty$ 에 대한 $S_{n}$ 의 값의 문제입니다. 이 경우에서, 팩토리얼에 대한 스털링의 근사(Stirling's approximation)를 사용할 수 있고, 다음과 같이 쓸 수 있습니다:

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\leq 1$ 에 대해 $2^{nH}$ 입니다. 스털링의 근사를 사용하여, P(k,n)에 대한 식에 대입하여, 정점의 위치와 너비를 풀고, 마지막으로 $n\to \infty$ 를 취함으로써 다음임을 찾습니다:

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} }$ 위에 자연스러운 평행이동 대칭이 있습니다:

T(X_{0},X_{1},X_{2},\cdots )=(X_{1},X_{2},\cdots )

위에 정의된 베르누이 측정은 평행이동-불변입니다; 즉, 임의의 원기둥 집합 $\sigma \in {\mathcal {B}}$ 가 주어지면, 다음을 가집니다:

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)은

f\circ T^{-1}

다시 어떤 함수 ${\mathcal {B}}\to \mathbb {R}$ 입니다. 따라서, 맵 $T$ 는 모든 함수 ${\mathcal {B}}\to \mathbb {R}$ 의 공간 위에 또 다른 맵 ${\mathcal {L}}_{T}$ 를 유도합니다. 즉, 일부 $f:{\mathcal {B}}\to \mathbb {R}$ 가 주어지면, 다음을 정의합니다:

{\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)입니다!^[3]^[4] 이 이름의 우연은 아마도 베르누이에게 알려지지 않았을 것입니다.

The 2x mod 1 map

The map T : [0,1) → [0,1), $x\mapsto 2x{\bmod {1}}$ preserves the Lebesgue measure.

위의 것은 더 정확하게 만들 수 있습니다. 이진 자릿수 $b_{0},b_{1},\cdots$ 의 무한한 문자열이 주어지면, 다음을 씁니다:

y=\sum _{n=0}^{\infty }{\frac {b_{n}}{2^{n+1}}}.

결과 $y$ 는 단위 구간 $0\leq y\leq 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)$ 가 주어지면, 다음임을 쉽게 찾을 수 있습니다:

\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)을 가짐을 찾습니다:

{\mathcal {L}}_{T}B_{n}=2^{-n}B_{n}

여기서 $B_{n}$ 은 베르누이 다항식(Bernoulli polynomials)입니다. 실제로, 베르누이 다항식은 다음 항등식을 따릅니다:

{\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)를 제공함을 주목하십시오:

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$ 는 다음에 의해 제공됩니다:

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)이 있습니다:

\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² + (1 − p)²를 버리며, 이는 p가 0 또는 1에 가까울 때 1에 가깝고, 원래 과정에 대해 p = 1/2일 때 1/4에서 최소화됩니다 (이 경우에서 출력 스트림 길이는 평균적으로 입력 스트림의 1/4 길이입니다).

폰 노이만 (고전적) 주요 연산 유사-코드(pseudocode):

if (Bit1 ≠ Bit2) {
   output(Bit1)
}

Iterated von Neumann extractor

이러한 효율성 감소, 또는 입력 스트림에 존재하는 무작위성의 낭비는 입력 데이터에 걸쳐 알고리듬을 반복함으로써 완화될 수 있습니다. 이 방법으로 출력을 "엔트로피 경계에 임의적으로 가깝게" 만들 수 있습니다.^[5]

고급 다중-수준 전략(Advanced Multi-Level Strategy, 줄여서 AMLS)로도^[6] 알려진 폰 노이만 알고리듬의 반복된 버전은 1992년에 유발 페레스(Yuval Peres)에 의해 도입되었습니다.^[5] 그것은 두 가지 원천: 버림/비-버림의 수열에서 "낭비된 무작위성"과 버려진 쌍의 값 (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의 더 많은 수준을 처리하는 대가로 더 일찍 폐기함으로써 이점을 얻을 수 있다는 관찰에 기반하여 또 다른 조정이 제시되었습니다.^[7]

References

^ ^a ^b Dekking, F. M.; Kraaikamp, C.; Lopuhaä, H. P.; Meester, L. E. (2005). A modern introduction to probability and statistics. pp. 45–46. ISBN 9781852338961.
^ Klenke, Achim (2006). Probability Theory. Springer-Verlag. ISBN 978-1-84800-047-6.
^ Pierre Gaspard, "r-adic one-dimensional maps and the Euler summation formula", Journal of Physics A, 25 (letter) L483-L485 (1992).
^ Dean J. Driebe, Fully Chaotic Maps and Broken Time Symmetry, (1999) Kluwer Academic Publishers, Dordrecht Netherlands ISBN 0-7923-5564-4
^ ^a ^b Peres, Yuval (March 1992). "Iterating Von Neumann's Procedure for Extracting Random Bits". The Annals of Statistics. 20 (1): 590–597. doi:10.1214/aos/1176348543.
^ "Tossing a Biased Coin" (PDF). eecs.harvard.edu. Retrieved 2018-07-28.
^ Rožić, Vladimir; Yang, Bohan; Dehaene, Wim; Verbauwhede, Ingrid (3–5 May 2016). Iterating Von Neumann's post-processing under hardware constraints (PDF). 2016 IEEE International Symposium on Hardware Oriented Security and Trust (HOST). Maclean, VA, USA. doi:10.1109/HST.2016.7495553.

External links

Using a binary tree diagram for describing a Bernoulli process

[:0-1] Dekking, F. M.; Kraaikamp, C.; Lopuhaä, H. P.; Meester, L. E. (2005). A modern introduction to probability and statistics. pp. 45–46. ISBN 9781852338961.

[klenke-2] Klenke, Achim (2006). Probability Theory. Springer-Verlag. ISBN 978-1-84800-047-6.

[3] Pierre Gaspard, "r-adic one-dimensional maps and the Euler summation formula", Journal of Physics A, 25 (letter) L483-L485 (1992).

[4] Dean J. Driebe, Fully Chaotic Maps and Broken Time Symmetry, (1999) Kluwer Academic Publishers, Dordrecht Netherlands ISBN 0-7923-5564-4

[Peres-5] Peres, Yuval (March 1992). "Iterating Von Neumann's Procedure for Extracting Random Bits". The Annals of Statistics. 20 (1): 590–597. doi:10.1214/aos/1176348543.

[6] "Tossing a Biased Coin" (PDF). eecs.harvard.edu. Retrieved 2018-07-28.

[7] Rožić, Vladimir; Yang, Bohan; Dehaene, Wim; Verbauwhede, Ingrid (3–5 May 2016). Iterating Von Neumann's post-processing under hardware constraints (PDF). 2016 IEEE International Symposium on Hardware Oriented Security and Trust (HOST). Maclean, VA, USA. doi:10.1109/HST.2016.7495553.

[1]

[2]

[3]

[4]

[5]

[6]

[7]