Satunnainen järjestys - Random sequence

Satunnaisjärjestyksen käsite on olennainen todennäköisyysteoriassa ja tilastoissa . Konsepti on yleensä riippuvainen käsitteestä sekvenssin sekä satunnaismuuttujia ja monia tilastollisia keskustelut alkaa sanoilla "let X 1 , ..., X n riippumattomia satunnaismuuttujia ...". Silti, kuten DH Lehmer totesi vuonna 1951: "Satunnainen sekvenssi on epämääräinen käsitys ... jossa kukin termi on arvaamaton aloittelijalle ja jonka numerot läpäisevät tietyn määrän tilastotieteilijöiden kanssa perinteisiä testejä".

Aksiomaattisen todennäköisyyden teoria välttää tarkoituksella satunnaisen sekvenssin määrittelyä. Perinteisessä todennäköisyysteoriassa ei ilmoiteta, onko tietty sekvenssi satunnainen, vaan yleensä keskustellaan satunnaismuuttujien ja stokastisten sekvenssien ominaisuuksista olettaen jonkinlainen satunnaisuuden määritelmä. Bourbaki koulu piti ilmoitus "Tarkastellaan satunnaisessa järjestyksessä" an kielen väärinkäyttöä .

Aikainen historia

Émile Borel oli yksi ensimmäisistä matemaatikoista, joka käsitteli virallisesti satunnaisuutta vuonna 1909. Vuonna 1919 Richard von Mises antoi ensimmäisen määritelmän algoritmisesta satunnaisuudesta, jonka innoittamana oli suurten lukujen laki, vaikka hän käytti termiä kollektiivinen eikä satunnaisjärjestys. Rahapelijärjestelmän mahdottomuuden käsitteen avulla von Mises määritteli loputtoman nollasekvenssin ja satunnaisjakson, jos sitä ei ole puolueellinen sillä, että sillä on taajuusstabiilisuusominaisuus, eli nollien taajuus menee 1/2: een ja jokainen osajoukko me voi valita siitä "oikealla" valintamenetelmällä ei myöskään ole puolueellinen.

Von Misesin asettama alijärjestyksen valintakriteeri on tärkeä, koska vaikka 0101010101 ... ei ole puolueellinen, saamme parittomat sijainnit 000000 ... mikä ei ole satunnainen. Von Mises ei koskaan formalisoinut määritelmäänsä oikeasta alisekvenssien valintasäännöstä, mutta vuonna 1940 Alonzo Church määritteli sen rekursiiviseksi funktioksi, joka lukenut sekvenssin ensimmäiset N alkua päättää, haluako se valita elementin numeron  N  + 1. Kirkko oli edelläkävijä laskettavien toimintojen alalla, ja hänen tekemänsä määritelmän mukaan laskentakelpoisuus perustui kirkon Turingin tutkielmaan . Tätä määritelmää kutsutaan usein Mises-kirkon satunnaisuudeksi .

Nykyaikaiset lähestymistavat

1900-luvulla kehitettiin erilaisia ​​teknisiä lähestymistapoja satunnaisten sekvenssien määrittelemiseen, ja nyt voidaan tunnistaa kolme erillistä paradigmaa. 1960-luvun puolivälissä AN Kolmogorov ja DW Loveland ehdottivat itsenäisesti sallivampaa valintasääntöä. Heidän mielestään kirkon rekursiivinen funktion määritelmä oli liian rajoittava siinä mielessä, että se luki elementit järjestyksessä. Sen sijaan he ehdottivat sääntöä, joka perustuu osittain laskettavaan prosessiin, joka lukenut kaikki sekvenssin N elementtiä päättää, haluatko valita toisen elementin, jota ei ole vielä luettu. Tätä määritelmää kutsutaan usein Kolmogorov – Loveland-stokastiseksi . Mutta Alexander Shen piti tätä menetelmää liian heikkona, joka osoitti, että on olemassa Kolmogorov – Loveland-stokastinen sekvenssi, joka ei ole yleisen satunnaisuuden käsitteen mukainen.

Vuonna 1966 Per Martin-Löf esitteli uuden käsitteen, jota pidetään nyt yleisesti tyydyttävimpänä algoritmisen satunnaisuuden käsitteenä . Hänen alkuperäiseen määritelmäänsä liittyi mittausteoria, mutta myöhemmin osoitettiin, että se voidaan ilmaista Kolmogorovin monimutkaisuutena . Kolmogorovin määritelmä satunnaisesta merkkijonosta oli, että se on satunnainen, jos sillä ei ole itseään lyhyempää kuvausta universaalin Turingin koneen kautta .

Satunnaisten sekvenssien käsittelemiseksi on nyt syntynyt kolme perusparadigmaa:

  • Taajuus / toimenpide teoreettista lähestymistapaa. Tämä lähestymistapa alkoi Richard von Misesin ja Alonzo Churchin työstä. 1960-luvulla Per Martin-Löf huomasi, että tällaisia ​​taajuuspohjaisia ​​stokastisia ominaisuuksia koodaavat joukot ovat erityinen mitta-nollajoukko ja että yleisempi ja sujuvampi määritelmä voidaan saada ottamalla huomioon kaikki tehokkaasti mitatut nollajoukot.
  • Monimutkaisuus / puristuvuus lähestymistapa. Tätä paradigmaa kannatti AN Kolmogorov yhdessä Leonid Levinin ja Gregory Chaitinin kanssa . Rajoitetuille sekvensseille Kolmogorov määrittelee binäärijonon, jonka pituus on n , satunnaisuuden entropiana (tai Kolmogorovin kompleksisuutena ), joka on normalisoitu pituudella n . Toisin sanoen, jos merkkijonon Kolmogorov-monimutkaisuus on lähellä n: tä , se on hyvin satunnainen; jos monimutkaisuus on paljon alle n , se ei ole niin satunnainen. Satunnaisuuden kaksoiskäsite on kokoonpuristuvuus - mitä satunnaisempi sekvenssi on, sitä vähemmän pakattava ja päinvastoin.
  • Ennustettavuus lähestymistapa. Tämä paradigma johtuu Claus P.Schnorrista, ja siinä käytetään hieman erilaista konstruktivisten martingalien määritelmää kuin perinteisessä todennäköisyysteoriassa käytetyissä martingaleissa. Schnorr osoitti, kuinka valikoivan vedonlyöntistrategian olemassaolo merkitsi valintasäännön olemassaoloa puolueelliselle osajonolle. Jos vaaditaan vain rekursiivista martingalea menestymään sekvenssissä sen sijaan, että sekvenssissä onnistutaan rakentavasti, saadaan rekursiivisen satunnaisuuden käsite. Yongge Wang osoitti, että rekursiivinen satunnaisuuskäsite eroaa Schnorrin satunnaisuuskäsitteestä.

Useimmissa tapauksissa näitä kolmea paradigmaa (usein vastaavuus) koskevat lauseet on osoitettu.

Katso myös

Viitteet

Huomautuksia

Ulkoiset linkit