Delta
  Wiw.pl   Na bieżąco:  Informacje   Co nowego   Matematyka i przyroda:  Astronomia   Biologia   Fizyka   Matematyka   Modelowanie rzeczywistości   Humanistyka:  Filozofia   Historia   Kultura antyczna   Literatura   Sztuka   Czytaj:  Biblioteka   Delta   Wielcy i więksi   Przydatne:  Słowniki   Co i gdzie studiować   Wszechświat w obrazkach    
  Jesteś tutaj:  Wirtualny Wszechświat > Delta > Matematyka - spis artykułów >  JAK ODRÓŻNIĆ CIĄG LOSOWY OD NIELOSOWEGO?  
  Jesteś tutaj
Wybór artykułów z miesięcznika "Delta"
"Delta" to miesięcznik popularyzujący matematykę, fizykę i astronomię na bardzo wysokim poziomie, wydawany od 1974 roku.
Wirtualny Wszechświat prezentuje wybór tekstów publikowanych w "Delcie" od pierwszego numeru po początek XXI wieku.
  Szukacz
Delta 07/1990
Rafał SZTENCEL
JAK ODRÓŻNIĆ CIĄG LOSOWY OD NIELOSOWEGO?

Słowo "losowy" będzie tu miało znaczenie "powstały w wyniku niezależnych rzutów symetryczną monetą". Przypatrzmy się poniższym trzem ciągom orłów i reszek:

(1) RRRORORROO OORRORRORR OOORRRRROO RORROROORO RRROROOROO OROORROOOR OROOROOROR RRORORROOO ORORRORROR ROROORORRO

(2) RRORORORRR RORRORORRO RRORROOOOR ORROORORRR ORORORRORO OOORRORORR RRROROORRR OROOORROOR OROORORRRO ROOORORROR

(3) OOORORRROR OROOOOROOO OROROROORO RORORROROR OOORORROOO OOOOORRORR ROORRORROR OORRORRROR OOORROOOOR RROOORRRRO.

Dwa z nich napisane zostały przez człowieka, jeden powstał w wyniku komputerowej symulacji rzutów symetryczną monetą. Czy można go rozpoznać?

Istnieje zaskakująco prosty sposób. Znajdźmy w każdym ciągu najdłuższą serię jednakowych symboli. Pierwszy ciąg zawiera serię pięciu reszek (w trzeciej dziesiątce), drugi - czterech reszek (pierwsza i druga dziesiątka), wreszcie trzeci - aż ośmiu orłów (piąta i szósta dziesiątka). Otóż człowiek będzie miał pewne opory przed umieszczeniem w ciągu długiej serii orłów lub reszek. Natura takich oporów nie ma, bo nie ma pamięci. Dlatego całkiem niezły test losowości dla ciągów o długości 100 polega na uznaniu za losowe ciągów z najdłuższą serią liczącą 6 lub więcej symboli. Ciąg (3) zostanie wtedy słusznie zakwalifikowany jako losowy.

Podany sposób nie jest, oczywiście, doskonały. Może się zdarzyć, że ciąg losowy zostanie uznany za nielosowy i odwrotnie: ciąg nielosowy uznany za losowy. Jak zobaczymy, można nietrudno oszacować prawdopodobieństwo błędu pierwszego rodzaju. Z błędem drugiego rodzaju jest nieco gorzej - trzeba by znać probabilistyczną charakterystykę źródła. W każdym razie niechęć do pisania długich serii gwarantuje, że błąd drugiego rodzaju zdarza się rzadko.

Teraz zastąpimy trudne rachunki symulacją komputerową. Jeśli ktoś wykona 10 000 eksperymentów, polegających na 100-krotnym rzucie monetą, to otrzyma pewnie wyniki zbliżone do poniższych:

liczba eksperymentów maksymalna długość serii
1 3
255 4
1658 5
2629 6
2221 7
1517 8
837 9
443 10
239 11
92 12
52 13
28 14
17 15
7 16
1 17
2 18
0 19
1 20

Widać teraz, że błąd pierwszego rodzaju zdarza się w około 19% przypadków (dla maksymalnej długości serii nie przekraczającej 5). Można by zmniejszyć o 1 krytyczną wartość długości serii - szansa błędu pierwszego rodzaju zmalałaby do 2,5%, ale wzrosłaby znacznie szansa błędu drugiego rodzaju.

Popatrzmy teraz na sytuację bardziej ogólnie. Mówiąc uczenie, mamy hipotezę dotyczącą rozkładu prawdopodobieństwa na przestrzeni próbek. Mówi ona, że szanse otrzymania każdego z 2100 możliwych ciągów orłów i reszek są równe.

Eksperyment może obalić hipotezę, może też nie być podstaw do jej odrzucenia. Prowadzi to do podziału przestrzeni próbek na dwa zbiory. W naszym przypadku podział nastąpił ze względu na maksymalną długość serii; należało przy tym zadbać o to, by prawdopodobieństwo błędu nie było zbyt duże. Jest teraz oczywiste, że testów losowości można wymyślić mnóstwo. Pierwszy z brzegu przykład to test oparty na liczbie serii. Za mała lub za duża liczba serii jest podejrzana i świadczy o braku losowości. Trzeba by ułożyć tabelę analogiczną do zamieszczonej wyżej (tu zresztą można się obejść bez komputera).

Interesujące byłoby zbadanie rozkładu maksymalnej długości serii w zależności od długości ciągu. Na rysunkach pokazano wyniki symulacji dla ciągów o długościach 10, 50, 100, 250.



powiększ...

Widać, że średnie są z grubsza proporcjonalne do logarytmu długości ciągu. Jak to uzasadnić teoretycznie? A z jakim typem rozkładu prawdopodobieństwa mamy do czynienia?




[góra strony]
Wiw.pl  |  Na bieżąco  |  Informacje  |  Co nowego  |  Matematyka i przyroda  |  Astronomia  |  Biologia  |  Fizyka  |  Matematyka  |  Modelowanie rzeczywistości  |  Humanistyka  |  Filozofia  |  Historia  |  Kultura antyczna  |  Literatura  |  Sztuka  |  Czytaj  |  Biblioteka  |  Delta  |  Wielcy i więksi  |  Przydatne  |  Słowniki  |  Co i gdzie studiować  |  Wszechświat w obrazkach