Как доказать правильность алгоритма перетасовки?

cs.stackexchange https://cs.stackexchange.com/questions/2152

Вопрос

У меня есть два способа составления списка элементов в случайном порядке, и я хотел бы определить, являются ли они одинаково справедливыми (беспристрастными).

Первый метод, который я использую,-это построить весь список элементов, а затем сделать перетасование на нем (скажем, перетасование Fisher-Yates). Второй метод - это скорее итеративный метод, который держит список перетасовки при каждой вставке. В псевдокоде функция вставки:

insert( list, item )
    list.append( item )
    swap( list.random_item, list.last_item )

Меня интересует, как кто -то показывает справедливость этого конкретного перетасовки. Преимущества этого алгоритма, где он используется, достаточно, что даже если немного несправедливо, это будет хорошо. Чтобы решить, мне нужен способ оценить его справедливость.

Моя первая идея заключается в том, что мне нужно рассчитать возможные общие перестановки по сравнению с общим возможным перестановкой для набора конечной длины. Однако я немного не могу рассчитать пересечение перестановки, возникающих в результате этого алгоритма. Я также не могу быть уверен, что это лучший или самый простой подход.

Это было полезно?

Решение

Во -первых, давайте сделаем два, возможно, очевидные, но важные предположения:

  1. _.random_item может выбрать последнюю позицию.
  2. _.random_item Выбирает каждую позицию с вероятностью $ frac {1} {n+1} $.

Чтобы доказать правильность вашего алгоритма, вам нужен индуктивный аргумент, похожий на тот, который использовался здесь:

  • Для списка Синглтона есть только одна возможность, поэтому она выбрана равномерно.
  • Предполагая, что список с элементами $ n $ был одинаково выбран (из всех перестановки), показывают, что тот, который с элементами $ n+1 $, полученными по вашей технике, является равномерно.

С этого момента доказательство неверно. Пожалуйста, смотрите ниже для правильного доказательства; Я оставляю это здесь, потому что как ошибка, так и следующие шаги (которые являются обоснованными) могут быть образовательными.

Полезно вывести местное (т.е. в стиле элемент) свойство, которое должно удерживать, потому что спорить обо всей перестановке болезненно. Обратите внимание, что перестановка выбрана равномерно, если каждый элемент имеет одинаковую вероятность быть в каждой позиции, т.е.

$ qquad displayStyle mathop { forall} limits _ { pi in mathrm {perm} _n} operatorname {pr} (l = pi) = frac {1} {n!} QuadleftrightRowRow Quad mathop { forall} limits_ {i = 1}^n mathop { forall} limits_ {j = 1}^n operatorname {pr} (l_i = j) = frac {1} { n} qquad (1) $

где $ n = | l | $, и мы предполагаем, что из -за тотационной простоты мы вставляем $ {1, dots, n } $ в список.

Теперь давайте посмотрим, что делает ваша техника при вставке элемента $ N+1 $ ST. Мы должны рассмотреть три случая (после обмена):

  1. Один из элементов в списке, не замененный, то есть $ i in {1, dots, n } $ и $ j in {1, dots, n } $
  2. Один из элементов в списке, поменяемый, то есть $ i = n+1 $ и $ j in {1, dots, n } $
  3. Новый элемент, то есть $ i in {1, dots, n+1 } $ и $ j = n+1 $

Для каждого случая мы рассчитываем вероятность того, что элемент $ j $ находится на позиции $ i $; Все должны оказаться $ frac {1} {n+1} $ (что достаточно из -за $ (1) $). Пусть $ p_n = frac {1} {n} $ станет вероятностью одного из первых элементов $ n $ в любой позиции в старом списке (гипотеза индукции) и $ p_s = frac {1} {n+ 1} $ вероятность выбора любой позиции random_item (предположения 1, 2). Обратите внимание, что косание списка с элементами $ n $ и выбором позиции свопа Независимые события, таким образом, вероятности совместного фактора событий, например,

