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

"Én nem látom. Annyit látok, hogy a 0-hoz konvergál a növekvési sebesség, ha n a végtelenbe tart."

Azt hiszem hogy Borel tételébõl adódik hogy a (végtelen) sorozatod 1 valószínûséggel normális lesz, azaz ilyen:

[link]

És ha jól gondolom, akkor egy normális számra az adott szubstringek száma konvergál, azaz, elég nagy N-re a 00-k aránya már soha a büdös életben nem lehet 1/16+1/2^100 fölött, nem csak nagyon ritkán, de soha.

(ebbõl a megfontolásból azt hiszem még nem jön ki az aszimptotika, de, Borel eljárását végigcsinálva valszeg kijön hogy 1 valószínûséggel ennyi az aszimptotika)

Írtad, nem érted, hogy n hosszú sorozatra az átlagos várakozási idő (sebesség reciproka) miért log(n)-nel arányos. Ez egy teljesen jogos kérdés: valóban nem log(n)-nel arányos, a válasz írója valamit benézett. A helyzet rosszabb: n-nel arányos.

Csak hogy valamit tisztázzunk, a válaszok többsége úgy született, hogy a várakozási idő egy 0-0-0-0 sorozatban nem 1+2+4+8 = 16-1 hanem simán 8. Ez egy félreértés volt az eredeti kiírás kétértelműsége miatt, a lényegen persze egyáltalán nem változtat, szinte csak egy skálázási faktor az egész. De tudod mit, használjuk a te 1+2+4+8-as várakozási szabályodat.

Legyen t(n) az n hosszú sorozatok átlagos teljes lefutási ideje, c(n) pedig a számláló átlagos értéke.

Az n hosszú stringhez egy új számjegyet csapva:

c(n+1) = c(n) + 0.5 [ami amúgy = n/2]

t(n+1) = t(n) + 0.25*(n+2)

Ez utóbbi nem egyértelmű, így kiírom:

1/2 eséllyel 1-es jön, ekkor a futásidő nem változik.

1/2 eséllyel 0 jön, ekkor a futásidő aszerint nő, hogy milyen hosszú 0-sorozat végéhez csapódik. Bontsuk le ez utóbbit:

1/4 eséllyel 1-eshez csapódik, ekkor 1 mp plusz futásidőt jelent az új 0

1/8 eséllyel egy árva 0-hoz csapódik: +2 mp

1/16 eséllyel két 0-hoz csapódik: +4 mp

...

1/2^(n+1) eséllyel n-1 darab 0-hoz: +2^(n-1) mp

végül szintén 1/2^(n+1) eséllyel n darab 0-hoz: +2^n mp

Tehát van n+1 elemünk. A valószínűségével súlyozva mindegyik 1/4 mp-nyi futásidővel járul hozzá az összeghez, kivéve az utolsót, ami kétszer annyival (próbáld ki papíron kis n-re ha nem látod elsőre). Azaz 0.25*(n+2) másodperccel nő az n hosszúságúról n+1 hosszúságúra bővített sorozat teljes futásideje.

Így, hogy megvan a c(n) -> c(n+1) és t(n) -> t(n+1) frissítési szabály, már könnyű belátni, hogy t(n)/c(n) aszimptotikusan n-nel lesz arányos, a sebesség pedig ebből következően hiperbolikusan tart 0-hoz.

#8 vagyok, újra próbálkozom, nézzük, hogy mit "néztem be"! :D

Valóban, ahogy előző a 2. bek.-ben írta, a várakozásokat sima 2-hatványnak vettem, a #11-ben leírtak szerint ennek kb. duplájával kell számolni.

A log2(n) viszont teljesen jó.

n számot ha felezgetjük, log2(n) lépésben jutunk az 1-hez, és nincs tovább, nincs értelme a töredékeknek.

Tehát pl. n=2^10=1024, felezgetjük 512,256,128,64,32,16,8,4,2,1 azaz log2(2^10)=10 lépésben jutunk 1-hez.

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

összegnek log2(n/8) tagja lesz, mindegyik = n/8-cal, az összeg:

n/8 * log2(n/8) = n/8 * (log2(n)-3) ~ n/8 * log2(n) ;ha n nagy

(És persze a duplája, mert másképp értelmeztem a vár.időt)

#13: "Tehát van n+1 elemünk." DEHOGY!

A felezgetésednél is n-ig kellett volna menni, nem 1/2^(n+1)-ig!

==> Tehát van log2(n) elemünk.

