повторное использование случайного числа в пробе пласта

Question

Недавно был задан вопрос относительно другого вопроса: Если задан список неизвестной длины, вернуть случайный элемент в нем, отсканировав его только 1 раз

Я знаю, что вы не должны, я просто не могу указать пальцем на каноническое объяснение, почему бы и нет.

Посмотрите на пример кода:

import random, sys

def rnd(): # a function that returns a random number each call
    return int(random.getrandbits(32))

class fixed: # a functor that returns the same random number each call
    def __init__(self):
        self._ret = rnd()
    def __call__(self):
        return self._ret

def sample(rnd,seq_size):
    choice = 0
    for item in xrange(1,seq_size):
        if (rnd() % (item+1)) == 0:
            choice = item
    return choice

dist = [0 for i in xrange(500)]
for i in xrange(1000):
    dist[sample(rnd,len(dist))] += 1
print "real",dist
print

dist = [0 for i in xrange(500)]
for i in xrange(1000):
    dist[sample(fixed(),len(dist))] += 1
print "reuse",dist

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

real [1, 3, 0, 1, 2, 3, 2, 3, 1, 2, 2, 2, 2, 0, 0, 1, 3, 3, 4, 0, 2, 1, 2, 1, 1, 4, 0, 3, 1, 1, 2, 0, 0, 0, 1, 4, 6, 2, 3, 1, 1, 3, 2, 1, 3, 3, 1, 4, 1, 1, 2, 2, 5, 1, 2, 1, 0, 3, 1, 0, 2, 6, 1, 2, 2, 1, 1, 1, 1, 3, 2, 1, 5, 4, 0, 3, 3, 4, 0, 0, 2, 1, 3, 2, 3, 0, 2, 4, 6, 3, 0, 1, 3, 0, 2, 2, 4, 3, 2, 1, 2, 1, 2, 2, 1, 4, 2, 0, 0, 1, 1, 0, 1, 4, 2, 2, 2, 1, 0, 3, 1, 2, 1, 0, 2, 2, 1, 5, 1, 5, 3, 3, 1, 0, 2, 2, 0, 3, 2, 3, 0, 1, 1, 3, 0, 1, 2, 2, 0, 1, 2, 2, 3, 2, 3, 1, 1, 0, 1, 2, 2, 2, 2, 2, 3, 2, 1, 2, 2, 2, 1, 3, 3, 1, 0, 1, 1, 0, 1, 3, 2, 1, 4, 3, 4, 1, 1, 1, 2, 1, 2, 0, 0, 0, 1, 1, 2, 6, 0, 1, 1, 0, 1, 0, 1, 2, 2, 3, 0, 1, 2, 2, 1, 0, 4, 2, 1, 2, 2, 0, 4, 4, 0, 3, 2, 2, 1, 2, 4, 1, 2, 1, 0, 2, 1, 1, 5, 1, 2, 2, 3, 2, 3, 0, 1, 2, 3, 2, 5, 2, 3, 0, 1, 1, 1, 1, 3, 4, 2, 4, 1, 2, 3, 2, 5, 2, 1, 0, 1, 1, 2, 2, 3, 1, 1, 1, 2, 1, 2, 0, 4, 1, 1, 2, 3, 4, 3, 1, 2, 3, 3, 3, 2, 1, 2, 0, 0, 4, 3, 2, 2, 5, 5, 3, 3, 3, 1, 0, 1, 3, 1, 1, 2, 4, 3, 1, 4, 4, 2, 5, 0, 5, 4, 2, 1, 0, 4, 1, 3, 3, 2, 4, 2, 3, 3, 1, 3, 3, 4, 2, 2, 1, 1, 1, 1, 3, 3, 5, 3, 2, 4, 0, 1, 3, 2, 2, 4, 2, 2, 3, 4, 5, 3, 2, 1, 2, 3, 2, 2, 2, 4, 4, 0, 1, 3, 3, 3, 4, 1, 2, 4, 0, 4, 0, 3, 2, 1, 1, 4, 2, 1, 0, 0, 0, 4, 2, 2, 1, 4, 3, 1, 1, 3, 2, 4, 3, 4, 2, 1, 1, 2, 2, 3, 3, 1, 2, 2, 1, 1, 2, 3, 1, 9, 1, 3, 4, 2, 4, 4, 0, 1, 0, 1, 0, 2, 1, 0, 1, 2, 3, 3, 6, 2, 2, 1, 2, 4, 3, 3, 3, 2, 1, 2, 1, 2, 8, 2, 3, 1, 5, 3, 0, 2, 1, 1, 4, 2, 2, 1, 2, 3, 2, 1, 0, 4, 3, 4, 3, 1, 3, 2, 3, 2, 2, 1, 0, 1, 2, 5, 3, 0, 3, 1, 2, 2, 2, 1, 0, 1, 4]

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

