Изменения
→Оценка времени работы для OneMax
|id=proposal5
|about=Лемма об ожидании
|statement=Если вероятность наступления события <tex>A</tex> на каждом шаге равна <tex>p</tex>, то матожидание времени наступления этого события <tex>E(t_A) = \frac{1}{p}</tex>.
|proof=По определению математического ожидания:
Воспользовавшись этим фактом, получаем:
<tex> (\frac{1}{1 - x})' = \frac{1}{(1 - x) ^ 2} = \sum_{i=0}^\infty i x^{i - 1} </tex>.
Отсюда видно, что: <tex> \frac{p}{ (1 - (1 - p)) ^ 2} = p \sum_{i=1}^\infty i (1 - p)^{i-1} = \frac{1}{p} </tex>.
=== Алгоритм RMHC ===
Решение задачи OneMax с помощью алгоритма RMHC выглядит следующим образом. В качестве начального решения примем случайный вектор, а затем на каждой итерации равномерно равновероятно выбираем и инвертируем один бит из <tex> n </tex>. Пусть <tex> k </tex> {{---}} количество единиц в векторе (то есть значение <tex> f </tex>) в начале фазы. При <tex> k + 1 = k' > k </tex> фаза заканчивается.
Оценим время работы алгоритма для данной задачи.