$ qquad displaystyle operatorname {pr} (l_i = j, i text {shappuct}) = operatorname {pr} (l_i = j) cdot operatorname {pr} (i tex $

для $ i, j in {1, dots, n } $. Теперь для расчетов.

  1. Мы рассматриваем только старые элементы $ n $. Такой элемент $ j $ находится на позиции $ i $, если и только если он был там до последней вставки, а $ i $ не выбран в качестве своп -позиции, то есть

    $ Quad DisplayStyle OperatorName {pr} (l_i = j) = p_n (1-p_s) = frac {1} {n} cdot frac {n} {n+1} = frac {1} { n+1} $.

  2. Здесь мы считаем, что один из старых элементов заменяется на последнюю позицию. Элемент $ J $ мог быть на любой из старых должностей, поэтому мы суммируем все вероятности, что $ j $ была на позиции $ i $ и $ i $, выбран в качестве свопа, то есть

    $ Quad DisplayStyle OperatorName {pr} (l_ {n+1} = j) = sum_ {i = 1}^n p_np_s = sum_ {i = 1}^n frac {1} {n} cdot frac {1} {n+1} = frac {1} {n+1} $.

  3. Новый элемент заканчивается в позиции $ i $, если и только тогда, когда $ i $ выбрана в качестве позиции свопа, то есть

    $ Quad DisplayStyle OperatorName {pr} (l_i = j) = p_s = frac {1} {n+1} $.

Все получилось хорошо, ваша стратегия вставки действительно сохраняет единообразие. Силой индукции это доказывает, что ваш алгоритм создает равномерно распределенные перестановки.

Слово предупреждения: это доказательство разрушается, если вставленные элементы не являются парными различными соответствующими. различим, потому что тогда самое первое уравнение больше не является действительным. Но ваш алгоритм все еще действителен; каждый перестановка с дубликатами генерируется тем же количеством случайных выполнений. Вы можете подтвердить это, отмечая дубликаты (то есть, заставляя их различать), выполнить выше доказательства и удалить маркировку (практически); Последний шаг разрушает наборы перестановки равных размеров до того же.

В качестве Стивен правильно отметил в комментариях, вышеуказанное доказательство в корне ошибочно, поскольку $ (1) $ не имеет; Вы можете построить распределения на наборе перестановки, которые выполняют правую, но не на левой стороне.

Поэтому нам придется работать с вероятностями перестановки, что, в конце концов, не так уж плохо. Предположения на random_item И индуктивная структура, изложенная в самом начале поста, остается на месте, мы продолжаем оттуда. Пусть $ l^{(k)} $ обозначает список после $ {1, dots, k } $ вставлен.

Пусть $ pi ' in mathrm {perm} _ {n+1} $. Произвольная перестановка $ {1, dots, n+1 } $. Это можно написать уникально в качестве

$ qquad displaystyle pi '= ( pi (1), pi (2), dots, pi (i-1), n+1, pi (i+1), dots, pi (n), pi (i)) $

для некоторых $ pi in mathrm {perm} _n $ и $ i in {1, dots, n+1 } $. По гипотезе индукции, $ OperatorName {pr} (l^{(n)} = pi) = frac {1} {n!} $. Более того, random_item Выбирает позицию $ i $ с вероятностью $ frac {1} {n+1} $ по предположению. Поскольку случайный выбор $ pi $ и $ i $ (стохастически) независимы, мы получаем

$ qquad displaystyle operatorname {pr} (l^{(n+1)} = pi ') = operatorname {pr} (l^{(n)} = pi) cdot operatorname {pr} (i text {заменять}) = frac {1} {(n+1)!} $

что мы должны были показать. Силой индукции это доказывает, что ваш алгоритм создает равномерно распределенные перестановки.

  1. Например, назначьте каждую перестановку в $ {(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3) } $ вероятность $ frac {1} {4} $ и все остальные $ 0 $. Есть также примеры, которые приписывают каждую перестановку ненулевую вероятность.
Лицензировано под: CC-BY-SA с атрибуция
Не связан с cs.stackexchange
scroll top