무작위 시퀀스

Random sequence

확률 이론과 통계학에서는 무작위 시퀀스의 개념이 필수적이다.개념은 일반적으로 랜덤 변수의 시퀀스 개념에 의존하며, 많은 통계적 논의는 "X1,...,X를n 독립된 랜덤 변수가 되게 하라"라는 단어로 시작한다.그러나 D. H. 레머가 1951년에 말했듯이, "임의의 순서는 모호한 개념이다..."통계학자와 함께 사용되는 일정한 수의 시험을 통과하며, 각 용어는 아직 작성되지 않은 사람에게 예측할 수 없다."[1]

자명 확률 이론은 의도적으로 무작위 수열의 정의를 회피한다.[2]전통적인 확률 이론은 특정한 순서가 무작위인지 여부를 명시하지 않고, 일반적으로 랜덤성의 정의를 가정하여 랜덤 변수와 확률적 시퀀스의 특성에 대해 논의한다.부르바키 학교는 "임의의 순서를 고려하자"는 성명을 언어의 남용으로 간주했다.[3]

초기 역사

에밀 보렐은 1909년에 공식적으로 무작위성을 언급한 최초의 수학자 중 한 명이었다.[4]1919년 리처드 폰 미제스는 무작위 순서가 아닌 집합적이라는 용어를 사용했지만 대수의 법칙에서 영감을 받은 알고리즘 무작위성의 첫 번째 정의를 내렸다.폰 미제스는 도박 시스템의 불가능성의 개념을 이용하여 0과 1의 무한 시퀀스를 주파수 안정성 속성을 가지고 있어 편중되지 않으면 임의로 정의했다. 즉, 0의 주파수는 1/2로 가고, 0에서 선택할 수 있는 모든 하위 시퀀스는 "적절한" 선택 방법에 의해 편중되지 않는다.[5]

