Ciąg algorytmicznie losowy - Algorithmically random sequence

Intuicyjnie, algorytmicznie losowa sekwencja (lub losowa sekwencja ) to sekwencja cyfr binarnych, która pojawia się losowo dla dowolnego algorytmu działającego na uniwersalnej maszynie Turinga (bez prefiksów lub nie) . Pojęcie to można zastosować analogicznie do ciągów na dowolnym alfabecie skończonym (np. cyfry dziesiętne). Sekwencje losowe są kluczowymi przedmiotami badań w algorytmicznej teorii informacji .

Ponieważ czasami rozważane są różne typy algorytmów, od algorytmów z określonymi ograniczeniami czasu działania po algorytmy, które mogą zadawać pytania maszynie wyroczni , istnieją różne pojęcia losowości. Najczęstszym z nich jest losowość Martina-Löfa ( K-losowość lub 1-losowość ), ale istnieją również silniejsze i słabsze formy losowości. Kiedy termin „algorytmicznie losowy” jest używany w odniesieniu do określonej pojedynczej (skończonej lub nieskończonej) sekwencji bez wyjaśnienia, zwykle przyjmuje się, że oznacza on „niekompresowalny” lub, w przypadku gdy sekwencja jest nieskończona i przedrostek algorytmicznie losowy (tj. K -nieściśliwy), „Martin-Löf-Chaitin losowo”.

Ważne jest, aby odróżnić losowość algorytmiczną od losowości stochastycznej. W przeciwieństwie do losowości algorytmicznej, która jest zdefiniowana dla procesów obliczeniowych (a zatem deterministycznych), losowość stochastyczna jest zwykle określana jako właściwość sekwencji, o której wiadomo a priori, że jest generowana (lub jest wynikiem) przez niezależny, identycznie rozłożony, równie prawdopodobny stochastyczny proces.

Ponieważ nieskończone ciągi cyfr binarnych można utożsamiać z liczbami rzeczywistymi w przedziale jednostkowym, losowe ciągi binarne są często nazywane (algorytmicznie) losowymi liczbami rzeczywistymi . Dodatkowo nieskończone ciągi binarne odpowiadają charakterystycznym funkcjom zbiorów liczb naturalnych; dlatego te sekwencje mogą być postrzegane jako zbiory liczb naturalnych.

Klasa wszystkich losowych (binarnych) sekwencji Martina-Löfa jest oznaczona przez RAND lub MLR.

Historia

Pierwszą odpowiednią definicję ciągu losowego podał Per Martin-Löf w 1966 roku. Wcześniejsi badacze, tacy jak Richard von Mises, próbowali sformalizować pojęcie testu na losowość , aby zdefiniować ciąg losowy jako taki, który przeszedł wszystkie testy na losowość. losowość; jednak dokładne pojęcie testu losowości pozostało niejasne. Kluczowym spostrzeżeniem Martina-Löfa było wykorzystanie teorii obliczeń do formalnego zdefiniowania pojęcia testu na losowość. Kontrastuje to z ideą losowości w prawdopodobieństwie ; w tej teorii o żadnym konkretnym elemencie przestrzeni próbki nie można powiedzieć, że jest losowy.

Od samego początku wykazano, że losowość Martina-Löfa dopuszcza wiele równoważnych charakteryzacji — pod względem kompresji , testów losowości i hazardu — które mają niewielkie zewnętrzne podobieństwo do pierwotnej definicji, ale każda z nich spełnia nasze intuicyjne pojęcie właściwości, które sekwencje powinny posiadać: losowe sekwencje powinny być nieściśliwy, powinni przechodzić testy statystyczne dla przypadkowości i powinno to być trudne, aby pieniądze zakłady na nich. Istnienie tych wielu definicji losowości Martina-Löfa oraz stabilność tych definicji w różnych modelach obliczeniowych, dostarczają dowodów, że losowość Martina-Löfa jest fundamentalną właściwością matematyki, a nie przypadkiem konkretnego modelu Martina-Löfa. Tezę, że definicja losowości Martina-Löfa „poprawnie” oddaje intuicyjne pojęcie losowości została nazwana Tezą Martina-Löfa-Chaitina ; jest ona nieco podobna do tezy Kościoła-Turinga .

Trzy równoważne definicje

