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

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

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

Вступ

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

Формальне визначення

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

Інтерпретація

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

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

Нехай ${\displaystyle W_{1},W_{2},\dots }$ — деяка послідовність незалежних однаково-розподілених випадкових величин (винагороди), яка задовольняє ${\displaystyle \mathbb {E} |W_{i}|<\infty .\,}$. Тоді випадкова величина ${\displaystyle Y_{t}=\sum _{i=1}^{X_{t}}W_{i}}$ називається процесом відновленням-винагороди. На відміну від ${\displaystyle S_{i}}$, кожна ${\displaystyle W_{i}}$ може набувати як додатних так і від'ємних значень. Випадкова величина ${\displaystyle Y_{T}}$ залежить від двох послідовностей: проміжків часу ${\displaystyle S_{1},S_{2},\dots }$ і винагороди ${\displaystyle W_{1},W_{2},\dots }$. Ці дві послідовності не обов'язково незалежні. Зокрема, ${\displaystyle W_{i}}$ може бути функцією від ${\displaystyle S_{i}}$.

Інтерпретація

У контексті вище зазначеної інтерпретації проміжків часу, як термінів між послідовними несправностями машини, «винагороди» ${\displaystyle W_{1},W_{2},}$… (які в даному випадку є від'ємними) можна розглядати як послідовні витрати на ремонт, після послідовних несправностей. Можна також розглядати чарівну гуску, що відкладає яйця з інтервалами, розподіленими як ${\displaystyle S_{i}}$. Іноді вона несе золоті яйця випадкової ваги, а іноді вона відкладає токсичні яйця (також випадкової ваги), які вимагають витратного знешкодження. «Винагороди» ${\displaystyle W_{i}}$ це послідовні (випадкові) фінансові втрати/прибуток від послідовних яєць (і = 1,2,3, …), а ${\displaystyle Y_{t}}$ визначає загальну фінансову «винагороду» в момент часу t.

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

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

Елементарна теорема відновлення

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

Доведення

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

Тому маємо ${\displaystyle {\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}}}$.

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

Визначимо функцію винагороди: ${\displaystyle g(t)=\mathbb {E} [Y_{t}].\,}$. Функція винагороди задовольняє ${\displaystyle \lim _{t\to \infty }{\frac {1}{t}}g(t)={\frac {\mathbb {E} [W_{1}]}{\mathbb {E} [S_{1}]}}}$.

Рівняння відновлення

Функція відновлення задовольняє ${\displaystyle m(t)=F_{S}(t)+\int _{0}^{t}m(t-s)f_{S}(s)\,ds}$, де ${\displaystyle F_{S}}$ — функція розподілу від ${\displaystyle S_{1}}$, а ${\displaystyle F_{S}}$ це ймовірнісна функція щільності.

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

Ми можемо записати: ${\displaystyle m(t)=\mathbb {E} [X_{t}]=\mathbb {E} [\mathbb {E} (X_{t}\mid S_{1})].\,}$. Але за властивістю Маркова ${\displaystyle \mathbb {E} (X_{t}\mid S_{1}=s)=\mathbb {I} _{\{t\geq s\}}\left(1+\mathbb {E} [X_{t-s}]\right).\,}$. Отже, ${\displaystyle {\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}}}$.

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

${\displaystyle (X_{t})_{t\geq 0}}$ і ${\displaystyle (Y_{t})_{t\geq 0}}$ задовольняють ${\displaystyle \lim _{t\to \infty }{\frac {1}{t}}X_{t}={\frac {1}{\mathbb {E} S_{1}}}}$ (Посилений закон великих чисел для процесів відновлення) ${\displaystyle \lim _{t\to \infty }{\frac {1}{t}}Y_{t}={\frac {1}{\mathbb {E} S_{1}}}\mathbb {E} W_{1}}$ (Сильний закон великих чисел для процесів відновлення-винагороди) майже напевно.

Доведення

Спочатку розглянемо ${\displaystyle (X_{t})_{t\geq 0}}$. За визначенням маємо: ${\displaystyle J_{X_{t}}\leq t\leq J_{X_{t}+1}}$ для всіх ${\displaystyle t\geq 0}$і тому ${\displaystyle {\frac {J_{X_{t}}}{X_{t}}}\leq {\frac {t}{X_{t}}}\leq {\frac {J_{X_{t}+1}}{X_{t}}}}$ для всіх t ≥ 0. Тепер, з того що ${\displaystyle 0<\mathbb {E} S_{i}<\infty }$ ми маємо:${\displaystyle X_{t}\to \infty }$, при ${\displaystyle t\to \infty }$ майже достеменно (з імовірністю 1). Отже, ${\displaystyle {\frac {J_{X_{t}}}{X_{t}}}={\frac {J_{n}}{n}}={\frac {1}{n}}\sum _{i=1}^{n}S_{i}\to \mathbb {E} S_{1}}$ майже напевно(з використанням сильного закону великих чисел), аналогічно: ${\displaystyle {\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}$ майже напевно. Таким чином (оскільки ${\displaystyle t/X_{t}}$ знаходиться між цими двома виразами) ${\displaystyle {\frac {1}{t}}X_{t}\to {\frac {1}{\mathbb {E} S_{1}}}}$ майже напевно. Далі розглянемо ${\displaystyle (Y_{t})_{t\geq 0}}$. Маємо ${\displaystyle {\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}}$ майже напевно ( використовуючи попередній результат і закон великих чисел на ${\displaystyle Y_{T}}$).

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

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

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

Позначимо час останнього стрибка перед t як ${\displaystyle J_{X_{t}}}$, тоді інтервал відновлення, що містить t це ${\displaystyle S_{X_{t}+1}}$. Тоді

${\displaystyle {\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}}}$

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

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

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

Див. також

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

Джерела

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

• Doob, J. L. (1948). (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.