Теория обновления

Раздел теории вероятностей

Теория возобновления — это раздел теории вероятностей , который обобщает процесс Пуассона для произвольных времен удержания. Вместо экспоненциально распределенных времен удержания процесс возобновления может иметь любые независимые и идентично распределенные (IID) времена удержания, имеющие конечное среднее значение. Процесс возобновления-вознаграждения дополнительно имеет случайную последовательность вознаграждений, получаемых в каждое время удержания, которые являются IID, но не обязательно независимы от времен удержания.

Процесс восстановления имеет асимптотические свойства, аналогичные усиленному закону больших чисел и центральной предельной теореме . Функция восстановления (ожидаемое число поступлений) и функция вознаграждения (ожидаемое значение вознаграждения) имеют ключевое значение в теории восстановления. Функция восстановления удовлетворяет рекурсивному интегральному уравнению, уравнению восстановления. Ключевое уравнение восстановления дает предельное значение свертки с подходящей неотрицательной функцией. Суперпозицию процессов восстановления можно изучать как частный случай процессов восстановления Маркова . ${\displaystyle m(t)}$ ${\displaystyle g(t)}$ ${\displaystyle m'(t)}$

Приложения включают расчет лучшей стратегии замены изношенного оборудования на заводе и сравнение долгосрочных выгод различных страховых полисов. Парадокс инспекции связан с тем фактом, что наблюдение за интервалом обновления в момент времени t дает интервал со средним значением, большим, чем средний интервал обновления.

Процессы обновления

Введение

Процесс восстановления является обобщением процесса Пуассона . По сути, процесс Пуассона является непрерывным во времени процессом Маркова на положительных целых числах (обычно начинающимся с нуля), который имеет независимые экспоненциально распределенные времена удержания для каждого целого числа перед переходом к следующему целому числу, . В процессе восстановления времена удержания не обязательно должны иметь экспоненциальное распределение; скорее, времена удержания могут иметь любое распределение на положительных числах, при условии, что времена удержания независимы и одинаково распределены ( IID ) и имеют конечное среднее значение. ${\displaystyle i}$ ${\displaystyle i+1}$

Формальное определение

Пример эволюции процесса обновления с временами удержания S _i и временами скачков J _n .

Пусть — последовательность положительных независимых одинаково распределенных случайных величин с конечным ожидаемым значением ${\displaystyle (S_{i})_{i\geq 1}}$

${\displaystyle 0<\operatorname {E} [S_{i}]<\infty .}$

Мы называем случайную величину « -ым временем удержания». ${\displaystyle S_{i}}$ ${\displaystyle i}$

Определим для каждого n > 0:

${\displaystyle J_{n}=\sum _{i=1}^{n}S_{i},}$

каждый из них называется « -м временем скачка», а интервалы называются «интервалами обновления». ${\displaystyle J_{n}}$ ${\displaystyle n}$ ${\displaystyle [J_{n},J_{n+1}]}$

Тогда задается случайной величиной ${\displaystyle (X_{t})_{t\geq 0}}$

${\displaystyle X_{t}=\sum _{n=1}^{\infty }\operatorname {\mathbb {I} } _{\{J_{n}\leq t\}}=\sup \left\{\,n:J_{n}\leq t\,\right\}}$

где индикаторная функция ${\displaystyle \operatorname {\mathbb {I} } _{\{J_{n}\leq t\}}}$

${\displaystyle \operatorname {\mathbb {I} } _{\{J_{n}\leq t\}}={\begin{cases}1,&{\text{if }}J_{n}\leq t\\0,&{\text{otherwise}}\end{cases}}}$

${\displaystyle (X_{t})_{t\geq 0}}$представляет собой количество скачков, произошедших к моменту времени t , и называется процессом обновления.

Интерпретация

Если рассматривать события, происходящие в случайные моменты времени, можно думать о времени удержания как о случайном времени, прошедшем между двумя последовательными событиями. Например, если процесс обновления моделирует количество поломок различных машин, то время удержания представляет собой время между поломкой одной машины до поломки другой. ${\displaystyle \{S_{i}:i\geq 1\}}$

Процесс Пуассона является уникальным процессом восстановления с марковским свойством , ^[1] поскольку экспоненциальное распределение является уникальной непрерывной случайной величиной со свойством отсутствия памяти.

Процессы возобновления-вознаграждения

Пример эволюции процесса возобновления-вознаграждения с временами удержания S _i , временами прыжка J _n и вознаграждениями W _i

Пусть будет последовательностью случайных величин IID ( вознаграждений ), удовлетворяющей ${\displaystyle W_{1},W_{2},\ldots }$

${\displaystyle \operatorname {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},\ldots }$ ${\displaystyle W_{1},W_{2},\ldots }$ ${\displaystyle W_{i}}$ ${\displaystyle S_{i}}$

Интерпретация

В контексте вышеприведенной интерпретации времени обслуживания как времени между последовательными неисправностями машины, «вознаграждения» (которые в данном случае оказываются отрицательными) можно рассматривать как последовательные затраты на ремонт, понесенные в результате последовательных неисправностей. ${\displaystyle W_{1},W_{2},\ldots }$

Альтернативная аналогия: у нас есть волшебный гусь, который несет яйца с интервалами (временами выдержки), распределенными как . Иногда он несет золотые яйца случайного веса, а иногда он несет токсичные яйца (также случайного веса), которые требуют ответственной (и дорогостоящей) утилизации. «Награды» — это последовательные (случайные) финансовые потери/прибыли, возникающие в результате последовательных яиц ( i = 1,2,3,...), и регистрирует общую финансовую «награду» в момент времени t . ${\displaystyle S_{i}}$ ${\displaystyle W_{i}}$ ${\displaystyle Y_{t}}$

Функция обновления

Мы определяем функцию восстановления как ожидаемое значение числа скачков, наблюдаемых до некоторого момента времени : ${\displaystyle t}$

${\displaystyle m(t)=\operatorname {E} [X_{t}].\,}$

Элементарная теорема восстановления

Функция обновления удовлетворяет

${\displaystyle \lim _{t\to \infty }{\frac {1}{t}}m(t)={\frac {1}{\operatorname {E} [S_{1}]}}.}$

Элементарная теорема о возобновлении для процессов вознаграждения за возобновление

Определим функцию вознаграждения :

${\displaystyle g(t)=\operatorname {E} [Y_{t}].\,}$

Функция вознаграждения удовлетворяет

${\displaystyle \lim _{t\to \infty }{\frac {1}{t}}g(t)={\frac {\operatorname {E} [W_{1}]}{\operatorname {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}}$

Теорема обновления ключа

Пусть X — процесс обновления с функцией обновления и средним значением взаимного обновления . Пусть — функция, удовлетворяющая: ${\displaystyle m(t)}$ ${\displaystyle \mu }$ ${\displaystyle g:[0,\infty )\rightarrow [0,\infty )}$

• ${\displaystyle \int _{0}^{\infty }g(t)\,dt<\infty }$
• g монотонна и невозрастает

Ключевая теорема восстановления гласит, что, как : ^[3] ${\displaystyle t\rightarrow \infty }$

${\displaystyle \int _{0}^{t}g(t-x)m'(x)\,dx\rightarrow {\frac {1}{\mu }}\int _{0}^{\infty }g(x)\,dx}$

Теорема восстановления

Рассматривая для любого дает как частный случай теорему восстановления: ^[4] ${\displaystyle g(x)=\mathbb {I} _{[0,h]}(x)}$ ${\displaystyle h>0}$

${\displaystyle m(t+h)-m(t)\rightarrow {\frac {h}{\mu }}}$как ${\displaystyle t\rightarrow \infty }$

Результат может быть доказан с помощью интегральных уравнений или с помощью аргумента связи . ^[5] Хотя это и частный случай ключевой теоремы восстановления, его можно использовать для вывода полной теоремы, рассматривая ступенчатые функции и затем увеличивая последовательности ступенчатых функций. ^[3]

Асимптотические свойства

Процессы обновления и процессы обновления-вознаграждения имеют свойства, аналогичные сильному закону больших чисел , который можно вывести из той же теоремы. Если — процесс обновления и — процесс обновления-вознаграждения, то: ${\displaystyle (X_{t})_{t\geq 0}}$ ${\displaystyle (Y_{t})_{t\geq 0}}$

${\displaystyle \lim _{t\to \infty }{\frac {1}{t}}X_{t}={\frac {1}{\operatorname {E} [S_{1}]}}}$^[6]

${\displaystyle \lim _{t\to \infty }{\frac {1}{t}}Y_{t}={\frac {1}{\operatorname {E} [S_{1}]}}\operatorname {E} [W_{1}]}$

почти наверняка.

Процессы восстановления дополнительно обладают свойством, аналогичным центральной предельной теореме : ^[6]

${\displaystyle {\frac {X_{t}-t/\mu }{\sqrt {t\sigma ^{2}/\mu ^{3}}}}\to {\mathcal {N}}(0,1)}$

Парадокс инспекции

Интервал обновления, определяемый случайной точкой t (показан красным), стохастически больше первого интервала обновления.

Любопытной особенностью процессов обновления является то, что если мы подождем некоторое заранее определенное время t , а затем посмотрим, насколько велик интервал обновления, содержащий t , мы должны ожидать, что он, как правило, будет больше интервала обновления среднего размера.

Математически парадокс инспекции гласит: для любого t > 0 интервал обновления, содержащий t, стохастически больше первого интервала обновления. То есть для всех x > 0 и для всех t > 0:

${\displaystyle \operatorname {P} (S_{X_{t}+1}>x)\geq \operatorname {P} (S_{1}>x)=1-F_{S}(x)}$

где F _S — кумулятивная функция распределения времени ожидания IID S _i . Ярким примером является парадокс времени ожидания автобуса : при заданном случайном распределении прибытия автобусов среднестатистический пассажир на автобусной остановке наблюдает больше задержек, чем среднестатистический оператор автобусов.

Разрешение парадокса заключается в том, что наше выборочное распределение в момент времени t имеет смещение по размеру (см. смещение выборки ), в том смысле, что вероятность выбора интервала пропорциональна его размеру. Однако интервал обновления среднего размера не имеет смещения по размеру.

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

Если процесс восстановления не является пуассоновским процессом, суперпозиция (сумма) двух независимых процессов восстановления не является процессом восстановления. ^[7] Однако такие процессы могут быть описаны в рамках более широкого класса процессов, называемых процессами Марковского восстановления . ^[8] Однако кумулятивная функция распределения первого межсобытийного времени в процессе суперпозиции определяется как ^[9]

${\displaystyle R(t)=1-\sum _{k=1}^{K}{\frac {\alpha _{k}}{\sum _{l=1}^{K}\alpha _{l}}}(1-R_{k}(t))\prod _{j=1,j\neq k}^{K}\alpha _{j}\int _{t}^{\infty }(1-R_{j}(u))\,{\text{d}}u}$

где R _k ( t ) и α _k  > 0 — это CDF времен между событиями и скорости поступления процесса k . ^[10]

Пример заявки

У Эрика-предпринимателя есть n машин, каждая из которых имеет равномерно распределенный срок службы от нуля до двух лет. Эрик может позволить каждой машине работать до тех пор, пока она не выйдет из строя, со стоимостью замены €2600; в качестве альтернативы он может заменить машину в любое время, пока она еще функционирует, со стоимостью €200.

Какова его оптимальная политика замены?

Смотрите также

• Теорема Кэмпбелла (вероятность)
• Процесс сложного Пуассона
• Непрерывный марковский процесс
• Лемма Литтла
• Интегральное уравнение Лотки
• Теорема Пальма–Хинчина
• процесс Пуассона
• Теория массового обслуживания
• Остаточное время
• Теория руин
• Полумарковский процесс
• Уравнение фон Ферстера

Примечания

1. Гримметт и Стирзакер (1992), стр. 393.
2. Гримметт и Стирзакер (1992), стр. 390.
3. Гримметт и Стирзакер (1992), стр. 395.
4. Феллер (1971), стр. 347–351.
5. Гримметт и Стирзакер (1992), стр. 394–5.
6. Grimmett & Stirzaker (1992), стр. 394.
7. Гримметт и Стирзакер (1992), стр. 405.
8. Чинлар, Эрхан (1969). «Теория восстановления Маркова». Достижения в прикладной теории вероятностей . 1 (2). Applied Probability Trust: 123–187. doi :10.2307/1426216. JSTOR  1426216.
9. Лоуренс, А. Дж. (1973). «Зависимость интервалов между событиями в процессах суперпозиции». Журнал Королевского статистического общества. Серия B (Методологическая) . 35 (2): 306–315. doi :10.1111/j.2517-6161.1973.tb00960.x. JSTOR  2984914.формула 4.1
10. Choungmo Fofack, Nicaise; Nain, Philippe; Neglia, Giovanni; Towsley, Don (6 марта 2012 г.). Анализ сетей кэширования на основе TTL. Труды 6-й Международной конференции по методам и инструментам оценки производительности (отчет) . Получено 15 ноября 2012 г.

Ссылки

• Кокс, Дэвид (1970). Теория обновления . Лондон: Methuen & Co. стр. 142. ISBN 0-412-20570-X.
• Дуб, Дж. Л. (1948). «Теория возобновления с точки зрения теории вероятностей» (PDF) . Труды Американского математического общества . 63 (3): 422–438. doi : 10.2307/1990567 . JSTOR  1990567.
• Феллер, Уильям (1971). Введение в теорию вероятностей и ее приложения . Т. 2 (второе изд.). Wiley.
• Grimmett, GR ; Stirzaker, DR (1992). Вероятность и случайные процессы (второе изд.). Oxford University Press. ISBN 0198572220.
• Смит, Уолтер Л. (1958). «Теория обновления и ее разветвления». Журнал Королевского статистического общества, Серия B. 20 ( 2): 243–302. JSTOR  2983891.
• Wanli Wang, Johannes HP Schulz, Weihua Deng и Eli Barkai (2018). «Теория возобновления с распределенным временем пребывания с толстым хвостом: типичное против редкого». Phys. Rev. E . 98 (4): 042139. arXiv : 1809.05856 . Bibcode :2018PhRvE..98d2139W. doi :10.1103/PhysRevE.98.042139. S2CID  54727926.{{cite journal}}: CS1 maint: multiple names: authors list (link)