Ha ezt javítod, akkor bizonyítod az én számításomat, ugyanis szerintem az össz. várakozás c*n*log2(n),

aminek a deriváltja/növekménye c*log2(n), ami a Te számításod korrigált eredménye.

(Sajnálom, de nem tudok ennél érthetőbben írni, nem vagyok tanár.)

#14 "n számot ha felezgetjük, log2(n) lépésben jutunk az 1-hez, és nincs tovább, nincs értelme a töredékeknek"

Már hogyne lenne értelme a töredéknek? Azt mondod, hogy n=1024 esetében nincs értelme 10-nél (sőt, 8-nál) hosszabb 0-sorozatokkal számolni? Na ne viccelj. Természetesen lehet 11, 20, 100 vagy akár 1000 hosszúságú 0-sorozat is egy 1024 hosszú sztringben. És a futásidő várható értékéhez ezek is ugyanúgy hozzájárulnak a maguk n/4 * 2^-k gyakoriságával és 2^(k-1) mp várakozásukkal ahol k bármi lehet ami befér 1024 alá.

Attól, hogy valami átlagosan 1-nél kevesebbszer fordul elő n hosszúságú sorozatokban, még számolni kell vele. Ugyan szimulálj már le néhány 1024 hosszú sorozatot és nézd már meg, hogy tényleg nem találsz-e bennük 8-nál hosszabb sorozatokat...

Nézd meg a #8-at figyelmesebben egy 640 milliós szimulációról.

log2(80m)=26.25 , ez azt jelenti, hogy a tagok száma kb., átlagosan 26 (míg eléri az egyet) de lehet több, vagy kevesebb is.

Viszont az előfordulások számát egyszerűen beszorzod az időkkel, 2-hatványokkal, és nem mondhatod, hogy még 1/2-szer előfordul a 28-hosszú is, 1/4-szer a 29h, stb., mert ez értelmetlen.

Az átlagban, várható értékben benne van, hogy 26 tagnál hosszabb, rövidebb is lehet.

Szerintem simán megeshet hogy egy N hosszú sorozatra a sebesség várható érték 1/N nagyságú, viszont nagyon nagy valószínûséggel ((mondjuk p=1-1/2^hatszázmillió)) log(N)/N méretû lesz a sebesség.

Végtelen sorozat esetén meg 1 valószínûséggel tart a logos képlethez.

#16: Annyira el vagy tájolva, hogy ezen csak a dolog leprogramozása segíthet.

Annyit tegyél meg, hogy generáld le az összes lehetséges 1-0 sztringet n=5-től 20-ig, számold ki minden n-re az átlagos, egy betűre vetített lefutási idejüket (az 1-esek számlálásával ne is vacakolj), és másold be ide a számokat.

Logaritmikusnak tűnik ez neked? Akkor jó, mert nekem sem. Nemhogy lassulna az egységnyi futásidő növekedése, hanem egyenesen nő. Garantálom, hogy a sorozat differenciája 1/8-hoz fog konvergálni, vagy ha a kérdező általi definíciót használod, 1/4-hez. Magyarán aszimptotikusan lineáris.

Nem tudok rajtad jobban segíteni, próbáld ki és higgy a saját szemednek. Amúgy dq jó úton jár: azokkal az esetekkel, amelyek a magas várható értékért felelnek, olyan alacsony valószínűséggel találkozol, hogy a kis random szimulációdban nem fognak megjelenni és nagy valószínűséggel csak log(n)-hez közel eső egységnyi futásidejű eseteket látsz. De az eloszlásnak olyan hosszú farka van felfelé, hogy a várható érték mégis n-nel lesz arányos.

Kis n-ekre (javaslatom szerint mondjuk 5-20 között) viszont le tudod generálni a teljes eseményteret, számba veszed az extrém eseteiket, és megbizonyosodhatsz arról, hogy az n-nel arányos várható értékért pont az a néhány ritka, extrém eset felel.

Tessék, le is programoztam helyetted. A kérdező által definiált szabályt használva, azaz négy egymást követő nulla esetén 1+2+4+8 = 2^4-1 másodpercet várva. Alulra bemásoltam a program kimenetét is.

pastebin pont com / 2iaiyTqQ

A sorozat differenciája nemhogy konvergál az 1/8-hoz hanem konkrétan végig annyi, full lineáris. És ha megnézed közelről, pontosan követi azt a szabályt t(n)-re, amit a #13-ban írtam, csak az ottani teljes t(n)-hez ugye az egységnyi futásidőt fel kell szorozni n-nel.