Mam problem z takim zadaniem, kompletnie go nie mogę zrozumieć.
Dany jest n-elementowy zbiór S. Ze zbioru wszystkich podzbiorów wybieramy kolejno ze zwracaniem 2 zbiory (każdy podzbiór z jednakowym prawdopodobieństwem). Jakie jest prawdopodobieństwo że wylosowane zbiory są rozłączne ?
Widziałem na forum takie rozumowanie:
W pierwszym losowaniu losujemy k elementów z prawdopodobieństwem \(\displaystyle{ \frac{{n \choose k}}{2^{n}}}\), a w drugim losowaniu
nie możemy wylosować żadnego z tych k elementów co robimy z prawdopodobieństwem \(\displaystyle{ \frac{1}{2^{k}}}\)
O ile pierwsza część jest oczywista, nie rozumiem dlaczego prawdopodobieństwo niewyciągnięcia żadnego z tych k elementów w drugim losowaniu jest równa \(\displaystyle{ \frac{1}{2^{k}}}\).
Przykładowo przy n=4 i k=1, w pierwszej części mamy naturalnie 4 możliwości. Jeśli wylosujemy 1, to w drugim losowaniu możemy wylosować wszystkie podzbiory oprócz samej 1 (czyli jest ich 15), to samo jeśli chodzi o wylosowanie 2, 3 i 4 w pierwszym losowaniu. Dlaczego więc ma być niby \(\displaystyle{ \frac{1}{2^{k}}}\)?
Źle to rozumiem, czy błędne rozwiązanie?
zbiór n-elem.,2 losowania, zbiory rozłączne
- sebnorth
- Użytkownik
- Posty: 635
- Rejestracja: 12 sty 2011, o 16:27
- Płeć: Mężczyzna
- Lokalizacja: Puck i Trójmiasto
- Pomógł: 201 razy
zbiór n-elem.,2 losowania, zbiory rozłączne
Dziwne zadanie i dziwny wynik mi wyszedł. Czy robie gdzieś błąd? :
Dwa losowania ze ze zbioru podzbiorów daje mi \(\displaystyle{ 2^{n} \cdot 2^{n}}\) zdarzeń elementarnych.
Teraz które zdarzenia sprzyjają temu danemu zadaniu. Załózmy że w pierwszym losowaniu wypadło \(\displaystyle{ k}\) elementów. To sie może zdarzyć na \(\displaystyle{ {n \choose k}}\) sposobów. Zostaje \(\displaystyle{ n-k}\) elementów z których moge losować dowolny podzbiór w drugim losowaniu. Czyli razem mam \(\displaystyle{ 2^{n-k}}\) możliwośći. Sumując po \(\displaystyle{ k}\) dostajemy:
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k} \cdot 2^{n-k} = \sum_{k=0}^{n} {n \choose k} \cdot 1^{k} \cdot 2^{n-k} = (1+2)^{n} = 3^{n}}\)
Zatem \(\displaystyle{ P = \frac{3^{n}}{2^{2n}}}\) .
Dwa losowania ze ze zbioru podzbiorów daje mi \(\displaystyle{ 2^{n} \cdot 2^{n}}\) zdarzeń elementarnych.
Teraz które zdarzenia sprzyjają temu danemu zadaniu. Załózmy że w pierwszym losowaniu wypadło \(\displaystyle{ k}\) elementów. To sie może zdarzyć na \(\displaystyle{ {n \choose k}}\) sposobów. Zostaje \(\displaystyle{ n-k}\) elementów z których moge losować dowolny podzbiór w drugim losowaniu. Czyli razem mam \(\displaystyle{ 2^{n-k}}\) możliwośći. Sumując po \(\displaystyle{ k}\) dostajemy:
\(\displaystyle{ \sum_{k=0}^{n} {n \choose k} \cdot 2^{n-k} = \sum_{k=0}^{n} {n \choose k} \cdot 1^{k} \cdot 2^{n-k} = (1+2)^{n} = 3^{n}}\)
Zatem \(\displaystyle{ P = \frac{3^{n}}{2^{2n}}}\) .
-
- Użytkownik
- Posty: 244
- Rejestracja: 25 paź 2010, o 15:59
- Płeć: Mężczyzna
- Lokalizacja: Nowy Sącz
- Podziękował: 56 razy
zbiór n-elem.,2 losowania, zbiory rozłączne
Moim zdaniem dobrze, o to samo mi chodziło. Ostatecznie wyjdzie z tego \(\displaystyle{ (\frac{3}{4})^{n}}\). W rozumowaniu, które przedstawiłem na początku też wychodził taki wynik, ale nie mogłem zrozumieć tłumaczenia do tego zadania.