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

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

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

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

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

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

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


hash math probability hash-collision birthday-paradox
person ʞɔıu    schedule 31.01.2014    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Пусть 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 оценил бы X как 100.

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

person Timothy Shields    schedule 01.02.2014