폰 미제스가 부과한 하위순서 선정기준이 중요한데, 왜냐하면 01010101이기는 하지만...편향되지 않아, 홀수 포지션을 선택해서 00000000을 얻을 수 있어...무작위가 아니라폰 미제스는 하위 순서에 대한 적절한 선택 규칙에 대한 정의를 완전히 공식화한 적이 없지만, 1940년에 알론조 교회는 이 규칙을 모든 재귀 함수로 정의했는데, 이 순서의 첫 번째 N 요소를 읽은 후 N + 1 원소를 선택할지 여부를 결정한다.Church는 계산 가능한 기능 분야의 개척자였고, 그가 만든 정의는 계산가능성을 위해 Church Turing Statement에 의존했다.[6]이러한 정의를 흔히 미세스-처치 임의성(Mises-Church randomness라고 부른다.

현대적 접근 방식

20세기 동안 무작위 시퀀스 정의에 대한 다양한 기술적 접근방식이 개발되었고 이제 세 가지 뚜렷한 패러다임을 확인할 수 있다.1960년대 중반, A. N. Kolmogorov와 D. W. Loveland는 독립적으로 더 관대한 선택 규칙을 제안했다.[7][8]그들이 보기에 Church의 재귀적 함수 정의는 요소들을 순서대로 읽었다는 점에서 너무 제한적이었다.대신 그들은 수열의 N 요소를 읽은 부분 계산 가능한 프로세스에 기초하여 규칙을 제안하고, 아직 읽지 않은 다른 요소를 선택할지 여부를 결정한다.이 정의는 종종 콜모고로프-러블랜드 확률론이라고 불린다.그러나 이 방법은 무작위성의 일반적인 개념에 부합하지 않는 콜모고로프-러블랜드 확률적 수열이 있다는 것을 보여준 알렉산더 셴에 의해 너무 약한 것으로 간주되었다.

1966년 Per Martin-Löf는 현재 일반적으로 알고리즘 무작위성의 가장 만족스러운 개념으로 간주되는 새로운 개념을 도입했다.그의 원래 정의에는 측정 이론이 포함되었지만, 나중에 그것이 콜모고로프 복잡성의 관점에서 표현될 수 있다는 것이 밝혀졌다.콜모고로프의 무작위 문자열의 정의는 범용 튜링 기계를 통해 자신보다 짧은 설명이 없으면 무작위라는 것이었다.[9]

무작위 시퀀스 처리를 위한 세 가지 기본 패러다임이 등장했다.[10]

  • 주파수/측정-이론적 접근법.이러한 접근은 리차드 폰 미제스와 알론조 교회의 작업에서 시작되었다.1960년대에 Per Martin-Löf는 그러한 주파수 기반 확률적 특성을 코딩하는 세트들이 특별한 종류의 측정 제로 세트라는 것을 알게 되었고, 모든 측정 세트를 효과적으로 고려함으로써 보다 일반적이고 부드러운 정의를 얻을 수 있다는 것을 알게 되었다.
  • 복잡성/압축성 접근 방식.이 패러다임은 A에 의해 옹호되었다.레오니드 레빈, 그레고리 차이틴의 기부와 함께 N. 콜모고로프.유한 시퀀스의 경우, 콜모고로프는 길이 n의 이항 문자열의 무작위성을 길이 n에 의해 정규화된 엔트로피(또는 콜모고로프 복잡성)로 정의한다.즉, 문자열의 Kolmogorov 복잡성이 n에 가까우면 매우 무작위적이고, 복잡성이 n보다 훨씬 낮으면 그렇게 무작위적이지 않다.랜덤성의 이중 개념은 압축성 ‒ 시퀀스가 랜덤할수록 압축성이 떨어지며, 그 반대의 경우도 마찬가지다.
  • 예측 가능성 접근 방식.이 패러다임은 Claus P 때문이다. Schnorr 그리고 전통적인 확률 이론에 사용된 마팅세일즈와는 약간 다른 건설적인 마팅세일즈의 정의를 사용한다.[11]슈노르는 선택적 베팅 전략의 존재가 편향된 하위 시퀀스에 대한 선택 규칙의 존재를 어떻게 암시하는지 보여주었다.만약 어떤 사람이 어떤 순서에 따라 건설적으로 성공하는 대신 어떤 순서에 따라 성공하도록 재귀 마팅게일만 요구한다면, 어떤 사람은 재귀적 무작위성의 개념을 얻게 된다.[further explanation needed]융게 왕은 재귀적 무작위 개념과 슈노르의 무작위 개념은 다르다는 것을 보여주었다[12][13].[further explanation needed]

대부분의 경우, 세 가지 패러다임(종종 동등성)과 관련된 이론이 입증되었다.[14]

참고 항목

참조

메모들

  1. ^ 2006년 필립 J. 데이비스의 수학 상식과 상식에서의 "Randomant라는 단어가 의미하는 것" ISBN1-56881-270-1페이지 180-182
  2. ^ Jozsef Beck 2009 ISBN 0-8218-4756-2페이지 44페이지에 의한 이산수학의 필연적 무작위성
  3. ^ 알고리즘: Vladimir Andreevich Uspenskiĭ, Alekseĭ, lʹvovich Seminov 1993 Springer ISBN 0-7923-2210-X 페이지 166에 의한 주요 아이디어와 응용
  4. ^ E. Borel, Les 확률형 표시제 등 응용 프로그램 산술 렌드.Circ. Mat. Palermo 27 (1909) 247–271
  5. ^ STACS 2007의 라우란트 비엔에누 "Kolmogorov Loveland Stochasticity": 제24회 볼프강 토마스 ISBN 3-540-70917-7페이지
  6. ^ Church, Alonzo (1940). "On the Concept of Random Sequence". Bull. Amer. Math. Soc. 46 (2): 130–136. doi:10.1090/S0002-9904-1940-07154-X.
  7. ^ A. N. Kolmogorov, 정보 및 전송의 정보 문제의 양적 정의에 대한 세 가지 접근방식, 1:1–7, 1965.
  8. ^ D.W. 러브랜드, 폰 미제스의 무작위 시퀀스 Z 개념에 대한 새로운 해석.수학. 로직 그룬들라겐 수학 12 (1966) 279–294
  9. ^ Kolmogorov 복잡성과 M. B. Vitány 1997년 0387948686페이지 149-151에 의한 적용에 대한 소개
  10. ^ R. 다우니, 컴퓨터 과학 2004의 수학적 기초에서 알고리즘 무작위성의 최근 진보: 지지 피알라, 바클라브 쿠벡 2004 ISBN 3-540-22823-3 페이지 44
  11. ^ Schnorr, C. P. (1971). "A unified approach to the definition of a random sequence". Mathematical Systems Theory. 5 (3): 246–258. doi:10.1007/bf01694181.
  12. ^ 용게 왕: 무작위성과 복잡성.박사 학위 논문, 1996.http://webpages.uncc.edu/yonwang/papers/IPL97.pdf
  13. ^ Wang, Yongge (1999). "A separation of two randomness concepts". Information Processing Letters. 69 (3): 115–118. CiteSeerX 10.1.1.46.199. doi:10.1016/S0020-0190(98)00202-6.
  14. ^ 볼프강 머클, 오토마타의 콜모고로프 러브랜드 스토크라스틱성, 언어와 프로그래밍: 제29회 국제 콜로키움, ICALP 2002, 피터 위드마이어 외 연구진ISBN 3-540-43864-5 페이지 391

외부 링크