Банк задач по математике

Задача 9.1

Рассмотрим простое случайное блуждание $\{ S_{n}; n \geq 1\}$ с $S_{n} = X_{1}+\cdots +X_{n}$ и $\mathbb {P}\left(X_{i} = 1\right) = p$ , $\mathbb {P}\left(X_{i} = -1\right) = 1-p$ ; предположим, что $p \leq 1/2$ .

?

(a)

Покажите, что $\mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq k\right\} \right) = \left[\mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq 1\right\} \right)\right]^{k}$ для любого положительного целого $k$ .

(b)

Найдите квадратное уравнение для $y = \mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq 1\right\} \right)$ .

(c)

Для $p<1/2$ покажите, что два корня этого квадратного уравнения равны $p/(1-p)$ и $1$ . Покажите, что $\mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq 1\right\} \right)$ не может быть равно $1$ и, следовательно, должно быть равно $p/(1-p)$ .

(d)

Для $p = 1/2$ покажите, что квадратное уравнение из (в) имеет двойной корень в точке $1$ , и, таким образом, $\mathbb {P}\left(\bigcup_{n \geq 1} \left\{ S_{n} \geq 1\right\} \right) = 1$ .

(e)

Пусть $r^{*}$ — единственный положительный корень уравнения $\mathsf{g}(r) = 1$ , где $\mathsf{g}(r) = \mathbb {E}\left[e^{rX}\right]$ . Покажите, что $p/(1-p) = \exp (-r^{*})$ .

Задача 9.2

(a)(b)(c)(d)

Рассмотрим систему массового обслуживания G/G/1 с н.о.р. интервалами между поступлениями $\{ X_{i}; i \geq 1\}$ , н.о.р. временами обслуживания в порядке поступления (FCFS) $\{ Y_{i}; i \geq 0\}$ и первым поступлением в пустую систему в момент времени $0$ . Определим $U_{i} = X_{i}-Y_{i-1}$ для $i \geq 1$ . Рассмотрим траекторию, для которой $(u_{1}, \ldots , u_{6}) = (1, -2, 2, -1, 3, -2)$ .

?

(a)

Пусть $Z_{i}^{6} = U_{6}+U_{6-1}+\cdots +U_{6-i+1}$ . Найдите время ожидания в очереди для клиента $6$ как максимум «обратного» случайного блуждания с элементами $0, Z_{1}^{6}, Z_{2}^{6}, \ldots , Z_{6}^{6}$ ; нарисуйте это случайное блуждание.

(b)

Найдите время ожидания в очереди для клиентов с $1$ по $5$ .

(c)

Какие клиенты начинают период занятости (т.е. поступают, когда очередь и обслуживающее устройство пусты)? Проверьте, что если $Z_{i}^{6}$ максимизирует случайное блуждание в (а), то период занятости начинается с поступления $6-i$ .

(d)

Теперь рассмотрим прямое случайное блуждание $V_{n} = U_{1}+\cdots +U_{n}$ . Нарисуйте это блуждание для приведённой выше траектории и покажите, что время ожидания в очереди для каждого клиента равно разности двух соответствующим образом выбранных значений этого блуждания.

Задача 9.3

(a)(b)(c)

Система массового обслуживания G/G/1 имеет детерминированное время обслуживания $2$ и интервалы между поступлениями, равные $3$ с вероятностью $p<1/2$ и $1$ с вероятностью $1-p$ .

?

(a)

Найдите распределение $W_{1}$ — времени ожидания в очереди первого поступления после начала периода занятости.

(b)

Найдите распределение $W_{\infty }$ — стационарного времени ожидания в очереди.

(c)

Повторите (а) и (б), предполагая, что времена обслуживания и интервалы между поступлениями имеют экспоненциальное распределение с параметрами $\mu$ и $\lambda$ соответственно.

Задача 9.4

Пусть $U = V_{1}+\cdots +V_{n}$ , где $V_{1}, \ldots , V_{n}$ — независимые одинаково распределённые случайные величины с МПФ $\mathsf{g}_{V}(s)$ . Покажите, что $\mathsf{g}_{U}(s) = \left[\mathsf{g}_{V}(s)\right]^{n}$ .

?

Задача 9.5

(a)(b)(c)

Пусть $\{ a_{n}; n \geq 1\}$ и $\{ \alpha_{n}; n \geq 1\}$ — последовательности чисел. Предположим, что для некоторого $b$ выполняется $a_{n} \leq \alpha_{n} e^{-bn}$ для всех $n \geq 1$ . Для каждого из следующих вариантов $\alpha_{n}$ и произвольного $b$ определите, является ли оценка экспоненциально точной. При желании можете считать, что $b \geq 0$ , но это на самом деле не имеет значения.

?

(a)

$\alpha_{n} = \sum_{j=1}^{k} c_{j} n^{-j}$ .

(b)

$\alpha_{n} = \exp (-\sqrt{n})$ .

(c)

$\alpha_{n} = e^{-n^{2}}$ .

Смысл этого упражнения в том, чтобы понять, что экспоненциально точная оценка не обязательно является разумным приближением при больших $n$ . Она предназначена для последовательностей, которые по существу экспоненциально убывают по $n$ , и в случаях, когда достаточно знать показатель экспоненты, не заботясь о неэкспоненциальных коэффициентах.

Задача 9.6

Определим $\gamma (r)$ как $\ln \left[\mathsf{g}(r)\right]$ , где $\mathsf{g}(r) = \mathbb {E}\left[\exp (rX)\right]$ . Предположим, что $X$ дискретна с возможными значениями $\{ a_{i}; i \geq 1\}$ , пусть $p_{i}$ обозначает $\mathbb {P}\left(X=a_{i}\right)$ , и предположим, что $\mathsf{g}(r)$ существует на некотором открытом интервале $(r_{-}, r_{+})$ , содержащем $r=0$ . Для любого заданного $r$ , $r_{-}<r<r_{+}$ , определим случайную величину $X_{r}$ с тем же множеством возможных значений $\{ a_{i}; i \geq 1\}$ , что и у $X$ , но с ФРВ $q_{i} = \mathbb {P}\left(X_{r}=a_{i}\right) = p_{i} \exp \left[a_{i} r-\gamma (r)\right]$ . Заметим, что $X_{r}$ не является функцией от $X$ и её даже не следует рассматривать как заданную на том же вероятностном пространстве, что и $X$ ; она представляет интерес просто в силу поведения её заданной функции вероятностей. Она называется наклонённой (tilted) случайной величиной относительно $X$ , и это упражнение вместе с упражнением 9.11 обоснует наш интерес к ней.

?

(a)

Проверьте, что $\sum_{i} q_{i} = 1$ .

(b)

Проверьте, что $\mathbb {E}\left[X_{r}\right] = \sum_{i} a_{i} q_{i}$ равно $\gamma '(r)$ .

(c)

Проверьте, что $\operatorname {Var}\left[X_{r}\right] = \sum_{i} a_{i}^{2} q_{i}-(\mathbb {E}\left[X_{r}\right])^{2}$ равно $\gamma ''(r)$ .

(d)

Покажите, что $\gamma ''(r) \geq 0$ для всех $r$ , при которых $\mathsf{g}(r)$ существует, и что $\gamma ''(r)>0$ , если $\gamma ''(0)>0$ .

(e)

Дайте аналогичное определение $X_{r}$ для случайной величины $X$ с плотностью и соответствующим образом измените (а)--(г).

Задача 9.7

(a)(b)(c)(d)

?

(a)

Предположим, что $Z$ равномерно распределена на $[-b, +b]$ . Найдите $\mathsf{g}_{Z}(r)$ , $\mathsf{g}_{Z}'(r)$ и $\gamma '(r)$ как функции от $r$ .

(b)

Покажите, что интервал, на котором существует $\mathsf{g}_{Z}(r)$ , есть вся числовая прямая, т.е. $r_{+}=\infty$ и $r_{-}=-\infty$ . Покажите, что $\lim_{r \rightarrow \infty } \gamma '(r) = b$ .

(c)

Покажите, что если $a>b$ , то $\inf_{r \in I(X)} \gamma (r)-ra = -\infty$ , так что оптимизированная оценка Чернова даёт $\mathbb {P}\left(S_{n}>na\right) = 0$ . Объясните без каких-либо вычислений, почему $\mathbb {P}\left(S_{n}>na\right)=0$ должно выполняться. Объясните (используя как можно меньше математических выкладок), почему в оптимизированной оценке Чернова должен использоваться инфимум, а не минимум.

(d)

Покажите, что для произвольной случайной величины $X$ , если $r_{+}=\infty$ и $\lim_{r \rightarrow \infty } \gamma '(r) = b$ , то оптимизированная оценка Чернова даёт $\mathbb {P}\left(S_{n}>na\right)=0$ при $a>b$ .

Задача 9.8

