Hány véletlen szám kell hozzá?
Generálunk egy véletlen számot 1 és 1 billió között, majd ezt ismételgetjük amíg minden 1 és 1 billió közötti szám ki nem jön legalább egyszer.
Közben lesznek olyan számok, amik már sokszor (10-20-30-40-szer?) kijöttek, de néhány szám még egyszer sem.
Várhatóan kb. hány számot kell generálni, mire mind kijön legalább egyszer?
válasza: válasza:Gyorsan összedobtam egy szkriptet:
amivel azt tesztelem, hogy egy adott intervallumú egyedi, nem ismétlődő véletlenszám-lista generálásához a lista/az intervallum méretéhez képest mennyivel több véletlenszámot kell generálni. Ebből egy ilyen grafikont:
kaptam - a vízszintes tengely az intervallum/a lista mérete, a függőleges a véletlenszám-generálások száma.
Azt tapasztaltam, hogy:
- 1-10 intervallumhoz kb. 3-szor annyit
- 1-100 intervallumhoz kb. 5-ször annyit
- 1-1000 intervallumhoz kb. 7-szer annyit
- 1-10000 intervallumhoz kb. 9-szer annyit
így feltételezem, hogy az 1-N intervallumhoz kb. 2 * log10(N) + 1 véletlenszám-generálás kell.
Tehát ezek szerint 1 billiós (10^12) intervallumhoz 25-ször több (25*10^12) véletlenszám-generálás kellhet.
válasza:"a függőleges a véletlenszám-generálások száma."
Pontosítanám magam: a lista méretéhez képest mennyivel több véletlenszámot kell generálni.
válasza:Ha ugyanakkora valószínűséggel generálódik az összes szám, akkor egészen pontosan:
(1/(1 billió))^(1 billió)
De gyanítom, hogy téged az érdekel, amikor nem egyforma eséllyel generálódnak a számok, azt viszont csak úgy lehet megmondani, ha ismertek a paraméretek.
válasza:enwp.org/Coupon_collector%27s_problem
Illetve, ha kutakodtok kicsit a GyK-en, akkor 2×Sü és sokan mások is levezették már a megoldást. (És a ma 03:39-es válaszadó n*ln(n)-es sejtése sem olyan rossz.) Egészen pontosan n*sum(1/k, k=1..n) lesz a várhatóérték.
Ebben az esetben (kábé)
21 300 481 501 848,444.
válasza:OMG, korán van még... Inkább
28 208 236 780 830,581-et
szerettem volna írni. Bocsánat!
#7: Köszi, igen, ez a 28 billió tűnik jónak.
És kb. mennyi lehet a maximum, ahányszor kihúzzák a legtöbbször kijövő számot?
válasza: válasza:A 05:06-os és 05:11-es válaszban egyenletes eloszlást tételeztem fel, tehát hogy mindegyik szám pontosan 1e-12 valószínűséggel jön ki. A linkelt Wikipédia-oldalon van egy általános képlet tetszőleges p_k valószínűségekre is, ha érdekel (nem barátságos, ha 1e12 darab valószínűségre számolnánk ki).
Illetve itt is van egy levezetés (egyenletes eloszlásra): https://www.gyakorikerdesek.hu/tudomanyok__egyeb-kerdesek__9.. GyK/9717534
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!