Jak asymptotycznie źle jest naiwne tasowanie?

Powszechnie wiadomo, że ten „naiwny” algorytm tasowania tablicy poprzez zamianę każdego elementu na inny losowo wybrany nie działa poprawnie:

for (i=0..n-1)
  swap(A[i], A[random(n)]);

W szczególności, ponieważ w każdym z $n$ powtórzeń, jeden z $n$ wyboru jest (z jednolitego prawdopodobieństwa) jest $n^n$ możliwych ścieżek „” do obliczeń; ponieważ liczba możliwych permutacji $n!$nie dzieli się równomiernie na liczbę ścieżek $n^n$ , algorytm nie jest w stanie wygenerować każdego z $n!$permutacje z jednakowym prawdopodobieństwem. (Zamiast tego należy użyć tak zwanego losowania Fischera-Yatesa , który zasadniczo zmienia połączenie, aby wybrać losową liczbę z [0..n) z połączeniem, aby wybrać losową liczbę z [i..n); jest to jednak kwestia mojego pytania).

Zastanawiam się, jak „zły” może być naiwny los. Mówiąc dokładniej, pozwalając $P(n)$ być zbiorem wszystkich permutacji, a $C(\rho)$ być liczbą ścieżek przez naiwny algorytm, który wytwarza wynikową permutację $\rho\in P(n)$ , jakie jest asymptotyczne zachowanie funkcji

$\qquad \displaystyle M(n) = \frac{n!}{n^n}\max_{\rho\in P(n)} C(\rho)$

i

? $\qquad \displaystyle m(n) = \frac{n!}{n^n}\min_{\rho\in P(n)} C(\rho)$

Najważniejszym czynnikiem jest „normalizacja” tych wartości: jeśli naiwny los jest „asymptotycznie dobry”, to znaczy

. $\qquad \displaystyle \lim_{n\to\infty}M(n) = \lim_{n\to\infty}m(n) = 1$

Podejrzewam (na podstawie niektórych symulacjach komputerowych widziałem), że rzeczywiste wartości są ograniczone od 1, ale jest jeszcze wiadomo, czy jest skończony, czy lim m ( n ) jest ograniczony od 0? Co wiadomo o zachowaniu tych ilości?$\lim M(n)$$\lim m(n)$

Pokażemy przez indukcję, że permutacja jest przykładem z C ( ρ n ) = 2 n - 1 . Jeśli jest to najgorszy przypadek, tak jak w przypadku pierwszych kilku n (patrz uwagi do sekwencji OEIS A192053 ), to m ( n ) ≈ ( 2 / e ) $\rho_n = (2,3,4,\ldots, n,1)$$C(\rho_n) = 2^{n-1}$$n$$m(n) \approx (2/e)^{n}$. Znormalizowana wartość minimalna, podobnie jak znormalizowana wartość maksymalna, jest „wykładniczo zła”.

Podstawa jest łatwa. Na etapie wprowadzenia potrzebujemy lematu:

Lemat: W każdej ścieżce od do ( 1 , 2 , 3 , ... , n ) , albo pierwszy ruch swap pozycji 1 i n , lub ostatni ruch swap pozycji 1 i n .$(2,3,4, \ldots, n, 1)$$(1,2,3, \ldots, n)$$1$$n$$1$$n$

Szkic próbny: Załóżmy, że nie. Rozważ pierwszy ruch, który obejmuje -tą pozycję. Załóżmy, że jest i -tym ruch, i ≠ 1 i I ≠ n . Ten ruch musi umieścić przedmiot 1 na i miejscu. Teraz rozważ następny ruch, który dotknie przedmiotu 1 . Załóżmy, że ten ruch jest j -ty. Ten ruch musi zamienić i i j , przesuwając element 1 na j -te miejsce, z i < j . Podobny argument mówi, że pozycja $n$$i$$i\neq 1$$i \neq n$$1$$i$$1$$j$$i$$j$$1$$j$$i < j$$1$ can only subsequently be moved to the right. But the item $1$ needs to end up in the first place, a contradiction. $\square$

Teraz, jeżeli pierwsze swapy ruch z pozycji i n , pozostałe przemieszcza musi mieć permutacji ( 1 , 3 , 4 , 5 , ... , n , 2 ) do ( 1 , 2 , 3 , 4 , ... , n ) . Jeśli pozostałe ruchy nie dotykają pierwszej pozycji, to jest to permutacja ρ n - 1 na pozycjach 2 … n , a dzięki indukcji wiemy, że są$1$$n$$(1, 3,4,5, \ldots, n,2)$$(1,2,3,4, \ldots, n)$$\rho_{n-1}$$2 \ldots n$$C(\rho_{n-1})=2^{n-2}$ paths that do this. An argument similar to the proof of the Lemma says that there is no path that touches the first position, as the item $1$ must then end up in the incorrect position.

$1$$n$$n-1$$(2,3,4,\ldots, n,1)$$(n,2, 3,4, \ldots, n-1, 1)$. Again, if these moves don't touch the last position, then this is the permutation $\rho_{n-1}$, and by induction there are $C(\rho_{n-1})=2^{n-2}$$n-1$$1$

$C(\rho_n) = 2C(\rho_{n-1}) = 2^{n-1}$.

After some digging around thanks to mhum's pointer to OEIS, I've finally found an excellent analysis and a nice (relatively) elementary argument (due, as far as I can tell, to Goldstein and Moews [1]) that $M(n)$ grows superexponentially fast in $n$:

Any involution $\iota$ of $\{1\ldots n\}$ corresponds to a run of the 'naive' shuffling algorithm that produces the identity permutation as its result, since the algorithm will swap $k$ with $\iota(k)$ and subsequently swap $\iota(k)$ with $k$, leaving both unchanged. This means that the number of runs of the algorithm that yield the identity permutation is at least the number of involutions $Q(n)$ (in fact, a little thinking shows that the correspondence is 1-1 and so it's exactly $Q(n)$), and so the maximum in $M(n)$ is bounded from below by $Q(n)$.

$Q(n)$ apparently goes by a number of names, including the telephone numbers : see http://oeis.org/A000085 and http://en.wikipedia.org/wiki/Telephone_number_%28mathematics%29 . The asymptotics are well-known, and it turns out that $Q(n) \approx C\left(\frac{n}{e}\right)^{n/2}e^\sqrt{n}$; from the recurrence relation $Q(n) = Q(n-1)+(n-1)Q(n-2)$ it can be inductively shown that the ratio $R(n) = \frac{Q(n)}{Q(n-1)}$ satisfies $\sqrt{n}\lt R(n)\lt\sqrt{n+1}$ and from there basic analysis gets the leading $n^{n/2}$ term in the asymptotics, though the other terms require a more careful effort. Since the 'scale factor' $\frac{n!}{n^n}$ in the definition of $M(n)$ is only about $C\sqrt{n}e^{-n}$, the leading term of $Q(n)$ dominates and yields (asymptotically) $M(n)\geq Cn^{(n+1)/2}e^{-3n/2+\sqrt{n}}$.

Goldstein and Moews in fact go on to show in [1] that the identity permutation is the most likely for large $n$, so the $\geq$ is in fact a $\approx$ and the behavior of $M(n)$ is fully settled. This still leaves the question of the behavior of $m(n)$ open; I wouldn't be too surprised if that also yielded to the analysis in their paper, but I haven't had opportunity to read it closely enough yet to really get a grip on their methods, only enough to grok the basic result.

[1] Goldstein, D. and Moews, D.: "The identity is the most likely exchange shuffle for large n", http://arxiv.org/abs/math/0010066