Oryginalna definicja ciągu losowego Martina-Löfa dotyczyła konstruktywnych pokryw zerowych; zdefiniował sekwencję jako losową, jeśli nie jest zawarta w żadnej takiej okładce. Gregory Chaitin , Leonid Levin i Claus-Peter Schnorr udowodnili charakterystykę pod względem złożoności algorytmicznej : sekwencja jest losowa, jeśli istnieje jednorodne ograniczenie ściśliwości jej początkowych segmentów. Schnorr podał trzecią równoważną definicję w kategoriach martyngałów . Książka Li i Vitanyi „ Wprowadzenie do złożoności Kołmogorowa i jej zastosowań” jest standardowym wprowadzeniem do tych idei.

Złożoność algorytmiczna (Chaitin 1969, Schnorr 1973, Levin 1973): Złożoność algorytmiczna (znana również jako (bez przedrostków) złożoność Kołmogorowa lub złożoność wielkości programu) może być traktowana jako dolna granica ściśliwości algorytmicznej skończonego ciągu znaków lub cyfr binarnych). Każdej takiej sekwencji w przypisuje liczbę naturalną K(w), która intuicyjnie mierzy minimalną długość programu komputerowego (napisanego w jakimś ustalonym języku programowania), który nie pobiera danych wejściowych i po uruchomieniu wyświetli w . Wymagana jest złożoność bez prefiksów: po programie (sekwencja 0 i 1) następuje nieskończony ciąg zer, a długość programu (zakładając, że się zatrzymuje) zawiera liczbę zer po prawej stronie program, który odczytuje uniwersalna maszyna Turinga. Dodatkowe wymaganie jest potrzebne, ponieważ możemy wybrać taką długość, aby długość kodowała informacje o podciągu. Mając liczbę naturalną c i ciąg w , mówimy, że w jest c -niekompresowalne, jeśli . ${\ Displaystyle K (w) \ geq | w | -c}$

Nieskończona sekwencja S jest losowa Martina-Löfa wtedy i tylko wtedy, gdy istnieje stała c taka, że wszystkie skończone przedrostki S są c -niekompresowalne.

Konstruktywne okładki zerowe (Martin-Löf 1966): To jest oryginalna definicja Martina-Löfa. Dla skończonego ciągu binarnego w niech C _w oznacza cylinder wygenerowany przez w . Jest to zbiór wszystkich ciągów nieskończonych zaczynających się na w , który jest podstawowym zbiorem otwartym w przestrzeni Cantora . Produkt środek μ ( C _w ) siłownika generowanej przez wagowych określa się 2 ^{- | w |}. Każdy otwarty podzbiór przestrzeni Cantora jest sumą przeliczalnego ciągu rozłącznych podstawowych zbiorów otwartych, a miara zbioru otwartego jest sumą miar dowolnego takiego ciągu. Skuteczny zbiór otwarty jest zbiorem otwartym, który jest sumą sekwencji podstawowych zbiorów otwartych określonych przez rekurencyjnie przeliczalny sekwencji łańcuchów binarnych. Konstruktywne pokrywa zerowy lub skutecznym środkiem 0 zestaw jest rekursywnie wyliczalnych sekwencja skutecznych otwartych odbiorników takie, że i dla każdej liczby naturalnej ı . Każde efektywne pokrycie wartości zerowej określa zbiór miary 0, czyli przecięcie zbiorów . ${\ Displaystyle U_ {i}}$ ${\ Displaystyle U_ {i + 1} \ podseteq U_ {i}}$ ${\ Displaystyle \ mu (U_ {i}) \ równa 2 ^ {-i}}$ $G_{\delta}$ ${\ Displaystyle U_ {i}}$

Sekwencję definiuje się jako losową Martina-Löfa, jeśli nie jest zawarta w żadnym zbiorze określonym przez konstruktywne pokrycie zerowe. $G_{\delta}$

Konstruktywne martyngały (Schnorr 1971): Martyngał jest funkcją taką, że dla wszystkich skończonych ciągów w , , gdzie jest konkatenacją ciągów a i b . Nazywa się to „warunkiem uczciwości”: jeśli martingale jest postrzegany jako strategia obstawiania, powyższy warunek wymaga, aby obstawiający grał przeciwko uczciwym kursom. Martyngał d mówi się, że udaje się na sekwencji S jeśli którym to pierwsze N bitów S . Martyngał d jest konstruktywny (znany również jako słabo obliczalny , niższy półobliczalny ), jeśli istnieje funkcja obliczalna taka, że dla wszystkich skończonych ciągów binarnych w ${\ Displaystyle d: \ {0,1 \} ^ {*} \ do [0, \ infty)}$ ${\ Displaystyle d (w) = (d (w ^ {\ małe zmarszczone} 0) + d (w ^ {\ małe zmarszczone} 1))/2}$ $a^{\małe zmarszczenie}b$ ${\ Displaystyle \ Limsup _ {n \ do \ infty} d (S \ upharpoonright n) = \ infty}$ ${\ Displaystyle S \ upharpoonright n}$ ${\ Displaystyle {\ widehat {d}}: \ {0,1 \} ^ {*} \ razy \ mathbb {N} \ do {\ mathbb {Q}}}$

