LVI OM - I - Zadanie 10

Spośród wszystkich podzbiorów ustalonego zbioru $ n $-elementowego $ X $ losujemy kolejno ze zwracaniem trzy zbiory $ A $, $ B $, $ C $. Za każdym razem wylosowanie każdego spośród $ 2^n $ podzbiorów zbioru $ X $ jest jednakowo prawdopodobne. Wyznaczyć najbardziej prawdopodobną liczbę elementów zbioru $ A\cap B\cap C $.

Rozwiązanie

Zbiór zdarzeń elementarnych $ \Omega $ składa się ze wszystkich trójek $ (A,B,C) $, gdzie $ A $, $ B $ i $ C $ są podzbiorami danego zbioru $ n $-elementowego $ S $. Wylosowanie każdej z $ (2^n)^3 =8^n $ trójek $ (A,B,C) $ jest jednakowo prawdopodobne. Niech $ X_k $ $ (k =0,1,2,\ldots,n) $ oznacza zdarzenie polegające na tym, że trójka zbiorów $ (A,B,C) $ spełnia warunek $ |A\cap B\cap C|= k $, gdzie $ |F| $ oznacza liczbę elementów zbioru $ F $. Szukamy takiej liczby naturalnej $ k $, dla której prawdopodobieństwo zajścia zdarzenia $ X_k $ jest największe.

Ustalmy liczbę $ k\in\{0,1,2, \ldots,n\} $. Obliczymy liczbę trójek $ (A, B, C) $, dla których $ |A\cap B\cap C|=k $.

Jeśli $ (A,B,C) $ jest trójką podzbiorów zbioru $ S $, to każdy element zbioru $ S $ znajduje się w dokładnie jednym spośród następujących ośmiu zbiorów

\[<br />
(1)\qquad \begin{array}{l}<br />
A\cap B\cap C,\ (A\cap B)\backslash C,\ (B\cap C)\backslash A,\ (C\cap A)\backslash B,\\<br />
A\backslash (B\cup C),\ B\backslash (C\cup A),\ C\backslash (A\cup B),\ S\backslash (A\cup B\cup C).<br />
\end{array}<br />
\]

Aby uzyskać trójkę zbiorów $ (A,\ B,\ C) $, dla których $ |A\cap B\cap C|=k $, wybieramy najpierw $ k $ elementów zbioru $ S $, które umieścimy w zbiorze $ A\cap B\cap C $ — możemy to uczynić na $ n \choose k $ sposobów. Każdemu z pozostałych $ n-k $ elementów $ k $ przyporządkowujemy jedną z pozostałych siedmiu możliwości występujących w (1) — możemy to zrobić na $ 7^{n-k} $ sposobów. Opisane postępowanie określa jednoznacznie trójkę $ (A,B,C) $. Zatem liczba trójek $ (A,B,C) $, dla których $ |A \cap B \cap C| = k $ wynosi $ {n \choose k} \cdot 7^{n-k} $. Stąd uzyskujemy

\[<br />
P(X_{k})=\frac{{n \choose k} \cdot 7^{n-k}}{8^{n}}.<br />
\]

Aby wyznaczyć taką liczbę $ k $, dla której prawdopodobieństwo zajścia zdarzenia $ X_k $ jest największe, obliczamy iloraz

\[<br />
\frac{P(X_{k+1})}{P(X_{k})}=\frac{n-k}{7k+7}.<br />
\]

Stąd wynika, że

\[<br />
\left\{<br />
\begin{array}{ll}<br />
P(X_{k+1})>P(X_k),&\textrm{jeśli}\ k<\frac{1}{8}(n-7);\\<br />
P(X_{k+1})<P(X_k),&\textrm{jeśli}\ k>\frac{1}{8}(n-7);\\<br />
P(X_{k+1})=P(X_k),&\textrm{jeśli}\ k=\frac{1}{8}(n-7).\\<br />
\end{array}\right.<br />
\]

Oznaczając $ \lambda=[(n-7)/8] $, gdzie $ [x] $ jest największą liczbą całkowitą nie większą od $ x $, otrzymujemy

\[<br />
\begin{array}{l}<br />
P(X_{0})<P(X_{1})<P(X_{2})<\ldots<P(X_{\lambda})\leq P(X_{\lambda+1}),\\<br />
P(X_{\lambda+1})>P(X_{\lambda+2})>\ldots>P(X_{n}).<br />
\end{array}<br />
\]

Zatem prawdopodobieństwo $ P (X_k) $ jest największe dla $ k = \lambda+1 =[ \frac{1}{8} (n+1)] $.

Jeśli $ \frac{1}{8}(n-7) $ jest liczbą całkowitą, to istnieją dwie wartości $ k $, dla których liczba $ P(X_k) $ jest największa, a mianowicie $ k = \frac{1}{8} (n-7) $ oraz $ k = \frac{1}{8} (n+1) $.

Komentarze

Dodaj nową odpowiedź