В этой лекции ознакомимся с первыми ключевыми подходами к анализу рандомизированных алгоритмов: с линейностью математического ожидания и вероятностным методом доказательства.

Оба подхода проиллюстрируем на примере построения деревьев двоичного разбиения пространства (BSP-деревьев), приобретших большую известность из-за приложений при быстрой прорисовке 3D-сцен и обнаружении столкновений в компьютерных играх как Doom и Quake. Для быстрой прорисовки сцены важно, чтобы дерево было маленьким. Построение маленького дерева нетривиально. Мы посмотрим простой рандомизированный алгоритм для построения BSP-дерева почти оптимального размера.

Дальше мы перейдём к ещё одному элементарному средству для анализа рандомизированных алгоритмов --- к неравенству Буля. Оно говорит о том, что хотя бы одно из событий \(E_1,\dots,E_n\) наступит с вероятностью не больше, чем сумма вероятностей индивидуальных событий. Этот элементарное неравенство теории вероятностей встречается в анализе многих алгоритмов.