reuse [92, 50, 34, 19, 23, 16, 13, 9, 9, 9, 11, 10, 6, 7, 8, 5, 5, 6, 4, 2, 2, 3, 2, 3, 3, 6, 6, 1, 4, 3, 5, 2, 2, 1, 1, 2, 3, 4, 3, 4, 1, 3, 1, 0, 0, 1, 5, 3, 1, 2, 0, 2, 0, 1, 1, 6, 2, 0, 2, 2, 4, 2, 2, 0, 2, 2, 2, 0, 3, 0, 4, 1, 2, 1, 4, 2, 2, 0, 1, 0, 1, 1, 0, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 2, 0, 0, 1, 2, 1, 3, 1, 0, 1, 2, 0, 4, 3, 0, 0, 2, 0, 0, 1, 0, 0, 2, 0, 2, 1, 0, 1, 0, 0, 1, 1, 3, 0, 1, 1, 0, 2, 0, 1, 2, 0, 1, 1, 4, 1, 1, 1, 2, 1, 0, 1, 2, 0, 2, 1, 1, 2, 0, 1, 1, 0, 2, 0, 2, 0, 0, 2, 0, 1, 0, 2, 1, 1, 0, 0, 1, 2, 4, 1, 0, 2, 0, 1, 2, 1, 3, 0, 1, 0, 0, 1, 0, 0, 2, 1, 0, 0, 0, 3, 2, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 4, 1, 0, 2, 1, 0, 0, 2, 1, 1, 3, 3, 2, 0, 1, 0, 2, 0, 1, 1, 0, 0, 3, 1, 0, 0, 1, 0, 3, 2, 2, 0, 0, 0, 0, 0, 2, 0, 1, 0, 2, 0, 4, 1, 0, 0, 2, 0, 1, 1, 0, 0, 3, 1, 3, 2, 2, 1, 3, 1, 2, 0, 1, 1, 3, 0, 3, 1, 2, 0, 2, 0, 2, 0, 3, 0, 3, 0, 3, 1, 0, 2, 3, 1, 1, 0, 1, 3, 3, 1, 1, 1, 0, 2, 1, 1, 4, 1, 1, 1, 2, 0, 3, 1, 1, 0, 4, 1, 1, 0, 1, 3, 1, 0, 1, 1, 0, 3, 3, 0, 2, 4, 0, 1, 2, 1, 6, 1, 0, 0, 0, 0, 1, 2, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 4, 2, 0, 1, 2, 0, 1, 4, 1, 2, 0, 5, 2, 2, 0, 6, 2, 2, 1, 3, 0, 3, 1, 1, 0, 3, 1, 4, 2, 0, 1, 0, 1, 2, 3, 1, 1, 3, 0, 0, 0, 1, 1, 4, 3, 3, 0, 0, 1, 0, 1, 1, 2, 1, 0, 2, 1, 4, 5, 1, 1, 3, 0, 1, 1, 1, 3, 1, 1, 0, 3, 3, 1, 3, 0, 1, 0, 0, 1, 1, 3, 2, 1, 0, 3, 1, 1, 3, 1, 3, 1, 2, 2, 2, 0, 0, 5, 1, 3, 0, 1, 4, 1, 1, 1, 3, 2, 1, 3, 2, 1, 3, 1, 2, 2, 3, 2, 2, 1, 0, 3, 3, 1, 3, 3, 3, 2, 1, 2, 3, 3, 3, 1, 2, 2, 2, 4, 2, 1, 5, 2, 2, 0]

Что здесь за математика? Почему вы не можете повторно использовать одно и то же случайное число?

Answer 1

Редактировать, в ответ на комментарий:

Способ отбора проб из резервуара должен работать так: вы хотите точно выбрать правильную пропорцию проб из каждого из существующих бинов, чтобы создать дополнительный бин с той же вероятностью. В вашем цикле sample(), учитывая, что вы случайно выбрали одну из item корзин, вам нужно выбрать выборки из каждой ячейки с вероятностью 1/(item + 1).

