Matematické Fórum

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
🔒 23. 3. 2019 Přešli jsme na HTTPS. Prosíme o kontrolu funkčnosti fóra.
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 20. 06. 2009 12:05

nordec
Příspěvky: 122
Reputace:   
 

Střední hodnota pevných bodů

Ahoj, poradí, prosím, někdo, jak spočítat střední hodnotu počtu pevných bodů náhodné permutace?

Offline

 

#2 20. 06. 2009 12:17

Kondr
Moderátor
Místo: Linz, Österreich
Příspěvky: 4246
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
Web
 

Re: Střední hodnota pevných bodů

Opsal jsem tvé zadání do googlu (anglicky) a baflo na mě tohle:

http://everything2.com/title/the%2520av … 20is%25201

na víc teď nemám čas, snad případné nejasnosti objasní někdo z kolegů.


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

#3 20. 06. 2009 15:40

nordec
Příspěvky: 122
Reputace:   
 

Re: Střední hodnota pevných bodů

Děkuji, angličtinou vládnu trochu hůře, takže
střední hodnota počtu pevných bodů náhodné permutace je $\sum{n.\frac{1}{n}}=1$ ? Jenom jeden bod se zobrazí sám na sebe? (Odhadoval jsem, že to bude víc.)

Offline

 

#4 25. 06. 2009 16:48

nordec
Příspěvky: 122
Reputace:   
 

Re: Střední hodnota pevných bodů

Proč 1 ? Objasníte mi někdo, jak se k tomu dojde?

Offline

 

#5 26. 06. 2009 12:00

jelena
Jelena
Místo: Opava
Příspěvky: 29831
Škola: MITHT (abs. 1986)
Pozice: plním požadavky ostatních
Reputace:   89 
 

Re: Střední hodnota pevných bodů

↑ nordec:

Zdravím,

to je z mého pohledu nevýhoda českého pojmu "střední hodnota" - to se pak představuje nějaký průměr (třeba v mém případě česká "střední hodnota" vůběc nesouhlasí s ruským pojmem "očekávání" nebo anglicky "expectation").

http://www.umiacs.umd.edu/~joseph/class … lution.pdf - zde to hezky vysvětluji v řešení k příkladu 5.2.4

a z formulace ulohy jsem se dostala sem, určitě to bude mít i českou variantu "hat check problem".

Třeba já bych se přesvědčovala tak, že prozkouším, jaka je pravděpodobnost dostat svůj vlastní klobouk pro 1 osobu, pro 2 osoby, pro 3 osoby, sestavila bych si tabulku pravděpodobnosti a vypočetla bych "střední hodnotu diskrétní veličiny" - V knize, co odkazuji, je to uděláno v tabulce nad textem. A v textu říkají, že je to surpresing :-)

Pokud se nenajde česká varianta této úlohy, tak bych přislibila "pracovní překlad", ale dnes těžko, do té doby se určitě najde i česká varianta.

Offline

 

#6 26. 06. 2009 12:59

radekm
Příspěvky: 146
Reputace:   11 
Web
 

Re: Střední hodnota pevných bodů

Já "hat-check problem" znám pod názvem "problém šatnářky" (jaká je pst. že žádný pán nedostane svůj klobouk). Je to ale něco jiného než se původně tazatel ptal.

Offline

 

#7 26. 06. 2009 13:25 — Editoval jelena (26. 06. 2009 13:31)

jelena
Jelena
Místo: Opava
Příspěvky: 29831
Škola: MITHT (abs. 1986)
Pozice: plním požadavky ostatních
Reputace:   89 
 

Re: Střední hodnota pevných bodů

↑ radekm:

Já jsem tomu rozuměla tak, že kolega ↑ nordec: po přečtení úplně prvního odkazu je překvapen, že výsledek "střední hodnota" je jen "1" a myslí, že těchto bodu (s vlastnosti se zobrazit sam na sebe) bude víc. A tak jsem ho chtěla navést, že pevných bodů může být více (i méně), ale střední hodnota vychází právě tak, jak vychází - tento materiál jsem hlavně měla na mysli.

Pokud touto informaci jen matu, tak se samozřejmě omlouvám a děkuji za doplnění i za další uvedení na pravou míru, děkuji.

Offline

 

#8 26. 06. 2009 13:40

radekm
Příspěvky: 146
Reputace:   11 
Web
 

Re: Střední hodnota pevných bodů

↑ jelena:

To jsem rozhodně nechtěl říci, že matete (pokud to tak vyznělo, tak se omlouvám). Naopak, je velmi rozumné si to vyzkoušet.

Offline

 

#9 26. 06. 2009 14:34

nordec
Příspěvky: 122
Reputace:   
 

Re: Střední hodnota pevných bodů

