Tilfeldig sekvens: Forskjell mellom sideversjoner

Fra Wikipedia, den frie encyklopedi
Neste endring →
Slettet innhold Innhold lagt til
VisuellWikitekst
Jokkeen (diskusjon | bidrag)
42 redigeringer
Oversatt den engelske siden på emnet.
(Ingen forskjell)

Sideversjonen fra 18. apr. 2018 kl. 23:51

Fortuna, lykkens gudinne avbildet av Tadeusz Kuntze, 1754 (Nasjonalmuseet i Warszawa).

Konseptet om en tilfeldig sekvens er essensiell i sannsynlighetsteori og statistikk. Konseptet avhenger vanligvis av en sekvens' forestilling av en tilfeldig variabel, og mange statistiske diskusjoner starter med ordene "la X1,...,Xn være tilfeldige uavhengige variabler...". Fortsatt, som D. H. Lehmer uttalte i 1951: "En tilfeldig sekvens er en vag betegnelse... hvor hvert begrep er uforutsigbart for de uinitierte og hvis siffer går igjennom et visst antall tester som er tradisjonelle hos statistikere".[1]

Aksiomatisk sannsynlighetsteori unngår bevisst å definere en tilfeldig sekvens.[2] Tradisjonell sannsynlighetsteori uttaler seg ikke om en bestemt sekvens er tilfeldig, men fortsetter vanligvis med å diskutere tilfeldige variablers egenskaper og stokastiske sekvener antar en definisjon av tilfeldighet. Bourbaki skolen betrakter utsagnet "la oss vurdere en tilfeldig sekvens" som misbruk av språket.[3]

Tidlig historie

Émile Borel var en av de første matematikere til å først adressere tilfedlighet i 1909.[4] I 1919 gav Richard von Mises den første definisjonen av algoritmisk tilfeldighet, som var inspirert av store talls lov, selv om han brukte betegnelsen kollektiv heller enn tilfeldig sekvens. Ved å bruke konseptet om et gambling systems umulighet definerte von Mises en uendelig sekvens av nuller og ett-tall som tilfeldig hvis den ikke er forutinntatt å inneha egenskapen frekvensstabilitet i.e. nullenes frekvens går mot 1/2 og hver undersekvens vi kan velge fra den ved en "rett" valgsmetode er heller ikke forutinntatt.[5]

Undersekvensens utvalgskriterion pålagt av von Mises er viktig, fordi selv om sekvensen 0101010101... ikke er partisk kan man, ved å velge annenhvert tall, få 000000... som ikke er tilfeldig. Von Mises formaliserte aldri definisjonen om rett utvalgsregel for undersekvenser fullstendig, men i 1940 definerte Alonzo Church det som at hvilken som helst rekursiv funksjon som har lest de første N elementer i en sekvens bestemmer om den vil selv velge element nummer N+1. Church var en pioner innen beregningsfunksjoner, og definisjonen han lagde var avhengig av Church-Turing avhandlingen for bergnbarhet.[6] Denne definisjonen er ofte kalt Mises-Church tilfeldighet.

Moderne tilnærminger

Under det 21. århundre ble det utarbeidet ulike tekniske tilnærminger for å definere tilfeldige sekvenser, og tre distinkte paradigmer er i dag å identifisere. På 60-tallet foreslo A. N. Kolmogorov og D. W. Loveland uavhengig en mer givende utvalgsregel.[7][8] Fra deres syn var Church sin definisjon av den rekursive funksjonen for restriktiv i den forstand at den leste elementenes rekkefølge. De foreslo i steden en regel basert på en delvis beregnelig prosess som har lest noen N elementer i sekvensen og bestemmer om den vil velge et annet element som ennå ikke har blitt lest. Denne definisjonen er ofte kalt Kolmogorov-Lovelands stokastisitet. Denne metoden ble igjen ansett å være for svak av Alexander Shen, som viste at det er en stokastisk Kolmogorov-Loveland sekvens som ikke samsvarer med den generelle tilfeldighetsbegrepet.

I 1966 introduserte Per Martin-Löf en ny betegnelse som nå er ansett som den mest tilfredsstillende betegnelsen av algoritmisk tilfeldighet. Hans opprinnelige definisjon involverte målteori, men det ble senere vist at det kan bli uttrykt i form av Kolmogorovsk kompleksitet. Kolmogorovs definisjon av en tilfeldig streng var at det er tilfeldig dersom den ikke har noen beskrivelse kortere enn seg selv via en universell Turingmaskin.[9]

