바이어 싱 다이로 페어 다이 시뮬레이션 알고리즘은 확률 1로 종료해야합니다. 즉,

바이어스 된 다이가 주어지면 범위의 난수가 어떻게 균일하게 생성 될 수 있습니까? 다이 페이스의 확률 분포는 알려져 있지 않으며, 알려진 모든 것은 각각의 페이스가 0이 아닌 확률을 가지며 확률 분포는 모든 드로우에서 동일하다는 것입니다 (특히, 스로우는 독립적 임). 이것은 불공정 한 주사위공정 결과를 명백히 일반화 한 것 입니다.

N

[1,N]

: 컴퓨터 과학 용어 이러는 우리가 다이 롤 나타내는 오라클이 되도록 제로와 무관 . 우리는 결정 론적 알고리즘을 찾고 에 의해 매개 변수화되어 (즉, 호출 할 수 있습니다 ) 등이 . 알고리즘은 확률 1로 종료해야합니다. 즉, AD를 n 번 이상 호출 할 확률 은 n \ to \ infty0에 수렴해야합니다 .

D:N→[1,N]

pi=P(D(k)=i)

k

A

D

A

D

P(A()=i)=1/N

A

n

D

0

n→∞

들면

N=2

, 공지의 알고리즘이있다 (코인이 바이어스 동전 뒤집에서 공정한 동전 시뮬레이션) :

  • 두 번의 던지기가 뚜렷한 결과 ((머리, 꼬리) 또는 (꼬리, 머리))가 나올 때까지 “두 번 플립”을 반복하십시오. 즉, k = 0 .. \ infty for D (2k + 1) \ ne D (2k)
    k=0..∞

    까지 반복 D(2k+1)≠D(2k)

  • 마지막 뒤집기 쌍이 (머리, 꼬리)이면 0을 반환하고 (꼬리, 머리)이면 1을 반환합니다. 즉, 리턴 D (2K) k는 루프가 종료 된 인덱스이다.
    D(2k)

    k

편향된 다이로부터 편견없는 다이를 만드는 간단한 방법은 코인 플립 비 편향 방법을 사용하여 공정한 코인을 구축하고 시퀀스의 편향 제거 에서처럼 거부 샘플링으로 공정한 다이를 만드는 것입니다 . 그러나 이것이 확률 분포의 일반 값에 대해 최적입니까?

구체적으로, 내 질문은 : oracle에 대한 최소 예상 호출 횟수 가 필요한 알고리즘은 무엇 입니까? 도달 가능한 기대 값 세트가 열려 있으면 하한은 무엇이며이 하한으로 수렴하는 알고리즘 클래스는 무엇입니까?

서로 다른 확률 분포에 대해 서로 다른 알고리즘 계열이 최적 인 경우 거의 공정한 주사위에 초점을 맞 춥니 다. 나는 \ forall i, \ bigl | p_i-1 / 과 같은 분포에 최적 인 알고리즘 또는 알고리즘 계열을 찾고 있습니다. N \ 더 큰 |

∀i,|pi−1/N|<ϵ

일부 \ epsilon \ gt 0의 경우 \ lt \ epsilon

ϵ>0

.



답변

다음의 논문은이 질문의 유사 변형에 대한 답을 제시한다 : 편견없는 랜덤 시퀀스의 효율적인 구성, Elias 1972 .

이 편향된 독립 소스에 대한 액세스가 주어지면 으로 임의의 숫자 시퀀스 를 출력하십시오 (단 하나의 출력 기호 만 요청되는 질문과의 차이에 유의하십시오). 원하는 출력의 길이가 무한대에 가까워짐에 따라 (von Neumann의 자연적인 일반화처럼 보이는) 논문의 체계의 “효율”은 . 이는 엔트로피 를 갖는 입력 이로 변환 됨을 의미 합니다. 접근하는 엔트로피의 출력 .

[1,N]

1

h

h

예를 들어 샘플을 가져 와서 많은 정보를 가진 출력으로 끝나는 경우 (예를 들어, 모든 입력 심볼이 고유 하기 때문에) 단일 출력 자릿수를 요청하는 대신 이런 식으로 표현하면 질문이 훨씬 더 잘 작동하는 것 같습니다 그런 다음 모든 정보를 사용하여 많은 출력 기호를 생성 할 수 있지만 여기에 나와있는 질문에서 하나의 출력 기호를 생성하는 데 사용 된 정보 이외의 정보는 낭비됩니다.

