Losowa sekwencja

Pojęcie sekwencji losowej jest niezbędne w teorii prawdopodobieństwa i statystyce . Koncepcja generalnie opiera się na pojęciu sekwencji zmiennych losowych , a wiele dyskusji statystycznych zaczyna się od słów „niech X 1 ,…, X n będą niezależnymi zmiennymi losowymi…”. Jeszcze jako DH Lehmer stwierdził w 1951 r.: „Losowa sekwencja to niejasne pojęcie… w którym każdy termin jest nieprzewidywalny dla niewtajemniczonych i którego cyfry przechodzą pewną liczbę testów tradycyjnych dla statystyków”.

Aksjomatyczna teoria prawdopodobieństwa celowo unika definicji sekwencji losowej. Tradycyjna teoria prawdopodobieństwa nie stwierdza, czy dana sekwencja jest losowa, ale ogólnie przechodzi do omawiania właściwości zmiennych losowych i sekwencji stochastycznych, przyjmując jakąś definicję losowości. Szkoła Bourbaki uznała stwierdzenie „rozważmy przypadkową sekwencję” za nadużycie językowe .

Wczesna historia

Émile Borel był jednym z pierwszych matematyków, który formalnie zajął się losowością w 1909 r. W 1919 r. Richard von Mises podał pierwszą definicję losowości algorytmicznej, zainspirowaną prawem wielkich liczb, chociaż użył terminu zbiorowość , a nie sekwencja losowa. Posługując się koncepcją niemożliwości istnienia systemu hazardowego , von Mises zdefiniował nieskończoną sekwencję zer i jedynek jako losową, jeśli nie jest ona obciążona właściwością stabilności częstotliwości, tj. można z niej wybierać „właściwą” metodą selekcji, również nie jest stronnicza.

Kryterium wyboru podsekwencji narzucone przez von Misesa jest ważne, ponieważ chociaż 0101010101... nie jest obciążone, wybierając nieparzyste pozycje, otrzymujemy 000000... co nie jest przypadkowe. Von Mises nigdy całkowicie nie sformalizował swojej definicji właściwej reguły wyboru dla podsekwencji, ale w 1940 roku Alonzo Church zdefiniował ją jako dowolną funkcję rekurencyjną , która po przeczytaniu pierwszych N elementów sekwencji decyduje, czy chce wybrać element o numerze N + 1. Church był pionierem w dziedzinie funkcji obliczeniowych, a definicja, którą stworzył, opierała się na tezie Churcha Turinga dla obliczalności. Ta definicja jest często nazywana losowością Misesa-Churcha .

Nowoczesne podejścia

W XX wieku opracowano różne techniczne podejścia do definiowania sekwencji losowych i obecnie można zidentyfikować trzy różne paradygmaty. W połowie lat 60. AN Kołmogorow i DW Loveland niezależnie zaproponowali bardziej liberalną zasadę selekcji. Ich zdaniem definicja funkcji rekurencyjnej Churcha była zbyt restrykcyjna, ponieważ odczytywała elementy w kolejności. Zamiast tego zaproponowali regułę opartą na częściowo obliczalnym procesie, który po przeczytaniu dowolnych N elementów sekwencji decyduje, czy chce wybrać inny element, który nie został jeszcze odczytany. Ta definicja jest często nazywana Stochastyczność Kołmogorowa-Lovelanda . Ale ta metoda została uznana za zbyt słabą przez Alexandra Shena, który wykazał, że istnieje sekwencja stochastyczna Kołmogorowa-Lovelanda, która nie jest zgodna z ogólnym pojęciem losowości.

W 1966 roku Per Martin-Löf wprowadził nowe pojęcie, które jest obecnie powszechnie uważane za najbardziej satysfakcjonujące pojęcie losowości algorytmicznej . Jego pierwotna definicja obejmowała teorię miary, ale później wykazano, że można ją wyrazić w kategoriach złożoności Kołmogorowa . Definicja losowego ciągu Kołmogorowa była taka, że ​​​​jest on losowy, jeśli nie ma opisu krótszego niż on sam za pośrednictwem uniwersalnej maszyny Turinga .

Pojawiły się teraz trzy podstawowe paradygmaty radzenia sobie z sekwencjami losowymi:

  • częstotliwości / miary . Podejście to rozpoczęło się od prac Richarda von Misesa i Alonzo Churcha. W latach sześćdziesiątych Per Martin-Löf zauważył, że zbiory kodujące takie właściwości stochastyczne oparte na częstotliwościach są szczególnym rodzajem zbiorów miar zerowych i że bardziej ogólną i płynną definicję można uzyskać, biorąc pod uwagę wszystkie skutecznie mierzące zbiory zerowe. Podejście
  • złożoność /ściśliwość . Ten paradygmat był orędownikiem AN Kołmogorowa wraz z wkładem Leonida Levina i Gregory'ego Chaitina . Dla sekwencji skończonych Kołmogorow definiuje losowość ciągu binarnego o długości n jako entropię (lub złożoność Kołmogorowa ) znormalizowaną przez długość n . Innymi słowy, jeśli złożoność łańcucha Kołmogorowa jest bliska n , jest to bardzo losowe; jeśli złożoność jest znacznie poniżej n , nie jest tak losowa. Podwójną koncepcją losowości jest ściśliwość — im bardziej losowa jest sekwencja, tym mniej można ją skompresować i na odwrót.
  • Podejście przewidywalności . Ten paradygmat pochodzi od Clausa P. Schnorra i używa nieco innej definicji martyngałów konstruktywnych niż martyngały stosowane w tradycyjnej teorii prawdopodobieństwa. Schnorr pokazał, w jaki sposób istnienie selektywnej strategii obstawiania implikuje istnienie reguły selekcji dla tendencyjnej podsekwencji. Jeśli ktoś wymaga tylko rekurencyjnego martyngału, aby odnieść sukces w sekwencji, zamiast konstruktywnie odnieść sukces w sekwencji, wówczas otrzymuje koncepcję losowości rekurencyjnej. [ potrzebne dalsze wyjaśnienia ] Yongge Wang pokazał, że koncepcja losowości rekurencyjnej różni się od koncepcji losowości Schnorra. [ potrzebne dalsze wyjaśnienia ]

W większości przypadków udowodniono twierdzenia dotyczące trzech paradygmatów (często równoważności).

Zobacz też

Notatki

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Random_sequence&oldid=1136395612 ”