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

24

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

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

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

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

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

эд-ка морт-ора-й
источник
Вы можете сделать статистическую выборку по большому количеству прогонов вашего алгоритма и сравнить его с ожидаемым значением или выполнить какой-либо тест на случайность.
Дейв Кларк
Вы хотите проверить распределение. Равномерно ли это распределено или перекошено? Я подозреваю, однако, что вам нужно будет запустить его много-много раз.
Дейв Кларк
Мне не ясно, как я это сделаю. Это не случайность содержимого, которое я ищу, а случайность порядка. Какой подход может измерить распределение заказа?
edA-qa mort-ora-y
Ах, глупый я, я мог бы использовать фиксированный набор входных данных и использовать конечную позицию каждого элемента, чтобы получить распределение. Тем не менее, я бы предпочел больше логического доказательства, чем симуляции.
edA-qa mort-ora-y
@ edA-qamort-ora-y: Ваше желание - моя команда. ;)
Рафаэль

Ответы:

22

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

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

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

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

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

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

πPermnPr(L=π)=1n!i=1n j=1nPr(Li=j)=1n(1)

где и для простоты обозначения мы предполагаем, что вставляем { 1 , , n } в список.n=|L|{1,,n}

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

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

Для каждого случая мы вычисляем вероятность того, что элемент окажется в позиции i ; все должно быть 1ji (что достаточно из-за(1)). Пустьpn=11n+1(1) - вероятность того, что один из первыхnэлементовокажетсяв любой позиции старого списка (гипотеза индукции), аps=1pn=1nn вероятность выбора какой-либо позиции(предположения 1, 2). Обратите внимание, что выбор списка сnэлементами и выбор позиции свопинга являютсянезависимыми событиями, поэтому вероятности совместного события составляют фактор, напримерps=1n+1random_itemn

Pr(Li=j,i swapped)=Pr(Li=j)Pr(i swapped)=pnps

i,j{1,,n}

  1. njii

    Pr(Li=j)=pn(1ps)=1nnn+1=1n+1

  2. jjii

    Pr(Ln+1=j)=i=1npnps=i=1n1n1n+1=1n+1

  3. ii

    Pr(Li=j)=ps=1n+1

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

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


(1)

random_itemL(k){1,,k}

πPermn+1{1,,n+1}

π=(π(1),π(2),,π(i1),n+1,π(i+1),,π(n),π(i))

πPermni{1,,n+1}Pr(L(n)=π)=1n!random_itemi1n+1πi

Pr(L(n+1)=π)=Pr(L(n)=π)Pr(i swapped)=1(n+1)!

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


  1. {(1,2,3,4),(2,3,4,1),(3,4,1,2),(4,1,2,3)}140
Рафаэль
источник
4
«Заметьте, что перестановка выбирается равномерно, если каждый элемент имеет равную вероятность нахождения в каждой позиции» - это не так. Например, набор из четырех перестановок на четырех элементах {(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3 )} удовлетворяет вашему ограничению, но, очевидно, не является набором всех перестановок. К сожалению, вы должны использовать глобальные свойства своей перестановки, потому что локальных условий недостаточно для определения однородности.
Стивен Стадницки