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

Пусть $X_{1}, X_{2}, \ldots$ — последовательность НОРР случайных величин интервалов между восстановлениями. Пусть $S_{n} = X_{1}+\cdots +X_{n}$ — соответствующие моменты восстановления для каждого $n \geq 1$. Предположим, что каждая $X_{i}$ имеет конечное математическое ожидание $\overline{X}>0$, и для произвольного заданного $t>0$ используйте СЗБЧ (слабый закон больших чисел), чтобы показать, что $\lim_{n \rightarrow \infty } \mathbb {P}\left(S_{n} \leq t\right) = 0$.

Используя (а), покажите, что $\lim_{n \rightarrow \infty } \mathbb {P}\left(N(t) \geq n\right) = 0$ для каждого $t>0$, и объясните, почему это означает, что $N(t)$ является случайной величиной, т.е. не вырождена.

Предположим теперь, что $X_{i}$ не имеют конечного среднего. Рассмотрим усечение каждой $X_{i}$ до $\check{X}_{i}$, где для произвольного заданного $b>0$ $\check{X}_{i} = \min (X_{i}, b)$. Пусть $\check{N}(t)$ — считающий процесс восстановления для интервалов между восстановлениями $\check{X}_{i}$. Покажите, что $\check{N}(t)$ невырождена для каждого $t>0$. Покажите, что $N(t) \leq \check{N}(t)$ и, следовательно, $N(t)$ невырождена.

Пусть интервалы между восстановлениями имеют функцию распределения $\mathsf{F}_{X}(x)$, причём, как обычно, $\mathsf{F}_{X}(0) = 0$. Используя любую удобную вам комбинацию математики и здравого смысла, покажите, что для любого $\epsilon$, $0<\epsilon <1$, найдётся $\delta >0$ такое, что $\mathsf{F}_{X}(\delta ) \leq 1-\epsilon$. Иными словами, вам нужно показать, что положительная случайная величина должна с положительной вероятностью лежать в некотором диапазоне положительных значений, отделённом от нуля.

Покажите, что $\mathbb {P}\left(S_{n} \leq \delta \right) \leq (1-\epsilon )^{n}$.

Покажите, что $\mathbb {E}\left[N(\delta )\right] \leq 1/\epsilon$.

Для $\epsilon , \delta$ из пункта (а) покажите, что для любого целого $k$ выполнено $\mathbb {E}\left[N(k \delta )\right] \leq k/\epsilon$, и, следовательно, $\mathbb {E}\left[N(t)\right] \leq (t+\delta )/\epsilon \delta$ для любого $t>0$.

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

Найдите функцию распределения каждой $Y_{i}$ через функцию распределения $X_{i}$.

Найдите распределение вероятностей числа приходов обобщённого процесса восстановления в каждый момент, в который приходы происходят.

Объясните, как можно рассматривать обобщённый процесс восстановления как обычный процесс восстановления с интервалами между восстановлениями $\left\{ Y_{i}; i \geq 1\right\}$ и групповыми приходами в каждый момент восстановления.

Если рассматривать обобщённый процесс восстановления как обычный процесс восстановления с групповыми приходами, каково распределение размера группы приходов? (Смысл этого пункта — показать, что групповые приходы в обычном процессе восстановления существенно более общи, чем обобщённые процессы восстановления.)

$N(t)<n$ тогда и только тогда, когда $S_{n}>t$?

$N(t) \leq n$ тогда и только тогда, когда $S_{n} \geq t$?

$N(t)>n$ тогда и только тогда, когда $S_{n}<t$?

Покажите, что если $\lim_{n \rightarrow \infty } Y_{n}(\omega ) = 0$ для некоторого заданного $\omega$, то (при любом заданном $k$) $\omega \in A(m, k)$ для некоторого положительного целого $m$.

Покажите, что для всех $k \geq 1$

Покажите, что для всех $m \geq 1$ выполнено $A(m, k) \subseteq A(m+1, k)$. Используйте это (вместе с (1.9)), чтобы показать, что

Покажите, что если $\omega \in A(m, k)$, то $\left|Y_{m}(\omega )\right| \leq 1/k$. Используйте это (вместе с (в)), чтобы показать, что

