Насколько бессимптически плохим является наивным перетасовкой?

Question

Хорошо известно, что этот «наивный» алгоритм для перетасовки массива, заменив каждый элемент другим случайно выбранным, не работает правильно:

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

В частности, поскольку в каждой из итераций $ n $ один из $ n $ выбора (с единой вероятностью), через вычисление существует $ n^n $ «Пути»; Поскольку количество возможных перестановок $ N! $ не делится равномерно на количество путей $ n^n $, этот алгоритм невозможно производить каждую из перестановки $ n! $ с одинаковой вероятностью. (Вместо этого следует использовать так называемый Фишер-Йейтс Shuffle, который, по сути, меняет вызов, чтобы выбрать случайное число из [0..n) с вызовом, чтобы выбрать случайное число из [i..n); Это спорно для моего вопроса, хотя.)

Что мне интересно, так это то, как может быть «плохо» наивным шаффл? Более конкретно, позволяя $ p (n) $ быть набором всех перестановок и $ c ( rho) $ числа путей через наивный алгоритм, которые производят результирующую перестановку $ rho in p (n) $, что асимптотическое поведение функций

$ qquad displaystyle m (n) = frac {n!} {n^n} max _ { rho in p (n)} c ( rho) $

а также

$ qquad displaystyle m (n) = frac {n!} {n^n} min _ { rho in p (n)} c ( rho) $?

Ведущий фактор состоит в том, чтобы «нормализовать» эти значения: если наивный перетасов

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

Я подозреваю, что (на основе некоторых компьютерных симуляций, которые я видел), что фактические значения ограничены от 1, но это даже известно, является ли $ lim m (n) $ конечным, или если $ lim m (n) $ ограничено от 0? Что известно о поведении этих величин?

Answer 1

По индукции мы покажем, что перестановка $ rho_n = (2,3,4, ldots, n, 1) $ является примером с $ c ( rho_n) = 2^{n-1} $. Если это худший случай, как и для первых нескольких $ n $ (см. Примечания для Последовательность OEI A192053), тогда $ m (n) abx (2/e)^{n} $. Таким образом, нормализованный мин, как и нормализованный макс, «экспоненциально плохо».

Базовый корпус прост. Для шага индукции нам нужна лемма:

Лемма: На любом пути от $ (2,3,4, ldots, n, 1) $ до $ (1,2,3, ldots, n) $, либо первые переводы, сводится на 1 $ и $ n $, или Последний ход обменивается позициями $ 1 $ и $ n $.

Доказательство эскиза: Предположим, нет. Рассмотрим первый шаг, который включает в себя позицию $ n $ '. Предположим, что это $ i $ 'th, $ i neq 1 $ и $ i neq n $. Этот ход должен разместить товар $ 1 $ в $ i $ 'That. Теперь рассмотрим следующий ход, который касается предмета $ 1 $. Предположим, что этот шаг - это $ J $ 'ho. Этот шаг должен поменять $ i $ и $ j $, перемещая товар $ 1 $ в $ j $ ', с $ i <J $. Аналогичный аргумент говорит, что пункт $ 1 $ может быть впоследствии перемещаться вправо. Но предмет $ 1 $ должен оказаться в первую очередь, что противоречит. $ square $

Теперь, если первый шаг меняет позиции $ 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} $ пути, которые делают это. Аргумент, аналогичный доказательству леммы, говорит о том, что нет пути, который касается первой позиции, так как пункт $ 1 $ должен оказаться в неправильной позиции.

Если последний шаг меняет позиции $ 1 $ и $ n $ $, первые ходы $ n-1 $ должны перенести перестановку $ (2,3,4, ldots, n, 1) $ в перестановку $ (n, 2 , 3,4, ldots, n-1, 1) $. Опять же, если эти движения не касаются последней позиции, то это перестановка $ rho_ {n-1} $, и при индукции есть $ c ( rho_ {n-1}) = 2^{n- 2} $ Пути, которые делают это. И опять же, если один из первых движений $ n-1 $ здесь затрагивает последнюю позицию, пункт $ 1 $ никогда не сможет оказаться в правильном месте.

Таким образом, $ c ( rho_n) = 2c ( rho_ {n-1}) = 2^{n-1} $.

Answer 2

После некоторого копания благодаря указателю Мхума на OEI, я наконец -то нашел отличный анализ и хороший (относительно) элементарный аргумент (насколько я могу судить, Гольдштейну и Моусу [1]), что $ m (N ) $ растет сверхэкспоненциально быстро в $ n $:

Любая инволюция $ iota $ of $ {1 ldots n } $ соответствует использованию алгоритма «наивного», который создает перестановку личности в качестве результата, поскольку алгоритм обменяется $ k $ с $ iota ( k) $ и впоследствии поменяйте $ iota (k) $ с $ k $, оставляя оба без изменений. Это означает, что количество прогонов алгоритма, которые дают перестановку личности, составляет как минимум количество вовлечений $ Q (n) $ (на самом деле, небольшое мышление показывает, что соответствие 1-1, и поэтому это точно $ Q ( n) $), и поэтому максимум в $ m (n) $ ограничен ниже $ q (n) $.

$ Q (n) $, по -видимому, носит ряд имен, включая телефонные номера : видеть http://oeis.org/a000085 а также http://en.wikipedia.org/wiki/telephone_number_%28mathematics%29 Анкет Асимптотики хорошо известны, и оказывается, что $ q (n) ablecx c left ( frac {n} {e} right)^{n/2} e^ sqrt {n} $; Из отношения рецидивов $ q (n) = q (n-1)+(n-1) q (n-2) $ можно показать, что отношение $ r (n) = frac {q (n) } {Q (n-1)} $ удовлетворяет $ sqrt {n} lt r (n) lt sqrt {n+1} $ и оттуда базовый анализ получает ведущий $ n^{n/2} $ Термин в асимптотике, хотя другие термины требуют более осторожных усилий. Поскольку «масштабный фактор» $ frac {n!} {N^n} $ в определении $ m (n) $ только около $ c sqrt {n} e^{-n} $, ведущий термин $ q (n) $ доминирует и допускает (асимптотически) $ m (n) geq cn^{(n+1)/2} e^{-3n/2+ sqrt {n}} $.

Гольдштейн и Моуз фактически продолжают показывать в [1], что перестановка личности является наиболее вероятной для крупных $ n $, поэтому $ geq $ на самом деле является $ примерно и поведение $ m (n) $ полностью урегулирован. Это все еще оставляет вопрос о поведении $ m (n) $ open; Я не был бы слишком удивлен, если бы это также уступило анализу в их статье, но у меня не было возможности прочитать его достаточно внимательно, чтобы по -настоящему понять их методы, только достаточно, чтобы Grok основной результат.

1] Гольдштейн Д. и Моуз, д. http://arxiv.org/abs/math/0010066