15
правок
Изменения
Нет описания правки
|id=statement2
|about=2
|statement=<tex>E(T) = \sum\limits_{i = 0}^{\infty} P(T >= \ge i)</tex>
|proof=
Это утверждение достаточно известно в теории вероятностей.
<tex>E(T) = \sum\limits_{i = 0}^{\infty}iP(T = i) = \sum\limits_{i = 1}^{\infty}\sum\limits_{j = 1}^{i}P(T = i) = \sum\limits_{j = 1}^{\infty}\sum\limits_{i = j}^{\infty}P(T = i) = \sum\limits_{i = 0}^{\infty} P(T >= \ge i)</tex>
}}
Так как из <tex>X_i = 0</tex> следует <tex>T \le i</tex>, то <tex>P(T \ge i) \le P(X_i > 0)</tex>.
Следовательно, по [[#statement2|утверждению(2)]], <tex>E(T) = \sum\limits_{i = 0}^{\infty} P(T >= \ge i) \le \sum\limits_{t = 0}^{\infty} P(X_t > 0)</tex>.
Для произвольного натурального <tex>K</tex>:
<tex>\parbox{0px}{\begin{align*}
E(T) &\le \sum\limits_{t = 0}^{\infty} P(X_t > 0) \le K + \sum\limits_{t=K}^{\infty} P(X_t > 0) =\\
&= K + \sum\limits_{t=K}^{\infty} P(X_t >= \ge 1) \le K + \sum\limits_{t=K}^{\infty} E(X_t)
\end{align*}}</tex>.
Здесь мы использовали то, что <tex>X_t > 0 \Leftrightarrow X_t >= \ge 1</tex>, а также неравество Маркова: <tex>P(|X| \ge a) \le \frac{E(|X|)}{a}</tex>.
}}
Теорема о дрифте достаточно естественно применяется для эволюционных алгоритмов, оперирующих одной особью. Продемонстрируем это.
Пусть в эволюционном алгоритме проcтранство протранство поиска <tex>S_n</tex>, а целевая функция – <tex>f: S_n \rightarrow \mathbb{N}</tex>.
Пусть оптимальное значение целевой функции – <tex>f_{opt}</tex>
Положим, что <tex>X_t = |f_{opt} - f(x_t)|</tex>, где <tex>x_t \in S_n</tex> – особь, полученная на шаге номер <tex>t</tex>. Почти все условия [[#theorem1| теоремы о дрифте]] выполнены, последнее условие (оценка на <tex>E(X_{i+1}|X_i)</tex>)доказывается для каждой задачи отдельно.
