osobliwy nick
2021-09-30 15:11:20 UTC
Wiemy, że oczekiwania długość cyklu w losowej permutacji o wielkości n wynosi (n+1)/2:
https://en.wikipedia.org/wiki/Random_permutation_statistics#Expected_cycle_size_of_a_random_element
Rozważmy jednak zbiór 2^n elementowy liczb n-bitowych. W takim zbiorze liczby mogą się powtarzać. Przykładowo tworzymy zbiór 1024 elementowy losując liczby z przedziału od 0 do 1023. Następnie przyporządkowujemy liczbom liczby porządkowe (załóżmy, że również od zera do 1023).
Teraz możemy poszukać cykli, jak w typowej permutacji. Niektóre liczby będą wpadać w cykle, niektóre będą elementami cykli. Może podam jeszcze mały przykład:
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
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
Zaczynając od 29 otrzymujemy:
29 -> 7 -> 42 -> 62 -> 17 -> 26 -> 28 -> 3 -> 14 -> 48 -> 2 -> 62
Kończymy zatem z cyklem o długości 8. Nie wiem, czy akurat w tym zbiorze jest więcej cykli, ani jaka jest średnia długość cyklu.
1. Jaka jest oczekiwania długość cyklu w czymś takim?
2. Jaka jest oczekiwana liczba kroków, po których losowa liczba wpadnie w cykl?
3. Jakie jest prawdopodobieństwo, że dostaniemy jakiś krótki cykl o długości m, zaczynając od losowego elementu (m < 2^n)?
Wstępnie udało mi się ustalić, że liczba unikalnych liczb w takim zbiorze wynosi prawdopodobnie około:
w = 1-1/e * 2^n
Możemy zatem rozpatrywać pary liczb od 0 do 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 w, bo tutaj mamy tylko w par, ale wylosowanych z przedziału większego niż w.
https://en.wikipedia.org/wiki/Random_permutation_statistics#Expected_cycle_size_of_a_random_element
Rozważmy jednak zbiór 2^n elementowy liczb n-bitowych. W takim zbiorze liczby mogą się powtarzać. Przykładowo tworzymy zbiór 1024 elementowy losując liczby z przedziału od 0 do 1023. Następnie przyporządkowujemy liczbom liczby porządkowe (załóżmy, że również od zera do 1023).
Teraz możemy poszukać cykli, jak w typowej permutacji. Niektóre liczby będą wpadać w cykle, niektóre będą elementami cykli. Może podam jeszcze mały przykład:
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
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
Zaczynając od 29 otrzymujemy:
29 -> 7 -> 42 -> 62 -> 17 -> 26 -> 28 -> 3 -> 14 -> 48 -> 2 -> 62
Kończymy zatem z cyklem o długości 8. Nie wiem, czy akurat w tym zbiorze jest więcej cykli, ani jaka jest średnia długość cyklu.
1. Jaka jest oczekiwania długość cyklu w czymś takim?
2. Jaka jest oczekiwana liczba kroków, po których losowa liczba wpadnie w cykl?
3. Jakie jest prawdopodobieństwo, że dostaniemy jakiś krótki cykl o długości m, zaczynając od losowego elementu (m < 2^n)?
Wstępnie udało mi się ustalić, że liczba unikalnych liczb w takim zbiorze wynosi prawdopodobnie około:
w = 1-1/e * 2^n
Możemy zatem rozpatrywać pary liczb od 0 do 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 w, bo tutaj mamy tylko w par, ale wylosowanych z przedziału większego niż w.