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

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

Процеси відновлення

Вступ

Процес відновлення є узагальненням процесу Пуассона. По суті, процес Пуассона, це неперервний в часі Марківський процес на множині натуральних чисел (звичайно починаючи з нуля), який має незалежні однаково розподілені терміни перебування в кожному цілому ί (терміни перебування мають експоненціальний розподіл), до переходу (з ймовірністю 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\geq 0}$, яка задається $X_{t}=\sum _{n=1}^{\infty }\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{aligned}{\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^{2}x^{2}}}\leq {\frac {E\left[{\overline {X_{t}}}^{2}\right]}{t^{2}x^{2}}}\leq {\frac {C}{x^{2}}}.\end{aligned}}$.

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

Визначимо функцію винагороди: $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{aligned}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{aligned}}$.

Асимптотичні властивості

$(X_{t})_{t\geq 0}$ і $(Y_{t})_{t\geq 0}$ задовольняють $\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\geq 0}$. За визначенням маємо: $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\geq 0}$. Маємо ${\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{aligned}\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{aligned}}$

що і треба було довести.

Суперпозиція

Суперпозиція незалежних процесів відновлення в цілому не є процесом відновлення, але вона може бути описана в ширшому класі процесів,що має назву процесів відновлення Маркова. Проте, функція розподілу першого міжподієвого часу між подіями у процесі суперпозиції задається $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.

Див. також

• Теорема Кемпбелла
• Ланцюги Маркова з неперервним часом
• Закон Літтла
• Пуассонівський процес
• Теорія масового обслуговування
• Процеси відновлення Маркова

Джерела

• Іксанов О.М. Теорія випадкових процесів [Архівовано 22 лютого 2014 у Wayback Machine.] - Київ, 2013.
• Cox, David (1970). Renewal Theory. London: Methuen & Co. с. 142. ISBN 0-412-20570-X.

• Doob, J. L. (1948). Renewal Theory From the Point of View of the Theory of Probability (PDF). Transactions of the American Mathematical Society. 63 (3): 422—438. JSTOR 1990567. Архів оригіналу (PDF) за 22 лютого 2014. Процитовано 15 лютого 2014.

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