170
правок
Изменения
Нет описания правки
Для оценки мат. ожидания посчитаем вероятность того, что количество уровней <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>p(h = k) = 1 - p(h > k) - p(h < k) = 1 - (1 - (1 - p^{k + 1})^n) - (1 - p^{k})^n = (1 - p^{k + 1})^n - (1 - p^k)^n \leq np^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>\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 = p^{\log_{1/p} n} \cdot \sum\limits_{k = 0}^{\infty} (k + \log_{1/p} n) \cdot p^k = p^{\log_{1/p} n} \cdot (\sum\limits_{k = 0}^{\infty} (k p^k) + \log_{1/p} n \cdot \sum\limits_{k = 0}^{\infty} (p^k)) = p^{\log_{1/p} n} \cdot (O(1) + \log_{1/p} n \cdot O(1)) = 1/n \cdot O(\log(n) \cdot 1/n)</tex>
Суммируя всё вышесказанное, получаем, что <tex>O(\log(n))</tex>.