N

N

나는 그 체계가 반복적으로 드로우를 가져 와서 시퀀스를보고 출력 또는 빈 문자열을 매핑 한다고 믿습니다 . 기호를 출력하기에 “충분한”정보가있는 경우 접두사를보고 중지하여 질문에 대한 체계를 개선 할 수있는 방법이 있습니까? 모르겠어요

N

답변

일반화에 대해 설명하는 방법 . 롤이 독립적이기 때문에 [ 1 .. N ] 의 모든 순열은 바이어스 된 다이에서도 동일하게 사용됩니다. 따라서 마지막 N 롤과 같은 순열을보고 마지막 롤을 출력 할 때까지 계속 롤링 할 수 있습니다 .

N=2

[1..N]

N

일반적인 분석은 까다 롭습니다. 그러나, 주어진 단계에서 순열을 볼 확률이 작기 때문에 (그리고 이전과 이후의 단계와 무관하기 때문에) 까다로운 롤의 예상 롤 수는 에서 빠르게 증가한다는 것이 분명 합니다. 그것은 이상 0 고정을 위해 N 절차가 거의 확실하므로 종료하지만 (즉, 확률 1 ).

N

0

N

1

고정 경우 , 합산 되는 마지막 파릭-벡터 집합에 대해 마르코프 체인을 구성 하여 마지막 롤 의 결과를 요약하고 도달 할 때까지 예상 단계 수를 결정할 수 있습니다. 처음으로 . 이것은 Parikh-vector를 공유하는 모든 순열이 동일하게 가능하기 때문에 충분합니다. 이런 식으로 체인과 계산이 더 간단합니다.

N

≤N

N

(1,…,1)

우리는 상태에있는 가정 와 . 그런 다음 요소 i얻을 확률 (즉, 다음 롤은 i )은 항상n i = 1 v iN

v=(v1,…,vN)

∑i=1nvi≤N

i

i

.

홍보⁡[이득 나는]=피나는

한편, 이력에서 원소 i떨어 뜨릴 가능성 은 다음과 같이 주어진다.

나는

홍보V⁡[하락 나는]=V나는엔

마다 (그리고 0 , 그렇지) 정확하게 Parikh 벡터의 모든 순열 때문에 V는 똑같이 보인다. 이러한 확률은 독립적이므로 (롤이 독립적이므로) 다음과 같이 전이 확률을 계산할 수 있습니다.

∑나는=1엔V나는=엔

0

V

