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.

  • Wersja do wydrukuWersja do wydruku
  • Podziel się / Zapisz

Komentarze

Dodaj nową odpowiedź