${\widehat {d}}(w,t)\leq {\widehat {d}}(w,t+1)<d(w),$ dla wszystkich liczb całkowitych dodatnich t ,
${\ Displaystyle \ lim _ {t \ do \ infty} {\ widehat {d}} (w, t) = d (w).}$

Sekwencja jest losowa Martina-Löfa wtedy i tylko wtedy, gdy nie powiedzie się w niej żaden konstruktywny martyngał.

Interpretacje definicji

Charakteryzacja złożoności Kołmogorowa przekazuje intuicję, że ciąg losowy jest niekompresowalny: żaden prefiks nie może zostać utworzony przez program znacznie krótszy niż prefiks.

Charakterystyka zerowej okładki przekazuje intuicję, że losowa liczba rzeczywista nie powinna mieć żadnej właściwości, która jest „niezwykła”. Każdy zestaw taktu 0 można traktować jako rzadko spotykaną właściwość. Nie jest możliwe, aby sekwencja nie znajdowała się w zestawach bez taktu 0, ponieważ każdy zestaw jednopunktowy ma miarę 0. Pomysł Martina-Löfa polegał na ograniczeniu definicji do zestawu zerowego, który można skutecznie opisać; definicja efektywnego pokrycia zerowego określa policzalny zbiór efektywnie opisywanych zestawów miary 0 i definiuje sekwencję jako losową, jeśli nie znajduje się w żadnym z tych konkretnych zestawów miary 0. Ponieważ suma policzalnego zbioru zbiorów miar 0 ma miarę 0, ta definicja natychmiast prowadzi do twierdzenia, że istnieje zbiór losowych sekwencji miar 1. Zauważmy, że jeśli utożsamimy przestrzeń Cantora ciągów binarnych z przedziałem [0,1] liczb rzeczywistych, to miara na przestrzeni Cantora zgadza się z miarą Lebesgue'a .

Charakterystyka martyngałów wyraża intuicję, że żadna skuteczna procedura nie powinna być w stanie zarobić pieniędzy na obstawianiu losowej sekwencji. Martingale d to strategia obstawiania. d odczytuje skończony ciąg w i stawia pieniądze na następny bit. Obstawia część swoich pieniędzy, że następny bit będzie miał wartość 0, a resztę pieniędzy, że następny bit będzie miał wartość 1. d podwaja pieniądze, które postawił na bit, który faktycznie wystąpił, a resztę przegrywa. d ( w ) to ilość pieniędzy, jaką ma po zobaczeniu ciągu w . Ponieważ zakład postawiony po obejrzeniu ciągu w można obliczyć z wartości d ( w ), d ( w 0) i d ( w 1), obliczenie posiadanej kwoty jest równoznaczne z obliczeniem zakładu. Charakterystyka Martingale mówi, że żadna strategia obstawiania realizowana przez dowolny komputer (nawet w słabym sensie strategii konstruktywnych, które niekoniecznie są obliczalne ) nie może zarabiać pieniędzy obstawiając ciąg losowy.

Własności i przykłady ciągów losowych Martina-Löfa

