Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
Stránky: 1
Pro dané přirozené si představme následující pokus:
Máme n očíslovaných mincí. Pomocí těchto mincí budeme tvořit n posloupností (každé minci přísluší jedna posloupnost) tak, že si vždy hodíme najednou všemi mincemi (to považujeme za jeden hod) a do příslušné posloupnosti si zapíšeme 0 nebo 1 podle toho, jestli na příslušné minci padla panna nebo orel. Ve chvíli, kdy žádné dvě posloupnosti nejsou shodné, skončíme, počet uskutečněných hodů označíme k.
Definujeme náhodnou veličinu X=k. Najděte střední hodnotu X v závislosti na n.
(Řešení neznám, ani nevím, jak je úloha obtížná.)
Edit: Zpřesněno zadání, aby bylo srozumitelnější
Offline
EDIT: Takhle to nepůjde.
Co to zkusit takto:
Je to Narozeninový problém s následující modifikací:
Možností není 365, ale .
Pravděpodobnost, že žádné 2 posloupnosti nebudou stejné právě při k-tém hodu, tedy bude
.
Náhodná veličina má geometrické rozdělení.
Její střední hodnota bude
.
Offline
↑ KennyMcCormick:
Ta pravděpodobnost p, kterou uvádíš, je pravděpodobnost, že dvě posloupnosti budou různé po k hodech. Nás ale hlavně zajímá, jaká je pravděpodobnost, že budou po k hodech poprvé různé (tj. po k-1 hodech ještě všechny různé nebyly).
Vůbec mi není jasné, proč myslíš, že X má geometrické rozdělení. A už vůbec mi není jasný ten výpočet střední hodnoty, vždyť ta nemůže záviset na k. Spočte se přece jako
Offline
Máš pravdu, nemá geometrické rozdělení, protože je funkcí (takže ani nebude takové, jaké jsem napsal).
Díky za upozornění na omyl.
Offline
↑ Pavel Brožek:
Ahoj, takže jestli to dobře chápu, tak po prvním hodu budeme mít vytvořen první člen každé posloupnosti, po druhém hodu budeme mít dva členy každé posloupnosti, atd.? A pokud se některé dvě takto doposud vytvořené posloupnosti shodují, tak pokračujeme v házení dále?
PS: Koukám, že jsi se dal na informatiku. Ve fyzice bylo tedy již vše objeveno a zbývá jen upřesnit hodnoty důležitých konstant? :-) (Abych citoval vážně míněné tvrzení někdy z konce 19. století.)
Offline
↑ check_drummer:
Ahoj, chápeš to správně. :)
Ano, dal jsem se na informatiku :). Mám takový pocit, že abych se ve fyzice přiblížil něčemu významnému, tak bych jí musel prakticky obětovat život, což se mi nechce. A ani práce vědce mě zas tak moc neláká. V informatice má člověk mnohem víc možností uplatnění bych řekl.
Offline
↑ Pavel Brožek:
Zkoušel jsi si to simulovat pro nějaké hodnoty n? Dolním odhadem je a horním , tak by bylo zajmavé vidět, kde se ta střední hodnota pohybuje - třeba bude nakonec záviset na n lineárně (to by bylo velmi zajímavé).
Offline
↑ check_drummer:
Simulovat jsem to nezkoušel. Došel jsem ke stejnému tvaru jako má KennyMcCormick (vůbec mě nenapadlo, že jde o narozeninový paradox, dospěl jsem k tomu jiným způsobem). Pravděpodobnost, že se skončí právě po k hodech je rovna rozdílu pravděpodobnosti, že se skončí po k hodech nebo dříve, a pravděpodobnosti, že se skončí po k-1 hodech nebo dříve. Ta pravděpodobnost, kterou uvedl KennymcCormick je pravděpodobnost, že se skončí po k hodech nebo dříve. Takže pravděpodobnost, že se skončí právě po k hodech je
(Přitom beru , pokud b>a.)
Ta střední hodnota se dá upravit do tvaru
kde . Členy sumy jsou zřejmě čísla z intervalu (0,1), takže dostáváme odhad , který jsme očekávali. Ale bylo by zajímavé zjistit přesněji asymptotiku, tipnul bych si, že to bude nakonec právě ta logaritmická.
Offline
↑ Pavel Brožek:
Ahoj, to je vlastně pravda, že lze použít narozeninový paradox. Mohl bys prosím vysvětlit tu úpravu střední hodnoty - první řádek, kde je E[x]? Nezapomněl jsi násobit hodnotou k?
Možná by šel použít nějaký odhad na ten binomický koeficient a faktoriál pomocí čísla e. Nějaké odhady byly přímo na těch stránkách narozeninového paradoxu.
Offline
↑ Pavel Brožek:
Teď mě napadá, že tahle úloha souvisí s hashováním, o kterém jsi tu taky nedávno psal. Je to jen náhoda nebo jsi na tuto úlohu přišel v souvislosti se zkoumáním hashování?
Offline
↑ check_drummer:
Je to trochu delší výpočet, než se k tomu člověk dostane. k mi tam nechybí, ono se v průběhu výpočtu ztratí samo :).
Ve výpočtu jsem použil
nenapadá mě teď, jak důkaz této rovnosti stručně sepsat, a podrobně rozepisovat se mi to nechce, protože když si to člověk trochu rozepíše na papír, tak je to celkem zřejmé (dominantní člen se odečte a všechny ostatní klesají aspoň jako ).
Není to náhoda, souvisí to s hashováním. Konkrétně jsem na to narazil u Extendible hashing, kde je právě potřeba rozlišit každé dva hashe tím, že se budeme dívat na dostatečný počet bitů hashe. A zajímalo mě, jaký bude střední počet bitů, na které se musím dívat. Chtěl jsem tak při daném počtu záznamů zjistit, jak dobře v průměru bude využitý prostor adresáře.
Offline
↑ Pavel Brožek:
Děkuji za objsnění, čekal jsem že je to jen úprava na jeden řádek. :-)
Nad tou asymptotikou jsme se nezamýšlel, ale asi bude lepší aproximovat tu sumu (konečným součtem), co jsi odvodil, než to simulovat. I když u logaritmických závislostí je těch členů potřeba hodně. Viz třeba harmonická řada...
Offline
Stránky: 1