임의성 합병
Randomness merger추출자 이론에서, 임의성 합치는 적어도 하나 이상의 변수가 균일하게 랜덤하다는 전제 하에, 일련의 랜덤 변수에서 랜덤성을 추출하는 함수다.그것의 이름은 그것이 모든 변수를 "머그"하여 균일하게 무작위 변수에 포함된 엔트로피의 최소한 일부를 보존하는 절차로 볼 수 있다는 사실에서 유래한다.합병은 현재 무작위 추출기를 명시적으로 구성하기 위해 사용된다.
직관과 정의
{ {\ 1 에 분산된k \{0,1에 된 변수 집합을 고려하되, 어떤 변수인지는 알 수 없다.또한 변수들은 임의로 상관될 수 있다. 변수들은 서로의 함수일 수도 있고, 일정할 수도 있다.그러나 적어도 그 중 하나가 균일하기 때문에 전체적으로 세트에는 적어도 비트의 엔트로피가 포함되어 있다.
합병의 일은 가능한 한 엔트로피를 많이 유지하는 새로운 랜덤 변수를 출력하는 것이다 또한 { , 에 걸쳐 분포한다이상적으로는 어떤 변수가 균일한지 알면 출력으로 사용할 수 있지만 그 정보는 알 수 없다.합병의 이면에 있는 아이디어는 작은 추가 랜덤시드를 사용함으로써 어떤 것이 균일한 변수인지 알지 못하더라도 좋은 결과를 얻을 수 있다는 것이다.
정의(머거):
함수 :({ 0 ) { →{ } M is called an -merger if for every set of random variables distributed over , at least one of which is uniform, the distributionof has smooth min-entropy .변수 는 d{\비트에 대한 균일한 분포를 나타내며, 진정한 랜덤 시드를 나타낸다.
즉, 길이 의 작은 균일한 시드를 사용함으로써 합병은 m{\}min-entropy를 갖는 것에 {{\인 문자열을 반환한다. 는 m mmin-ent-entropy가 있는 문자열과의 통계적 거리가 보다 작다는 것을 의미한다.
주의사항:분포의 랜덤성을 측정하는 몇 가지 개념이 있다. 랜덤 변수 Z의 최소 엔트로피는 큰 k 로 정의되며, Z {\ Z}의 가장 가능성이 높은 이2 -k {\ 2를 초과하지 않는 확률로 발생한다문자열의 최소 엔트로피는 문자열에서 추출할 수 있는 무작위성의 양에 대한 상한이다.[1]
매개변수
합병을 구축할 때 최적화해야 할 세 가지 매개변수가 있다.
- 출력의 최소 m 은(는) 가능한 한 높아야 하며, 그러면 더 많은 비트가 출력에서 추출될 수 있다.
- 은(는) 가능한 한 작아야 하며, 그 경우 합병의 산출물에 추출기를 적용한 후에는 결과가 균일성에 가까워질 것이다.
- 시드 길이 은(는) 가능한 한 작아야 하며, 그렇게 되면 합병이 작동하기 위해 더 적은 수의 초기 실제 무작위 비트를 요구하기 때문이다.
합병에 대한 명시적 구조는 비교적 양호한 매개변수로 알려져 있다.예를 들어 드비르와 위그더슨의 구조는 다음을 제공한다.[2]For every and integer , if , there exists an explicit -merger 화살표 이 (가) 다음과 같이 하십시오.
그 증거는 건설적이며 주어진 매개변수의 다항식 시간에 그러한 합병을 구축할 수 있다.
사용법
매개변수가 좋은 무작위 추출기를 생산하기 위해 합병을 사용하는 것이 가능하다.추출기가 최소 엔트로피가 높은 랜덤 변수를 취하여 더 작은 랜덤 변수를 반환하지만 균일성에 가까운 변수를 반환하는 함수라는 점을 상기하십시오.임의의 최소-엔트로피 추출기는 다음과 같은 합병 기반 체계를 사용하여 얻을 수 있다.[2][3]
- 높은 최소 엔트로피의 소스가 주어지면 블록으로 분할한다.알려진 결과에 의해,[4] 적어도 이러한 파티션들 중 하나는 블록 소스로서 높은 최소 엔트로피를 가질 것이다.
- 블록 추출기를 모든 블록에 개별적으로 도포하십시오.이것은 더 약한 종류의 추출기로, 그것을 위한 좋은 구조물이 알려져 있다.[2]적어도 하나의 블록이 높은 최소 엔트로피를 가지므로, 적어도 하나의 출력은 균일성에 매우 가깝다.
- 합병을 사용하여 모든 이전 출력을 하나의 문자열로 결합하십시오.합병이 잘 되면 그 길이에 비해 결과 문자열의 최소 엔트로피가 매우 높을 것이다.
- 랜덤성을 추출하려면 매우 높은 최소 엔트로피 소스에만 사용되는 알려진 추출기를 사용하십시오.
위의 계획의 본질은 임의의 최소 엔트로피가 있는 문자열을 더 작은 문자열로 변환하기 위해 합병을 사용하는 동시에, 그 과정에서 많은 최소 엔트로피가 손실되지 않도록 하는 것이다.이 새로운 문자열은 그 길이에 비해 매우 높은 미니 엔트로피를 가지고 있으며, 그런 유형의 문자열에만 적용되는 오래된 알려진 추출기를 사용할 수 있다.
참고 항목
참조
- ^ De, Portmann, Vidick and Renner (2009). "Trevisan's extractor in the presence of quantum side information". SIAM Journal on Computing. 41 (4): 915–940. arXiv:0912.5514. doi:10.1137/100813683.
{{cite journal}}
: CS1 maint: 복수 이름: 저자 목록 (링크) 2.2절. - ^ a b c Zeev Dvir & Avi Wigderson. "Kakeya sets, new mergers and old extractors" (PDF).
- ^ Noam Nissan & Amnon Ta-Shma. "Extracting Randomness: A Survey and New Constructions" (PDF). 섹션 4.3.
- ^ Amnon Ta-Shma. "Refining Randomness". 박사 논문