У меня есть два способа составить список предметов в случайном порядке, и я хотел бы определить, являются ли они одинаково справедливыми (беспристрастными).
Первый метод, который я использую, состоит в том, чтобы создать весь список элементов, а затем выполнить случайное перемешивание (скажем, случайное перемешивание Фишера-Йейтса). Второй метод - это скорее итеративный метод, который поддерживает перемешивание списка при каждой вставке. В псевдокоде функция вставки:
insert( list, item )
list.append( item )
swap( list.random_item, list.last_item )
Я заинтересован в том, чтобы показать справедливость этой конкретной перетасовки. Преимущества этого алгоритма, где он используется, достаточно, что даже если он будет немного несправедливым, все будет в порядке. Чтобы решить, мне нужен способ оценить его справедливость.
Моя первая идея заключается в том, что мне нужно рассчитать общее количество возможных перестановок таким образом в сравнении с общими возможными перестановками для набора конечной длины. Однако я немного растерялся, как рассчитать перестановки, полученные из этого алгоритма. Я также не могу быть уверен, что это лучший или самый простой подход.
источник
Ответы:
Во-первых, давайте сделаем два, возможно, очевидных, но важных предположения:
_.random_item
Можно выбрать последнюю позицию._.random_item
выбирает каждую позицию с вероятностью .Чтобы доказать правильность вашего алгоритма, вам нужен индуктивный аргумент, подобный тому, который используется здесь :
С этого момента доказательство неверно. Пожалуйста, смотрите ниже для правильного доказательства; Я оставляю это здесь, потому что и ошибка, и последующие шаги (которые являются правильными) могут быть образовательными.
Полезно получить локальное (т.е. поэлементное) свойство, которое должно храниться, потому что спорить о всей перестановке болезненно. Заметьте, что перестановка выбирается равномерно, если каждый элемент имеет равную вероятность нахождения в каждой позиции, т.е.
где и для простоты обозначения мы предполагаем, что вставляем { 1 , … , n } в список.n = | L | { 1 , … , n }
Теперь давайте посмотрим, что делает ваша техника при вставке го элемента. Мы должны рассмотреть три случая (после обмена):n + 1
Для каждого случая мы вычисляем вероятность того, что элемент окажется в позиции i ; все должно быть 1J я (что достаточно из-за(1)). Пустьpn=11n + 1 ( 1 ) - вероятность того, что один из первыхnэлементовокажетсяв любой позиции старого списка (гипотеза индукции), аps=1пN= 1N N вероятность выбора какой-либо позиции(предположения 1, 2). Обратите внимание, что выбор списка сnэлементами и выбор позиции свопинга являютсянезависимыми событиями, поэтому вероятности совместного события составляют фактор, напримерпs= 1n + 1 N
random_item
Все получилось хорошо, ваша стратегия вставки действительно сохраняет единообразие. В силу индукции это доказывает, что ваш алгоритм создает равномерно распределенные перестановки.
Предупреждение: это доказательство ломается, если вставленные элементы не отличаются попарно, соответственно. различимы, потому что тогда самое первое уравнение больше не действует. Но ваш алгоритм все еще действует; каждая перестановка с дубликатами генерируется одинаковым количеством случайных выполнений. Вы можете доказать это, пометив дубликаты (то есть сделав их различимыми), выполнив приведенные выше проверки и удалив маркировку (виртуально); последний шаг объединяет равные по размеру наборы перестановок в одно и то же.
random_item
random_item
который мы должны были показать. В силу индукции это доказывает, что ваш алгоритм создает равномерно распределенные перестановки.
источник