Поскольку $k \geq 1$ произвольно, это показывает, что $\left\{ Y_{n}; n \geq 1\right\}$ сходится по вероятности.

Найдите $\mathbb {E}\left[Z_{n}\right]$ как функцию $n$ и найдите $\lim_{n \rightarrow \infty } \mathbb {E}\left[Z_{n}\right]$.

Пусть $W_{n} = \log_{2} X_{n}$. Найдите $\mathbb {E}\left[W_{n}\right]$ и $\mathbb {E}\left[\log_{2}(Z_{n}/Z_{0})\right]$ как функцию $n$.

Существует константа $\alpha$ такая, что $\lim_{n \rightarrow \infty }(1/n)[\log_{2}(Z_{n}/Z_{0})] = \alpha$ ПН1. Найдите $\alpha$ и объясните, как это следует из УЗБЧ.

Используя (в), покажите, что $\lim_{n \rightarrow \infty } Z_{n} = \beta$ ПН1 для некоторого $\beta$ и вычислите $\beta$.

Тщательно объясните, как результат в (а) и результат в (г) совместимы. Из этой задачи следует усвоить, что математическое ожидание логарифма произведения НОР с.в. может быть более значимым, чем математическое ожидание самого произведения.

Пусть $\left\{ Y_{n}; n \geq 1\right\}$ — последовательность с.в. Используя определение сходимости для последовательности чисел, обоснуйте следующие эквивалентности множеств:

Объясните, как это показывает, что $\left\{ \omega : \lim_{n} Y_{n}(\omega ) = 0\right\}$ обязательно является событием.

Используя законы де Моргана, покажите, что дополнение приведённой выше эквивалентности имеет вид

Покажите, что для сходимости $\left\{ Y_{n}; n \geq 1\right\}$ ПН1 необходимо и достаточно выполнение

Покажите, что для сходимости $\left\{ Y_{n}; n \geq 1\right\}$ ПН1 необходимо и достаточно выполнение

Покажите, что

Покажите, что если $\sum_{m=1}^{\infty } \mathbb {P}\left(A_{m}\right)<\infty$, то $\lim_{m \rightarrow \infty } \mathbb {P}\left(\bigcup_{n \geq m} A_{n}\right) = 0$.

Покажите, что если $\sum_{m=1}^{\infty } \mathbb {P}\left(A_{m}\right)<\infty$, то $\mathbb {P}\left(\bigcap_{m \geq 1} \bigcup_{n \geq m} A_{n}\right) = 0$. Этот хорошо известный результат называется леммой Бореля–Кантелли.

Множество $\left\{ \bigcap_{m} \bigcup_{n \geq m} A_{n}\right\}$ часто называют множеством $\omega$, содержащихся в бесконечно многих $A_{n}$. Не пытаясь дать точное определение этому последнему утверждению, объясните, почему именно так удобно понимать $\left\{ \bigcap_{m} \bigcup_{n \geq m} A_{n}\right\}$.

Покажите, что для любой константы $M>0$ найдётся достаточно большое $b$ такое, что $\mathbb {E}\left[\check{X}_{i}\right] \geq M$.

Пусть $\left\{ \check{N}(t); t \geq 0\right\}$ — считающий процесс восстановления с интервалами между восстановлениями $\left\{ \check{X}_{i}; i \geq 1\right\}$, и покажите, что для всех $t>0$ выполняется $\check{N}(t) \geq N(t)$.

Покажите, что для всех выборочных функций $N(t, \omega )$, за исключением множества вероятности 0, $N(t, \omega )/t \leq 2/M$ для всех достаточно больших $t$. Замечание: поскольку $M$ произвольно, это означает, что $\lim_{t \rightarrow \infty } N(t)/t = 0$ с вероятностью 1.

Покажите, что для любого $x>0$ выполняется $x^{m} \leq 1+x^{n}$.

Покажите, что для любой случайной величины $X$, если $\mathbb {E}\left[\left|X^{n}\right|\right]<\infty$, то $\mathbb {E}\left[\left|X^{m}\right|\right] \leq 1+\mathbb {E}\left[\left|X^{n}\right|\right]$.

среднее по времени значение $Y(t)$;

среднее по времени значение $Y^{2}(t)$ (т.е. $\lim_{T \rightarrow \infty }(1/T) \int_{0}^{T} Y^{2}(t) \, dt$).

