XLVI OM - I - Zadanie 11

Zawody matematyczne:

XLVI OM, 1994-1995

Etap:

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

$ p_r = P(X=r)= {{n}\choose{m}}^{-1} (n-r) {{r-1}\choose{m-2}}. $

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

$ {{r-1}\choose{m-2}} =\frac{m - 1}{r} {{r}\choose{m-1}}= \frac{(m-1)m}{r(r+1)} {{r+1}\choose{m}} $

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

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

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

$ E(X) = \sum_{r=m-1}^{n-1} rp_r, $

jest równa

$ (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]. $

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

$ (2) \qquad \quad \sum_{s=j}^N {{s}\choose{j}} = {{N+1}\choose{j+1}} \quad \textrm{dla} \quad N \geq j \geq 0 $

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

$ \sum_{r=m-1}^{n-1} {{r}\choose{m-1}} = {{n}\choose{m}}, \quad \sum_{r=m-1}^{n-1} {{r+1}\choose{m}} = \sum_{s=m}^{n} {{s}\choose{m}}= {{n+1}\choose{m+1}} $

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

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

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.