166
правок
Изменения
Нет описания правки
}}
{{Лемма
|about=о математическом ожидании глубины узла
|statement=Математическое ожидание глубины <tex>k</tex>-го узла равно <tex>H_k + H_{n-k+1} - 1</tex>, где <tex>H_j = \sum_{i=1}^j\frac{1}{i} \approx \ln j</tex>.
|proof=Глубина <tex>k</tex>-го узла - это количество узлов, которые являются прародителями этого узла. Введем случайную величину <tex>A_i</tex>, равную единице, если <tex>i</tex>-й узел является прародителем <tex>k</tex>-го узла, и нулю в противном случае. Легко проверить, что <tex>A_i</tex> и <tex>A_j</tex> независимы при <tex>i \ne j</tex>. Из того, что <tex>y_i</tex> выбраны случайно и независимо с одинаковым распределением и предыдущей леммы следует, что <tex>M(A_i) = \frac{1}{|i - k| + 1}</tex> при <tex>i \ne k</tex>.
<tex>M(depth_k)=M(\sum_{i=1}^nA_i)=\sum_{i=1}^nM(A_i)=\sum_{i=1}^n\frac{1}{|i-k|+1}=\sum_{i=1}^k\frac{1}{k-i+1}+\sum_{i=k}^n\frac{1}{i-k+1}-1=H_k+H_{n-k+1}-1</tex>.}}
Таким образом, мы доказали, что матожидание глубины конкретного узла <tex>O(\log n)</tex>.
}}