Prawdopodobieństwo zakończenia pracy Chaitina Ω jest przykładem sekwencji losowej.
RAND ^c ( uzupełnienie RAND) jest podzbiorem miary 0 zbioru wszystkich nieskończonych sekwencji. Wynika to z faktu, że każde konstruktywne pokrycie wartości zerowej obejmuje zbiór miary 0, istnieje tylko przeliczalnie wiele konstruktywnych pokryw wartości zerowych, a policzalna suma zestawów miar 0 ma miarę 0. Oznacza to, że RAND jest podzbiorem miary 1 tego zbioru. wszystkich nieskończonych ciągów.
Każda losowa sekwencja jest normalna .
Istnieje konstruktywna zerowa osłona RAND ^c . Oznacza to, że wszystkie skuteczne testy na losowość (tj. konstruktywne zakrycia wartości zerowych) są w pewnym sensie objęte tym uniwersalnym testem na losowość, ponieważ każda sekwencja, która przejdzie ten pojedynczy test na losowość, przejdzie wszystkie testy na losowość. (Martin-Löf 1966)
Istnieje uniwersalny konstruktywny martyngał d . Ten martyngał jest uniwersalny w tym sensie, że biorąc pod uwagę dowolny konstruktywny martyngał d , jeśli d powiedzie się na sekwencji, to d uda się również na tej sekwencji. W ten sposób d powiedzie się w każdej sekwencji w RAND ^c (ale ponieważ d jest konstruktywne, nie powiedzie się w żadnej sekwencji w RAND). (Schnorr 1971)
Klasa RAND jest podzbiorem przestrzeni Cantora, gdzie odnosi się do drugiego poziomu hierarchii arytmetycznej . Dzieje się tak, ponieważ sekwencja S jest w RAND wtedy i tylko wtedy, gdy istnieje jakiś otwarty zbiór w uniwersalnej efektywnej osłonie zerowej, która nie zawiera S ; ta właściwość może być postrzegana jako definiowalna za pomocą formuły. ${\ Displaystyle \ Sigma _ {2} ^ {0}}$ ${\ Displaystyle \ Sigma _ {2} ^ {0}}$ ${\ Displaystyle \ Sigma _ {2} ^ {0}}$
Istnieje losowa sekwencja , która jest obliczalna względem wyroczni dla problemu Haltinga. (Schnorr 1971) Ω Chaitina jest przykładem takiej sekwencji. ${\ Displaystyle \ Delta _ {2} ^ {0}}$
Żadna losowa sekwencja nie jest rozstrzygalna , obliczalnie przeliczalna ani współobliczalna-przeliczalna . Ponieważ odpowiadają one poziomom , , i hierarchii arytmetycznej , oznacza to, że jest to najniższy poziom w hierarchii arytmetycznej, na którym można znaleźć ciągi losowe. ${\ Displaystyle \ Delta _ {1} ^ {0}}$ ${\ Displaystyle \ Sigma _ {1} ^ {0}}$ ${\ Displaystyle \ Pi _ {1} ^ {0}}$ ${\ Displaystyle \ Delta _ {2} ^ {0}}$
Każda sekwencja jest Turinga sprowadzalna do jakiegoś losowego ciągu. (Kučera 1985/1989, Gács 1986). Istnieją więc ciągi losowe o dowolnie wysokim stopniu Turinga .

Względna losowość

Ponieważ każda z równoważnych definicji losowego ciągu Martina-Löfa opiera się na tym, co jest obliczalne przez maszynę Turinga, można naturalnie zapytać, co jest obliczalne przez maszynę wyroczni Turinga . W przypadku ustalonej wyroczni A sekwencja B, która jest nie tylko losowa, ale w rzeczywistości spełnia równoważne definicje obliczalności względem A (np. żaden martyngał, który jest konstruktywny względem wyroczni A nie powiedzie się na B ) jest określany jako losowy względny do A . Dwie sekwencje, choć same w sobie losowe, mogą zawierać bardzo podobne informacje, a zatem żaden z nich nie będzie losowy względem drugiego. Za każdym razem, gdy następuje redukcja Turinga z jednej sekwencji do drugiej, druga sekwencja nie może być losowa w stosunku do pierwszej, tak jak sekwencje obliczalne same w sobie nie są losowe; w szczególności oznacza to, że Ω Chaitina nie jest losowe w stosunku do problemu zatrzymania .

Ważnym wynikiem odnoszącym się do losowości względnej jest twierdzenie van Lambalgena , które mówi, że jeśli C jest ciągiem złożonym z A i B przez przeplatanie pierwszego bitu A , pierwszego bitu B , drugiego bitu A , drugiego bitu z B itd., wtedy C jest algorytmicznie losowe wtedy i tylko wtedy, gdy A jest algorytmicznie losowe, a B jest algorytmicznie losowe względem A . Ściśle powiązaną konsekwencją jest to, że jeśli A i B same są losowe, to A jest losowe względem B wtedy i tylko wtedy, gdy B jest losowe względem A .

Silniejszy niż losowość Martina-Löfa

