XL OM - II - Zadanie 2

Dla losowo wybranej permutacji $ \mathbf{f} = (f_1,</p> <p>\ldots, f_n) $ zbioru $ \{1,\ldots, n\} $ oznaczmy przez $ X(\mathbf{f}) $ największą liczbę $ k \leq n $ taką, że $ f_i < f_{i+1} $ dla wszystkich numerów $ i < k $. Udowodnić, że wartość oczekiwana zmiennej losowej $ X $ wynosi $ \sum_{k=1}^n \frac{1}{k!} $.

Rozwiązanie

Rozważana zmienna losowa zależy oczywiście od $ n $. Oznaczmy ją wobec tego przez $ X_n $. Znajdziemy zależność rekurencyjną między wartościami oczekiwanymi zmiennych $ X_{n-1} $ i $ X_n $ .

Weźmy dowolną permutację $ f = (f_1, \ldots , f_n) $ zbioru $ \{1,\ldots, n\} $. Po odrzuceniu wyrazu $ f_n $ otrzymujemy permutację pewnego $ (n -1) $ - elementowego zbioru różnych liczb. Długość początkowego odcinka tworzącego ciąg rosnący to wartość zmiennej $ X_{n-1} $. (Nie jest bowiem istotne, czy permutowanym zbiorem jest, zgodnie z definicją $ X_{n-1} $ , zbiór $ \{1,\ldots, n-1\} $ , czy też dowolny inny zbiór liniowo uporządkowany przez relację mniejszości.)

Dołączamy z powrotem wyraz $ f_n $. Długość początkowego odcinka tworzącego ciąg rosnący pozostanie nie zmieniona lub zwiększy się o $ 1 $. Zwiększenie to nastąpi tylko w jednym przypadku: gdy permutacja $ f $ jest identyczna z ciągiem $ (1,2, \ldots , n) $. Prawdopodobieństwo takiego zdarzenia wynosi $ 1/n! $.

Dostajemy więc zależność

\[<br /> X_n= \left\{<br /> \begin{array}{ll}<br /> X_{n-1} & \textrm{z prawdopodobieństwem } 1-1/n!\\<br /> X_{n-1}+1 & \textrm{z prawdopodobieństwem } 1/n!<br /> \end{array}<br /> \right.<br /> \]

Stąd natychmiast wynika wzór rekurencyjny

\[<br /> E(X_n) = E(X_{n-1}) + \frac{1}{n!} .<br /> \]

Ponieważ zaś $ E(X_1) = 1 $, dany do udowodnienia w zadaniu wzór otrzymujemy przez oczywistą indukcję.

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

Komentarze

Dodaj nową odpowiedź