Заметим, что МПФ неотрицательной экспоненциальной случайной величины с плотностью $e^{-x}$ равна $(1-r)^{-1}$ при $r<r_{+}=1$ . Из этого видно, что $\mathsf{g}(r_{+})$ не существует (т.е. бесконечна), и что как $\lim_{r \rightarrow r_{+}} \mathsf{g}(r) = \infty$ , так и $\lim_{r \rightarrow r_{+}} \mathsf{g}'(r) = \infty$ , где предел берётся по $r<r_{+}$ . В этом упражнении сначала предположите произвольную случайную величину $X$ , для которой $r_{+}<\infty$ и $\mathsf{g}(r_{+}) = \infty$ , и покажите, что как $\lim_{r \rightarrow r_{+}} \mathsf{g}(r) = \infty$ , так и $\lim_{r \rightarrow r_{+}} \mathsf{g}'(r) = \infty$ . Затем используйте это, чтобы показать, что если $\sup_{r<r_{+}} \mathsf{g}'(r)<\infty$ , то $\gamma (r_{+})<\infty$ и оптимизированный показатель Чернова $\mu (a)$ задаётся формулой $\mu (a) = \gamma (r_{+})-r_{+} a$ при $a>\sup_{r<r_{+}} \gamma '(r)$ .

?

(a)

Для $X$ такой, что $r_{+}<\infty$ и $\mathsf{g}(r_{+})=\infty$ , объясните, почему

\lim _{A \rightarrow \infty } \int _{0}^{A} e^{x r_{+}} \, d\mathsf{F}(x) = \infty .

(b)

Покажите, что для любого $\epsilon >0$ и любого $A>0$

\mathsf{g}(r_{+}-\epsilon ) \geq e^{-\epsilon A} \int _{0}^{A} e^{x r_{+}} \, d\mathsf{F}(x).

(c)

Выберите $A=1/\epsilon$ и покажите, что

\lim _{\epsilon \rightarrow 0} \mathsf{g}(r_{+}-\epsilon ) = \infty .

(d)

Покажите, что $\lim_{\epsilon \rightarrow 0} \mathsf{g}'(r_{+}-\epsilon ) = \infty$ .

(e)

Используя (а)--(г), покажите, что если $r_{+}<\infty$ и $\sup_{r<r_{+}} \mathsf{g}'(r)<\infty$ , то $\mathsf{g}(r_{+})<\infty$ .

(f)

Покажите, что если $r_{+}<\infty$ и $\sup_{r<r_{+}} \mathsf{g}'(r)<\infty$ , то $\mu (a) = \gamma (r_{+})-r_{+} a$ при $a>\sup_{r<r_{+}} \gamma '(r)$ .

Задача 9.9

(a)(b)(c)

?

(a)

Покажите, что два появления $\epsilon$ в экспоненциальной нижней оценке, установленной в тексте для $\mathbb {P}\left(S_{n} \geq n \gamma '(r)\right)$ , можно заменить двумя независимыми произвольными положительными величинами $\epsilon_{1}$ и $\epsilon_{2}$ , получив

\mathbb {P}\left(S_{n} \geq n(\gamma '(r)-\epsilon _{1})\right) \geq (1-\delta ) \exp \left[-n(r \gamma '(r)+r \epsilon _{2}-\gamma (r))\right].

Покажите, что если это равенство выполняется для $\epsilon_{1}$ и $\epsilon_{2}$ , то оно выполняется и для всех больших значений $\epsilon_{1}$ и $\epsilon_{2}$ .

(b)

Покажите, что, увеличив требуемое значение $n_{o}$ так, чтобы это неравенство выполнялось для всех $n \geq n_{o}$ , множитель $(1-\delta )$ можно устранить выше.

(c)

Для произвольного $r \in (0, r_{+})$ пусть $\delta_{1}$ — произвольное число из $(0, r_{+}-r)$ , пусть $r_{1} = r+\delta_{1}$ , и пусть $\epsilon_{1} = \gamma '(r_{1})-\gamma '(r)$ . Покажите, что найдётся такое $m$ , что для всех $n \geq m$

\mathbb {P}\left(S_{n} \geq n \gamma '(r)\right) \geq \exp \left\{ -n\left[(r+\delta _{1}) \gamma '(r+\delta _{1})+(r+\delta _{1}) \epsilon _{2}-\gamma (r+\delta _{1})\right]\right\} . \tag {9.164}

