Изменения
→RMHC для OneMax
Пусть <tex>X_{t-1} = k</tex>. Тогда
<tex>E(X_t | X_{t-1} = k) = (k-1)\frac{k}{n} + k \frac{n-1k}{n} = k (1 - \frac{1}{n})</tex>, то есть <tex> \delta = \frac{1}{n}</tex>.
Отсюда по [[#theorem1|теореме о дрифте]], с учетом того, что <tex> X_0 \leq n </tex> получаем: <tex> E(T) \leq n(\ln{n} + 1)</tex>.
