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

Amúgy pont tegnap tett fel valaki egy jópofa kérdést ami nagyon hasonló ehhez a problémához. Igazából azon se lennék meglepve, ha ugyanaz az ember írta volna ki:

http://www.gyakorikerdesek.hu/tudomanyok__egyeb-kerdesek__84..

Ez nem ugyanaz a feladat mint ami a kérdésben van, vagy a #8-ban leprogramozva. Ez az álagos lépésszám az összes N hosszú sorozatra nézve. Más néven várható érték.

Ez csak egy szám.

A kérdésben az van, hogy mihez fog konvergálni egy így elkezdett sorozat. Az is egy szám, de, nem azonos a tieddel 1 valószínûséggel legalábbis.

Száztrilliárd kísérletet ha elvégzel, mindegyikben kivétel nélkül egy idõ (N_0) után 1/log(N)-es lesz a konvergencia. (ezt nem tudom belátni)

Nagyon nem érdemes túlragozni egyébként.

Két választ is kapott a kérdezõ, nyilván megnézi mindkét programot, azt annyi.

Na jó, ezt is visszavonom további átgondolás erejéig.

(Most már tényleg csöndben maradok.)

Bevallom, nem értem, hogy mi lehet a félreértés oka, de komolyan kíváncsi vagyok rá.

Kiszámoltam egy n hosszúságú sorozat egységre vetített futásidejének várható értékét. Ezzel úgy láttam nem volt probléma, egyikőtök sem vonta kétségbe az eredményt, és annak n-ben lineáris voltát.

De született egy olyan megjegyzés, hogy ez nem releváns, mivel "a várható érték csak egy szám". Ezzel a kijelentéssel nem tudok mit kezdeni. Nem pont ez a várható érték az egész problémának a lényege? Hogy máshogy definiálsz valószínűségi változókon átlagot?

A konvergencia kifejezés is előkerült, de nem tudom, mit kéne alatta érteni. Kaphatok egy definíciót? Mi konvergál 1/log(n)-hez 1 valószínűséggel? Egyáltalán mi az, hogy 1/log(n)-hez konvergálni?

Nem akarom helyetted megválaszolni a kérdést, de egyvalamit tudok elképzelni, a #17-est alapul véve, és sebesség helyett egységre vetített várakozást nézve. Hihetőnek tűnik, hogy tetszőleges ɛ>0-hoz és p<1-hez található olyan N, melyre az n>N hosszúságú sorozatok egységnyi várakozási ideje legalább p valószínűséggel log2(n)/8 ± ɛ intervallumba esik.

Ami persze nem azonos azzal, hogy az N hosszúságú sorozatok ÁTLAGOS várakozása log2(n)/8 lenne, mert a kimaradó 1-p-nyi sorozat annyival log2(n)/8 felett van, hogy a várható értéket felhúzzák n/8-hoz. És nem tudsz akkora p-t mondani, amivel szemben a maradék 1-p ereje túl kevés lenne, mivel a nagyobb N küszöb miatt a sávból kimaradó 1-p-nyi sorozat még extrémebb értékekkel húzza felfelé a várható értéket.

Remélem valamennyie sikerül közös nevezőre jutnunk és megértenünk egymást.

felvetették a problémát az index fórumon is, bár ott végtelen sorozat helyett véges sorozatokra:

[link]

8372 hozzászólástól kezdve.