Математическое ожидание количества уровней составляет <tex>O(log(n))</tex>
|proof=
ПатакДля оценки мат.ожидания посчитаем вероятность того, что количество уровней <tex>h</tex> равно <tex>k</tex>. <tex>p(h = k) = p(h \leq k) \cdot p(h \geq k)</tex>. <tex>p(h \leq k) = (1 - p^{k+1})^n</tex>, потому что вероятность того, что точка дойдёт до уровня <tex>k + 1</tex> равна <tex>p^{k + 1}</tex>. <tex>p(h \geq k) = (1 - (1 - p^k)^n)</tex>, потому что вероятность того, что точка не дойдёт до уровня <tex>k</tex> равна <tex>1 - p^k</tex>. <tex>E(h) = \sum\limits_{k = 1}^{\infty} k \cdot p(h = k) = p(1) \cdot 1 + \dots + p(log_{1/p} n) \cdot log_{1/p} n + \sum\limits_{k = log_{1/p} n + 1}^{\infty} k \cdot p(k)</tex> Оценим первую сумму: <tex>p(1) \cdot 1 + \dots + p(log_{1/p} n) \cdot log_{1/p} n \leq 1 + \dots + log_{1/p} n \leq smth = O(log(n))</tex> Оценим вторую сумму: <tex>\sum\limits_{k = log_{1/p} n + 1}^{\infty} k \cdot p(k) = \sum\limits_{k = log_{1/p} n + 1}^{\infty} k \cdot (1 - (1 - p^k)^n) \cdot p(h \leq k) \leq \sum\limits_{k = log_{1/p} n}^{\infty} k \cdot n p^k \cdot 1 = n \cdot \sum\limits_{k = log_{1/p} n}^{\infty} k \cdot p^k</tex> Рассмотрим эту сумму: <tex>\sum\limits_{k = log_{1/p} n}^{\infty} k \cdot p^k = </tex> Суммируя всё вышесказанное, получаем, что <tex>O(log(n))</tex>. ''Для лучшего понимания можно представлять, что <tex>p = 1/2</tex>.''
}}
