Ha a sorozat hossza n, akkor az információtartlama legyen legalább n- log n?

Ez egy definíció, és azt definiálja, hogy mikor nevezel véletlennek egy sorozatot.

Feltételezi, hogy az "információtartalom" korábban már definiálásra került.

Ezek nem általános definíciók, hanem a tanár/könyv írója vezette be őket, szóval lapozz csak szépen vissza.

Az "információtartalom" lehet, hogy a Kolgorov bonyolultság ( [link] )(de persze lehet akármi más is).

Amit ez a definíció takarni akar, az az, hogy ha egy sorozat nem véletlenszerű, akkor van benne valami szabályosság, és a sorozat több elemét is le lehet esetleg írni kevesebb információval is. Pl. ha van ez a sorozatod:

1, 3, 5, 7, 9, 11, 13

Akkor ez 7 számot jelent. De ha úgy írom le, hogy egy 7 elemű számtani sorozat, 1-gyel kezdődően, és 2-es differenciával, akkor ha még azt, hogy „számtani sorozat” egy kóddal jelzem, akkor is 4 számmal leírtam a sorozatot.

Vagy ha sok benne az ismétlődő elem, akkor is ez a helyzet:

1, 5, 5, 5, 5, 5, 2, 2, 2, 2, 8, 8

12 számjegy. De 8 számjeggyel leírható: 1 darab 1-es, 5 darab 5-ös, 4 darab 2-es, 2 darab 8-as.

Ha a sorozat véletlenszerű, akkor nem lehet szabályok leírásával „tömöríteni” az információt. Mivel véletlenszerű, lehet, hogy van benne mondjuk 4 egymást követő azonos számjegy, azt esetleg lehet rövidíteni, de ezeknek az előfordulása kellően ritka ahhoz, hogy n növekedésével az ilyen csak log(n) ütemben növekedjen.

Ugyan nem egy tökéletes definíció a véletlenszerűségre, de elmegy.