Pr⁡[v→(v1,…,vj+1,…,vN)]={Pr⁡[gain j],∑v<N0, else,Pr⁡[v→(v1,…,vi−1,…vj+1,…,vN)]={0,∑v<N∨vi=0∨vj=NPrv⁡[drop i]⋅Pr⁡[gain j], else andPr⁡[v→v]={0,∑v<N∑vi≠0Prv⁡[drop i]⋅Pr⁡[gain i], else;

다른 모든 전이 확률은 0입니다. 단일 흡수 상태는 [ 1. N ] 의 모든 순열의 파리 크 벡터 인 입니다.

(1,…,1)

[1..N]

들면 결과 마르코프 chain¹은

N=2


[ 출처 ]

흡수 될 때까지 예상 단계 수

Esteps=2p0p1⋅2+∑i≥3(p0i−1p1+p1i−1p0)⋅i=1−p0+p02p0−p02,

단순화를 위해 . 지금, 제안대로, p 0 = 1

p1=1−p0

일부ϵ[0,1의 경우 2 ±ϵ

p0=12±ϵ

다음,

ϵ∈[0,12)

.

Esteps=3+4ϵ21−4ϵ2

들면 균일 분포 (최상의 경우) I algebra² 컴퓨터로 계산을 수행했다; 상태 공간이 빠르게 폭발하므로 더 큰 값을 평가하기가 어렵습니다. 결과 (위로 반올림)는

N≤6


플롯 쇼 N 의 함수로서의 단계 ; 왼쪽에는 정규, 오른쪽에는 로그 플롯이 있습니다.

Esteps

N

성장은 기하 급수적으로 보이지만 값이 너무 작아서 좋은 추정치를 제공 할 수 없습니다.

의 섭동에 대한 안정성에 대해서는 우리가 상황을 볼 수 N = 3 :

pi

N=3


플롯은 E를 보여줍니다. 의 함수로서 페이지 0 페이지 1 ; 당연히 p 2 = 1 - p 0 - p 1 입니다.

Esteps

p0

p1

p2=1−p0−p1

더 비슷한 사진을 가정하면 (커널도에 대한 상징적 인 결과를 계산 충돌하는 N = 4 ) 단계의 예상 수는 상당히 모두를위한 안정적인 있지만 가장 극단적 인 선택 (거의 모든 또는 없음 질량 일부에서 보인다 P ).

N

N=4

pi

비교 를 위해, 공정한 동전을 시뮬레이션하고 최종적으로 비트 단위 거부 샘플링을 수행하기 위해이를 사용하여 바이어스 동전을 시뮬레이션합니다 (예 : 가능한 한 골고루 다이를 01 에 할당 하여).

ϵ

0

1

2⌈log⁡N⌉⋅3+4ϵ21−4ϵ2

다이 롤 기대-아마 당신은 그것에 충실해야합니다.


  1. 체인이 흡수하기 때문에 회색으로 표시된 모서리는 절대로 이송되지 않으며 계산에 영향을 미치지 않습니다. 나는 단지 완전성과 설명을 목적으로 그것들을 포함시킵니다.
    (11)

  2. Mathematica 10에서의 구현 ( 노트북 , 베어 소스 ); 죄송합니다. 이런 종류의 문제에 대해 제가 아는 것입니다.

답변

사례 에 관한 간단한 설명 입니다. 일부 대형 번호를 가지고 m를 , 샘플 m은 다이의 발생합니다. k 개의 머리 가 있다면 로그 를 추출 할 수 있습니다 ( m

N=2

m

m

k

비트. 다이가p바이어스되어있다고 가정하면,평균 정보량은
m k=0pk(1p)mk ( m

log⁡(mk)

p


이 추정치를 얻으려면 이항 변수가추정로그와 함께k=pm주위에 집중되어 있다는 사실을 사용하십시오 ( m

∑k=0mpk(1−p)m−k(mk)log⁡(mk)≈mh(p).

k=pm

. 마찬가지로m이커지면, 우리는 최적의 속도 얻었다H(P)동전 던지기 당 (이것은 예를 들면, 점근선 균등 분배 속성 정보 이론적 이유로 적합하다).

log⁡(mk)≈mh(k/m)

m

h(p)

일반 대해 동일한 방법을 사용할 수 있으며 아마도 동일한 H ( p )를 얻게 될 것입니다 . 이 알고리즘은 한계 내에서만 최적이며 알고리즘이 한계보다 빠르게 한계에 도달 할 수 있습니다. 사실, 나는 수렴 속도를 계산하는 것을 소홀히했다 – 그것은 흥미로운 운동일지도 모른다.

N

H(p→)

답변

다음과 같은 대답이 위험합니다.

(피+큐)2

2피큐

피큐

큐피

피큐

큐피

엔=삼

(피+큐+아르 자형)삼

pqr

q

p

r

N=3

pqr

.

특별한:

이것은 주사위의 각 결과의 확률을 추정하기 위해 단순히 많은 양을 샘플링하는 아이디어에 대해 생각하게합니다. 숨겨진 계층 (알려진 모델)이없는이 단일 계층 모델의 경우, 추정이 빠르게 수렴된다는 결론을 내릴 수 있습니다. 실제로 Chernoff 경계는 샘플링이 증가함에 따라 (선형 적으로) 오차가 기하 급수적으로 감소 함을 보여줍니다.

∏i=1i=np나는

그럼에도 불구하고,이 접근법은 질문의 다른 풍미에 대한 해답입니다. 이 질문은 잠재적으로 큰 샘플링 비용 (낮은 프로빙)에도 불구하고 완벽한 편견없는 보장을 요구합니다. 이 방법은 신뢰 매개 변수에 바인딩 된 유한 샘플링 만 사용합니다. 그래서 나는이 접근법이 매우 흥미 롭더라도이 질문에 적합하다고 생각하지 않습니다.