Losowość względna daje nam pierwsze pojęcie, które jest silniejsze niż losowość Martina-Löfa, która jest losowością względem jakiejś ustalonej wyroczni A . Dla każdej wyroczni jest to co najmniej tak samo silne, a dla większości wyroczni jest ściśle silniejsze, ponieważ istnieją losowe sekwencje Martina-Löfa, które nie są losowe względem wyroczni A . Ważnymi wyroczniami, często branymi pod uwagę, są problem zatrzymania i wyrocznia n- tego skoku , ponieważ te wyrocznie są w stanie odpowiedzieć na konkretne pytania, które pojawiają się naturalnie. Sekwencja losowa w stosunku do wyroczni nazywana jest n- losową; ciąg jest więc 1-losowy wtedy i tylko wtedy, gdy jest losowy Martina-Löfa. Ciąg, który jest n -losowy dla każdego n nazywamy arytmetycznie losowym. Sekwencje n- losowe pojawiają się czasem przy rozważaniu bardziej skomplikowanych własności. Na przykład jest tylko przeliczalnie wiele zestawów, więc można by pomyśleć, że nie powinny one być losowe. Jednak prawdopodobieństwo zatrzymania Ω jest i 1-losowe; dopiero po osiągnięciu 2-losowości niemożliwe jest, aby zbiór losowy był . $\pusty zestaw '$ ${\ Displaystyle \ pusty zestaw ^ {(n)}}$ ${\ Displaystyle \ pusty zestaw ^ {(n-1)}}$ ${\ Displaystyle \ Delta _ {2} ^ {0}}$ ${\ Displaystyle \ Delta _ {2} ^ {0}}$ ${\ Displaystyle \ Delta _ {2} ^ {0}}$

Słabsza niż losowość Martina-Löfa

Dodatkowo istnieje kilka pojęć losowości, które są słabsze niż losowość Martina-Löfa. Niektóre z nich to słaba 1-losowość, losowość Schnorra, losowość obliczalna, losowość częściowa obliczalna. Yongge Wang wykazał, że losowość Schnorra różni się od losowości obliczalnej. Ponadto wiadomo, że losowość Kołmogorowa-Lovelanda nie jest silniejsza niż losowość Martina-Löfa, ale nie wiadomo, czy jest faktycznie słabsza.

Na przeciwległym końcu spektrum losowości znajduje się pojęcie zbioru K-trywialnego . Zbiory te są antylosowe w tym sensie, że wszystkie początkowe segmenty są kompresowalne logarytmicznie (tj. dla każdego początkowego segmentu w), ale nie są obliczalne. ${\ Displaystyle K (w) \ równoważnik K (| w |) + b}$

Zobacz też

Bibliografia

Dalsza lektura

Downey, Rod; Hirschfeldt, Denis R.; Nies, Andrzej; Terwijn, Sebastian A. (2006). „Kalibracja losowości” . Biuletyn Logiki Symbolicznej . 12 (3/4): 411–491. CiteSeerX 10.1.1.135.4162 . doi : 10.2178/bsl/1154698741 . Zarchiwizowane od oryginału w dniu 2016-02-02.
Gács, Peter (1986). „Każda sekwencja daje się zredukować do losowej” (PDF) . Informacja i kontrola . 70 (2/3): 186–192. doi : 10.1016/s0019-9958(86)80004-3 .
Kučera, A. (1985). „Zmierz, Π⁰
₁-klasy i kompletne rozszerzenia PA". Tydzień Teorii Rekurencji . Notatki z matematyki. 1141 . Springer-Verlag. s. 245–259. doi : 10.1007/BFb0076224 . ISBN 978-3-540-39596-6.

Kučera, A. (1989). „O wykorzystaniu funkcji nierekurencyjnych po przekątnej”. Studia z logiki i podstaw matematyki . 129 . Północna Holandia. s. 219-239.

Levin, L. (1973). „O pojęciu losowej sekwencji”. Matematyka radziecka - Dokłady . 14 : 1413-1416.

Li, M.; Vitanyi, PMB (1997). Wprowadzenie do złożoności Kołmogorowa i jej zastosowań (wyd. drugie). Berlin: Springer-Verlag.

Martin-Löf, P. (1966). „Definicja ciągów losowych” . Informacja i kontrola . 9 (6): 602–619. doi : 10.1016/s0019-9958(66)80018-9 .
Nies, André (2009). Obliczalność i losowość . Oksfordzkie przewodniki logiczne. 51 . Oksford: Oxford University Press. Numer ISBN 978-0-19-923076-1. Zbl 1169.03034 .

Schnorr, CP (1971). „Zunifikowane podejście do definicji sekwencji losowej”. Teoria systemów matematycznych . 5 (3): 246–258. doi : 10.1007/BF01694181 . S2CID 8931514 .

Schnorr, Claus P. (1973). „Złożoność procesu i efektywne testy losowe” . Journal of Computer and System Sciences . 7 (4): 376–388. doi : 10.1016/s0022-0000(73)80030-3 .

Chaitin, Gregory J. (1969). „O długości programów do obliczania skończonych sekwencji binarnych: względy statystyczne”. Dziennik ACM . 16 (1): 145–159. doi : 10.1145/321495.321506 . S2CID 8209877 .

Ville, J. (1939). Etude critique de la conception de collectif . Paryż: Gauthier-Villars.

Languages

In other projects