V českých materiálech vždy byl jen takový nástin různě nazývaného problému "o kloboucích", "šatnářce", dokonce někde "o myslivcích střílejících na králíky". V anglických to "proč to tak vyjde" příliš nechápu, možná ale proto, že k mé škodě neumím dobře anglicky.
Výsledek mi přijde divný, protože buď 1 nebo 2 nebo ... nebo n lidí dostane zpět svůj klobouk, kolik očekáváme lidí se svým kloboukem? Jenže ono když 1 člověk dostane svůj klobouk, není 1 možnost, ale asi (n-1)! možností a v tom se už ztrácím...

Offline

 

#10 26. 06. 2009 15:27

Kondr
Moderátor
Místo: Linz, Österreich
Příspěvky: 4246
Škola: FI MU 2013
Pozice: Vývojář, JKU
Reputace:   38 
Web
 

Re: Střední hodnota pevných bodů

nordec napsal(a):

buď 1 nebo 2 nebo ... nebo n lidí dostane zpět svůj klobouk

Nebo taky 0. A to je velmi pravděpodobné -- ta pravděpodobnost je pro velká n někde mezi 30% a 40% (blíží se k 1/e). Naopak čím více lidí má získat svůj klobouk, tím méně je to pravděpodobné. Přístup na stránce kterou jsem odkazoval já (materiály od Jeleny si přečtu, až budu v Brně na déle než skok) mi přijde jednoduchý: pro každého člověka i (i jde od 1 do n) zavedeme náhodnou veličinu N_i která je 1 pokud člověk i dostane svůj klobouk a 0 pokud ne. Celkový počet lidí, kteří dostali svůj klobouk označme N. Platí N=N_1+N_2+...N_n. Z linearity střední hodnoty máme E(N)=E(N_1)+E(N_2)+...+E(N_n). Stačí určit očekávané hodnoty E(N_i). Z definice střední hodnoty je E(N_i)=1*p+0*(1-p)=p, přitom p je pravděpodobnost, že člověk i dostane svůj klobouk. Protože je pro každý klobouk stejně pravděpodbné, že ho dostane i-tý člověk, je p=1/n. Proto E(N)=1/n+1/n+...+1/n=1.


BRKOS - matematický korespondenční seminář pro střední školy

Offline

 

#11 26. 06. 2009 15:33

radekm
Příspěvky: 146
Reputace:   11 
Web
 

Re: Střední hodnota pevných bodů

↑ nordec:

Doporučuju vám, abyste se nezabýval faktoriálem, ten tam totiž vůbec není potřeba.

Představte si, že v šatně je n klobouků a přijde si pro ně n pánů. Teď si představte, že jste klobouk. Jakou máte pravděpodobnost, že se dostanete zpět ke svému majiteli (když pánové
přicházejí náhodně a šatnářka to vydává postupně)? Je to 1/n.

Tedy formálně: X(i) je nahodná veličina nabývající 0, nedostane-li se i-tý klobouk ke svému majiteli, a 1 dostane-li se klobouk i-tý ke svému majiteli. X(i) má pro každé i alternativní rozdělení. Tudíž EX(i) je 1/n.

To platí pro každý klobouk, tedy n/n = 1.

Konkrétně: Když v šatně budou 3 klobouky a šatnářka bude vydávat jen jeden (zbylé dva jí spadly na zem a ona je nevidí). Pánové mohou přijít následovně:

[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

Každopádně se šatnářka trefí ve 2 případech z 6. Tj. očekáváme 1/3 správných vydání.
Když tam budou i zbylé dva klobouky, tak pro ně také očekáváme 1/3 správných vydání.
Tedy dohromady 1 správné vydání.

Offline

 

#12 26. 06. 2009 15:48

radekm
Příspěvky: 146
Reputace:   11 
Web
 

Re: Střední hodnota pevných bodů

Nebo ještě jinak. Představte si všechny permutace z n prvků, těch je n!. V kolika z nich je prvek i pevný bod? Jednoduše: zafixuji i -- to musí být na i-tém místě a zbylé prvky libovolně zpermutuji. Tedy i je v (n-1)! permutacích pevný bod.

To platí pro každé i. Za i mohu zvolit n různých hodnot. Podívám-li se na všechny možné permutace objeví se tam n*(n-1)! pevných bodů.

Offline

 

#13 26. 06. 2009 16:34

nordec
Příspěvky: 122
Reputace:   
 

Re: Střední hodnota pevných bodů

Heuréka, už je to jasný. Pořád jsem se snažil na to jít přes všechny možnosti (variace), až se to čím dál víc zamotávalo, byl v tom zmatek. Ale trik s 1 a 0 (který jsem z ang. textu holt nevyčetl) to náramně zpřehlednil: n lidí, každý s pravděpodobností 1/n, dostane svůj klobouk, tj. n . 1/n = 1. Teď vím, proč to tak je. Všem moc děkuju.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson