Mennyi a számláló átlag növekedési sebessége?

"A számláló minden növelése után lévő várakozások függetlenek a korábbiaktól."

"Ha 0-át olvas akkor vár egy időegységet, majd a sorra következő elemre ugrik, ha az is 0 akkor dupla annyi időt vár"

Ok. Sikerült megértenem a feladatot.

Meg merném kockáztatni hogy a sebessége tart a 0-hoz.

Váltakozó 1-es és 0-s részsorozatokra bontod a végtelen sorozatodat. Minden részsorozatnak lesz egy hossza.

Az 1-es sorozatok átlagos növekménye 2, mivel szumma n*0.5^n 1-től végtelenig pontosan 2. A szorzatban az n a növekmény, a 0.5^n pedig az n hosszú sorozat valószínűsége.

A 0-s sorozatok átlagos várakozási ideje szumma 2^(n-1) * 0.5^n szintén 1-től végtelenig. Ez viszont nem korlátos, hiszen a végtelen összeg minden tagjának értéke 0.5. Tehát az átlagos várakozási idő végtelen.

A sorozat átlagos növekedési sebessége így valóban nulla lesz. Ahhoz hogy nullánál nagyobb legyen a növekedési sebesség, az kell, hogy a várakozáshoz hasonlóan a számlálód is (legalább) exponenciálisan növekedjen, ha több 1-es jön sorozatban.

Illetve még nem igazán sikerült kihozni, próbálgatok/keresgélek.

Inkább olyan képlet kéne, hogy N hosszú sorozat esetén mihez tart a csak 1 hosszú 0-k ból álló sorozatokban szereplõ 0-k aránya.

Azt gyanítom, hogy 0-hoz, így, a legalább 2 hosszú csupa 0 sorozatban levõ 0-k aránya 1/2-hez tart, stb. És ezt így végig minden számra. Ez már adná az állítást.

Egy n (nagy szám) hosszú sorozatban kb. n/8, n/16, n/32, ... db 1-2-3... hosszú 0-ás sorozat lesz.

Ezeket szorozva 2 hatványaival megkapjuk az össz. várakozási időt:

1*n/8 + 2*n/16 + 4*n/32 +...

Látszik, hogy az összeg n/8 * log2(n) körül lesz, egységre vetítve a várakozási idő ~ log2(n)/8.

Tehát valóban, a hosszal nő az átlagosan várható várakozási idő, csökken a sebesség (a végtelenben nullára).

Egy 640 milliós szimulációban az 1,2,3,4,... hosszú 0-sorozatok db-számai:

79999097, 40002406, 19994703, 10007622, 5001861, 2500279, 1248367, 624457, 312854, 156298, 78171, 39044, 19419, 9835, 4818, 2335, 1203, 585, 324, 167, 68, 36, 21, 7, 5, 2, 1, 0.

Jól illeszkedik az előbb leírtakhoz.

Na jó, de azok többsége hosszabb 0-sorozatok része.

Gondolkodj így: az n elemből körülbelül n/2 egy 0 vagy 1-sorozat első eleme (hiszen az előző számjegy 50% eséllyel más volt, mint ő).

Ebből az n/2 elemből n/4 egy 0-sorozat első eleme (hiszen ugyanannyi 0-sorozat van, mint 1-sorozat)

Ebből az n/4 elemből n/8 egy egyelemű 0-sorozat egyetlen eleme (hiszen 50% eséllyel 1-es jön utánuk, megszakítva a sorozatot).

Szóval ezért van kb. n/8 egyelemű 0-sorozat. És ugyanezt a gondolatmenetet követve n/16 kételemű 0-sorozat, n/32 háromelemű, stb.