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 />
\]

Komentarze

Dodaj nową odpowiedź