XL OM - III - Zadanie 4

Zawody matematyczne:

XL OM, 1988-1989

Etap:

III

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:

$ X_i = \left\{ \begin{array}{ll} 1 & \textrm{jeśli} \ i \in A_k \\ 0 & \textrm{jeśli} \ i \not \in A_k \end{array} \right. $

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

$ X = X_1 + \ldots + X_n. $

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

$ P(i \in A_1) = \frac{1}{2}; $

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$ :

$ P(i \in A_2 | i \in A_1) = \frac{1}{2}. $

Zatem

$ P(i \in A_2)=\left(\frac{1}{2}\right)^2. $

(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

$ P(i \in A_j) = 2^{-j} \ \textrm{dla} \ j = 0,1,\ldots,k. $

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

$ E(X) = E(X_1) + \ldots + E(X_n) = n2^{-k}. $