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

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

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

Вступ

Процес відновлення є узагальненням процесу Пуассона. По суті, процес Пуассона, це неперервний в часі Марківський процес на множині натуральних чисел (звичайно починаючи з нуля), який має незалежні однаково розподілені терміни перебування в кожному цілому ί (терміни перебування мають експоненціальний розподіл), до переходу (з ймовірністю 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.