XL OM - II - Zadanie 2

Zawody matematyczne:

XL OM, 1988-1989

Etap:

Dla losowo wybranej permutacji $\mathbf{f} = (f_1, \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ść

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

Stąd natychmiast wynika wzór rekurencyjny

$ E(X_n) = E(X_{n-1}) + \frac{1}{n!} . $

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