Однако при fixed() решение о выборе и номер предыдущего бина зависят от одного и того же фиксированного 32-разрядного номера. Это означает, что вероятность того, что образец будет удален из каждой ячейки, не будет одинаковой.

---

Рассмотрим, что происходит во время третьей итерации цикла sample(). У вас есть три существующих бункера (0, 1 и 2), и вы хотите выбрать 1/4 сэмплов в каждом и добавить их во вновь созданный бин 3.

Обратите внимание, что все 32-битные fixed() числа в ячейке 1 будут четными (поскольку при первом проходе были выбраны все числа, кратные 2), а все числа в ячейке 0 будут нечетными (поскольку четные были перемещены в корзину 1). Второй проход перемещает все числа, кратные трем, в ячейку 2 (которая должна быть в порядке пока, и не изменяет четное / нечетное деление в ячейках 0 и 1).

Третий проход затем перемещает все fixed() числа, делимые на 4, в ячейку 3. Но при этом выбирается половина чисел из ячейки 1 (поскольку половина всех четных чисел делится на 4), и ни одно из чисел из bin 0 (потому что они все странные). Таким образом, хотя ожидаемый размер новой корзины должен быть правильным, ожидаемые размеры старых корзин больше не совпадают.

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

---

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

Генераторы псевдослучайных чисел (PRNG) на самом деле не случайны; как вы знаете, их результаты на самом деле являются фиксированной последовательностью. Результаты PRNG намеренно скремблированы, чтобы они действовали достаточно как реальные случайные числа для большинства целей. Однако, если PRNG является «слабым» для конкретного приложения, внутренняя работа PRNG может взаимодействовать с деталями приложения странным образом, что приводит к очень неслучайным результатам.

То, что вы пробуете здесь, повторно используя то же случайное число, создает плохой PRNG. Фактические результаты зависят от деталей того, как приложение использует случайные числа ...

Несмотря на то, что fixed() является преднамеренно нарушенным PRNG, многие коммерческие PRNG библиотеки являются «слабыми» и могут привести к схожим странным взаимодействиям с некоторыми приложениями. С практической точки зрения, «слабость» относится к приложению - и, хотя существуют статистические тесты, которые широко используются для выявления слабых PRNG, нет никакой гарантии, что ваше приложение не наткнется на некоторую странную корреляцию четного "сильный" PRNG.

Answer 2

Если вы выбираете случайное число каждый раз, следующий элемент из потока имеет шанс 1 / CURRENTSIZE обыграть предыдущий выбранный элемент.

Так в чем же проблема с одним случайным числом на поток?Почему это искажает распределение?

Я еще не нашел полного ответа, но у меня есть идея.

Например, давайте возьмем поток из 100 чисел и выберем случайное число0 ... 999.Теперь мы смотрим на это с точки зрения второго элемента.

Когда он выигрывает?Ну, во-первых, это должно быть N% 2 == 0.Так что это должно быть четное число.Кроме того, он также побивается каждым другим кратным каждого кратного 2 в потоке, 4 ... 6 ... 8 ... 10 и т. Д. Но он выигрывает, например, на 106.

Расчетвсе числа, с которыми он выигрывает, 0..999, и мы получаем 81 раз!

Теперь давайте возьмем 4, оно должно быть N% 4 == 0, и оно побивается всеми коэффициентами от 4 до N (8... 12 .... 16).Если мы посчитаем, сколько раз 4 может выиграть, мы получим 45 раз ...!Таким образом, распределение не справедливо.

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

Например, если у нас есть размер потока 100, и мы выбираем случайное число 0..199.Мы знаем, что первые 100 случайных чисел имеют ровно 1 совпадение, поэтому они распределены равномерно.Но что происходит со случайными числами 99 ... 199?Распределение даже не!Например, 101 даст только 101% X == 0 для 1. Это верно для всех простых чисел (101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163,167, 173, 179, 181, 191, 193, 197, 199).Так что у первого предмета гораздо больше шансов выиграть, чем у других.

Это не тот случай, если вы выбираете новое случайное число для каждого предмета, в этом случае шансы могут быть добавлены.Например, когда появляется первый предмет, у него есть шанс на выигрыш, а именно:

НЕ (1/2 + 1/3 + 1/4 + 1/5 + 1/6 (... и т. Д.))

Answer 3

Подумайте об этом: что произойдет, если ваш фиксированный номер действительно маленький?