При анализе фильтра Блюма мы сделали упрощающее допущение, что после добавления элементов в фильтр определённое число ячеек в массиве пустые. Требуется определить, с какой вероятностью это действительно так. При анализе рандомизированных структурах данных часто возникает такая проблема: нужно оценить уровни наполненности урн. Однако уровни наполненности урн зависимы друг от друга: если мы знаем, что первые n-1 урны пустые, но мы кинули хотя бы один шар, то последняя урна точно не пуста. Зависимость этих случайных величин мешает нам, например, оценить число пустых ячеек в фильтре Блюма с помощью границ Чернова.

В этой лекции мы ознакомимся с приближением Пуассана: мы бпредположим, что уровни нагрузки ячеек --- независимые случайные величины с распределением Пуассана, и оценим ошибку, которую мы таким образом совершаем. Сделаем вывод, что чаще всего достаточно оценить алгоритм в модели Пуассана.