Tilfeldig sekvens

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".

Aksiomatisk sannsynlighetsteori unngår bevisst å definere en tilfeldig sekvens. 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.

Tidlig historie 
Émile Borel var en av de første matematikere som formelt henviste til tilfedlighet i 1909. 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.

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. Denne definisjonen er ofte kalt Mises-Church tilfeldighet.

Moderne tilnærminger 
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. 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.

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

 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. 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.

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

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.

Se også 

 Tilfeldighet
 Tilfeldighetens historie
 Tilfeldig tallgenerator
 Syv tilfeldighetstilstander
 Statistisk tilfedlighet

Referanser 

 Sergio B. Volchan What Is a Random Sequence?  The American Mathematical Monthly, Vol. 109, 2002, ss. 46–63

Noter

Eksterne lenker 
 Video om frekvensstabilitet - hvorfor mennesker ikke kan "gjette" tilfeldig
 Randomness tests by Terry Ritter

Følger og rekker
Sannsynlighet
Statistisk teori