Matematyka.pl

No dobra, więc tak:
Losowanie jest wtedy jak losujemy sobie jeden spośród n różnych przedmiotów.
Ile potrzeba losowań, żeby wylosować k różnych przedmiotów (tzn. jaka jest wartość oczekiwana ilości losowań). Raz wylosowany przedmiot grzecznie oddajemy, ale zapamiętujemy, że już nam się udało przedmiot tego rodzaju wylosować.
Udowodnić że poszukiwana liczba to:
\(\displaystyle{ n * \sum_{i=0}^{k-1} \frac{1}{n-i}}\)

-- 8 stycznia 2011, 22:14 --

Aha i jeszcze małe pytanie z ostaniej chwili wyprowadzić aproksymację(tego samego wyniku):
\(\displaystyle{ n * \ln{(\Delta+1)}}\)
gdzie:
\(\displaystyle{ \Delta=\frac{2k}{2n-2k+1}}\)

Niech \(\displaystyle{ X_i}\) oznacza ilość losowań potrzebnych do wylosowania kolejnego (dowolnego) przedmiotu innego od dotychczas wylosowanych, zaś \(\displaystyle{ Y}\) liczbę losowań niezbędnych do wylosowania k różnych przedmiotów. Wówczas oczywiście

\(\displaystyle{ EY=E\left(\sum_{i=1}^{k}X_i\right)=\sum_{i=1}^{k}EX_i}\), gdzie \(\displaystyle{ k \in \{1,\ldots,n\}}\)

Łatwo pokazać, że

\(\displaystyle{ EX_i=\frac{n-(i-1)}{n}\left(1\left(\frac{i-1}{n}\right)^0+2\left(\frac{i-1}{n}\right)^1+\ldots\right)=\frac{n+1-i}{n}\frac{1}{(1-\frac{i-1}{n})^2}=\\=\frac{n}{n-i+1}}\)

Pierwszy czynnik to prawdopodobieństwo wylosowania nowego i-tego przedmiotu po wcześniejszym wylosowaniu i-1 innych. W nawiasie mamy ilość losowań potrzebną do tego aby tak się stało przemnożoną przez prawdopodobieństwo tego, że wcześniej możemy wylosować tylko to co wcześniej było już wylosowane. Ostatecznie otrzymuje się, że

\(\displaystyle{ EY=\sum_{i=1}^{k}\frac{n}{n-i+1}=n\sum_{i=0}^{k-1}\frac{1}{n-i}}\)

Druga część zadania to nie ten dział, ale OK

\(\displaystyle{ \sum_{i=0}^{k-1}\frac{1}{n-i}=\sum_{p=n-k+1}^{n}\frac{1}{p} \approx \int_{n-k}^{n}\frac{1}{x+\frac{1}{2}}=ln\left(\frac{n+\frac{1}{2}}{n-k+\frac{1}{2}}\right)=ln\left(\frac{2k}{2n-2k+1}+1\right)}\)

Widać też stąd, że dla k bliskich n powyższe przybliżenie zawyża nieco poprawny wynik.