Matematické Fórum

Anonymystik

Dobrý den.
Zkoušel jsem řešit následující úlohu: v klobouku jsou lístečky s čísly 1, 2, ..., N. Poslepu vytáhnu s lísteček s číslem a zapíšu si ho na papír. Poté lísteček vrátím do klobouku, zamíchám a tahám znovu. Úspěšným tahem nazvu ten, při kterém vytáhnu číslu, které jsem dosud ještě neměl. Naopak pokud už jsem číslo vytáhl podruhé, jedná se o neúspěšný tah. Představme si nyní hru, ve které opakovaně tahám a za každý úspěšný tah dostanu dolar. Naopak při prvním neúspěšném tahu hra končí (tj. další lístečky už vybírat nebudu). Otázka zní: jaká bude střední výhra v takové hře?
Problém jsem se pokoušel analyzovat a dospěl jsem k této sumě:
$V(N) = \sum_{k=1}^{N} \frac{N!}{(N-k+1)!} \frac{(k-1)^2}{N^k}$
To ale neumím sečíst. Ideální by bylo analytické řešení, ale byl byl vděčný i za asymptotické chování. Myslím si, že vyjde něco jako $V(N) \sim \sqrt{N}$ , ale neumím to dokázat. Poradíte někdo, prosím?

Jj · 30. 08. 2016 22:27

↑ Anonymystik:

Zdravím.
Řekl bych, že střední výhra bude $V(N) = \sum_{k=1}^{N\color{red}+1\color{black}} \frac{N!}{(N-k+1)!} \frac{(k-1)^2}{N^k}$

(Aspoň tak mi to vychází - ale sečíst to neumím.)

Xellos · 30. 08. 2016 23:47

Napisem to inak, $N! \sum_0^N \frac{(N-k)^2}{k!} \frac{1}{N^{N-k}}$ . Potom

$\frac{N!}{N^N} \sum_0^N \frac{N^2+k^2-2Nk}{k!} N^k$

$\frac{N!}{N^N} \sum_0^N \left( \frac{N^2}{k!}-\frac{2N}{(k-1)!}+\frac{k}{(k-1)!} \right) N^k$

$\frac{N!}{N^N} \left( \sum_0^N \frac{N^2}{k!} N^k -2N^2 \sum \frac{1}{(k-1)!} N^{k-1} + N \sum \frac{1}{(k-1)!} N^{k-1} + N^2 \sum \frac{1}{(k-2)!} N^{k-2} \right)$

$\frac{N!}{N^N} \left( N^2 \sum_0^N \frac{1}{k!} N^k + (N-2N^2) \sum_0^{N-1} \frac{1}{k!} N^{k} + N^2 \sum_0^{N-2} \frac{1}{k!} N^k \right)$

Kopa veci sa vykrati a dostaneme

$\frac{N!}{N^{N-1}} \sum_0^{N-1} \frac{1}{k!} N^{k}$

kde vidno Taylorov polynom $e^x$ v bode $x=N$ ... co sa asi lepsie vyjadrit neda, ale pre velke $N$ je dobra aproximacia $ce^N$ s experimentalne urcenym $c$ - konkretne $\frac{N!}{N^{N-1}}\frac{4}{3}e^{N-1}$ . So Stirlingovou aproximaciou $N! \approx \sqrt{2\pi N} e^{-N} N^N$ mame z toho $\frac{4}{3e}\sqrt{2\pi N} N$ . Pre $N=5$ to uz dava chybu pod 10%.

Anonymystik

↑ Xellos: Ahoj, děkuju moc, potřeboval jsem nakopnout hlavně ten první krok, pak už mi ten výpočet nějak šel. :-)
Jinak to tvrzení, že existuje nějaká konstanta C taková, že $\lim_{N \to \infty} \frac{1}{e^N} \sum_{k=0}^{N-1} \frac{N^k}{k!} = C$ zní docela zajímavě. Pokud tě chápu dobře, tak dokonce $C = \frac{4}{3e}$ . Mohu se zeptat, jaké metody se používají k důkazu něčeho takového?

Matematické Fórum

#1 26. 08. 2016 15:47 — Editoval Anonymystik (26. 08. 2016 17:16)

Průměrná výhra

#2 30. 08. 2016 22:27

Re: Průměrná výhra

#3 30. 08. 2016 23:47

Re: Průměrná výhra

#4 31. 08. 2016 12:07 — Editoval Anonymystik (31. 08. 2016 12:14)

Re: Průměrná výhra

Zápatí