Изменения
Нет описания правки
|about=Multiplicative Drift Theorem
|statement=
Пусть <tex>X_0, X_1, \ldots</tex> – последовательность случайных величин, <tex>X_i \in \{0\} \cup [1, \infty)</tex> и существует <tex>\delta > 0</tex>, такое что <tex>\forall x \: : \: E(X_{i t + 1} | X_{it} = x) \le \left( 1 - \delta \right)x</tex>
Тогда для <tex>T = \min\{t | X_t = 0\}</tex>
# <tex>\forall c > 0 \: : \: P\left(T > \delta^{-1} (\ln X_0 + c)\right) \le e^{-c}</tex>
|proof=
В формулировке и в доказательстве <tex>X_0</tex> – не случайная величина, а ее оценка сверху. Последовательность <tex>\left\{X_i\right\}_{i=0}^{\infty}</tex> обычно воспринимается, как случайный процесс. В этом смысле все утверждения теоремы можно воспринимать как условные по отношению к первому значению.
Сформулируем несколько утверждений, которые понадоятся в ходе доказательства.
{{Утверждение
|id=statement1
|about=1
|statement=Следующие утверждения верны:# <tex>\forall x \in \mathbf{R} \: : \: 1 + x \le e^{x}</tex># <tex>P(|X| \ge 1) \le E(|X|)</tex># <tex>E(X_t) \le e^{\left(1 -\delta \right)^t X_0</tex># <tex>P(T \ge t) \le P(X_t > 0)</tex># <tex>P(X_t > 0) = P(X_t \ge 1)</tex># <tex>E(T) = \sum\limits_{t = 1}^{\infty} X_0P(T \ge t)</tex>
|proof=
}}
|id=statement2
|about=2
|statement=<tex>\forall K \in \mathbb{N} \: : \: E(T) = \le K - 1 + \sum\limits_{i t= 0K}^{\infty} PE(T \ge iX_t)</tex>
|proof=
Для произвольного натурального <tex>K</tex>:
<tex>\parbox{0px}{\begin{align*}
E(T) &=_{(1)} \sum\limits_{t = 1}^{\infty} P(T \ge t) \le_{(2)}\\ &\le le_{(2)} \sum\limits_{t = 01}^{\infty} P(X_t > 0) \le le_{(3)}\\&\le_{(3)} K - 1 + \sum\limits_{t=K}^{\infty} P(X_t > 0) =_{(4)}\\&= _{(4)} K - 1 + \sum\limits_{t=K}^{\infty} P(X_t \ge 1) \le le_{(5)}\\&\le_{(5)} K - 1 + \sum\limits_{t=K}^{\infty} E(X_t)
\end{align*}}</tex>.
}}
Положим теперь <tex>K = \lceil \delta^{-1} \ln X_0 \rceil = \delta^{-1} \ln X_0 + \epsilon</tex> для некоторого <tex>0 \le \epsilon < 1 </tex>.
Подставляя выбранное <tex>K</tex> в [[#statement3statement2|утверждение(32)]] получаем:
<tex>\parbox{0px}{\begin{align*}
E(T) &= \le K - 1 + \sum\limits_{t=K}^{\infty} E(X_t) =\\&= \left(\delta^{-1} \ln X_0 + \epsilon- 1\right) + \sum\limits_{t=K}^{\infty} E(X_t) \le_{(1)}\\&\le_{(1)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^K X_0 \sum\limits_{i = 0}^{\infty}(1 - \delta)^i =_{(2)} \\&=_{(2)} \delta^{-1} \ln X_0 + \epsilon - 1+ (1 - \delta)^K X_0 \delta^{-1} \le_{(3)} \\&\le_{(3)} \delta^{-1} \ln X_0 + \epsilon - 1+ (1 - \delta)^\epsilon (1 - \delta)^{\delta^{-1} \ln X_0} X_0 \delta^{-1} =_\le_{(4)}\\&\le_{(4)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^\epsilon e^{- \delta (\delta^{-1} \ln X_0)} X_0 \delta^{-1} =_{(5)}\\&=_{(5)} \delta^{-1} \ln X_0 + \epsilon - 1 + (1 - \delta)^{\epsilon}\delta^{-1} \le_{(6)}\\
&\le_{(6)} \delta^{-1} (\ln X_0 + 1)
\end{align*}}</tex>
Пояснение:
# Аналогично По [[#statement1|утверждению(1).3]].
# Используем формулу суммы геометрической прогрессии.
# Подставляем значение <tex>K</tex>.
# По [[#statement1|утверждению(1).1]].
# Упрощаем выражение.
# Находим экстремумы функции Так как <tex>f(\epsilon) = \epsilon + - 1 < 0</tex> и <tex>(1 - \delta)^{\epsilon}\delta^{-1}</tex> на интервале <tex>[0, le 1)</tex>.
2. Докажем второе утверждение теоремы. Пусть <tex>T_c = \lceil \delta^{-1} (\ln X_0 + c) \rceil</tex>. Тогда
<tex>\parbox{0px}{\begin{align*}
P(T > T_c) &\le_{(1)} P(X_{T_c} > 0) \le_{(12)}\\&\le_{(12)} E(X_{T_c}) \le_{(23)}\\&\le_{(23)} e^{-\delta T_c}X_0 \le_{(34)}\\&\le_{(34)} e^{-\delta \left( \delta^{-1}(\ln X_0 + c)\right) } X_0 =_{(45)}\\&=_{(45)} e^{-c}
\end{align*}}</tex>
Пояснение:
# Аналогично По [[#statement3statement1|утверждению(3)1.4]].# По [[#statement1|1.5]] и [[#statement1|1.2]].# По [[#statement1|утверждению(1).3]] и [[#statement1|1.1]].
# Подставляем <tex>T_c</tex>
# Упрощаем.
