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

Question

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

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

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

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

Конечно, если n == c, тогда не будет никакого способа узнать, поэтому давайте отложим это и предположим, что c < n.

Какова общая формула для оценки k с учетом n и c (с учетом c < n)?

Answer 1

Проблема в ее нынешнем виде некорректна.

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

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

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

P(X=k|Y=1) = (P (Y = 1 | X = k) * P (X = k)) / P(Y=1)
= (1 / n^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 = k) = 1/2^k для k > 0.
2. Я считаю, что P (X = k) = 1/2^{k - 100} для k > 100.

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

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