Komentarz

XL OM - III - Zadanie 4

Niech $ n, k $ będą liczbami naturalnymi. Wybieramy ciąg zbiorów $ A_0,\ldots, A_k $ tak, że $ A_0 = \{1,\ldots, n\} $, a dla $ i = 1,\ldots, k $ zbiór $ A_i $ jest losowo wybranym podzbiorem $ A_{i-1} $, przy czym wybór każdego podzbioru jest jednakowo prawdopodobny. Rozpatrujemy zmienną losową równą liczbie elementów $ A_k $ . Dowieść, że jej wartość oczekiwana jest równa $ n2^{-k} $.

Rozwiązanie

Wprowadzamy zmienne losowe $ X_1, \ldots , X_n $ określone następująco:

\[<br /> X_i = \left\{<br /> \begin{array}{ll}<br /> 1 & \textrm{jeśli} \ i \in A_k \\<br /> 0 & \textrm{jeśli} \ i \not \in A_k<br /> \end{array}<br /> \right.<br /> \]

\
($ i = 1,\ldots ,n $). Rozważana w zadaniu zmienna losowa $ X $ (liczba elementów zbioru $ A_k $) jest sumą wprowadzonych przed chwilą zmiennych:

\[<br /> X = X_1 + \ldots + X_n.<br /> \]

Ustalmy liczbę $ i \in A_0 = \{1, \ldots, n\} $ . Ponieważ $ A_1 $ jest losowo wybranym podzbiorem $ A_0 $, liczba $ i $ znajdzie się w zbiorze $ A_1 $ z prawdopodobieństwem

\[<br /> P(i \in A_1) = \frac{1}{2};<br /> \]

wynika to stąd, że zbiór $ A_0 $ ma tyle samo podzbiorów zawierających ustalony element $ i $, co podzbiorów nie zawierających tego elementu.

Z takim samym prawdopodobieństwem liczba $ i $ trafi do zbioru $ A_2 $ - pod warunkiem, że wcześniej trafiła do $ A_1 $:

\[<br /> P(i \in A_2 | i \in A_1) = \frac{1}{2}.<br /> \]

Zatem

\[<br /> P(i \in A_2)=\left(\frac{1}{2}\right)^2.<br /> \]

(Mówiąc mniej formalnie, a bardziej obrazowo: liczba $ i $ znajdzie się w zbiorze $ A_2 $, gdy dwa kolejne losowania okażą się dla niej ,,szczęśliwe''.) Kontynuując to rozumowanie stwierdzamy indukcyjnie, że

\[<br /> P(i \in A_j) = 2^{-j} \ \textrm{dla} \ j = 0,1,\ldots,k.<br /> \]

Dla $ j = k $ otrzymana równość $ P(i \in A_k) = 2^{-k} $ oznacza, że zmienna losowa $ X_i $ przyjmuje wartość $ 1 $ z prawdopodobieństwem $ 2^{-k} $ (i wartość $ 0 $ z prawdopodobieństwem $ 1-2^{-k} $). Stąd wynika, że jej wartość oczekiwana wynosi $ 2^{-k} $ .

Uzyskana konkluzja jest słuszna przy każdym wyborze $ i \in \{1,\ldots, n\} $ . To znaczy, że liczba $ 2^{-k} $ jest wartością oczekiwaną każdej ze zmiennych losowych $ X_1, \ldots , X_n $ . Wobec tego

\[<br /> E(X) = E(X_1) + \ldots + E(X_n) = n2^{-k}.<br /> \]
  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Dodaj komentarz