Oczekiwana długość cyklu w losowym zbiorze

Procesy stochastyczne. Sposoby racjonalizowania wielkich ilości informacji. Matematyka w naukach społecznych.
matemix
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 10 cze 2008, o 19:38
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 12 razy
Pomógł: 1 raz

Oczekiwana długość cyklu w losowym zbiorze

Post autor: matemix »

Wiemy, że oczekiwania długość cyklu w losowej permutacji o wielkości \(\displaystyle{ n}\) wynosi \(\displaystyle{ \frac {n+1}{2}}\):

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Random_permutation_statistics#Expected_cycle_size_of_a_random_element


Rozważmy jednak zbiór \(\displaystyle{ 2^{n}}\) elementowy liczb n-bitowych. W takim zbiorze liczby mogą się powtarzać. Przykładowo tworzymy zbiór \(\displaystyle{ 1024}\) elementowy losując liczby z przedziału od \(\displaystyle{ 0}\) do \(\displaystyle{ 1023}\). Następnie przyporządkowujemy liczbom liczby porządkowe (załóżmy, że również od zera do \(\displaystyle{ 1023}\)).

Teraz możemy poszukać cykli, jak w typowej permutacji. Niektóre liczby będą wpadać w cykle, niektóre będą elementami cykli. Pytanie jaka jest oczekiwania długość cyklu w takiej permutacji/zbiorze (chyba nie można tego nazwać permutacją)?

Dodano po 33 minutach 55 sekundach:
Może podam jeszcze mały przykład:

\(\displaystyle{ ( _{ 29 \ \ 59 \ \ 62 \ \ 14 \ \ 58 \ \ 29 \ \ 1 \ \ 42 \ \ 0 \ \ 53 \ \ 41 \ \ 63 \ \ 53 \ \ 56 \ \ 48 \ \ 27 \ \ 45 \ \ 26 \ \ 32 \ \ \ \ 7 \ \ \ \ 0 \ \ \ \ 2 \ \ 53 \ \ 63 \ \ 56 \ \ 63 \ \ 28 \ \ 62 \ \ 3 \ \ \ \ 7 \ \ \ \ 4 \ \ \ \ 48 \ \ 35 \ \ 63 \ \ 15 \ \ 28 \ \ 26 \ \ 8 \ \ \ \ 7 \ \ \ \ 7 \ \ \ \ 31 \ \ 0 \ \ \ \ 62 \ \ 35 \ \ 33 \ \ 18 \ \ 14 \ \ 17 \ \ 2 \ \ \ \ 58 \ \ 35 \ \ 60 \ \ 48 \ \ 45 \ \ 54 \ \ 52 \ \ 61 \ \ 3 \ \ \ \ 14 \ \ 20 \ \ 63 \ \ 31 \ \ 17 \ \ 63 } ^{0 \ \ \ \ 1 \ \ \ \ 2 \ \ \ \ 3 \ \ \ \ 4 \ \ \ \ 5 \ \ \ \ 6 \ \ 7 \ \ \ \ 8 \ \ 9 \ \ \ \ 10 \ \ 11 \ \ 12 \ \ 13 \ \ 14 \ \ 15 \ \ 16 \ \ 17 \ \ 18 \ \ 19 \ \ 20 \ \ 21 \ \ 22 \ \ 23 \ \ 24 \ \ 25 \ \ 26 \ \ 27 \ \ 28 \ \ 29 \ \ 30 \ \ 31 \ \ 32 \ \ 33 \ \ 34 \ \ 35 \ \ 36 \ \ 37 \ \ 38 \ \ 39 \ \ 40 \ \ 41 \ \ 42 \ \ 43 \ \ 44 \ \ 45 \ \ 46 \ \ 47 \ \ 48 \ \ 49 \ \ 50 \ \ 51 \ \ 52 \ \ 53 \ \ 54 \ \ 55 \ \ 56 \ \ 57 \ \ 58 \ \ 59 \ \ 60 \ \ 61 \ \ 62 \ \ 63} )}\)

Zaczynając od \(\displaystyle{ 29}\) otrzymujemy:

\(\displaystyle{ 29 \rightarrow 7 \rightarrow 42 \rightarrow 62 \rightarrow 17 \rightarrow 26 \rightarrow 28 \rightarrow 3 \rightarrow 14 \rightarrow 48 \rightarrow 2 \rightarrow 62 }\)

Kończymy zatem z cyklem o długości \(\displaystyle{ 8}\). Nie wiem, czy akurat w tym zbiorze jest więcej cykli, ani jaka jest średnia długość cyklu.

Dodano po 16 godzinach 38 minutach 57 sekundach:
Wstępnie udało mi się ustalić, że liczba unikalnych liczb w takim zbiorze wynosi prawdopodobnie około:

\(\displaystyle{ w=(1-\frac{1}{e}) \cdot 2^{n}}\)

Możemy zatem rozpatrywać pary liczb od \(\displaystyle{ 0}\) do \(\displaystyle{ w}\) (liczba porządkowa plus liczba ze zbioru), bez powtórzeń. Pytanie jaka jest oczekiwania długość cyklu w czymś takim? Na pewno mniejsza niż oczekiwana długość cyklu w losowej permutacji o liczbie elementów \(\displaystyle{ w}\), bo tutaj mamy tylko \(\displaystyle{ w}\) par, ale wylosowanych z przedziału większego niż \(\displaystyle{ w}\).
ODPOWIEDZ