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

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

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

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

Процессы продления [ править ]

Введение [ править ]

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

Формальное определение [ править ]

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

Пусть - последовательность положительных независимых одинаково распределенных случайных величин такая, что${\ Displaystyle S_ {1}, S_ {2}, S_ {3}, S_ {4}, S_ {5}, \ ldots}$

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

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

${\ displaystyle \ operatorname {E} [S_ {i}]}$является ожидание в .${\ displaystyle S_ {i}}$

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

${\ Displaystyle J_ {п} = \ сумма _ {я = 1} ^ {п} S_ {я},}$

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

Тогда задается случайной величиной${\ Displaystyle (X_ {т}) _ {т \ 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] , как экспоненциальное распределение является единственным непрерывным случайной переменной со свойством memorylessness.

Процессы возобновления и вознаграждения [ править ]

Позвольте быть последовательность случайных величин 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 \lim _{t\to \infty }{\frac {X_{t}}{t}}={\frac {1}{\operatorname {E} [S_{1}]}}.}$ Чтобы доказать элементарную теорему восстановления, достаточно показать, что она равномерно интегрируема.${\displaystyle \left\{{\frac {X_{t}}{t}};t\geq 0\right\}}$ Для этого рассмотрим некоторый усеченный процесс обновления, в котором время ожидания определяется тем, где - точка, которая существует для всех недетерминированных процессов обновления. Этот новый процесс обновления является верхней границей, и его обновления могут происходить только на решетке . Кроме того, количество обновлений в каждый момент времени геометрическое с параметром . Итак, у нас есть${\displaystyle {\overline {S_{n}}}=a\operatorname {\mathbb {I} } \{S_{n}>a\}}$${\displaystyle a}$${\displaystyle 0<F(a)=p<1}$${\displaystyle {\overline {X}}_{t}}$${\displaystyle X_{t}}$${\displaystyle \{na;n\in \mathbb {N} \}}$${\displaystyle p}$ ${\displaystyle {\begin{aligned}{\overline {X_{t}}}&\leq \sum _{i=1}^{[at]}\operatorname {Geometric} (p)\\\operatorname {E} \left[\,{\overline {X_{t}}}^{2}\,\right]&\leq C_{1}t+C_{2}t^{2}\\P\left({\frac {X_{t}}{t}}>x\right)&\leq {\frac {\operatorname {E} \left[X_{t}^{2}\right]}{t^{2}x^{2}}}\leq {\frac {\operatorname {E} \left[{\overline {X_{t}}}^{2}\right]}{t^{2}x^{2}}}\leq {\frac {C}{x^{2}}}.\end{aligned}}}$

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

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

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

Доказательство [2]