Используя непрерывность $\gamma$ и её производных, покажите, что для любого $\epsilon >0$ найдётся такое $\delta_{1}>0$ , что правая часть (9.164) больше либо равна $\exp \left[-n(\gamma '(r)-r \gamma (r)+\epsilon )\right]$ .

Задача 9.10

В этой задаче мы покажем, что оптимизированная граница Чернова точна для третьего случая экспоненты больших уклонений (случай $a>\sup_{r<r_{+}} \gamma '(r)$ при $r_{+}<\infty$ ), как и для первого случая. То есть мы покажем, что если $r_{+}<\infty$ и $a>\sup_{r<r_{+}} \gamma '(r)$ , то для любого $\epsilon >0$ выполняется $\mathbb {P}\left(S_{n} \geq na\right) \geq \exp \left\{ n\left[\gamma (r_{+})-r_{+} a-\epsilon \right]\right\}$ для всех достаточно больших $n$ .

?

(a)

Пусть $Y_{i}$ — усечённая версия $X_{i}$ , усечённая для некоторого заданного $b$ так, что $Y_{i}=X_{i}$ при $X_{i} \leq b$ и $Y_{i}=b$ в противном случае. Пусть $W_{n} = Y_{1}+\cdots +Y_{n}$ . Покажите, что $\mathbb {P}\left(S_{n} \geq na\right) \geq \mathbb {P}\left(W_{n} \geq na\right)$ .

(b)

Пусть $\mathsf{g}_{b}(r)$ — производящая функция моментов (МФМ) величины $Y$ . Покажите, что $\mathsf{g}_{b}(r)<\infty$ и что $\mathsf{g}_{b}(r)$ не убывает по $b$ для всех $r<\infty$ .

(c)

Покажите, что $\lim_{b \rightarrow \infty } \mathsf{g}_{b}(r) = \infty$ для всех $r>r_{+}$ и что $\lim_{b \rightarrow \infty } \mathsf{g}_{b}(r) = \mathsf{g}(r)$ для всех $r \leq r_{+}$ .

(d)

Пусть $\gamma_{b}(r) = \ln \mathsf{g}_{b}(r)$ . Покажите, что $\gamma_{b}(r)<\infty$ для всех $r<\infty$ . Также покажите, что $\lim_{b \rightarrow \infty } \gamma_{b}(r) = \infty$ при $r>r_{+}$ и $\lim_{b \rightarrow \infty } \gamma_{b}(r) = \gamma (r)$ при $r \leq r_{+}$ .

(e)

Пусть $\gamma_{b}'(r) = (\partial /\partial r) \gamma_{b}(r)$ , и пусть $\delta >0$ произвольно. Покажите, что для всех достаточно больших $b$ выполняется $\gamma_{b}'(r_{+}+\delta )>a$ .

(f)

Покажите, что оптимизированная граница Чернова для $\mathbb {P}\left(W_{n} \geq na\right)$ экспоненциально точна для значений $b$ из пункта (д). Покажите, что оптимизирующее $r$ меньше $r_{+}+\delta$ .

(g)

Покажите, что для любого $\epsilon >0$ и всех достаточно больших $b$

\gamma _{b}(r)-ra \geq \gamma (r)-ra-\epsilon \geq \gamma (r_{+})-r_{+} a-\epsilon \qquad \text{при } 0<r \leq r_{+}.

(h)

Покажите, что для произвольного $\epsilon >0$ существуют такие $\delta >0$ и $b_{o}$ , что

\gamma _{b}(r)-ra \geq \gamma (r_{+})-r_{+} a-\epsilon \qquad \text{при } r_{+}<r<r_{+}+\delta \text{ и } b \geq b_{o}.

(i)

Заметим, что если объединить (ж), (з) и (г), используя $\delta$ из (з) в (г), то мы показали, что оптимизированная экспонента в границе Чернова для $\mathbb {P}\left(W_{n} \geq na\right)$ удовлетворяет $\mu_{b}(a) \geq \gamma (r_{+})-r_{+} a-\epsilon$ для достаточно больших $b$ . Покажите, что это означает $\mathbb {P}\left(S_{n} \geq na\right) \geq \gamma (r_{+})-r_{+} a-2 \epsilon$ для достаточно больших $n$ .

Задача 9.11

(a)(b)(c)(d)

Предположим, что $X$ — дискретная случайная величина с возможными значениями $\{ a_{i}; i \geq 1\}$ и вероятностями $\mathbb {P}\left(X=a_{i}\right) = p_{i}$ . Пусть $X_{r}$ — соответствующая наклонённая (tilted) случайная величина, определённая в упражнении 9.6. Пусть $S_{n} = X_{1}+\cdots +X_{n}$ — сумма $n$ н.о.р. случайных величин с распределением $X$ , и пусть $S_{n,r} = X_{1,r}+\cdots +X_{n,r}$ — сумма $n$ н.о.р. наклонённых случайных величин с распределением $X_{r}$ . Предположим, что $\overline{X}<0$ и что $r>0$ таково, что $\gamma (r)$ существует.

?

(a)

Покажите, что $\mathbb {P}\left(S_{n,r}=s\right) = \mathbb {P}\left(S_{n}=s\right) \exp \left[sr-n \gamma (r)\right]$ .

(b)

Найдите математическое ожидание и дисперсию $S_{n,r}$ через $\gamma (r)$ .

(c)

Определим $a = \gamma '(r)$ и $\sigma_{r}^{2} = \gamma ''(r)$ . Покажите, что $\mathbb {P}\left(\left|S_{n,r}-na\right| \leq \sqrt{2n} \sigma_{r}\right)>1/2$ . Используйте это, чтобы показать, что

\mathbb {P}\left(\left|S_{n}-na\right| \leq \sqrt{2n} \sigma _{r}\right) > (1/2) \exp \left[-r(an+\sqrt{2n} \sigma _{r})+n \gamma (r)\right].

(d)

Используйте это, чтобы показать, что для любого $\epsilon$ и для всех достаточно больших $n$

\mathbb {P}\left(S_{n} \geq n(\gamma '(r)-\epsilon )\right) > \frac{1}{2} \exp \left[-rn(\gamma '(r)+\epsilon )+n \gamma (r)\right].

Задача 9.12

(a)(b)(c)

Пусть $\overrightarrow {p} = (p_{1}, \ldots , p_{\mathsf{M}})$ и $\overrightarrow {\tilde{p}} = (\tilde{p}_{1}, \ldots , \tilde{p}_{\mathsf{M}})$ — строго положительные вероятностные векторы. Дивергенция Кульбака--Лейблера между $\overrightarrow {\tilde{p}}$ и $\overrightarrow {p}$ определяется как

D(\overrightarrow {\tilde{p}} \| \overrightarrow {p}) = \sum _{j} \tilde{p}_{j} \ln \left(\frac{\tilde{p}_{j}}{p_{j}}\right).

?

(a)

Покажите, что дивергенция $D(\overrightarrow {\tilde{p}} \| \overrightarrow {p}) \geq 0$ и равна $0$ , если $\overrightarrow {\tilde{p}} = \overrightarrow {p}$ .

(b)

Пусть $\overrightarrow {u} = u_{1}, \ldots , u_{\mathsf{M}}$ удовлетворяет условию $\sum_{j} u_{j} = 0$ ; покажите, что $\overrightarrow {\tilde{p}} + \epsilon \overrightarrow {u}$ является вероятностным вектором в достаточно малой окрестности $\epsilon$ вокруг $0$ . Покажите, что

\frac{\partial }{\partial \epsilon } D(\overrightarrow {\tilde{p}} + \epsilon \overrightarrow {u} \| \overrightarrow {p})\Big|_{\epsilon = 0} = 0.

(c)

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

\frac{\partial ^{2}}{\partial \epsilon ^{2}} D(\overrightarrow {\tilde{p}} + \epsilon \overrightarrow {u} \| \overrightarrow {p}) \geq 0,

где $\overrightarrow {\tilde{p}} + \epsilon \overrightarrow {u}$ — вероятностный вектор с ненулевыми компонентами. Объясните, почему из этого следует, что $D$ выпукла по $\overrightarrow {\tilde{p}}$ и неотрицательна на области вероятностных векторов.

Задача 9.13

(a)(b)(c)(d)

Рассмотрим случайное блуждание $\left\{ S_{n}; n \geq 1\right\}$ , где $S_{n} = X_{1} + \cdots + X_{n}$ и $\left\{ X_{i}; i \geq 1\right\}$ — последовательность н.о.р. экспоненциальных случайных величин с ПРВ $\mathsf{f}(x) = \lambda e^{-\lambda x}$ при $x \geq 0$ . Другими словами, это случайное блуждание представляет собой последовательность моментов поступления в пуассоновском процессе.

?

(a)

Покажите, что при $\lambda a > 1$ оптимизированная граница Чернова для $\mathbb {P}\left(S_{n} \geq na\right)$ имеет вид

\mathbb {P}\left(S_{n} \geq na\right) \leq (a \lambda )^{n} e^{-n(a \lambda - 1)}.

(b)

Покажите, что точное значение $\mathbb {P}\left(S_{n} \geq na\right)$ равно

\mathbb {P}\left(S_{n} \geq na\right) = \sum _{i=0}^{n-1} \frac{(na \lambda )^{i} e^{-na \lambda }}{i!}.

(c)

Оценивая сверху и снизу величину в правой части выше, покажите, что

\frac{(na \lambda )^{n} e^{-na \lambda }}{n! \, a \lambda } \leq \mathbb {P}\left(S_{n} \geq na\right) \leq \frac{(na \lambda )^{n} e^{-na \lambda }}{n! (a \lambda - 1)}.

(d)

Используя оценки Стирлинга для $n!$ , покажите, что

\frac{(a \lambda )^{n} e^{-n(a \lambda - 1)}}{\sqrt{2 \pi n} \, a \lambda \exp (1 / 12 n)} \leq \mathbb {P}\left(S_{n} \geq na\right) \leq \frac{(a \lambda )^{n} e^{-n(a \lambda - 1)}}{\sqrt{2 \pi n} \, (a \lambda - 1)}.

Примечание.

?

Смысл этого упражнения — показать, что граница Чернова не только экспоненциально точна для этого примера, но и отражает важные факторы в поведении $\mathbb {P}\left(S_{n} \geq na\right)$ .

Задача 9.14

(a)(b)

Рассмотрим случайное блуждание с порогами $\alpha > 0$ , $\beta < 0$ . Требуется найти $\mathbb {P}\left(S_{J} \geq \alpha \right)$ в отсутствие нижнего порога. Используйте верхнюю оценку $\mathbb {P}\left(S_{J} \geq \alpha \right) \leq \exp (-r^{*}\alpha )$ (формула (9.46), следствие 9.4.4) для вероятности того, что случайное блуждание пересекает $\alpha$ раньше, чем $\beta$ .

?

(a)

Считая, что случайное блуждание сначала пересекает $\beta$ , найдите верхнюю оценку вероятности того, что $\alpha$ будет пересечено раньше, чем ещё более низкий порог $2\beta$ .

(b)

Считая, что $2\beta$ пересекается раньше, чем $\alpha$ , оцените сверху вероятность того, что $\alpha$ будет пересечено раньше порога $3\beta$ . Распространив это рассуждение на последовательно понижающиеся пороги, найдите верхнюю оценку для каждого последующего слагаемого и найдите верхнюю оценку для полной вероятности того, что $\alpha$ будет пересечено. Заметив, что $\beta$ произвольно, покажите, что (9.46) справедливо и при отсутствии нижнего порога.

Задача 9.15

(a)(b)(c)

Это упражнение проверяет, что следствие 9.4.4 выполняется в ситуации, когда $\gamma (r_{+}) < 0$ . Мы определили $r^{*} = r_{+}$ в этом случае.

?

(a)

Используя тождество Вальда при $r = r_{+}$ , покажите, что

\mathbb {P}\left(S_{J} \geq \alpha \right)\mathbb {E}\left[\exp (r_{+}S_{J} - J\gamma (r_{+})) \mid S_{J} \geq \alpha \right] \leq 1.

(b)

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

\mathbb {P}\left(S_{J} \geq \alpha \right)\exp \left[r_{+}\alpha - \gamma (r_{+})\right] \leq 1.

(c)

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

\mathbb {P}\left(S_{J} \geq \alpha \right) \leq \exp \left[-r_{+}\alpha + \gamma (r_{+})\right] \qquad \text{и} \qquad \mathbb {P}\left(S_{J} \geq \alpha \right) \leq \exp \left[-r^{*}\alpha \right].

Примечание.

?

Заметим, что первая из приведённых выше оценок немного сильнее второй, и заметим, что оценка снизу для $J$ значением $1$ не обязательно является очень слабой оценкой, поскольку это именно тот случай, когда, если $\alpha$ пересекается, оно, как правило, пересекается при малых $J$ .

Задача 9.16

(a)(b)(c)(d)

?

(a)

Используя равенство Вальда, покажите, что если $\overline{X} = 0$ , то $\mathbb {E}\left[S_{J}\right] = 0$ , где $J$ — момент пересечения порога при одном пороге $\alpha > 0$ и другом $\beta < 0$ .

(b)

Получите выражение для $\mathbb {P}\left(S_{J} \geq \alpha \right)$ . Ваше выражение должно включать математическое ожидание $S_{J}$ при условии пересечения соответствующих порогов (вычислять эти математические ожидания не требуется).

(c)

Вычислите ваше выражение для случая простого случайного блуждания.

(d)

Вычислите ваше выражение, когда $X$ имеет экспоненциальную плотность $\mathsf{f}_{X}(x) = a_{1}e^{-\lambda x}$ при $x \geq 0$ и $\mathsf{f}_{X}(x) = a_{2}e^{\mu x}$ при $x < 0$ , где $a_{1}$ и $a_{2}$ выбраны так, что $\overline{X} = 0$ .

Задача 9.17

(a)(b)(c)

Случайное блуждание $\left\{ S_{n}; n \geq 1\right\}$ , где $S_{n} = \sum_{i=1}^{n} X_{i}$ , имеет для $X_{i}$ следующую плотность вероятности:

\mathsf{f}_{X}(x) = \begin{cases} \dfrac {e^{-x}}{e - e^{-1}}, & -1 \leq x \leq 1, \\ 0, & \text{иначе.} \end{cases}

?

(a)

Найдите значения $r$ , при которых $\mathsf{g}(r) = \mathbb {E}\left[\exp (rX)\right] = 1$ .

(b)

Пусть $P_{\alpha }$ — вероятность того, что случайное блуждание когда-либо пересечёт порог $\alpha$ для некоторого $\alpha > 0$ . Найдите верхнюю оценку для $P_{\alpha }$ вида $P_{\alpha } \leq e^{-\alpha A}$ , где $A$ — константа, не зависящая от $\alpha$ ; вычислите $A$ .

(c)

Найдите нижнюю оценку для $P_{\alpha }$ вида $P_{\alpha } \geq Be^{-\alpha A}$ , где $A$ то же, что и в (б), а $B$ — константа, не зависящая от $\alpha$ .

Задача 9.18

(a)(b)(c)

Пусть $\left\{ X_{n}; n \geq 1\right\}$ — последовательность н.о.р. целочисленных с.в. с ПМВ $\mathsf{p}_{X}(k) = Q_{k}$ . Предположим, что $Q_{k} > 0$ при $\left|k\right| \leq 10$ и $Q_{k} = 0$ при $\left|k\right| > 10$ . Пусть $\left\{ S_{n}; n \geq 1\right\}$ — случайное блуждание с $S_{n} = X_{1} + \cdots + X_{n}$ . Пусть $\alpha > 0$ и $\beta < 0$ — целочисленные пороги, пусть $J$ — наименьшее значение $n$ , при котором либо $S_{n} \geq \alpha$ , либо $S_{n} \leq \beta$ . Пусть $\left\{ S_{n}^{*}; n \geq 1\right\}$ — остановленное случайное блуждание, т.е. $S_{n}^{*} = S_{n}$ при $n \leq J$ и $S_{n}^{*} = S_{J}$ при $n > J$ . Пусть $\pi_{i}^{*} = \mathbb {P}\left(S_{J} = i\right)$ .

?

(a)

Рассмотрим марковскую цепь, в которой это остановленное случайное блуждание запускается повторно до момента остановки. То есть переходные вероятности марковской цепи заданы как $P_{ij} = Q_{j-i}$ при $\beta < i < \alpha$ и $P_{i0} = 1$ при $i \leq \beta$ и $i \geq \alpha$ . Все остальные переходные вероятности равны $0$ , а множество состояний — это множество целых чисел $[-9+\beta , 9+\alpha ]$ . Покажите, что эта марковская цепь эргодична.

(b)

Пусть $\left\{ \pi_{i}\right\}$ — множество стационарных вероятностей этой марковской цепи. Найдите множество вероятностей $\left\{ \pi_{i}^{*}\right\}$ для останавливающих состояний остановленного случайного блуждания через $\left\{ \pi_{i}\right\}$ .

(c)

Найдите $\mathbb {E}\left[S_{J}\right]$ и $\mathbb {E}\left[J\right]$ через $\left\{ \pi_{i}\right\}$ .

Задача 9.19

(a)(b)

Рассмотрим следующую задачу проверки бинарной гипотезы: имеются две гипотезы $X=0, X=1$ , и при каждой гипотезе н.о.р. наблюдения $Y_{1}, \ldots , Y_{n}$ берутся с условной плотностью $\mathsf{f}_{Y|X}(y \mid 0)$ или $\mathsf{f}_{Y|X}(y \mid 1)$ соответственно.

?

(a)

При условии $X = 0$ для этой задачи проверки гипотез рассмотрим с.в. $Z_{i} = \ln \left[\mathsf{f}(y_{i} \mid X=1)/\mathsf{f}(y_{i} \mid X=0)\right]$ . Покажите, что $r^{*}$ — положительное решение уравнения $\mathsf{g}(r) = 1$ , где $\mathsf{g}(r) = \mathbb {E}\left[\exp (rZ_{i})\right]$ , — равно $r^{*} = 1$ .

(b)

Предполагая, что $Y$ — дискретная с.в. (при каждой гипотезе), покажите, что наклонённая (tilted) с.в. $Z_{r}$ при $r = 1$ имеет ПМВ $\mathsf{p}_{Y}(y \mid X=1)$ .

Задача 9.20

(a)(b)(c)(d)

Вспомним оценки из теоремы 9.5.1: для порогового теста при $\eta = e^{n\gamma_{0}(r)}$ ,

\mathbb {P}\left(e(n) \mid X=0\right) \leq \exp \left(n\left[\gamma _{0}(r) - r\gamma _{0}'(r)\right]\right) \tag {9.61}

и

\mathbb {P}\left(e(n) \mid X=1\right) \leq \exp \left(n\left[\gamma _{0}(r) + (1-r)\gamma _{0}'(r)\right]\right), \tag {9.62}

где $\gamma_{0}(r)$ — полуинвариантная производящая функция моментов логарифмического отношения правдоподобия $Z$ при условии $X = 0$ .

?

(a)

Используя разложение в степенной ряд в окрестности $r = 0$ , покажите, что $\gamma_{0}(r) - r\gamma_{0}'(r) = -r^{2}\gamma_{0}''(0)/2 + o(r^{2})$ .

(b)

Выберите $r = n^{-1/3}$ в (9.61) и (9.62). Покажите, что (9.61) тогда можно переписать в виде

\begin{aligned} \mathbb {P}\left(e(n) \mid X=0\right) & \leq \exp \left\{ n\left[-r^{2}\gamma _{0}''(0)/2 + o(r^{2})\right]\right\} \\ & = \exp \left\{ -n^{1/3}\gamma _{0}''(0)/2 + o(n^{1/3})\right\} . \end{aligned}

Таким образом, $\mathbb {P}\left(e(n) \mid X=0\right)$ стремится к $0$ с ростом $n$ экспоненциально по $n^{1/3}$ .

(c)

Используя то же разложение в степенной ряд по $r$ в (9.62), покажите, что

\begin{aligned} \mathbb {P}\left(e(n) \mid X=1\right) & \leq \exp \left\{ n\left[r^{2}\gamma _{0}''(0)/2 + \gamma _{0}'(0) + o(r)\right]\right\} \\ & = \exp \left\{ n\gamma _{0}'(0) + o(n^{2/3})\right\} . \end{aligned}

Таким образом, $\lim_{n}(1/n)\ln \mathbb {P}\left(e(n) \mid X=1\right) = \gamma_{0}'(0) = \mathbb {E}\left[Z \mid X=0\right]$ .

(d)

Объясните, почему оценка (9.62) экспоненциально точна, учитывая, что $\mathbb {P}\left(e(n) \mid X=0\right) \rightarrow 0$ при $n \rightarrow \infty$ .

Задача 9.21

(a)(b)(c)(d)

Эта задача иллюстрирует совершенно иной тип последовательной задачи принятия решений, чем задачи раздела 9.5. Алиса ищет супруга и последовательно, по одному в неделю, встречается с $n$ претендентами. Для простоты предположим, что Алиса должна принять решение о согласии на брак с претендентом сразу после встречи с ним; она не может впоследствии вернуться и принять предложение ранее отклонённого претендента. Её решение должно основываться только на том, является ли текущий претендент более подходящим, чем все предыдущие. Математически можно рассматривать процесс встреч как продолжающийся все $n$ недель, но выбор на неделе $m$ представляет собой правило остановки. Предположим, что пригодность каждого претендента представлена вещественным числом и что все $n$ чисел различны. Алиса не наблюдает сами числа пригодности, а лишь узнаёт в каждый момент времени $m$ , является ли претендент $m$ наиболее подходящим из всех, встреченных до сих пор. Претенденты подвергаются случайной перестановке до того, как Алиса начинает с ними встречаться.

?

(a)

Разумный алгоритм для Алисы состоит в том, чтобы отклонить первых $k$ претендентов (значение $k$ будет оптимизировано позже), а затем выбрать первого претендента $m > k$ , который окажется более подходящим, чем все предыдущие $m - 1$ претендентов. Найдите вероятность $q_{k}$ того, что Алиса выберет наиболее подходящего из всех $n$ претендентов, используя этот алгоритм при заданном $k$ .

(b)

Приближая $\sum_{i=1}^{j} 1/i$ величиной $\ln j$ , покажите, что при больших $n$ и $k$

q_{k} \approx \frac{k}{n}\ln (n/k).

Игнорируя ограничение целочисленности $n$ и $k$ , покажите, что правая часть выражения выше максимизируется при $k/n = e$ и что $\max_{k} q_{k} \approx 1/e$ .

(c)

(Необязательно) Покажите, что алгоритм из пункта (а), оптимизированный по $k$ , является оптимальным среди всех алгоритмов (при заданных ограничениях задачи). Пусть $p_{m}$ — максимальная вероятность выбора оптимального претендента при условии, что до момента времени $m$ выбор ещё не сделан. Покажите, что

p_{m} = \max \left[\frac{1}{n} + \frac{m-1}{m}p_{m+1}, \; p_{m+1}\right];

часть задачи здесь состоит в том, чтобы точно понять, что означает $p_{m}$ .

(d)

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

Примечание.

?

Примечание: если алгоритм в пункте (а) не выбирает ни одного претендента, не имеет значения, будет ли в итоге выбран претендент $n$ или не выбран никто.

Задача 9.22

(a)(b)

?

(a)

Пусть $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал. Проверьте, что

\mathbb {E}\left[Z_{n}\right] = \mathbb {E}\left[Z_{1}\right] \quad \text{для } n > 1. \tag {9.83}

(b)

Если $\left\{ Z_{n}; n \geq 1\right\}$ — субмартингал, проверьте, что

\mathbb {E}\left[Z_{n}\right] \geq \mathbb {E}\left[Z_{i}\right] \quad \text{для всех } i, 1 \leq i < n, \tag {9.88}

а если супермартингал, проверьте, что

\mathbb {E}\left[Z_{n}\right] \leq \mathbb {E}\left[Z_{i}\right] \quad \text{для всех } i, 1 \leq i < n. \tag {9.89}

Задача 9.23

Пусть $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал. Покажите, что

\mathbb {E}\left[Z_{m} \mid Z_{n_{i}}, Z_{n_{i-1}}, \ldots , Z_{n_{1}}\right] = Z_{n_{i}} \quad \text{для всех } 0 < n_{1} < n_{2} < \cdots < n_{i} < m.

?

Задача 9.24

(a)(b)(c)

?

(a)

Предположим, что $\left\{ Z_{n}; n \geq 1\right\}$ — субмартингал. Покажите, что

\mathbb {E}\left[Z_{m} \mid Z_{n}, Z_{n-1}, \ldots , Z_{1}\right] \geq Z_{n} \quad \text{для всех } n < m.

(b)

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

\mathbb {E}\left[Z_{m} \mid Z_{n_{i}}, Z_{n_{i-1}}, \ldots , Z_{n_{1}}\right] \geq Z_{n_{i}} \quad \text{для всех } 0 < n_{1} < n_{2} < \cdots < n_{i} < m.

(c)

Предположим теперь, что $\left\{ Z_{n}; n \geq 1\right\}$ — супермартингал. Покажите, что (а) и (б) остаются верны, если заменить $\geq$ на $\leq$ .

Задача 9.25

Пусть $\left\{ Z_{n} = \exp \left(rS_{n} - n\gamma (r)\right); n \geq 1\right\}$ — мартингал производящей функции из (9.77), где $S_{n} = X_{1} + \cdots + X_{n}$ , а $X_{1}, \ldots , X_{n}$ независимы и одинаково распределены со средним $\overline{X} < 0$ . Пусть $J$ — возможно дефектный момент остановки, для которого процесс останавливается после пересечения порога на уровне $\alpha > 0$ (отрицательного порога нет). Покажите, что $\exp \left(r^{*}\alpha \right)$ является верхней оценкой вероятности пересечения порога, рассматривая остановленный процесс $\left\{ Z_{n}^{*}; n \geq 1\right\}$ .

?

Примечание.

?

Цель этой задачи — проиллюстрировать, что остановленный процесс может давать полезные верхние оценки даже тогда, когда момент остановки дефектен.

Задача 9.26

В этом упражнении с помощью мартингала находится среднее число последовательных испытаний $\mathbb {E}\left[J\right]$ до появления некоторого фиксированного шаблона $a_{1}, a_{2}, \ldots , a_{k}$ из последовательных двоичных цифр в последовательности НОРС двоичных случайных величин $X_{1}, X_{2}, \ldots$ (см. Пример 4.5.1 и Упражнение 5.35 для альтернативных подходов). В качестве момента остановки $J$ мы берём наименьшее $n$ , для которого $(X_{n-k+1}, \ldots , X_{n}) = (a_{1}, \ldots , a_{k})$ . Для нахождения $\mathbb {E}\left[J\right]$ будет использовано мифическое казино и последовательность игроков, следующих предписанной стратегии. Исходы испытаний $\left\{ X_{n}; n \geq 1\right\}$ в казино образуют двоичную НОРС-последовательность, для которой $\mathbb {P}\left(X_{n} = i\right) = p_{i}$ при $i \in \left\{ 0,1\right\}$ .

Если игрок делает ставку $s$ на 1 в испытании $n$ , то выигрыш равен $s/p_{1}$ , если $X_{n} = 1$ , и $0$ в противном случае. При ставке $s$ на 0 выигрыш равен $s/p_{0}$ , если $X_{n} = 0$ , и $0$ в противном случае; то есть игра честная.

?

(a)

Предположим произвольный выбор ставок на 0 и 1 различными игроками в различных испытаниях. Пусть $Y_{n}$ — чистый выигрыш казино в испытании $n$ . Покажите, что $\mathbb {E}\left[Y_{n}\right] = 0$ . Пусть $Z_{n} = Y_{1} + Y_{2} + \cdots + Y_{n}$ — суммарный выигрыш казино за $n$ испытаний. Покажите, что при любой заданной схеме ставок $\left\{ Z_{n}; n \geq 1\right\}$ является мартингалом.

(b)

Чтобы найти $\mathbb {E}\left[J\right]$ для заданного шаблона $a_{1}, a_{2}, \ldots , a_{k}$ , мы программируем наших игроков делать ставки следующим образом:

(i) Игрок 1 имеет начальный капитал 1, который ставится на $a_{1}$ в испытании 1. Если $X_{1} = a_{1}$ , капитал вырастает до $1/p_{a_{1}}$ , весь который ставится на $a_{2}$ в испытании 2. Если $X_{2} = a_{2}$ , капитал вырастает до $1/(p_{a_{1}}p_{a_{2}})$ , весь который ставится на $a_{3}$ в испытании 3. Игрок 1 продолжает таким образом, пока либо не проиграет в каком-то испытании (в этом случае он уходит без денег), либо не выиграет $k$ последовательных испытаний подряд (в этом случае он уходит с капиталом $1/\left[p_{a_{1}} \cdots p_{a_{k}}\right]$ ).

(ii) Игрок $\ell$ , для каждого $\ell > 1$ , следует той же стратегии, но начинает в испытании $\ell$ . Заметим, что если шаблон $a_{1}, \ldots , a_{k}$ впервые появляется в испытаниях $n-k+1, n-k+2, \ldots , n$ , т.е. если $J = n$ , то игрок $n-k+1$ уходит в момент $n$ с капиталом $1/\left[p(a_{1}) \cdots p(a_{k})\right]$ , а игроки $j < n-k+1$ все потеряли свой капитал. Позже мы вернёмся к рассмотрению капитала в момент $n$ у игроков с $n-k+2$ по $n$ .

Сначала рассмотрим строку $a_{1}=0, a_{2}=1$ при $k = 2$ . Найдите значения выборки $Z_{1}, Z_{2}, Z_{3}$ для выборочной последовательности $X_{1} = 1, X_{2} = 0, X_{3} = 1, \ldots$ . Заметим, что игроки 1 и 3 потеряли свой капитал, а игрок 2 теперь имеет капитал $1/p_{0}p_{1}$ . Покажите, что выборочное значение момента остановки в этом случае равно $J = 3$ . Для произвольного выборочного значения $n \geq 2$ величины $J$ покажите, что $Z_{n} = n - 1/p_{0}p_{1}$ .

(c)

Найдите $\mathbb {E}\left[Z_{J}\right]$ из (а). Используйте это вместе с (б), чтобы найти $\mathbb {E}\left[J\right]$ .

(d)

Повторите (б) и (в) для строки $(a_{1}, \ldots , a_{k}) = (1,1)$ , изначально предполагая $(X_{1}X_{2}X_{3}) = (011)$ . Будьте внимательны с игроком 3 при $J = 3$ . Покажите, что $\mathbb {E}\left[J\right] = 1/p_{1}^{2} + 1/p_{1}$ .

(e)

Повторите (б) и (в) для $(a_{1}, \ldots , a_{k}) = (1,1,1,0,1,1)$ .

(f)

Рассмотрим произвольную двоичную строку $a_{1}, \ldots , a_{k}$ и обусловимся на $J = n$ при некотором $n \geq k$ . Покажите, что выборочный капитал игрока $\ell$ тогда равен

$0$ при $\ell < n-k$ ;
$1/\left[p_{a_{1}}p_{a_{2}} \cdots p_{a_{k}}\right]$ при $\ell = n-k+1$ ;
$1/\left[p_{a_{1}}p_{a_{2}} \cdots p_{a_{i}}\right]$ при $\ell = n-i+1$ , $1 \leq i < k$ , если $(a_{1}, \ldots , a_{i}) = (a_{k-i+1}, \ldots , a_{k})$ ;
$0$ при $\ell = n-i+1$ , $1 \leq i < k$ , если $(a_{1}, \ldots , a_{i}) \neq (a_{k-i+1}, \ldots , a_{k})$ .

Проверьте, что эта общая формула согласуется с (б), (г) и (д).

(g)

Для заданной двоичной строки $(a_{1}, \ldots , a_{k})$ и каждого $j$ , $1 \leq j \leq k$ , положим $\mathbb {I}_{j} = 1$ , если $(a_{1}, \ldots , a_{j}) = (a_{k-j+1}, \ldots , a_{k})$ , и $\mathbb {I}_{j} = 0$ в противном случае. Покажите, что

\mathbb {E}\left[J\right] = \sum _{i=1}^{k} \frac{\mathbb {I}_{i}}{\prod _{m=1}^{i} p_{a_{m}}}.

Заметим, что это совпадает с итоговым результатом Упражнения 4.28. Здесь рассуждение короче, но там оно более мотивировано и содержательно. Оба подхода полезны и допускают простые обобщения.

Задача 9.27

(a)(b)(c)

?

(a)

Этот пример показывает, почему условие $\mathbb {E}\left[\left|Z_{J}\right|\right] < \infty$ требуется в лемме 9.8.4. Пусть $Z_{1} = -2$ и при $n \geq 1$ пусть $Z_{n+1} = Z_{n}\left[1 + X_{n}(3n+1)/(n+1)\right]$ , где $X_{1}, X_{2}, \ldots$ независимы и одинаково распределены и принимают значения $+1$ и $-1$ с вероятностью $1/2$ каждое. Покажите, что $\left\{ Z_{n}; n \geq 1\right\}$ является мартингалом.

(b)

Рассмотрим момент остановки $J$ , равный наименьшему значению $n > 1$ , для которого $Z_{n}$ и $Z_{n-1}$ имеют одинаковый знак. Покажите, что при условии $n < J$ выполняется $Z_{n} = (-2)^{n}/n$ , а при условии $n = J$ выполняется $Z_{J} = -(-2)^{n}(2n-1)/(n^{2}-n)$ .

(c)

Покажите, что $\mathbb {E}\left[\left|Z_{J}\right|\right]$ бесконечно, так что $\mathbb {E}\left[Z_{J}\right]$ не существует согласно определению математического ожидания, и покажите, что $\lim_{n \rightarrow \infty } \mathbb {E}\left[Z_{n} \mid J > n\right] \mathbb {P}\left(J > n\right) = 0$ .

Задача 9.28

(a)(b)(c)(d)

Этот пример показывает, почему супремум мартингала может вести себя существенно иначе, чем максимум произвольно большого числа его слагаемых. Точнее, он показывает, что $\mathbb {P}\left(\sup_{n \geq 1} Z_{n} \geq a\right)$ может не совпадать с $\mathbb {P}\left(\bigcup_{n \geq 1}\left\{ Z_{n} \geq a\right\} \right)$ .

?

(a)

Рассмотрим мартингал, в котором $Z_{n}$ может принимать только значения $2^{-n-1}$ и $1-2^{-n-1}$ , каждое с вероятностью $1/2$ . Учитывая, что $Z_{n}$ при условии $Z_{n-1}$ не зависит от $Z_{1}, \ldots Z_{n-2}$ , найдите $\mathbb {P}\left(Z_{n} \mid Z_{n-1}\right)$ для каждого $n$ так, чтобы выполнялось условие мартингала.

(b)

Покажите, что $\mathbb {P}\left(\sup_{n \geq 1} Z_{n} \geq 1\right) = 1/2$ и что $\mathbb {P}\left(\bigcup_{n}\left\{ Z_{n} \geq 1\right\} \right) = 0$ .

(c)

Покажите, что для любого $\epsilon > 0$ выполняется $\mathbb {P}\left(\sup_{n \geq 1} Z_{n} \geq a\right) \leq \mathbb {E}\left[Z_{1}\right]/(a-\epsilon )$ .

(d)

Используя (в), установите

\mathbb {P}\left(\sup _{n \geq 1} Z_{n} \geq a\right) \leq \frac{\mathbb {E}\left[Z_{1}\right]}{a} \quad \text{для всех } a > 0. \tag {9.111}

Задача 9.29

Теорема 9.7.4 утверждает: пусть $h$ — выпуклая функция из $\mathbb {R}$ в $\mathbb {R}$ , $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал и $\mathbb {E}\left[\left|h(Z_{n})\right|\right] < \infty$ для всех $n$ . Тогда $\left\{ h(Z_{n}); n \geq 1\right\}$ — субмартингал.

Покажите, что теорема 9.7.4 верна также для мартингалов относительно совместного процесса. То есть покажите, что если $h$ — выпуклая функция вещественной переменной и $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал относительно совместного процесса $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ , то $\left\{ h(Z_{n}); n \geq 1\right\}$ — субмартингал относительно $\left\{ h(Z_{n}), X_{n}; n \geq 1\right\}$ .

?

Задача 9.30

Покажите, что если $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал (субмартингал или супермартингал) относительно совместного процесса $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ и если $J$ — момент остановки для $\left\{ Z_{n}; n \geq 1\right\}$ относительно $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ , то остановленный процесс является соответственно мартингалом (субмартингалом или супермартингалом) относительно совместного процесса.

?

Задача 9.31

Докажите следствия 9.9.3–9.9.5, т.е. докажите следующие три утверждения.

Пусть $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал с $\mathbb {E}\left[Z_{n}^{2}\right] < \infty$ для всех $n \geq 1$ . Тогда
$\mathbb {P}\left(\max _{1 \leq n \leq m} \left|Z_{n}\right| \geq b\right) \leq \frac{\mathbb {E}\left[Z_{m}^{2}\right]}{b^{2}} \quad \text{для всех целых } m \geq 2 \text{ и всех } b > 0.$
(Неравенство Колмогорова для случайного блуждания) Пусть $\left\{ S_{n}; n \geq 1\right\}$ — случайное блуждание с $S_{n} = X_{1} + \cdots + X_{n}$ , где $\left\{ X_{i}; i \geq i\right\}$ — набор н.о.р.случайных величин со средним $\overline{X}$ и дисперсией $\sigma^{2}$ . Тогда для любого положительного целого $m$ и любого $\epsilon > 0$
$\mathbb {P}\left(\max _{1 \leq n \leq m} \left|S_{n} - n\overline{X}\right| \geq m\epsilon \right) \leq \frac{\sigma ^{2}}{m\epsilon ^{2}}.$
Пусть $\left\{ S_{n}; n \geq 1\right\}$ — случайное блуждание, $S_{n} = X_{1} + \cdots + X_{n}$ , где каждая $X_{i}$ имеет среднее $\overline{X} < 0$ и семиинвариантную производящую функцию моментов $\gamma (r)$ . Для любого $r > 0$ такого, что $0 < \gamma (r) < \infty$ , и для любого $\alpha > 0$
$\mathbb {P}\left(\max _{1 \leq i \leq n} S_{i} \geq \alpha \right) \leq \exp \left\{ -r\alpha + n\gamma (r)\right\} .$

?

Задача 9.32

(a)(b)

Пусть $\left\{ Z_{n}; n \geq 1\right\}$ — масштабированный ветвящийся процесс из раздела 9.6.2: $\left\{ X_{n}; n \geq 0\right\}$ — ветвящийся процесс, где $X_{n}$ — суммарное число элементов поколения $n$ , каждый элемент $i$ поколения $n$ (для $1 \leq i \leq X_{n}$ ) имеет число потомков $Y_{i,n}$ , в совокупности составляющих поколение $n+1$ (т.е. $X_{n+1} = \sum_{i=1}^{X_{n}} Y_{i,n}$ ), а случайные величины $Y_{i,n}$ н.о.р.как по $i$ , так и по $n$ , со средним $\overline{Y} := \mathbb {E}\left[Y_{i,n}\right]$ ; масштабированный процесс есть $Z_{n} := X_{n}/\overline{Y}^{n}$ .

?

(a)

Предположим, что $Y$ — число потомков каждого элемента — имеет конечное среднее $\overline{Y}$ и конечную дисперсию $\sigma^{2}$ . Предположим, что численность популяции в момент 0 равна 1. Покажите, что

\mathbb {E}\left[Z_{n}^{2}\right] = 1+\sigma ^{2}\left[\overline{Y}^{-2}+\overline{Y}^{-3}+\cdots +\overline{Y}^{-n-1}\right].

(b)

Предположим, что $\overline{Y} > 1$ , и найдите $\lim_{n \rightarrow \infty } \mathbb {E}\left[Z_{n}^{2}\right]$ . Покажите на основе этого, что условия теоремы о сходимости мартингалов, теоремы 9.9.8, выполнены.

Примечание.

?

Теорема 9.9.8 (Теорема о сходимости мартингалов): пусть $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал и предположим, что существует такое конечное $M$ , что $\mathbb {E}\left[Z_{n}^{2}\right] \leq M$ для всех $n$ . Тогда существует случайная величина $Z$ такая, что для всех выборочных последовательностей, кроме множества вероятности 0, $\lim_{n \rightarrow \infty } Z_{n} = Z$ .

Примечание: это условие не выполняется, если $\overline{Y} \leq 1$ . Общая теорема о сходимости мартингалов требует лишь ограниченности первого абсолютного момента, поэтому она справедлива и при $\overline{Y} \leq 1$ .

Задача 9.33

Покажите, что если $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал (субмартингал или супермартингал) относительно совместного процесса $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ и если $J$ — момент остановки для $\left\{ Z_{n}; n \geq 1\right\}$ относительно $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ , то остановленный процесс удовлетворяет соответственно (9.98), (9.99) или (9.100).

?

Задача 9.34

Покажите, что если $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал относительно совместного процесса $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ и если $J$ — момент остановки для $\left\{ Z_{n}; n \geq 1\right\}$ относительно $\left\{ Z_{n}, X_{n}; n \geq 1\right\}$ , то $\mathbb {E}\left[Z_{J}\right] = \mathbb {E}\left[Z_{1}\right]$ тогда и только тогда, когда выполнено (9.104).

?

Задача 9.35

Рассмотрим пример инвестирования, аналогичный примеру 9.10.1, в котором есть только одна инвестиция помимо наличных денег. Отношение $X$ стоимости этой инвестиции в конце эпохи к её стоимости в начале равно либо 2, либо $1/4$ , каждое с равной вероятностью. Таким образом, $\mathbb {P}\left(X=2\right) = 1/2$ и $\mathbb {P}\left(X=1/4\right) = 1/2$ . Последовательные отношения $X_{1}, X_{2}, \ldots$ являются НОРС (независимыми одинаково распределёнными).

?

(a)

В пунктах (а)--(в) предположим фиксированную стратегию распределения, при которой доля $\lambda$ хранится в инвестиции «удвоение или четвертование», а $1-\lambda$ — в наличных деньгах. Найдите ожидаемое богатство $W_{n}(\lambda )$ и ожидаемое логарифмическое богатство $\mathbb {E}\left[L_{n}(\lambda )\right]$ как функцию константы $\lambda \in \left[0,1\right]$ и $n \geq 1$ . Предполагайте единичное начальное богатство.

(b)

Для $\lambda =1$ найдите ПМФ (функцию вероятностей) для $W_{4}(1)$ и дайте краткое объяснение того, почему $\mathbb {E}\left[W_{n}(1)\right]$ растёт экспоненциально с $n$ , а $\mathbb {E}\left[L_{n}(1)\right]$ линейно убывает к $-\infty$ .

(c)

Используя тот же подход, что и в примере 9.10.1, найдите значение $\lambda^{*}$ , максимизирующее $\mathbb {E}\left[L_{n}(\lambda )\right]$ . Покажите, что ваше решение удовлетворяет условиям оптимальности из (9.136).

(d)

Найдите диапазон значений $\lambda$ , при которых $\mathbb {E}\left[L_{n}(\lambda )\right]$ положительно.

(e)

Найдите ПМФ случайной величины $Z_{n}/Z_{n-1}$ , заданной в (9.138), для произвольного заданного $\lambda_{n}$ .

Задача 9.36

Интересным частным случаем этой простой теории инвестирования является игра на скачках, предложенная Дж. Келли. В забеге участвует $\ell -1$ лошадей, и каждая лошадь $j$ выигрывает с некоторой вероятностью $p(j) > 0$ . Выигрывает одна и только одна лошадь, и если выигрывает $j$ , игрок получает $r(j) > 0$ за каждый доллар, поставленный на $j$ , и ничего за ставки на других лошадей. Другими словами, относительная цена $X(j)$ для каждого $j$ , $1 \leq j \leq \ell -1$ , равна $r(j)$ с вероятностью $p(j)$ и 0 в противном случае. Для наличных $X(\ell )=1$ .

Распределение капитала игрока на забег обозначается $\lambda (j)$ для каждой лошади $j$ , при этом $\lambda (\ell )$ остаётся в наличных. Как обычно, $\sum_{j} \lambda (j)=1$ и $\lambda (j) \geq 0$ для $1 \leq j \leq \ell$ . Отметим, что $X(1), \ldots , X(\ell -1)$ сильно зависимы, поскольку только одна из них имеет ненулевое значение выборки в каждом забеге.

?

(a)

Для произвольного заданного распределения $\overrightarrow {\lambda }$ найдите математическое ожидание капитала и математическое ожидание логарифма капитала в конце забега при единичном начальном капитале.

(b)

Предположим, что проводится статистически идентичная последовательность забегов, т.е. $\overrightarrow {X}_{1}, \overrightarrow {X}_{2}, \ldots$ независимы и одинаково распределены, где каждое $\overrightarrow {X}_{n} = \left(X_{n}(1), \ldots , X_{n}(\ell )\right)^{\mathsf{T}}$ . Предполагая постоянное распределение на каждый забег и единичный начальный капитал, найдите математическое ожидание логарифма капитала $\mathbb {E}\left[L_{n}(\overrightarrow {\lambda })\right]$ в конце $n$ -го забега и выразите его как $n\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]$ .

(c)

Пусть $\overrightarrow {\lambda }^{*}$ максимизирует $\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]$ . Используя необходимое и достаточное условие (9.136) на $\overrightarrow {\lambda }^{*}$ для лошади $j$ , $1 \leq j < \ell$ , покажите, что $\lambda^{*}(j)$ можно выразить следующими двумя эквивалентными способами; каждый однозначно определяет $\lambda^{*}(j)$ через $\lambda^{*}(\ell )$ .

\begin{align} \lambda ^{*}(j) & \geq p(j)-\frac{\lambda ^{*}(\ell )}{r(j)}; \qquad \text{с равенством, если } \lambda ^{*}(j) > 0. \\ \lambda ^{*}(j) & = \max \left\{ p(j)-\frac{\lambda ^{*}(\ell )}{r(j)}, 0\right\} . \end{align}

Решение относительно $\lambda^{*}(\ell )$ (которое, в свою очередь, определяет остальные компоненты $\overrightarrow {\lambda }^{*}$ ) распадается на 3 частных случая, рассматриваемых ниже в пунктах (г), (д) и (е) соответственно. Первый случай, в (г), показывает, что если $\sum_{j<\ell } 1/r(j) < 1$ , то $\lambda^{*}(\ell )=0$ . Второй случай, в (д), показывает, что если $\sum_{j<\ell } 1/r(j) > 1$ , то $\lambda^{*}(\ell ) > \min_{j}(p(j)r(j))$ , причём конкретное значение определяется единственным решением уравнения

\sum _{j<\ell } \frac{p(j)}{\max \left[p(j)r(j), \; \lambda ^{*}(\ell )\right]} \leq 1; \qquad \text{с равенством, если } \lambda ^{*}(\ell ) > 0.

Третий случай, в (е), показывает, что если $\sum_{j<\ell } 1/r(j)=1$ , то $\lambda^{*}(\ell )$ неоднозначно, и множество его возможных значений занимает диапазон $\left[0, \min_{j}\left(p(j)r(j)\right)\right]$ .

(d)

Просуммируйте первое неравенство из (в) по $j$ , чтобы показать, что если $\lambda^{*}(\ell ) > 0$ , то $\sum_{j<\ell } 1/r(j) \geq 1$ . Отметим, что логическим обращением этого является то, что $\sum_{j<\ell } 1/r(j) < 1$ влечёт $\lambda^{*}(\ell )=0$ и, следовательно, $\lambda^{*}(j)=p(j)$ для каждой лошади $j$ .

(e)

В (в) $\lambda^{*}(j)$ для каждого $j < \ell$ было выражено через $\lambda^{*}(\ell )$ ; здесь требуется использовать необходимое и достаточное условие (9.136) для наличных, чтобы определить $\lambda^{*}(\ell )$ . Точнее, требуется показать, что $\lambda^{*}(\ell )$ удовлетворяет каждому из следующих двух эквивалентных неравенств:

\begin{align} \sum _{j<\ell } \frac{p(j)}{\lambda ^{*}(j)r(j)+\lambda ^{*}(\ell )} & \leq 1; \qquad \text{с равенством, если } \lambda ^{*}(\ell ) > 0. \\ \sum _{j<\ell } \frac{p(j)}{\max \left[p(j)r(j), \; \lambda ^{*}(\ell )\right]} & \leq 1; \qquad \text{с равенством, если } \lambda ^{*}(\ell ) > 0. \end{align}

Покажите на основе второго неравенства выше, что если $\lambda^{*}(\ell ) \leq p(j)r(j)$ для каждого $j$ , то $\sum_{j} 1/r(j) \leq 1$ . Отметьте, что логическим обращением этого является то, что если $\sum_{j} 1/r(j) > 1$ , то $\lambda^{*}(\ell ) > \min_{j}\left(p(j)r(j)\right)$ . Объясните, почему это второе неравенство имеет единственное решение для $\lambda^{*}(\ell )$ в этом случае. Отметим, что $\lambda^{*}(j)=0$ для каждого $j$ , такого что $p(j)r(j) < \lambda^{*}(\ell )$ .

(f)

Теперь рассмотрим случай, когда $\sum_{j<\ell } 1/r(j)=1$ . Покажите, что второе неравенство из (д) выполняется как равенство для каждого выбора $\lambda^{*}(\ell )$ , $0 \leq \lambda^{*}(\ell ) \leq \min_{j<\ell }\left(p(j)r(j)\right)$ .

(g)

Рассмотрим частный случай забега только с двумя лошадьми. Пусть $p(1)=p(2)=1/2$ . Предположим, что $r(1)$ и $r(2)$ достаточно велики, чтобы удовлетворять $1/r(1)+1/r(2) < 1$ ; таким образом, при максимизации $\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]$ наличные не используются. При $\lambda (3)=0$ имеем

\mathbb {E}\left[Y(\overrightarrow {\lambda })\right] = \frac{1}{2}\ln \left[\lambda (1)r(1)\right]+\frac{1}{2}\ln \left[\lambda (2)r(2)\right] = \frac{1}{2}\ln \left[\lambda (1)r(1)\left(1-\lambda (1)\right)r(2)\right].

Используйте это уравнение, чтобы дать интуитивное объяснение того, почему $\lambda^{*}(1)=1/2$ независимо от $r(1)$ и $r(2)$ .

(h)

Снова рассмотрим частный случай двух лошадей с $p(1)=p(2)=1/2$ , но пусть $r(1)=3$ и $r(2)=3/2$ . Покажите, что $\overrightarrow {\lambda }^{*}$ неоднозначно, причём возможными значениями являются $(1/2,1/2,0)$ и $(1/4,0,3/4)$ . Покажите, что если $r(2) > 3/2$ , то первое из указанных решений единственно, а если $r(2) < 3/2$ , то единственно второе решение, при этом $p(1)=1/2$ и $r(1)=3$ считаются неизменными на всём протяжении.

(i)

Для случая, когда $\sum_{j<\ell } 1/r(j)=1$ , определим $q(j)=1/r(j)$ как распределение вероятностей на $\left\{ 1, \ldots , \ell -1\right\}$ . Покажите, что $\mathbb {E}\left[Y(\overrightarrow {\lambda }^{*})\right] = D(\mathsf{p} \parallel \mathsf{q})$ при условиях пункта (е).

Примечание.

?

Примечание (к пункту (з)): случай $3/2 < r(2) < 2$ даёт пример, когда инвестиция используется для максимизации логарифма капитала, даже несмотря на то, что $\mathbb {E}\left[X(2)\right] = p(2)r(2) < 1$ , т.е. лошадь 2 является плохой инвестицией, но в данном случае предпочтительнее наличных как средство хеджирования на случай проигрыша лошади 1.

Примечание (к пункту (и)): чтобы это интерпретировать, можно рассматривать забег, в котором каждая лошадь $j$ имеет вероятность $q(j)$ выиграть вознаграждение $r(j)=1/q(j)$ , как «честную игру». Наш игрок, зная, что истинные вероятности равны $\left\{ p(j); 1 \leq j < \ell \right\}$ , обладает «инсайдерской информацией», если $p(j) \neq q(j)$ , и может обеспечить положительную норму доходности, равную $D(\mathsf{p} \parallel \mathsf{q})$ .

Задача 9.37

(a)(b)(c)(d)

Пусть функция $h_{\epsilon }(u)$ принимает значение 0 при $-\epsilon < \mathbb {E}\left[Y(\overrightarrow {\lambda })\right] < \epsilon$ и значение 1 всюду иначе.

?

(a)

Покажите, что $\lim_{n \rightarrow \infty } h_{\epsilon }\left(L_{n}(\overrightarrow {\lambda })\right) = 0$ ПВ1.

(b)

Покажите, что для всех $\epsilon > 0, \delta > 0$ найдётся такое $n_{o}$ , что

\mathbb {P}\left(\bigcup _{n \geq n_{o}} \left\{ \left|\frac{1}{n}L_{n}(\overrightarrow {\lambda })-\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]\right| > \epsilon \right\} \right) \leq \delta .

(c)

Покажите, что вероятность дополнительного события равна

\mathbb {P}\left(\bigcap _{n \geq n_{o}} \left\{ \mathbb {E}\left[Y(\overrightarrow {\lambda })\right]-\epsilon \leq \frac{1}{n}L_{n}(\overrightarrow {\lambda }) \leq \mathbb {E}\left[Y(\overrightarrow {\lambda })\right]+\epsilon \right\} \right) > 1-\delta .

(d)

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

\mathbb {P}\left(\bigcap _{n \geq n_{o}} \left\{ \exp \left[n\left(\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]-\epsilon \right)\right] \leq W_{n}(\overrightarrow {\lambda }) \leq \exp \left[n\left(\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]+\epsilon \right)\right]\right\} \right) > 1-\delta .

Примечание.

?

Теорема 9.10.2: предположим, что $\mathbb {E}\left[\left|Y(\overrightarrow {\lambda })\right|\right] < \infty$ . Тогда для любых $\epsilon , \delta > 0$ найдётся такое $n_{o}$ , что

\mathbb {P}\left(\bigcap _{n \geq n_{o}} \left\{ \exp \left[n\left(\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]-\epsilon \right)\right] \leq W_{n}(\overrightarrow {\lambda }) \leq \exp \left[n\left(\mathbb {E}\left[Y(\overrightarrow {\lambda })\right]+\epsilon \right)\right]\right\} \right) > 1-\delta .

Задача 9.38

(a)(b)(c)

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

?

(a)

Предположим, что стратегия "купил и держи" начинается с распределения $\overrightarrow {\lambda }_{1}$ . Пусть $W_{n}(k)$ — капитал инвестора во вложении $k$ в момент времени $n$ . Покажите, что

W_{n}(k) = \lambda _{1}(k) \prod _{m=1}^{n} X_{m}(k).

(b)

Покажите, что $\lambda_{n}(k)$ можно выразить каждым из следующих способов:

\lambda _{n}(k) = \frac{W_{n-1}(k)}{\sum _{j} W_{n-1}(j)} = \frac{\lambda _{n-1}(k)X_{n-1}(k)}{\sum _{j} \lambda _{n-1}(j)X_{n-1}(j)}.

(c)

Для стратегии двух куч из (9.137) проверьте (9.137) и найдите выражение для $\lambda_{n}(k)$ .

Задача 9.39

(a)(b)(c)

?

(a)

Рассмотрим мартингал $\left\{ Z_{n}; n \geq 1\right\}$ , где $Z_{n} = W_{n}/W_{n}^{*}$ , $W_{n}$ — капитал в момент времени $n$ для чистой стратегии "утроить или ничего" из примера 9.10.1, а $W_{n}^{*}$ — капитал при использовании постоянного распределения $\overrightarrow {\lambda }^{*}$ . Найдите ЗРВ для $Z$ , где $Z = \lim_{n \rightarrow \infty } Z_{n}$ ПВ1.

(b)

Теперь рассмотрим стратегию двух куч из (9.137) и найдите ЗРВ предельной случайной величины $Z$ для этой стратегии.

(c)

Теперь рассмотрим стратегию «искушения судьбы», в которой чистая стратегия "утроить или ничего" используется в течение первых трёх эпох, а далее используется постоянное распределение $\overrightarrow {\lambda }^{*}$ . Снова найдите ЗРВ предельной случайной величины $Z$ .

Задача 9.40

(a)(b)(c)

Рассмотрим марковски-модулированное случайное блуждание, изображённое на рисунке ниже. Случайные величины $Y_{n}$ в этом примере принимают только одно значение при каждом переходе: это значение равно 1 для всех переходов из состояния 1, 10 для всех переходов из состояния 2 и 0 во всех остальных случаях. $\epsilon > 0$ — очень малое число, скажем, $\epsilon < 10^{-6}$ .

{#fig-1 width="50%"}

?

(a)

Покажите, что стационарный выигрыш на один переход равен $5.5/(1+\epsilon )$ . Покажите, что вектор относительного выигрыша равен $\overrightarrow {w} = \left(0, (\epsilon -4.5)/\left[\epsilon (1+\epsilon )\right], (10\epsilon +4.5)/\left[\epsilon (1+\epsilon )\right]\right)$ .

(b)

Пусть $S_{n} = Y_{0}+Y_{1}+\cdots +Y_{n-1}$ , и пусть начальное состояние $X_{0}$ равно 0. Пусть $J$ — наименьшее значение $n$ , при котором $S_{n} \geq 100$ . Найдите $\mathbb {P}\left(J=11\right)$ и $\mathbb {P}\left(J=101\right)$ . Найдите оценку для $\mathbb {E}\left[J\right]$ , точную в пределе $\epsilon \rightarrow 0$ .

(c)

Покажите, что $\mathbb {P}\left(X_{J}=1\right) = (1-45\epsilon +o(\epsilon ))/2$ и что $\mathbb {P}\left(X_{J}=2\right) = (1+45\epsilon +o(\epsilon ))/2$ . Проверьте, с точностью до первого порядка по $\epsilon$ , что соотношение (9.159) выполняется.

Задача 9.41

Покажите, что (9.159) получается взятием производной от (9.163) и её вычислением при $r=0$ .

?

Задача 9.42

(a)(b)(c)

Пусть $\left\{ Z_{n}; n \geq 1\right\}$ — мартингал, и для некоторого целого $m$ пусть $Y_{n} = Z_{n+m}-Z_{m}$ .

?

(a)

Покажите, что $\mathbb {E}\left[Y_{n} \mid Z_{n+m-1}=z_{n+m-1}, Z_{n+m-2}=z_{n+m-2}, \ldots , Z_{m}=z_{m}, \ldots , Z_{1}=z_{1}\right] = z_{n+m-1}-z_{m}$ .

(b)

Покажите, что $\mathbb {E}\left[Y_{n} \mid Y_{n-1}=y_{n-1}, \ldots , Y_{1}=y_{1}\right] = y_{n-1}$ .

(c)

Покажите, что $\mathbb {E}\left[\left|Y_{n}\right|\right] < \infty$ . Заметьте, что (б) и (в) показывают, что $\left\{ Y_{n}; n \geq 1\right\}$ является мартингалом.

Задача 9.43

(a)(b)

В этой задаче процесс ветвления с непрерывным временем из задачи 7.15 рассматривается как остановленное случайное блуждание. Напомним, что там этот процесс задавался как марковский процесс, такой что для каждого состояния $j$ , $j \geq 0$ , интенсивность перехода в $j+1$ равна $j\lambda$ , а в $j-1$ равна $j\mu$ . Других переходов нет, и, в частности, нет переходов из состояния 0, так что марковский процесс является приводимым. Напомним, что вложенная цепь Маркова совпадает с вложенной цепью системы массового обслуживания $\mathrm{M}/\mathrm{M}/1$ , за исключением того, что отсутствует переход из состояния 0 в состояние 1.

?

(a)

Чтобы смоделировать возможное вымирание популяции, преобразуйте указанную выше вложенную цепь Маркова в остановленное случайное блуждание $\left\{ S_{n}; n \geq 0\right\}$ . Остановленное случайное блуждание начинается с $S_{0}=0$ и останавливается при достижении порога $-1$ . До остановки на каждом шаге оно увеличивается на 1 с вероятностью $\lambda /(\lambda +\mu )$ и уменьшается на 1 с вероятностью $\mu /(\lambda +\mu )$ . Укажите (весьма простое) соотношение между состоянием $X_{n}$ цепи Маркова и состоянием $S_{n}$ остановленного случайного блуждания для каждого $n \geq 0$ .

(b)

Найдите вероятность того, что популяция в конце концов вымрет, как функцию от $\lambda$ и $\mu$ . Обязательно рассмотрите все три случая: $\lambda > \mu$ , $\lambda < \mu$ и $\lambda =\mu$ .

Случайные блуждания, большие уклонения и мартингалы