City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Рандомизированные структуры данных, приближение Пуассана
Randomized Algorithms

What: Lecture
When: Wednesday, 10 March 2021, 18:10–19:45
Where: НГУ, ауд. 5210, НГУ, новый корпус

Description

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

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