XLVI OM - I - Zadanie 11

Dane są liczby naturalne $ n > m > 1 $. Ze zbioru $ \{1,2, \ldots ,n\} $ losujemy bez zwracania $ m $ liczb. Obliczyć wartość oczekiwaną różnicy między największą a najmniejszą wylosowaną liczbą.

Rozwiązanie

Zdarzeniem elementarnym jest wybór $ m $-elementowego podzbioru ze zbioru $ n $-elementowego. Te zdarzenia elementarne są jednakowo prawdopodobne; jest ich $ {n}\choose{m} $. Oznaczmy największą i najmniejszą wybraną liczbę odpowiednio przez $ a $ i $ b $. Rozważana zmienna losowa $ X $, czyli różnica $ a-b $, może przyjąć każdą wartość całkowitą od $ m - 1 $ do $ n-1 $.

Ustalmy liczbę naturalną $ r $ spełniającą nierówności $ m-1 \leq r \leq n- 1 $. W zbiorze $ \{1,2,\ldots,n\} $ jest $ n - r $ par liczb $ a $, $ b $ o różnicy $ a - b = r $. Przy ustalonym położeniu liczb $ a $ i $ b $ mamy $ {r-1}\choose{m-2} $ możliwości wyboru pozostałych $ m-2 $ liczb ze zbioru $ \{b+1,\ldots,a-1\} $. Wobec tego iloczyn $ (n -r) {{r-1}\choose{m-2}} $ wyraża ilość $ m $-elementowych podzbiorów zbioru $ \{1,2,\ldots,n\} $, w których różnica między największym a najmniejszym elementem wynosi $ r $ - czyli ilość zdarzeń elementarnych, w których badana zmienna losowa $ X $ przyjmuje wartość $ r $.

Dzieląc ten iloczyn przez liczbę wszystkich zdarzeń elementarnych otrzymujemy prawdopodobieństwo tego, że $ X = r $; oznaczmy je przez $ p_r $. Tak więc

\[<br />
p_r = P(X=r)= {{n}\choose{m}}^{-1} (n-r) {{r-1}\choose{m-2}}.<br />
\]

Korzystając z łatwych do uzasadnienia związków

\[<br />
{{r-1}\choose{m-2}} =\frac{m - 1}{r} {{r}\choose{m-1}}= \frac{(m-1)m}{r(r+1)} {{r+1}\choose{m}}<br />
\]

przekształcamy uzyskane wyrażenie, jak następuje:

\[<br />
\begin{split}<br />
p_r & = {{n}\choose{m}}^{-1} \left[ (n+1) {{r-1}\choose{m-2}} - (r+1) {{r-1}\choose{m-2}} \right]=\\<br />
& = {{n}\choose{m}}^{-1} \cdot \frac{m-1}{r} \left[ (n+1) {{r}\choose{m-1}} - m {{r+1}\choose{m}} \right].<br />
\end{split}<br />
\]

Ponieważ $ r $ przebiega wartości od $ m-1 $ do $ n-1 $, zatem wartość oczekiwana zmiennej losowej $ X $, czyli liczba

\[<br />
E(X) = \sum_{r=m-1}^{n-1} rp_r,<br />
\]

jest równa

\[<br />
(1) \qquad \quad E(X)= {{n}\choose{m}}^{-1} (m-1) \left[ (n+1) \sum_{r=m-1}^{n-1} {{r}\choose{m-1}} - m \sum_{r=m-1}^{n-1} {{r+1}\choose{m}} \right].<br />
\]

Aby zwinąć sumy w nawiasie kwadratowym, skorzystamy ze wzoru

\[<br />
(2) \qquad \quad \sum_{s=j}^N {{s}\choose{j}} = {{N+1}\choose{j+1}} \quad \textrm{dla} \quad N \geq j \geq 0<br />
\]

(patrz: Uwaga). Przyjmując w tym wzorze najpierw $ N= n -1 $, $ j = m-1 $, a następnie $ N = n $, $ j = m $, otrzymujemy kolejno:

\[<br />
\sum_{r=m-1}^{n-1} {{r}\choose{m-1}} = {{n}\choose{m}}, \quad<br />
\sum_{r=m-1}^{n-1} {{r+1}\choose{m}} = \sum_{s=m}^{n} {{s}\choose{m}}= {{n+1}\choose{m+1}}<br />
\]

(zastosowaliśmy zmianę wskaźnika sumowania: $ s = r + 1 $). Możemy teraz dokończyć rachunek (1):

\[<br />
\begin{split}<br />
E(X)& = {{n}\choose{m}}^{-1} (m-1) \left[ (n+1) {{n}\choose{m}} - m {{n+1}\choose{m+1}} \right]=\\<br />
& = (m-1) \left[ (n+1) - m \cdot \frac{(n+1)!}{(m+1)!(n-m)!} \cdot \frac{m!(n-m)!}{n!} \right]=\\<br />
& = (m-1) \left[ (n+1) - m \cdot \frac{n+1}{m+1} \right]= \frac{(m-1)(n+1)}{m+1}.<br />
\end{split}<br />
\]

Jest to szukana wartość.

Uwaga. Wzór (2) jest dobrze znany. Można go łatwo udowodnić przez indukcję względem $ N $ przy ustalonym $ j $. Można go też ,,zobaczyć'', przyglądając się uważnie trójkątowi Pascala; proponujemy to Czytelnikom jako przyjemne ćwiczenie spostrzegawczości.

Komentarze

Dodaj nową odpowiedź