Теорія відновлення

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Теорія відновлення  — це галузь теорії ймовірностей, що узагальнює процеси Пуассона для довільних проміжків часу. Серед застосувань теорії є наприклад розрахунок середнього часу потраченого мавпою, яка випадково натискає на клавіатуру, до введення нею слова "Макбет" і порівняння довгострокових переваг різних страхових полісів.

Процеси відновлення[ред.ред. код]

Вступ[ред.ред. код]

Процес відновлення є узагальненням процесу Пуассона. По суті, процес Пуассона, це неперервний в часі Марківський процес на множині натуральних чисел (звичайно починаючи з нуля), який має незалежні однаково розподілені терміни перебування в кожному цілому ί (терміни перебування мають експоненціальний розподіл), до переходу (з ймовірністю 1) до наступного цілого числа ί+1. Таким же неформальним чином ми можемо визначити процес відновлення, який буде визначатися ідентично, за винятком того, що проміжки часу беруться на більш загальних розподілах.

Формальне визначення[ред.ред. код]

Допустимо, що S_1 , S_2 , S_3 , S_4 , S_5, \ldots це послідовність незалежно однаково розподіленими величинами таких, що  0<{\mathbb {E}}[S_{i}]<\infty.. Ми посилаємося на випадкову величину S_i як «i-й» проміжок часу. Введемо для кожного n > 0  J_n = \sum_ {I = 1} ^ N  S_i Величини J_n називаються " n–м " моментами стрибків а інтервали [J_n, J_ {N +1}] називаються інтервалами відновлення. Тоді випадкова величина (X_t)_{t\geq0} , яка задається  X_t = \sum^{\infty}_{n=1} \mathbb{I}_{\{J_n \leq t\}}=\sup \left\{\, n: J_n \leq t\, \right\} (Де \mathbb{I} — характеристична функція), показує кількість стрибків, які відбулися до часу t, і називається процес відновлення.

Інтерпретація[ред.ред. код]

Будемо вважати, що відрізок часу \{ S_i : i \geq 1 \} це час, який минув до моменту коли машина зазнає поломки в «ί-й» раз, відтоді як вона останній раз ламалась. (Зазначимо, що при цьому передбачається, що машина миттєво відновлюється і відразу ж перезапускається таймер). Відповідно до цієї інтерпретації,часи стрибків \{ J_n : n \geq 1 \} містять дані про послідовні моменти, коли машина ламалась, а процес відновлення X_t містить кількість разів, які машина мала бути відремонтована до цього часу в кожний момент часу t. Проте, корисно розуміти процес відновлення в його абстрактній формі, так як він може бути використаний для моделювання великого числа практичних ситуацій.

Процеси відновлення-винагороди[ред.ред. код]

Нехай W_1, W_2, \dots — деяка послідовність незалежних однаково-розподілених випадкових величин (винагороди), яка задовольняє \mathbb{E}|W_i| < \infty.\,. Тоді випадкова величина Y_t = \sum_{i=1}^{X_t}W_i називається процесом відновленням-винагороди. На відміну від S_i, кожна W_i може набувати як додатних так і від'ємних значень. Випадкова величина Y_T залежить від двох послідовностей: проміжків часу S_1, S_2, \dots і винагороди W_1, W_2, \dots. Ці дві послідовності не обов'язково незалежні. Зокрема, W_i може бути функцією від S_i.

Інтерпретація[ред.ред. код]

