Кому нужна математика? Понятная книга о том, как устроен цифровой мир (Литвак, Райгородский) - страница 84
Хеш-значения – это последовательности из нулей и единиц одинаковой длины. Обозначим длину хеш-значений через т. Тогда получим 2>m разных хеш-значений (см. главу 3 и приложение 1 к ней).
Теперь допустим, что нам нужно сосчитать n различных объектов. Чтобы присвоить им всем разные хеш-значения, понадобится как минимум n хеш-значений, то есть
Стало быть, m должно быть того же порядка величины, что и log>2(n).
Алгоритм К-Minimum Values запоминает К самых маленьких хеш-значений длины m, то есть для этого алгоритма нам нужен объем памяти примерно K log>2(n).
HyperLogLog запоминает только максимальное количество нулей в начале хеш-значений. Если сами хеш-значения длины m, то и нулей может быть не больше, чем т. Значит, нам нужно держать в памяти число между 0 и m. Оно тоже записывается с помощью последовательности нулей и единиц. Какой длины должны быть эти последовательности? Если последовательности длины l, то мы можем записать 2>l разных чисел. Стало быть, чтобы записать m + 1 разных чисел, должно выполняться
В памяти нам нужно держать только l битов информации (последовательность из нулей и единиц длины l). Из предыдущих формул получается:
Для повышения точности хеш-значения разбивают на r регистров и запоминают максимальное число нулей в каждом регистре отдельно. В результате требуется порядка r log>2 (log>2 (n)) битов памяти. Относительная точность оценки задается формулой 1,04÷ √r{36}.
Приложение к главе 8
Доказательство совместимости по стимулам аукциона второй цены
Рассмотрим аукцион второй цены, на котором один товар разыгрывается между n участниками. Обозначим v>i истинную ценность товара для участника i (от английского слова value – ценность). Далее обозначим через b>i ставку участника i (от англ. bid – ставка). Эти обозначения будем использовать для любого i = 1,2, …, n.
Совместимость по стимулам означает, что верна следующая теорема.
Теорема (Викри).Участник i получает максимальную прибыль, если b>i = v>i.
Доказательство. Если участник i получает товар, следовательно, его ставка b>i была самой высокой. Поскольку мы имеем дело с аукционом второй цены, то стоимость товара равна самой высокой из оставшихся ставок:
При этом ценность товара для участника i равна v>i. Значит, если участник i получает товар, то его прибыль составит
Если участник i товар не получает, он не приобретает никакой ценности и ничего не платит, то есть его прибыль равна нулю.
Дальше доказательство ведется так же, как в разделе