Mamy elementy \(\displaystyle{ \left\{ x_{1}, ..., x_{k} \right\}}\). Każdy z tych elementów można wylosować z prawdopodobieństwem \(\displaystyle{ \frac{1}{k}}\). (czyli pewnie jest to rozkład jednostajny dyskretny). Jaka jest wartość oczekiwana liczby potrzebnych losowań, aby każdy z elementów \(\displaystyle{ \left\{ x_{1}, ..., x_{k} \right\}}\) był wylosowany przynajmniej raz.
Jak to rozwiązać?
Czy dobrze rozumiem pytanie z zadania? - ile średnio potrzeba losowań, aby każdy z elementów był wylosowany przynajmniej raz?
Proszę o pomoc w rozwiązaniu, bądź przekierowanie do istniejącego wątku z rozwiązaniem, gdyż niestety takiego nie udało mi się odnaleźć.
Wartość oczekiwana liczby potrzebnych losowań...
-
midorisenko
- Użytkownik
- Posty: 1
- Rejestracja: 12 wrz 2016, o 15:43
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
-
Mruczek
- Użytkownik
- Posty: 1114
- Rejestracja: 26 paź 2008, o 19:43
- Płeć: Mężczyzna
- Podziękował: 23 razy
- Pomógł: 157 razy
Wartość oczekiwana liczby potrzebnych losowań...
Niech \(\displaystyle{ X}\) to zmienna losowa określająca szukaną liczbę losowań.
Załóżmy, że liczba losowań wynosiła \(\displaystyle{ i}\). Wtedy w ostatnim losowaniu po raz pierwszy pojawił się pewny z elementów (z prawdopodobieństwem \(\displaystyle{ \frac{1}{k}}\), na \(\displaystyle{ k}\) różnych sposobów), a w pierwszych \(\displaystyle{ i - 1}\) losowaniach mógł wypaść dowolny z pozostałych \(\displaystyle{ k - 1}\) elementów, w każdym z nich z prawdopodobieństwem \(\displaystyle{ 1 - \frac{1}{k}}\).
\(\displaystyle{ P(X=i) = k \cdot \frac{1}{k} \cdot \left( 1 - \frac{1}{k} \right) ^{i - 1} = \left( \frac{k - 1}{k} \right) ^{i - 1}}\)
\(\displaystyle{ EX = \sum_{i \ge 1} P(X=i) \cdot i = \sum_{i \ge k} P(X=i) \cdot i = \sum_{i \ge k} \left( \frac{k - 1}{k}\right) ^{i - 1} \cdot i}\)
Tą sumę można policzyć w tzw. trójkąt - jako sumę kolejnych sum szeregu geometrycznego.
Ewentualnie z pochodnej szeregu: \(\displaystyle{ \left( \frac{ x^{k} }{1 - x} \right) '=\left( \sum_{i \ge k} x^{i}\right) '= \sum_{ i\ge k} x^{i - 1} \cdot i}\), i podstawić \(\displaystyle{ \frac{k - 1}{k}}\) za \(\displaystyle{ x}\).
Załóżmy, że liczba losowań wynosiła \(\displaystyle{ i}\). Wtedy w ostatnim losowaniu po raz pierwszy pojawił się pewny z elementów (z prawdopodobieństwem \(\displaystyle{ \frac{1}{k}}\), na \(\displaystyle{ k}\) różnych sposobów), a w pierwszych \(\displaystyle{ i - 1}\) losowaniach mógł wypaść dowolny z pozostałych \(\displaystyle{ k - 1}\) elementów, w każdym z nich z prawdopodobieństwem \(\displaystyle{ 1 - \frac{1}{k}}\).
\(\displaystyle{ P(X=i) = k \cdot \frac{1}{k} \cdot \left( 1 - \frac{1}{k} \right) ^{i - 1} = \left( \frac{k - 1}{k} \right) ^{i - 1}}\)
\(\displaystyle{ EX = \sum_{i \ge 1} P(X=i) \cdot i = \sum_{i \ge k} P(X=i) \cdot i = \sum_{i \ge k} \left( \frac{k - 1}{k}\right) ^{i - 1} \cdot i}\)
Tą sumę można policzyć w tzw. trójkąt - jako sumę kolejnych sum szeregu geometrycznego.
Ewentualnie z pochodnej szeregu: \(\displaystyle{ \left( \frac{ x^{k} }{1 - x} \right) '=\left( \sum_{i \ge k} x^{i}\right) '= \sum_{ i\ge k} x^{i - 1} \cdot i}\), i podstawić \(\displaystyle{ \frac{k - 1}{k}}\) za \(\displaystyle{ x}\).