W jaki sposób obliczyć wartość oczekiwaną liczby cykli w permutacji losowej \(\displaystyle{ n}\) liczb?
Największym (chyba) problemem jest tu zliczenie ile jest permutacji o dokładnie \(\displaystyle{ k}\) cyklach, jak je zliczyć?
Wartość oczekiwana liczby cykli w permutacji
-
Kartezjusz
- Użytkownik
- Posty: 7330
- Rejestracja: 14 lut 2008, o 08:31
- Płeć: Mężczyzna
- Lokalizacja: Z Bielskia-Białej
- Podziękował: 6 razy
- Pomógł: 961 razy
-
MatXXX
- Użytkownik
- Posty: 59
- Rejestracja: 2 gru 2014, o 18:25
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 17 razy
Wartość oczekiwana liczby cykli w permutacji
Będziemy tworzyć permutację element po elemencie w zapisie kanonicznym. Weźmy \(\displaystyle{ n}\) niezależnych zmiennych zero-jedynkowych \(\displaystyle{ X_1...X_n}\). Niech \(\displaystyle{ X_i = 1}\) wtw gdy w \(\displaystyle{ i}\)-tym kroku zamykamy cykl (czyli wybierając \(\displaystyle{ i}\)-ty element trafiamy na taki, który przechodzi w pierwszy element aktualnego cyklu). \(\displaystyle{ Pr[X_i=1]=\frac{1}{n-(i-1)}}\), bo mamy do wyboru \(\displaystyle{ n-(i-1)}\) elementów i tylko jeden z nich przechodzi na pierwszy element w rozpatrywanym cyklu (gdy takiego elementu nie ma, czyli w poprzednim kroku zamknęliśmy cykl, to można liczyć ile jest możliwych par postaci \(\displaystyle{ <a,a>}\) wsród par \(\displaystyle{ <x,y>}\), gdzie \(\displaystyle{ x,y\in\{1...n-(i-1)\}}\)).
\(\displaystyle{ E[X]= \sum_{k=1}^{n}E[X_i] = \sum_{k=1}^{n}\frac{1}{n-(i-1)} = \sum_{k=1}^{n}\frac{1}{k} = H_n}\)
Można też rozpatrywać indykatory \(\displaystyle{ X_A}\), gdzie \(\displaystyle{ A}\) jest pewnym zbiorem, takie, że \(\displaystyle{ X_A = 1}\) wtw istnieje w permutacji cykl z elementów zbioru \(\displaystyle{ A}\). Wtedy \(\displaystyle{ E[X_A]=Pr[X_A = 1]=\frac{(|A|-1)! \cdot (n-|A|)!}{n!}}\), bo ustalamy jeden z elementów zbioru \(\displaystyle{ A}\) jako pierwszy element permutacji (nie ma znaczenia który, bo zawsze można uzyskać inny przez przesunięcie cykliczne zapisu permutacji), ustalamy permutację oraz pozostałe elementy oraz wybieramy takie permutacje ze zbioru wszystkich permutacji o mocy \(\displaystyle{ n!}\) .
\(\displaystyle{ E[X] = \sum_{k=1}^{n}\sum_{A \subseteq \{1..n\}, |A| = k}E[X_A] = \sum_{k=1}^{n} {n \choose k} \cdot \frac{(k-1)! \cdot (n-k)}{n!} = \sum_{k=1}^{n}\frac{1}{k} = H_n}\)
\(\displaystyle{ E[X]= \sum_{k=1}^{n}E[X_i] = \sum_{k=1}^{n}\frac{1}{n-(i-1)} = \sum_{k=1}^{n}\frac{1}{k} = H_n}\)
Można też rozpatrywać indykatory \(\displaystyle{ X_A}\), gdzie \(\displaystyle{ A}\) jest pewnym zbiorem, takie, że \(\displaystyle{ X_A = 1}\) wtw istnieje w permutacji cykl z elementów zbioru \(\displaystyle{ A}\). Wtedy \(\displaystyle{ E[X_A]=Pr[X_A = 1]=\frac{(|A|-1)! \cdot (n-|A|)!}{n!}}\), bo ustalamy jeden z elementów zbioru \(\displaystyle{ A}\) jako pierwszy element permutacji (nie ma znaczenia który, bo zawsze można uzyskać inny przez przesunięcie cykliczne zapisu permutacji), ustalamy permutację oraz pozostałe elementy oraz wybieramy takie permutacje ze zbioru wszystkich permutacji o mocy \(\displaystyle{ n!}\) .
\(\displaystyle{ E[X] = \sum_{k=1}^{n}\sum_{A \subseteq \{1..n\}, |A| = k}E[X_A] = \sum_{k=1}^{n} {n \choose k} \cdot \frac{(k-1)! \cdot (n-k)}{n!} = \sum_{k=1}^{n}\frac{1}{k} = H_n}\)