Покажите, что последовательность моментов времени $S_{1}, S_{2}, \ldots$, в которые последовательные успешные клиенты поступают на обслуживание, являются моментами восстановления процесса восстановления. Покажите, что каждый интервал между восстановлениями $X_{i} = S_{i}-S_{i-1}$ (где $S_{0} = 0$) является суммой двух независимых с.в., $Y_{i}+U_{i}$, где $Y_{i}$ — $i$-е время обслуживания; найдите плотность вероятности $U_{i}$.

Пусть за каждого отвергнутого клиента начисляется вознаграждение (в данном случае фактически издержка) в размере одной единицы. Изобразите функцию ожидаемого вознаграждения как функцию времени для выборочной функции интервалов между восстановлениями и интервалов обслуживания, показанной ниже; ожидание берётся по тем (не показанным) прибытиям клиентов, которые должны быть отвергнуты. {#fig-1 width="70%"}

Пусть $\int_{0}^{t} R(\tau ) \, d\tau$ обозначает накопленное вознаграждение (т.е. издержку) от 0 до $t$, и найдите предел при $t \rightarrow \infty$ величины $(1/t) \int_{0}^{t} R(\tau ) \, d\tau$. Объясните (без попытки строгого или формального доказательства), почему этот предел существует с вероятностью 1.

В пределе больших $t$ найдите ожидаемое вознаграждение от момента времени $t$ до следующего восстановления. Указание: изобразите это ожидаемое вознаграждение как функцию $t$ для заданной выборки интервалов между восстановлениями и интервалов обслуживания; затем найдите среднее по времени.

Теперь предположим, что прибытия детерминированы, причём первое прибытие происходит в момент времени 0, а $n$-е прибытие — в момент времени $n-1$. Составляет ли по-прежнему последовательность моментов времени $S_{1}, S_{2}, \ldots$, в которые последующие клиенты начинают обслуживание, моменты восстановления процесса восстановления? Нарисуйте схему прибытий, уходов и интервалов обслуживания. Снова найдите $\lim_{t \rightarrow \infty }\left(\int_{0}^{t} R(\tau ) \, d\tau \right)/t$.

$\mathbb {P}\left(Y(t)>x \mid Z(t) = s\right)$;

$\mathbb {P}\left(Y(t)>x \mid Z(t+x/2) = s\right)$;

$\mathbb {P}\left(Y(t)>x \mid Z(t+x)>s\right)$ для пуассоновского процесса.

Пусть $J$ — правило остановки, а $\mathbb {I}_{\left\{ J \geq n\right\} }$ — индикаторная св события $\left\{ J \geq n\right\}$. Покажите, что $J = \sum_{n \geq 1} \mathbb {I}_{\left\{ J \geq n\right\} }$.

Покажите, что $\mathbb {I}_{\left\{ J \geq 1\right\} } \geq \mathbb {I}_{\left\{ J \geq 2\right\} } \geq \ldots$, т.е. покажите, что для каждого $n \geq 1$ $\mathbb {I}_{\left\{ J \geq n\right\} }(\omega ) \geq \mathbb {I}_{\left\{ J \geq n+1\right\} }(\omega )$ для каждого $\omega \in \Omega$ (за возможным исключением множества вероятности 0).

Используя равенство Вальда, вычислите ожидаемое число испытаний бернуллиевского процесса вплоть до и включая $k$-й успех.

Используя элементарные методы, найдите ожидаемое число испытаний вплоть до и включая первый успех. Используйте это, чтобы найти ожидаемое число испытаний вплоть до и включая $k$-й успех. Сравните с (а).

Пусть $J$ — число игр до того момента, когда игрок теряет все свои деньги. Достаточно ли слабого закона больших чисел, чтобы утверждать, что $\lim_{n \rightarrow \infty } \mathbb {P}\left(J>n\right) = 0$ (т.е. что $J$ — случайная величина), или необходим усиленный закон?

Найдите $\mathbb {E}\left[J\right]$.

Является ли $J$ моментом остановки? Почему да или почему нет?

Какие значения может принимать $S_{J}$?

Найдите выражение для $\mathbb {E}\left[S_{J}\right]$ через $p$, $a$ и $b$, где $p = \mathbb {P}\left(S_{J} \geq a\right)$.

Найдите выражение для $\mathbb {E}\left[S_{J}\right]$ из равенства Вальда. Используйте это, чтобы найти $p$.

Пусть $Z_{n} = \sum_{i=1}^{n}(X_{i}-V_{i-1})$, и пусть $I_{n}$ — сумма интервалов между 0 и $S_{n} = \sum_{i=1}^{n} X_{i}$, в течение которых сервер простаивает. Покажите, что $I_{n} \geq Z_{n}$, и объясните разницу между ними. Покажите, что если поступление $n$ застаёт систему пустой, то $I_{n} = Z_{n}$.

Предположим, что распределение интервалов между поступлениями ограничено в том смысле, что для некоторого $b<\infty$ выполняется $\mathbb {P}\left(X>b\right) = 0$. Покажите, что длительность каждого периода простоя для очереди G/G/1 не превышает $b$.

Покажите, что число интервалов простоя сервера до момента $S_{n}$ не меньше $Z_{n}/b$. Покажите, что число обновлений до момента $S_{n}$ ($N^{r}(S_{n})$), при которых поступление застаёт систему пустой, не меньше $(Z_{n}/b)$.

Покажите, что считающий процесс обновлений удовлетворяет соотношению $\lim_{t \rightarrow \infty } N^{r}(t)/t = a$ с вероятностью 1 для некоторого $a>0$. Покажите, что среднее число поступлений на одно поступление в пустую систему равно $1/a<\infty$.

Предположим всё вышеперечисленное, за исключением предположения, что $\mathbb {P}\left(X>b\right) = 0$ для некоторого $b$. Используйте метод усечения для $X$, чтобы установить (г) для этого нового случая.

Используйте тождество Вальда, чтобы найти $\mathbb {E}\left[T\right]$.

Вычислите $\mathbb {E}\left[\sum_{i=1}^{J} X_{i} \mid J = n\right]$ и покажите, что оно не равно $\mathbb {E}\left[\sum_{i=1}^{n} X_{i}\right]$.

Используйте (б) для второго вывода $\mathbb {E}\left[T\right]$.

Найдите $\mathbb {E}\left[T\right]$, если компания сообщает очередным программистам, какие подходы уже были безуспешно испробованы ранее.

Рассмотрим процесс восстановления, для которого интервалы между восстановлениями имеют ПМР $\mathsf{p}_{X}(1) = \mathsf{p}_{X}(2) = 1/2$. Пусть $m(t) = \mathbb {E}\left[N(t)\right]$; используя элементарную комбинаторику, покажите, что $m(1) = 1/2$, $m(2) = 5/4$ и $m(3) = 15/8$.

Элементарными средствами покажите, что $\mathbb {E}\left[S_{N(1)}\right] = 1/2$ и $\mathbb {E}\left[S_{N(1)+1}\right] = 9/4$. Проверьте (5.37) в этом случае (т.е. при $t = 1$) и покажите, почему $N(1)$ не является моментом остановки. Отметьте также, что математическое ожидание длительности $\mathbb {E}\left[S_{N(1)+1}-S_{N(1)}\right]$ не равно $\overline{X}$.

Обобщите (а) так, чтобы $\mathbb {P}\left(X = 1\right) = 1-p$ и $\mathbb {P}\left(X = 2\right) = p$. Пусть $W_{n} = N(n)-N(n-1)$, т.е. $W_{n}$ равно 1, если в момент времени $n$ происходит поступление, и равно 0, если поступления в момент $n$ не происходит. Покажите, что $\overline{W}_{n}$ удовлетворяет разностному уравнению $\overline{W}_{n} = 1-p \overline{W}_{n-1}$ при $n \geq 1$, где по соглашению $\overline{W}_{0} = 1$. Используя это, покажите, что

Отсюда найдите $m(n)$ при $n \geq 1$ и проверьте результат из (а).

Нарисуйте типичную выборочную функцию процесса $\left\{ N(t); t>0\right\}$. Заметьте, что $N(0)$ может быть отлично от нуля (т.е. $N(0)$ — это число нулевых интервалов между поступлениями, произошедших до первого ненулевого интервала между поступлениями).

Вычислите $\mathbb {E}\left[N(t)\right]$ как функцию от $t$.

Нарисуйте $\mathbb {E}\left[N(t)\right]/t$ как функцию от $t$.

Вычислите $\mathbb {E}\left[S_{N(t)+1}\right]$ как функцию от $t$ (сделайте это напрямую, а затем используйте равенство Вальда в качестве проверки).

Нарисуйте нижнюю границу $\mathbb {E}\left[N(t)\right]/t \geq 1/\mathbb {E}\left[X\right]-1/t$ на том же графике, что и в (в).

Нарисуйте $\mathbb {E}\left[S_{N(t)+1}-t\right]$ как функцию от $t$ и найдите среднее по времени этой величины.

Вычислите $\mathbb {E}\left[S_{N(t)}\right]$ как функцию от $t$; убедитесь, что $\mathbb {E}\left[S_{N(t)}\right] \neq \mathbb {E}\left[X\right] \mathbb {E}\left[N(t)\right]$.

Для всех $x>0$ и $t>x$ покажите, что $\mathbb {E}\left[N(t) \mid X_{1} = x\right] = \mathbb {E}\left[N(t-x)\right]+1$.

Используя (а), покажите, что $m(t) = \mathsf{F}_{X}(t)+\int_{0}^{t} m(t-x) \, d\mathsf{F}_{X}(x)$ при $t>0$. Это уравнение является уравнением восстановления, выведенным иным способом в (5.55).

Предположим, что $X$ — экспоненциальная случайная величина с параметром $\lambda$. Вычислите $L_{m}(s)$ из (5.57); убедитесь, что обратное преобразование Лапласа равно $\lambda t$; $t \geq 0$.

Пусть интервал между обновлениями процесса восстановления имеет плотность Эрланга второго порядка, $\mathsf{f}_{X}(x) = \lambda^{2} x \exp (-\lambda x)$. Найдите преобразование Лапласа для $m(t) = \mathbb {E}\left[N(t)\right]$.

Используя это, найдите $m(t)$ для $t \geq 0$. Убедитесь, что ваш ответ согласуется с (5.59).

Найдите наклон $m(t)$ при $t = 0$ и объясните, почему этот наклон не является неожиданным.

Рассмотрите обновления здесь как чётные по номеру приходы в пуассоновском процессе интенсивности $\lambda$. Изобразите $m(t)$ для данного процесса и покажите на том же рисунке половину ожидаемого числа приходов для пуассоновского процесса. Объясните разницу между ними.

Пусть $N(t)$ — число приходов на интервале $(0, t]$ для пуассоновского процесса интенсивности $\lambda$. Покажите, что вероятность того, что $N(t)$ чётно, равна $[1+\exp (-2 \lambda t)]/2$.

Пусть $\widetilde{N}(t)$ — число чётных по номеру приходов на $(0, t]$. Покажите, что $\widetilde{N}(t) = N(t)/2-\mathbb {I}_{\mathrm{odd}}(t)/2$, где $\mathbb {I}_{\mathrm{odd}}(t)$ — случайная величина, равная 1, если $N(t)$ нечётно, и 0 в противном случае.

Используя (а) и (б), найдите $\mathbb {E}\left[\widetilde{N}(t)\right]$. Заметьте, что это есть $m(t)$ для процесса восстановления с эрланговскими интервалами между обновлениями второго порядка.

Рассмотрим функцию $r(z) \geq 0$, определённую следующим образом для $0 \leq z<\infty$: для каждого целого $n \geq 1$ и каждого целого $k, 1 \leq k<n$, $r(z) = 1$ при $n+k/n \leq z \leq n+k/n+2^{-n}$. Для всех остальных $z$ $r(z) = 0$. Изобразите эту функцию и покажите, что $r(z)$ не является непосредственно риманово интегрируемой.

Найдите интеграл Римана $\int_{0}^{\infty } r(z) \, dz$.

Предположим, что $r(z)$ убывает, т.е. $r(z) \geq r(y)$ для всех $y>z>0$. Покажите, что если $r(z)$ риманово интегрируема, то она также непосредственно риманово интегрируема.

Предположим, что $f(z) \geq 0$, определённая для $z \geq 0$, убывает и риманово интегрируема, и что $f(z) \geq r(z)$ для всех $z \geq 0$. Покажите, что $r(z)$ непосредственно риманово интегрируема.

Пусть $X$ — неотрицательная случайная величина, для которой $\mathbb {E}\left[X^{2}\right]<\infty$. Покажите, что $x \mathsf{F}_{X}^{c}(x)$ непосредственно риманово интегрируема.

$\mathsf{f}_{Y(t)}(y \mid Z(t+s/2) = s)$ при заданном $s>0$;

$\mathsf{f}_{Y(t), Z(t)}(y, z)$;

$\mathsf{f}_{Y(t) \mid \widetilde{X}(t)}(y \mid x)$;

$\mathsf{f}_{Z(t) \mid Y(t-s/2)}(z \mid s)$ при заданном $s>0$;

$\mathsf{f}_{Y(t)}(y \mid Z(t+s/2) \geq s)$ при заданном $s>0$.

Найдите $\lim_{t \rightarrow \infty }\left\{ \mathbb {E}\left[N(t)\right]-t/\overline{X}\right\}$ для процесса восстановления $\left\{ N(t); t>0\right\}$ с временами между восстановлениями $\left\{ X_{i}; i \geq 1\right\}$.

Вычислите ваш результат для случая, когда $X$ — экспоненциальная случайная величина (вы уже знаете, каким должен быть результат в этом случае).

Вычислите ваш результат для случая, когда $\mathbb {E}\left[X\right]<\infty$ и $\mathbb {E}\left[X^{2}\right] = \infty$. Объясните (очень кратко), почему это не противоречит элементарной теореме восстановления.

Нарисуйте эскиз реализации функции $R(t)$.

Если известно, что первый автобус прибывает в момент времени $X_{1} = x$, найдите ожидаемое число забранных клиентов; затем найдите $\mathbb {E}\left[\int_{0}^{x} R(t) \, dt\right]$, снова при условии, что первый автобус прибывает в момент $X_{1} = x$.

Найдите $\lim_{t \rightarrow \infty } \frac{1}{t} \int_{0}^{t} R(\tau ) \, d\tau$ (с вероятностью 1). Предполагая, что $\mathsf{F}_{X}$ — неарифметическое распределение, найдите $\lim_{t \rightarrow \infty } \mathbb {E}\left[R(t)\right]$. Дайте интерпретацию смысла этих величин.

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

Найдите долю времени, в течение которого на автобусной остановке нет клиентов. (Подсказка: эта часть не зависит от (а), (б) и (в); проверьте свой ответ при $\mathbb {E}\left[X\right] \ll 1/\lambda$.)

Является ли $N_{A}(t)$ процессом восстановления? Объясните свой ответ, и если вы не уверены, рассмотрите несколько примеров для $N_{2}(t)$.

Найдите $\lim_{t \rightarrow \infty } \frac{1}{t} N_{A}(t)$ и объясните, почему этот предел существует с вероятностью 1. Указание: используйте симметрию — т.е. рассмотрите $N_{1}(t)-N_{A}(t)$. Чтобы показать, почему предел существует, используйте теорему о вознаграждении при восстановлении. Какой процесс восстановления следует использовать здесь?

Теперь предположим, что $\left\{ N_{1}(t); t>0\right\}$ — неарифметический процесс восстановления, но не пуассоновский, и пусть математическое ожидание интервала между восстановлениями равно $1/\lambda$. Для заданного $\delta$ найдите $\lim_{t \rightarrow \infty } \mathbb {E}\left[N_{A}(t+\delta )-N_{A}(t)\right]$ и объясните свои рассуждения. Почему рассуждение из пункта (б) не позволяет продемонстрировать среднее по времени в этом случае?

Найдите долю времени, в течение которого система пуста, как функцию от $\lambda$ и $\mathbb {E}\left[Z\right]$. Тщательно сформулируйте, что вы понимаете под такой долей.

Примените теорему Литтла не ко всей системе целиком, а к числу клиентов на сервере (т.е. 0 или 1). Используйте это, чтобы найти долю времени, в течение которого сервер занят.

Объедините результаты пунктов (а) и (б), чтобы найти $\mathbb {E}\left[Z\right]$ через $\lambda$ и $\mathbb {E}\left[Y\right]$; приведите долю времени, в течение которого система простаивает, через $\lambda$ и $\mathbb {E}\left[Y\right]$.