6.14

Цепь Маркова Монте-Карло

[6/100%]
Показать
LaTeX
Задача 6.14.1

Пусть P\mathbf{P} — стохастическая матрица на конечном множестве Θ\Theta со стационарным распределением \vectπ\vect {\pi }. Определим скалярное произведение ⟨x,y⟩=∑k∈Θxkykπk\langle \mathbf{x}, \mathbf{y}\rangle = \sum_{k \in \Theta } x_{k} y_{k} \pi_{k} и пусть l2(π)={x∈RΘ:⟨x,x⟩<∞}l^{2}(\pi ) = \left\{ \mathbf{x} \in \mathbb {R}^{\Theta }:\langle \mathbf{x}, \mathbf{x}\rangle < \infty \right\}. Покажите, в очевидных обозначениях, что P\mathbf{P} обратима относительно π\pi тогда и только тогда, когда ⟨x,Py⟩=⟨Px,y⟩\langle \mathbf{x}, \mathbf{P y}\rangle = \langle \mathbf{P x}, \mathbf{y}\rangle для всех x,y∈l2(π)\mathbf{x}, \mathbf{y} \in l^{2}(\pi ).

?
Задача 6.14.2

Покажите, что возможным выбором вероятностей принятия в общем алгоритме Гастингса являются

bij=πjgjiπigij+πjgji b_{i j} = \frac{\pi _{j} g_{j i}}{\pi _{i} g_{i j}+\pi _{j} g_{j i}}

где G=(gij)\mathbf{G} = \left(g_{i j}\right) — матрица предложений.

?
Задача 6.14.3

Пусть SS — счётное множество. Для каждого j∈Sj \in S множества Ajk,k∈SA_{j k}, k \in S, образуют разбиение интервала [0,1][0,1]. Пусть g:S×[0,1]→Sg: S \times [0,1] \rightarrow S задана как g(j,u)=kg(j, u) = k, если u∈Ajku \in A_{j k}. Последовательность случайных величин {Xn:n≥0}\left\{ X_{n}: n \geq 0\right\} строится рекурсивно как Xn+1=g(Xn,Un+1),n≥0X_{n+1} = g\left(X_{n}, U_{n+1}\right), n \geq 0, где {Un:n≥1}\left\{ U_{n}: n \geq 1\right\} — независимые случайные величины, равномерно распределённые на [0,1][0,1]. Покажите, что XX — марковская цепь, и найдите её матрицу переходных вероятностей.

?
Задача 6.14.4

Пусть U=(ust)\mathbf{U} = \left(u_{s t}\right) — конечная стохастическая матрица размера ∣S∣×∣T∣\left|S\right| \times \left|T\right|. Эргодическим коэффициентом Добрушина называется

d(U)=12sup⁡i,j∈S∑t∈T∣uit−ujt∣ d(\mathbf{U}) = \frac{1}{2} \sup _{i, j \in S} \sum _{t \in T}\left|u_{i t}-u_{j t}\right|
?
(a)

Покажите, что если V\mathbf{V} — конечная стохастическая матрица размера ∣T∣×∣U∣\left|T\right| \times \left|U\right|, то d(UV)≤d(U)d(V)d(\mathbf{U V}) \leq d(\mathbf{U}) d(\mathbf{V}).

(b)

Пусть XX и YY — дискретные марковские цепи с одной и той же матрицей переходных вероятностей P\mathbf{P}, и покажите, что

∑k∣P(Xn=k)−P(Yn=k)∣≤d(P)n∑k∣P(X0=k)−P(Y0=k)∣ \sum _{k}\left|\mathbb {P}\left(X_{n} = k\right)-\mathbb {P}\left(Y_{n} = k\right)\right| \leq d(\mathbf{P})^{n} \sum _{k}\left|\mathbb {P}\left(X_{0} = k\right)-\mathbb {P}\left(Y_{0} = k\right)\right|
Задача 6.14.5

Пусть \vectπ\vect {\pi } — положительная функция вероятностей на конечном множестве Θ\Theta, и пусть P\mathbf{P} — матрица переходных вероятностей неприводимой апериодической марковской цепи со стационарным распределением \vectπ\vect {\pi }. Пусть W=(W(i):i∈Θ)W = (W(i): i \in \Theta ) — вектор случайных величин, такой что P(W(i)=j)=pij\mathbb {P}\left(W(i\right) = j) = p_{i j} при i,j∈Θi, j \in \Theta, и используем WW в качестве правила обновления в алгоритме «склейки из прошлого» для выборки из π\pi.

?
(a)

Если W(i),i∈ΘW(i), i \in \Theta, независимы, покажите, что время слияния почти наверное конечно.

(b)

Приведите два примера ситуаций, в которых время слияния почти наверное бесконечно.

Задача 6.14.6

Покажите, что распределение Изинга из примера (6.14.2) удовлетворяет решёточному условию FKG (6.14.20).

?