У контексті вище зазначеної інтерпретації проміжків часу, як термінів між послідовними несправностями машини, «винагороди» W_1, W_2,… (які в даному випадку є від'ємними) можна розглядати як послідовні витрати на ремонт, після послідовних несправностей. Можна також розглядати чарівну гуску, що відкладає яйця з інтервалами, розподіленими як S_i. Іноді вона несе золоті яйця випадкової ваги, а іноді вона відкладає токсичні яйця (також випадкової ваги), які вимагають витратного знешкодження. «Винагороди» W_i це послідовні (випадкові) фінансові втрати/прибуток від послідовних яєць (і = 1,2,3, …), а Y_t визначає загальну фінансову «винагороду» в момент часу t.

Властивості процесів відновлення та процесів відновлення-винагороди[ред.ред. код]

Визначимо функцію відновлення: m(t) = \mathbb{E}[X_t].\

Елементарна теорема відновлення[ред.ред. код]

Функція відновлення задовольняє \lim_{t \to \infty} \frac{1}{t}m(t) = 1/\mathbb{E}[S_1]

Доведення[ред.ред. код]

Як вказано нижче згідно сильного закону великих чисел для процесів відновлення \lim_{t \to \infty} \frac {X_t}{t} = \frac{1}{\mathbb{E}[S_1]}. Щоб довести елементарну теорему відновлення, досить показати, що \left\{\frac{X_t}{t}; t \geq 0\right\} може бути рівномірно проінтегрована. Для цього, розглянемо деякі усічені процеси відновлення, де проміжки часу визначаються \overline{S_n} = a \mathbb{I}\{S_n > a\}, де a точка така, що 0 < F(a) = p < 1  , яка існує для всіх недетерміністичних процесів відновлення. Цей новий процес відновлення \overline{X_t} є верхньою межею X_t і його відновлення може виникнути тільки на проміжку   \{na; n \in \mathbb{N} \} . Більш того, кількість відновлень в кожен момент часу має геометричний розподіл з параметром P.

Тому маємо 
\begin{align}
\overline{X_t} &\leq \sum_{i=1}^{[at]} \mathrm{Geometric}(p) \\
\mathbb{E}\left[\,\overline{X_t}\,\right]^2 &\leq C_1 t + C_2 t^2 \\
P\left(\frac{X_t}{t} > x\right) &\leq \frac{E\left[X_t^2\right]}{t^2x^2} \leq \frac{E\left[\overline{X_t}^2\right]}{t^2x^2} \leq \frac{C}{x^2}.
\end{align}
.

Елементарні теореми відновлення для процесів відновлення-винагороди[ред.ред. код]

Визначимо функцію винагороди: g(t) = \mathbb{E}[Y_t].\,. Функція винагороди задовольняє \lim_{t \to \infty} \frac{1}{t}g(t) = \frac{\mathbb{E}[W_1]}{\mathbb{E}[S_1]}.

Рівняння відновлення[ред.ред. код]

Функція відновлення задовольняє m(t) = F_S(t) + \int_0^t m(t-s) f_S(s)\, ds , де F_S — функція розподілу від S_1, а F_S це ймовірнісна функція щільності.

Доведення рівняння відновлення[ред.ред. код]

Ми можемо записати: m(t) = \mathbb{E}[X_t] = \mathbb{E}[\mathbb{E}(X_t \mid S_1)]. \, . Але за властивістю Маркова \mathbb{E}(X_t \mid S_1=s) = \mathbb{I}_{\{t \geq s\}} \left( 1 + \mathbb{E}[X_{t-s}]  \right). \, . Отже, 
\begin{align}
m(t) & {} = \mathbb{E}[X_t] \\[12pt]
& {} = \mathbb{E}[\mathbb{E}(X_t \mid S_1)] \\[12pt]
& {} =  \int_0^\infty \mathbb{E}(X_t \mid S_1=s) f_S(s)\, ds \\[12pt]
& {} = \int_0^\infty \mathbb{I}_{\{t \geq s\}} \left( 1 + \mathbb{E}[X_{t-s}] \right) f_S(s)\, ds \\[12pt]
& {} = \int_0^t \left( 1 + m(t-s) \right) f_S(s)\, ds \\[12pt]
& {} =  F_S(t) + \int_0^t  m(t-s) f_S(s)\, ds,
\end{align}.

Асимптотичні властивості[ред.ред. код]

(X_t)_{t\geq0} і (Y_t)_{t\geq0} задовольняють  \lim_{t \to \infty} \frac{1}{t} X_t = \frac{1}{\mathbb{E}S_1} (Посилений закон великих чисел для процесів відновлення)  \lim_{t \to \infty} \frac{1}{t} Y_t = \frac{1}{\mathbb{E}S_1} \mathbb{E}W_1 (Сильний закон великих чисел для процесів відновлення-винагороди) майже напевно.

Доведення[ред.ред. код]

Спочатку розглянемо  (X_t)_{t\geq0}. За визначенням маємо: J_{X_t} \leq t \leq J_{X_t+1} для всіх  t \geq 0і тому 
\frac{J_{X_t}}{X_t} \leq \frac{t}{X_t} \leq \frac{J_{X_t+1}}{X_t}
для всіх t ≥ 0. Тепер, з того що  0< \mathbb{E}S_i < \infty ми маємо:X_t \to \infty, при  t \to \infty майже вірогідно (з ймовірністю 1). Отже, \frac{J_{X_t}}{X_t} = \frac{J_n}{n} = \frac{1}{n}\sum_{i=1}^n S_i \to \mathbb{E}S_1 майже напевно(з використанням сильного закону великих чисел), аналогічно: \frac{J_{X_t+1}}{X_t} = \frac{J_{X_t+1}}{X_t+1}\frac{X_t+1}{X_t} = \frac{J_{n+1}}{n+1}\frac{n+1}{n}  \to \mathbb{E}S_1\cdot 1 майже напевно. Таким чином (оскільки  t/X_t знаходиться між цими двома виразами) 
\frac{1}{t} X_t \to \frac{1}{\mathbb{E}S_1}
майже напевно. Далі розглянемо  (Y_t)_{t\geq0}. Маємо \frac{1}{t}Y_t = \frac{X_t}{t} \frac{1}{X_t} Y_t \to \frac{1}{\mathbb{E}S_1}\cdot\mathbb{E}W_1 майже напевно ( використовуючи попередній результат і закон великих чисел на Y_T).

Парадокс перевірки[ред.ред. код]

Цікавою особливістю процесів відновлення є те, що якщо ми почекаємо деякий заданий час t, а потім подивимося на скільки великим є інтервал відновлення, який містить t, ми очікуємо, що він, зазвичай, буде більшим за середній по величині інтервал відновлення. Математично парадокс перевірки говорить: для будь-якого t > 0 інтервал відновлення, що містить t є стохастично більшим, ніж перший інтервал відновлення. Тобто, для всіх х > 0 і для всіх t > 0:  \mathbb{P}(S_{X_t+1} > x) \geq \mathbb{P}(S_1>x) = 1-F_S(x) , де F_S це функція розподілу незалежних однаково розподілених відрізків часу S_i.

Доведення парадоксу перевірки[ред.ред. код]

Позначимо час останнього стрибка перед t як  J_{X_t}, тоді інтервал відновлення, що містить t це  S_{X_t+1}. Тоді 
\begin{align}
\mathbb{P}(S_{X_t+1}>x) & {} = \int_0^\infty \mathbb{P}(S_{X_t+1}>x \mid J_{X_t} = s) f_S(s) \, ds \\[12pt]
& {} = \int_0^\infty \mathbb{P}(S_{X_t+1}>x | S_{X_t+1}>t-s) f_S(s)\, ds \\[12pt]
& {} =  \int_0^\infty \frac{\mathbb{P}(S_{X_t+1}>x \, , \, S_{X_t+1}>t-s)}{\mathbb{P}(S_{X_t+1}>t-s)} f_S(s) \, ds \\[12pt]
& {} = \int_0^\infty \frac{ 1-F(\max \{ x,t-s \})  }{1-F(t-s)} f_S(s) \, ds \\[12pt]
& {} = \int_0^\infty \min \left\{\frac{ 1-F(x)  }{1-F(t-s)},\frac{ 1-F(t-s)  }{1-F(t-s)}\right\} f_S(s) \, ds \\[12pt]
& {} = \int_0^\infty \min \left\{\frac{ 1-F(x)  }{1-F(t-s)},1\right\} f_S(s) \, ds \\[12pt]
& {} \geq 1-F(x) \\[12pt]
& {} = \mathbb{P}(S_1>x)
\end{align}
, що і треба було довести.

Суперпозиція[ред.ред. код]

Суперпозиція незалежних процесів відновлення в цілому не є процесом відновлення, але вона може бути описана в ширшому класі процесів,що має назву процесів відновлення Маркова. Проте, функція розподілу першого міжподієвого часу між подіями у процесі суперпозиції задається R(t) = 1 - \sum_{k=1}^K \frac{\alpha_K}{\sum_{k=1}^K \alpha_K} (1-R_k(t)) \prod_{j=1,j\neq k}^{K} \alpha_j \int_t^\infty (1-R_j(u))\text{d}u, де Rk(t) та αk > 0 функція розподілу між моментами часу і частота настання процесу k.

Див. також[ред.ред. код]

Джерела[ред.ред. код]

  • Smith, Walter L. (1958). «Renewal Theory and Its Ramifications». Journal of the Royal Statistical Society, Series B 20 (2). с. 243–302. JSTOR 2983891.