Tre grunnleggende paradigmer som håndterer tilfeldige sekvenser har nå fremkommet:[10]

  • En frekvens / målteoretisk tilnærming. Denne tilnærmingen startet med Richard von Mises og Alonzo Church sitt arbeid. På 60-tallet merket Per Martin-Löf at settene som koder slike frekvensbaserte stokastiske egenskaper er en spesiell type nullmålingssett, og at en mer generell og glatt definisjon kan fåes ved å vurdere alle effektive nullmålingssett.
  • En kompleksitets / komprimerbarhets tilnærming. Dette paradigmet var mestret av A. N. Kolmogorov sammen med bidragsyterne Levin og Gregory Chaitin. For avgrensede tilfeldige sekvenser definerte Kolmogorov "tilfeldigheten" som entropien, i.e. Kolmogorovsk kompleksitet, i en streng av lengde K med nuller og ettall som nærheten av dens entropi til K, i.e. hvis strengens kompleksitet er nær K er den veldig tilfeldig, og er dens kompleksitet langt under K er den ikke så tilfeldig.
  • En forutsigbarhets tilnærming. Dette paradigmet skyldtes Claus P. Schnorr og bruker en noe ulik definisjon av konstruktive martingaler enn martingaler brukt i tradisjonell sannsynlighetsteori.[11] Schnorr viste hvordan en selektiv oddsstrategis eksistens antydet en utvalgsregels eksistens for en partisk undersekvens. Dersom en kun krever en rekursiv martingale å lykkes på en sekvsens i steden for å konstruktivt lykkes på en sekvens, så får en rekursive tilfeldighetskonsepter. Yongge Wang viste[12][13] at et rekursivt tilfeldighetskonsept er ulikt fra Schorrs tilfeldighetskonsept.

I de fleste tilfeller har teoremer angående de tre paradigmene (ofte om ekvivalens) blitt bevist.[14]

Det er viktig å innse at for hver av de gitte definisjonene ovenfor er for uendelige sekvenser. Dersom en legger til en milliard nuller foran den tilfeldige sekvensen vil fortsatt den nye sekvensen bli ansett som tilfeldig. Derfor må enhver bruk av disse konseptene på praktiske problemer utføres med varsomhet.[15]

Se også

Referanser

Noter

  1. ^ "What is meant by the word Random" in Mathematics and common sense by Philip J. Davis 2006 ISBN 1-56881-270-1 pages 180-182
  2. ^ Inevitable Randomness in Discrete Mathematics by József Beck 2009 ISBN 0-8218-4756-2 page 44
  3. ^ Algorithms: main ideas and applications by Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer ISBN 0-7923-2210-X page 166
  4. ^ E. Borel, Les probabilites denombrables et leurs applications arithmetique Rend. Circ. Mat. Palermo 27 (1909) 247-271
  5. ^ Laurant Bienvenu "Kolmogorov Loveland Stochastocity" in STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science by Wolfgang Thomas ISBN 3-540-70917-7 page 260
  6. ^ Church, Alonzo (1940). «On the Concept of Random Sequence». Bull. Amer. Math. Soc. 46: 130–136. doi:10.1090/S0002-9904-1940-07154-X. 
  7. ^ A. N. Kolmogorov, Three approaches to the quantitative definition of information Problems of Information and Transmission, 1(1):1--7, 1965.
  8. ^ D.W. Loveland, A new interpretation of von Mises' concept of random sequence Z. Math. Logik Grundlagen Math 12 (1966) 279-294
  9. ^ An introduction to Kolmogorov complexity and its applications by Ming Li, P. M. B. Vitányi 1997 0387948686 pages 149-151
  10. ^ R. Downey, Some Recent Progress in Algorithmic Randomness in Mathematical foundations of computer science 2004: by Jiří Fiala, Václav Koubek 2004 ISBN 3-540-22823-3 page 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. ^ Yongge Wang: Randomness and Complexity. PhD Thesis, 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. doi:10.1016/S0020-0190(98)00202-6. 
  14. ^ Wolfgan Merkel, Kolmogorov Loveland Stochasticity in Automata, languages and programming: 29th international colloquium, ICALP 2002, by Peter Widmayer et al. ISBN 3-540-43864-5 page 391
  15. ^ Algorithms: main ideas and applications by Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer ISBN 0-7923-2210-X page 176

Eksterne linker

Hentet fra «https://no.wikipedia.org/w/index.php?title=Tilfeldig_sekvens&oldid=18444417»