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

33

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

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

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

Мне интересно, насколько «плохим» может быть наивное перемешивание? Точнее говоря, пусть будет множеством всех перестановок, а будет числом путей через наивный алгоритм, который создает результирующую перестановку , что является асимптотическим поведением функцииC ( ρ ) ρ P ( n )P(n)C(ρ)ρP(n)

M(n)=n!nnmaxρP(n)C(ρ)

а также

m(n)=n!nnminρP(n)C(ρ) ?

Главным фактором является «нормализация» этих значений: если наивное перемешивание «асимптотически хорошо», то

limnM(n)=limnm(n)=1 .

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

Стивен Стадницки
источник
8
Хороший вопрос Я не знаю, где лучшее место для этого вопроса. Если не ясно, что другой форум лучше для него, я думаю, что вы должны оставить его здесь на неделю или около того, и если вы не получите удовлетворительного ответа, задайте его на одном из других форумов (и вставьте ссылки в оба вопроса ).
Питер Шор
4
@vzn "Почему сложный анализ по известному некорректному алгоритму?" Поскольку математика является интересной, и вы никогда не знаете , где могут возникнуть другие приложения - см анализ Кнута пузырьковой сортировки, например. Диаграммы Этвуда дают грубый качественный анализ неоднородности, но это далеко от математически количественного анализа. (И есть несколько различных эквивалентных формулировок Фишера-Yates перетасовки -. В одном я упоминаю работает просто отлично)
Стивен Stadnicki
4
Для записи, последовательность OEIS A192053 имеет значение max и не содержит закрытой формы. Кроме того, примечания к этой записи предполагают, что min может быть , подразумевая, что . C ( ρ ) 2 n -C(ρ)C(ρ) м(n)02n1m(n)0
mhum
2
@vzn Что не так с открытыми вопросами?
Юваль Фильмус
1
@vzn Не согласен с твоим последним предложением, там много анализа "несовершенных" перемешиваний. Например, если мы делаем случайные транспозиции, известно, что порог случайности составляет примерно . Нынешний вопрос может быть сложным, но априори трудно сказать, является ли он «очень сложным». Ответ типа mhum уже очень удовлетворяет, показывая, что вопрос был уместен для форума и не представлял непреодолимого барьера (формальные доказательства отложены). (1/2)nlogn
Юваль Фильмус

Ответы:

13

По индукции мы покажем, что перестановка является примером с . Если это наихудший случай, как и для первых нескольких (см. Примечания к последовательности OEIS A192053 ), то . Таким образом, нормализованный минимум, как и нормализованный максимум, является «экспоненциально плохим».C ( ρ n ) = 2 n - 1 n m ( n ) ( 2 / e ) nρn=(2,3,4,,n,1)C(ρn)=2n1nm(n)(2/e)n

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

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

Эскиз доказательства: предположим, что нет. Рассмотрим первый ход, включающий -ю позицию. Предположим, что это -й ход, и . Этот ход должен поместить элемент в -е место. Теперь рассмотрим следующий ход, который касается предмета . Предположим, этот ход является -м ходом. Этот ход должен поменять местами и , переместив элемент на -е место, где . Аналогичный аргумент говорит о том, что пункт можно только впоследствии сдвинуть вправо. Но пунктi i 1 i n 1 i 1 j i j 1 j i < j 1 1 nii1in1i1jij1ji<j11должно закончиться в первую очередь, противоречие.

Теперь, если первый ход меняет позиции и , оставшиеся ходы должны переставить в . Если оставшиеся ходы не касаются первой позиции, то это перестановка в позициях , и по индукции мы знаем, что есть пути, которые делают это. Аргумент, аналогичный доказательству леммы, говорит о том, что не существует пути, который касается первой позиции, поскольку элемент должен затем оказаться в неправильной позиции.n ( 1 , 3 , 4 , 5 , , n , 2 ) ( 1 , 2 , 3 , 4 , , n ) ρ n - 1 2 n C ( ρ n - 1 ) = 2 n - 2 11n(1,3,4,5,,n,2)(1,2,3,4,,n)ρn12nC(ρn1)=2n21

Если последний ход меняет местами и , то первые ходы должны перевести перестановку в перестановку . Опять же, если эти шаги не касаются последней позиции, то это перестановка , и по индукции есть путей это сделать И снова, если один из первых ходов коснется последней позиции, элемент никогда не может оказаться в правильном месте.n n - 1 ( 2 , 3 , 4 , , n , 1 ) ( n , 2 , 3 , 4 , , n - 1 , 1 ) ρ n - 1 C ( ρ n - 1 ) = 2 n - 2 n - 1 11nn1(2,3,4,,n,1)(n,2,3,4,,n1,1)ρn1C(ρn1)=2n2n11

Таким образом, .C(ρn)=2C(ρn1)=2n1

Питер Шор
источник
Идеально - аргумент, лежащий в основе леммы, очень похож на аргумент, который я использовал для инволюций, являющихся единственным способом получения перестановки идентификаторов, но я упустил рекурсивную структуру в явном обмене. Спасибо!
Стивен Стадницки
10

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

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

Q ( n ) C ( nQ(n) очевидно, идет по нескольким именам, включая номера телефонов : см. Http://oeis.org/A000085 и http://en.wikipedia.org/wiki/Telephone_number_%28matmatics%29 . Асимптотика хорошо известна, и оказывается, что ; из рекуррентного соотношения можно индуктивно показать, что отношение удовлетворяет и оттуда базовый анализ получает ведущий член в асимптотике, хотя другой сроки требуют более тщательных усилий. Поскольку «масштабный фактор» Q(n)=Q(n-1)+(n-1)Q(n-2)R(n)=Q(n)Q(n)C(ne)n/2enQ(n)=Q(n1)+(n1)Q(n2)R(n)=Q(n)Q(n1) n n / 2 n !n<R(n)<n+1nn/2 M(n)Cn!nn в определении только о , главный член доминирует и дает (асимптотически) .M(n) Q(n)M(n)Cn ( n + 1 ) / 2 e - 3 n / 2 + CnenQ(n)M(n)Cn(n+1)/2e3n/2+n

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

[1] Гольдштейн Д. и Мьюз Д.: «Идентичность - наиболее вероятный случайный обмен для больших n», http://arxiv.org/abs/math/0010066

Стивен Стадницки
источник
1
Нетрудно показать, что перестановка является примером с . Если это наихудший случай, как и для первых нескольких , то . C ( ρ ) = 2 n - 1 n m ( n ) ( 2 / e ) n(2,3,4,...,N,1)С(ρ)знак равно2N-1Nм(N)(2/е)N
Питер Шор
@PeterShor Можете ли вы привести основной аргумент? Я чувствую, что мне не хватает какой-то простой версии аргумента инволюции, которая бы работала, но я не совсем понимаю. Я думаю, что даже если это не совсем минимально, этого было бы достаточно; минимальное число кажется маловероятным в и просто зная, что нормализованные max и min являются «экспоненциально плохими», это довольно удовлетворительный ответ. N
Стивен Стадницки
Я добавил ответ с аргументом ... это слишком долго для комментария.
Питер Шор