Hopp til innhold

Tilfeldig sekvens

Fra Wikipedia, den frie encyklopedi
Fortuna, lykkens gudinne, avbildet av Tadeusz Kuntze, 1754 (Nasjonalmuseet i Warszawa).

Konseptet tilfeldig sekvens er essensiell i sannsynlighetsteori og statistikk. Konseptet avhenger vanligvis av forestillingen av en sekvens' tilfeldige variabel. Mange statistiske diskusjoner starter med "la være tilfeldige uavhengige variabler...". Selv 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, for stokastiske sekvener har behov for en definisjon av tilfeldighet. Bourbaki-skolen betrakter utsagnet "la oss vurdere en tilfeldig sekvens" som misbruk av språket.[3]

Tidlig historie

[rediger | rediger kilde]

Émile Borel var en av de første matematikere som formelt henviste til 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 heller brukte betegnelsen kollektiv enn tilfeldig sekvens. Ved å bruke konseptet om et gamblingsystems umulighet definerte von Mises en uendelig sekvens av nuller og ettall som tilfeldig hvis den ikke er forutinntatt ved å 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 fastsatt av von Mises er viktig, fordi selv om sekvensen 0101010101... ikke er forutinntatt kan man, ved å velge annenhvert tall, få 000000... som ikke er tilfeldig. Von Mises selv beskrev 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-Turings avhandling for bergnbarhet.[6] Denne definisjonen er ofte kalt Mises-Church tilfeldighet.[7]

Moderne tilnærminger

[rediger | rediger kilde]

I det 19. århundre ble det utarbeidet ulike tekniske tilnærminger for å definere tilfeldige sekvenser, og i dag er tre distinkte paradigmer brukt. På 60-tallet foreslo A. N. Kolmogorov og D. W. Loveland hver for seg en mer givende utvalgsregel.[8][9] 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 sbestemmer så om den selv vil velge et nytt element som ennå ikke har blitt lest. Denne definisjonen er ofte kalt Kolmogorov-Lovelands stokastisitet. Denne metoden ble igjen ansett for å være for svak av Alexander Shen, som viste at det finnes en stokastisk Kolmogorov-Loveland sekvens som ikke samsvarer med den generelle tilfeldighetsbegrepet.

I 1966 introduserte Per Martin-Löf et nytt begrep 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 den er tilfeldig dersom den ikke har noen beskrivelse kortere enn seg selv via en universell turingmaskin.[10]

De tre grunnleggende paradigmene som håndterer tilfeldige sekvenser er som spesifisert:[11]

  • 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 glattere 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 en streng av lengde K med nuller og ettalls entropi (Kolmogorovsk kompleksitet) som nærheten av dens entropi til K. Dvs. 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 etablerte Claus P. Schnorr, som bruker en noe ulik definisjon av konstruktive martingaler enn martingaler brukt i tradisjonell sannsynlighetsteori.[12] 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 å suksessivt lykkes på en sekvens, resulterer dette i rekursive tilfeldighetskonsepter. Yongge Wang viste at et rekursivt tilfeldighetskonsept er ulikt fra Schorrs tilfeldighetskonsept.[13][14]

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

Det er viktig å forstå at for hver av de gitte definisjonene ovenfor gjelder det 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.[16]

Se også

[rediger | rediger kilde]

Referanser

[rediger | rediger kilde]

Noter

[rediger | rediger kilde]
  1. ^ "What is meant by the word Random" i Mathematics and common sense av Philip J. Davis 2006 ISBN 1-56881-270-1 side 180-182
  2. ^ Inevitable Randomness in Discrete Mathematics av József Beck 2009 ISBN 0-8218-4756-2 side 44
  3. ^ Algorithms: main ideas and applications av Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer ISBN 0-7923-2210-X side 166
  4. ^ E. Borel, Les probabilites denombrables et leurs applications arithmetique Rend. Circ. Mat. Palermo 27 (1909) side 247-271
  5. ^ Laurant Bienvenu "Kolmogorov Loveland Stochastocity" i STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science av Wolfgang Thomas ISBN 3-540-70917-7 side 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. ^ Shen, Alexander; Uspensky, Vladimir Andreevich; Vereshchagin, N. K. (2013). Kolmogorov Complexity and Algorithmic Randomness. Moskva: American Mathematical Society. ISBN 9781470431822. 
  8. ^ A. N. Kolmogorov, Three approaches to the quantitative definition of information Problems of Information and Transmission, 1(1):1--7, 1965.
  9. ^ D.W. Loveland, A new interpretation of von Mises' concept of random sequence Z. Math. Logik Grundlagen Math 12 (1966) 279-294
  10. ^ An introduction to Kolmogorov complexity and its applications av Ming Li, P. M. B. Vitányi 1997 0387948686 side 149-151
  11. ^ R. Downey, Some Recent Progress in Algorithmic Randomness in Mathematical foundations of computer science 2004: av Jiří Fiala, Václav Koubek 2004 ISBN 3-540-22823-3 side 44
  12. ^ 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. 
  13. ^ Yongge Wang: Randomness and Complexity. PhD Thesis, 1996. http://webpages.uncc.edu/yonwang/papers/IPL97.pdf
  14. ^ Wang, Yongge (1999). «A separation of two randomness concepts». Information Processing Letters. 69 (3): 115–118. doi:10.1016/S0020-0190(98)00202-6. 
  15. ^ Wolfgan Merkel, Kolmogorov Loveland Stochasticity i Automata, languages and programming: 29th international colloquium, ICALP 2002, av Peter Widmayer et al. ISBN 3-540-43864-5 side 391
  16. ^ Algorithms: main ideas and applications av Vladimir Andreevich Uspenskiĭ, Alekseĭ, Lʹvovich Semenov 1993 Springer ISBN 0-7923-2210-X side 176

Eksterne lenker

[rediger | rediger kilde]
Autoritetsdata
Hentet fra «https://no.wikipedia.org/w/index.php?title=Tilfeldig_sekvens&oldid=24712871»