212
правок
Изменения
→Алгоритм
Если на <tex>j</tex>-ой позиции находится черная точка, то точки с индексом <tex>j + 1</tex> и далее не будут содержать в окружности точку <tex>U</tex>(потому что <tex>j</tex> была ближайшей на предыдущем уровне из этой части пространства). Тогда если <tex> X </tex> {{---}} количество окружностей, которым принадлежит точка <tex>U</tex>, то так как точка проходит на следующий уровень с вероятностью <tex>p</tex>:
<tex dpi = 150>E(X) \leqslant \sum\limits_sum_{i = 1\dots}^{\infty}{i \cdot p(1 - p) ^ i} = </tex><tex dpi = 150>\sum\limits_sum_{i = 1\dots}^{\infty}{\sum\limits_sum_{j = i\dots}^{\infty}{p (1 - p) ^ j}} = </tex><tex dpi = 150>p\sum\limits_sum_{i = 1\dots}^{\infty}{(1-p)^i \cdot (\sum\limits_sum_{j = 0\dots}^{\infty}{(1 - p) ^ j})} = \sum\limits_sum_{i = 1\dots}^{\infty}{(1-p)^i} = \fracdfrac{1-p}{p} = O(1)</tex>
Получается, что каждая точка принадлежит <tex>O(1)</tex>, следовательно внутри каждой окружности содержит <tex>O(1)</tex> точек.
}}
