Изменения

Подставив последнее в нашу формулу с математическим ожиданием получим:: <tex>E(d(x_k)) = \sum\limits_{i = 1}^{n} Pr[A_{i,k} = 1] = \sum\limits_{i = 1}^{k - 1} \dfrac{1}{k - i + 1} + \sum\limits_{i = k + 1}^{n} \dfrac{1}{i - k + 1} \leqslant </tex><tex>\leqslant \ln(k) + \ln(n-k)+2</tex>(здесь мы использовали неравенство <tex>\sum\limits_{i = 1}^{n} \dfrac{1}{i} \leqslant \ln(n) + 1</tex>)