Мы можем повторить ожидания относительно первого времени выдержки: ${\displaystyle m(t)=\operatorname {E} [X_{t}]=\operatorname {E} [\operatorname {E} (X_{t}\mid S_{1})].\,}$ Исходя из определения процесса обновления, мы имеем ${\displaystyle \operatorname {E} (X_{t}\mid S_{1}=s)=\operatorname {\mathbb {I} } _{\{t\geq s\}}\left(1+\operatorname {E} [X_{t-s}]\right).\,}$ Так ${\displaystyle {\begin{aligned}m(t)&=\operatorname {E} [X_{t}]\\[12pt]&=\operatorname {E} [\operatorname {E} (X_{t}\mid S_{1})]\\[12pt]&=\int _{0}^{\infty }\operatorname {E} (X_{t}\mid S_{1}=s)f_{S}(s)\,ds\\[12pt]&=\int _{0}^{\infty }\operatorname {\mathbb {I} } _{\{t\geq s\}}\left(1+\operatorname {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 будет процессом обновления с функцией обновления и средним значением между обновлениями . Позвольте быть функцией, удовлетворяющей:${\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}]}$

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

Доказательство

Сначала подумайте . По определению мы имеем:${\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<\operatorname {E} [S_{i}]<\infty }$ ${\displaystyle X_{t}\to \infty }$ поскольку почти наверняка (с вероятностью 1). Следовательно:${\displaystyle t\to \infty }$ ${\displaystyle {\frac {J_{X_{t}}}{X_{t}}}={\frac {J_{n}}{n}}={\frac {1}{n}}\sum _{i=1}^{n}S_{i}\to \operatorname {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 \operatorname {E} [S_{1}]\cdot 1}$ почти наверняка. Таким образом (поскольку он зажат между двумя терминами)${\displaystyle t/X_{t}}$ ${\displaystyle {\frac {1}{t}}X_{t}\to {\frac {1}{\operatorname {E} [S_{1}]}}}$ почти наверняка. [3] Далее рассмотрим . У нас есть${\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}{\operatorname {E} [S_{1}]}}\cdot \operatorname {E} [W_{1}]}$ почти наверняка (используя первый результат и закон больших чисел ).${\displaystyle Y_{t}}$

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

${\displaystyle {\frac {X_{t}-t/\mu }{\sqrt {t\sigma ^{2}/\mu ^{3}}}}}$

Парадокс осмотра [ править ]

Любопытная особенность процессов обновления состоит в том, что если мы подождем некоторое заданное время 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 смещено по размеру, поскольку вероятность выбора интервала пропорциональна его размеру. Однако средний интервал обновления не зависит от размера.

Доказательство

Обратите внимание, что время последнего скачка перед t равно ; и что интервал обновления, содержащий t, равен . потом${\displaystyle J_{X_{t}}}$${\displaystyle S_{X_{t}+1}}$ ${\displaystyle {\begin{aligned}\operatorname {P} (S_{X_{t}+1}>x)&{}=\int _{0}^{\infty }\operatorname {P} (S_{X_{t}+1}>x\mid J_{X_{t}}=s)f_{J_{X_{t}}}(s)\,ds\\[12pt]&{}=\int _{0}^{\infty }\operatorname {P} (S_{X_{t}+1}>x|S_{X_{t}+1}>t-s)f_{J_{X_{t}}}(s)\,ds\\[12pt]&{}=\int _{0}^{\infty }{\frac {\operatorname {P} (S_{X_{t}+1}>x\,,\,S_{X_{t}+1}>t-s)}{\operatorname {P} (S_{X_{t}+1}>t-s)}}f_{J_{X_{t}}}(s)\,ds\\[12pt]&{}=\int _{0}^{\infty }{\frac {1-F(\max\{x,t-s\})}{1-F(t-s)}}f_{J_{X_{t}}}(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_{J_{X_{t}}}(s)\,ds\\[12pt]&{}=\int _{0}^{\infty }\min \left\{{\frac {1-F(x)}{1-F(t-s)}},1\right\}f_{J_{X_{t}}}(s)\,ds\\[12pt]&{}\geq \int _{0}^{\infty }(1-F(x))f_{J_{X_{t}}}(s)\,ds=1-F(x)=\operatorname {P} (S_{1}>x),\\[12pt]\end{aligned}}}$ поскольку оба и больше или равны для всех значений s .${\displaystyle {\frac {1-F(x)}{1-F(t-s)}}}$${\displaystyle 1}$${\displaystyle 1-F(x)}$

Суперпозиция [ править ]

Если процесс обновления не является пуассоновским, суперпозиция (сумма) двух независимых процессов обновления не является процессом обновления. ^[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 - функция распределения времени между событиями и скорость поступления процесса k . ^[10]

Пример приложения [ править ]

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

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

Решение

Срок службы n машин можно смоделировать как n независимых одновременных процессов возобновления и вознаграждения, поэтому достаточно рассмотреть случай n = 1 . Обозначим этот процесс через . Последовательные сроки службы S заменяемых машин независимы и одинаково распределены, поэтому оптимальная политика одинакова для всех заменяемых машин в процессе.${\displaystyle (Y_{t})_{t\geq 0}}$ Если Эрик решает в начале срока службы машины заменить ее в момент времени 0 < t <2, но машина выходит из строя до этого времени, то время жизни S машины равномерно распределяется на [0,  t ] и, таким образом, имеет математическое ожидание 0,5. т . Таким образом, общий ожидаемый срок службы машины составляет: ${\displaystyle {\begin{aligned}\operatorname {E} [S]&=\operatorname {E} [S\mid {\text{fails before }}t]\cdot \operatorname {P} [{\text{fails before }}t]+\operatorname {E} [S\mid {\text{does not fail before }}t]\cdot \operatorname {P} [{\text{does not fail before }}t]\\[6pt]&=0.5t({\frac {t}{2}})+t({\frac {2-t}{2}})\end{aligned}}}$ и ожидаемая стоимость W на машину составляет: ${\displaystyle {\begin{aligned}\operatorname {E} [W]&=\operatorname {E} [W\mid {\text{fails before }}t]\cdot \operatorname {P} ({\text{fails before }}t)+\operatorname {E} [W\mid {\text{does not fail before }}t]\cdot \operatorname {P} ({\text{does not fail before }}t)\\[6pt]&=2600({\frac {t}{2}})+200({\frac {2-t}{2}})=1200t+200.\end{aligned}}}$ Таким образом, согласно строгому закону больших чисел, его долгосрочные средние затраты на единицу времени равны: ${\displaystyle {\frac {1}{t}}Y_{t}\simeq {\frac {\operatorname {E} [W]}{\operatorname {E} [S]}}={\frac {4(1200t+200)}{t^{2}+4t-2t^{2}}}}$ затем дифференцируя по t : ${\displaystyle {\frac {\partial }{\partial t}}{\frac {4(1200t+200)}{t^{2}+4t-2t^{2}}}=4{\frac {(4t-t^{2})(1200)-(4-2t)(1200t+200)}{(t^{2}+4t-2t^{2})^{2}}},}$ это означает, что точки поворота удовлетворяют: ${\displaystyle {\begin{aligned}0&=(4t-t^{2})(1200)-(4-2t)(1200t+200)=4800t-1200t^{2}-4800t-800+2400t^{2}+400t\\[6pt]&=-800+400t+1200t^{2},\end{aligned}}}$ и поэтому ${\displaystyle 0=3t^{2}+t-2=(3t-2)(t+1).}$ Возьмем единственное решение t в [0, 2]: t = 2/3. Это действительно минимум (а не максимум), поскольку стоимость единицы времени стремится к бесконечности, когда t стремится к нулю, а это означает, что стоимость уменьшается с увеличением t до точки 2/3, где она начинает расти.

См. Также [ править ]

• Теорема Кэмпбелла (вероятность)
• Составной процесс Пуассона
• Марковский процесс с непрерывным временем
• Лемма Литтла
• Теорема Палма – Хинчина.
• Пуассоновский процесс
• Теория массового обслуживания
• Остаточное время
• Теория разорения
• Полумарковский процесс

Эта статья включает в себя список общих ссылок , но он остается в значительной степени непроверенным, поскольку в нем отсутствует достаточное количество соответствующих встроенных ссылок . Пожалуйста, помогите улучшить эту статью, добавив более точные цитаты. ( Июль 2010 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

Заметки [ править ]

Ссылки [ править ]

• Кокс, Дэвид (1970). Теория обновления . Лондон: Methuen & Co., стр. 142. ISBN. 0-412-20570-X.
• Дуб, JL (1948). "Теория обновления с точки зрения теории вероятностей" (PDF) . Труды Американского математического общества . 63 (3): 422–438. DOI : 10.2307 / 1990567 . JSTOR  1990567 .
• Феллер, Уильям (1971). Введение в теорию вероятностей и ее приложения . 2 (второе изд.). Вайли.
• Гримметт, Г.Р . ; Стирзакер, Д.Р. (1992). Вероятность и случайные процессы (второе изд.). Издательство Оксфордского университета. ISBN 0198572220.
• Смит, Уолтер Л. (1958). «Теория обновления и ее последствия». Журнал Королевского статистического общества, Series B . 20 (2): 243–302. JSTOR  2983891 .
• Ванли Ван, Йоханнес Х.П. Шульц, Вейхуа Дэн и Эли Баркай (2018). «Теория обновления с распределенным временем пребывания с толстыми хвостами: типичное или редкое». Phys. Rev. E . 98 (4): 042139. arXiv : 1809.05856 . Bibcode : 2018PhRvE..98d2139W . DOI : 10.1103 / PhysRevE.98.042139 .