Рассчитать первоначальный размер набора после возникновения столкновений с хэшем

Question

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

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

Скажите, что ваш лоток для кубиков льда имеет 100 ведер (т. Е. Сделал бы 100 кубиков льда). Если вы заметили, что ваш лоток имеет c = 80 пенни, каково наиболее вероятное количество пенни (k), с которым должен был начать ваш друг?

Если с низкий, вероятность столкновения достаточно низки, что наиболее вероятное количество к == с. Например. если c = 3, то это наиболее похоже на то, что k было 3. Однако вероятность столкновения становится все более вероятной, скажем, k = 14, тогда коэффициенты должны быть 1 столкновением, поэтому, возможно, максимально вероятно, что К = 15, если гр = 14.

конечно, если п == с, то не было бы никакого способа узнать, так что давайте установить, что в стороне и принять с < п.

Что общая формула для оценки K заданного п и с (с учетом с < п)?

Answer 1

Проблема в том, что она стоит некорректно.

Пусть n - количество лотков.
Пусть X - случайная величина для количества пенни, с которой начинал ваш друг.
Пусть Y - случайная величина для числа заполненных лотков.

Что вы просите - это режим распределения P (X | Y = c).
(Или, может быть, ожидание E [X | Y = c] в зависимости от того, как вы интерпретируете свой вопрос.)

Возьмем действительно простой случай: распределение P (X | Y = 1). Затем

Р (Х = к | Y = 1) = (P (Y = 1 | Х = к) * Р (Х = к))/P (Y = 1)
= (1/п ^k-1 * P (X = k))/P (Y = 1)

Поскольку P (Y = 1) нормализует постоянную, можно сказать, что P (X = k | Y = 1) пропорционально 1/n ^k-1 * P (X = k).

Но P (X = k) является предварительным распределением вероятности. Вы должны принять некоторое распределение вероятности по числу монет, с которыми должен начать ваш друг.

Например, вот две приоры я мог выбрать:

1. Мой предыдущий вера в том, что P (X = к) = 1/2 ^к при к> 0.
2. Мой предварительного убеждении в том, что Р (Х = к) = 1/2 ^{к - 100} к> 100.

Оба были бы действительными априорные; второй предполагает, что X> 100. Оба дадут совершенно разные оценки для X: предыдущий 1 оценил бы X примерно на 1 или 2; предыдущий 2 оценил бы Х равным 100.

Я бы предложил, если вы продолжите этот вопрос, вы просто зайдете вперед и выберите заранее. Что-то вроде этого будет хорошо работать: WolframAlpha. Это геометрическое распределение с поддержкой k> 0 и средним значением 10^4.