Jak efektownie skonstruować $\mathbb{P}$ takie, aby $\pi P = \pi$ i zbieżność $p_{ij}(n)\underset{n \rightarrow \infty}{\longrightarrow} \pi_{ij}$ była
szybka?\\
2092
Jak symulować rozkład Markowa? $$|\epsilon|<+\infty|$$
Funkcję $\varphi:[0,1] \to \epsilon$ nazywamy funkcją inicjującą (,,initiation function''), funkcję $\psi: \epsilon \times [0,1] \to \epsilon$ nazywamy funkcją
aktualizująca (,,update function''). Jeśli $|\epsilon|$ bardzo duża, to powyższa symulacja jest niewykonalna.\\
2113
W ogólnym przypadku szukana macierz $\mathbb{P}$ powinna zawierać mnóstwo zer, zamiast startować z $\pi$ zaczyna się symulację z dowolnego rozkładu.
2114
\end{problem}
2115
\begin{przyklad} (Algorytm Metropolisa)\\
2116
Przypuśćmy, że w $\epsilon$ możemy wyróżnić pewną strukturę krawędzi tak, że $(\epsilon,C)$ jest grafem. Graf taki nie powinien mieć zbyt skomplikowanej
struktury otoczeń, ale również dostatecznie bogatą, aby powstały łańcuch Markowa był nieprzywiedlny (nieredukowalny) i nieokresowy.\\
$\pi$ jest rozkładem stacjonarnym dla $\mathbb{P}$!\\
2134
$X_n=i$\\
2135
Losujemy sąsiada według rozkładu jednostajnego (każdy sąsiad z prawdopodobieństwem $\frac{1}{d_i}$). Wybieramy wylosowanego sąsiada $j$ z prawdopodobieństwem
$\min \Big\{\frac{d_i\pi_j}{\pi_id_j},1\Big\}$ lub pozostajemy w $i$ z prawdopodobieństwem $1-\min \Big\{\frac{d_i\pi_j}{\pi_id_j},1\Big\}$.\\
Kiedy $\mathbb{P}$ jest nieprzywiedlna? (graf łukowo spójny)\\
2141
Kiedy $\mathbb{P}$ jest nieokresowa?
2142
\end{wniosek}
2143
\begin{uwaga}
2144
Wystarczy znaleźć $\frac{\pi_i}{\pi_j}$. Np. w rozkładie Gibbsa z temperaturą $T:\pi\{x\}=\frac{e-\frac{f(x)}{T}}{Z_T}, \\ \frac{\pi\{x\}}{\pi\{y\}} =
e^{-\frac{1}{T}(f(x)-f(y))}$.
2145
\end{uwaga}
2146
\end{przyklad}
2147
\begin{przyklad}
2148
Model twarduch kul\\
2149
$V_{\{0,1\}}$ - konfiguracja $\{0,1\}$\\
2150
Konfiguracja twardych kul:
2151
\includegraphics[scale=0.7]{rys8.png}\\
2152
Jedynka może być w $V$, jeśli we wszystkich sąsiadujących wierzchołkach są zera. Nazwujmy takie konfiguracje ,,wykonalnymi'' (,,feasible'').\\
2153
$\Omega$ - zbiór konfiguracji wykonalnych.\\
2154
Losujemy ,,typową konfigurację'' z rozkładu jednostaknego\\
\begin{problem}Jak efektownie skonstruować $\mathbb{P}$ takie, aby $\pi P = \pi$ i zbieżność $p_{ij}(n)\underset{n \rightarrow \infty}{\longrightarrow} \pi_{ij}$ była szybka?\\\begin{enumerate}[a)]\item rozkład początkowy $\pi:(\pi_i)_{i\in \epsilon}, \ \ \ \ \pi_i>0, \ \ \ \sum\limits_{i \in \epsilon} \pi_i = 1$\includegraphics[scale=0.7]{rys7.png}x_0=|\epsilon| \ \ gdy \ \ U \in (\pi_1 + \pi_2 + \pi_3 + \ldots +\pi_{|\epsilon|-1},1]\\gdzie $\varphi$ - funkcja schodkowa, przyjmuje odpowiednie wartości na odcinku $(\pi_1+\pi_2 + \ldots +\pi_j, \ \pi_1+\pi_2+\ldots \pi_{j+1}]$$p_{ij}=P(X_{n+1} = j \ | \ X_n = i)\\\sum\limits_{j=1}^{|\epsilon|} p_{ij}=1, \ \ p_{ij} \geqslant 0\\X_{n+1} = \psi(i;U_{n+1}),\\\psi(i;x) = j \ \ gdy \ \ x \in (p_{i1} + p_{i2} + \ldots + p_{i \ j-1}, \ P_{i1}+p_{i2} + \ldots + p_{ij}]=I_{ij}, \ \ \ |I_{ij}|=p_{ij}$\end{enumerate}W ogólnym przypadku szukana macierz $\mathbb{P}$ powinna zawierać mnóstwo zer, zamiast startować z $\pi$ zaczyna się symulację z dowolnego rozkładu.\end{problem}\begin{przyklad} (Algorytm Metropolisa)\\$\mathbb{P}=p_{ji}$ (dla $\pi=(\pi_i)$ rozkładu początkowego stacjonarnego dla $\mathbb{P}, \ \pi_i>0, \ i\in \epsilon)$\\$$P(X_{n+1}=j \ | X_n=i)=\left \{ \begin{matrix} \frac{1}{d_i} \cdot \min \Big\{\frac{d_i\pi_j}{\pi_id_j},1\Big\}, & \left. \begin{matrix} \mbox{ \ gdy \ } i\sim j \mbox{ (tzn. ,,}j\mbox{'' jest sąsiadem ,,}i\mbox{'',} \\ \mbox{ czyli jest krawędź pomiędzy ,,}i\mbox{'' i ,,}j\mbox{'') oraz }i\neq j \end{matrix} \right. \\ \\ 1-\sum\limits_{j\sim i} \cdot \min \Big\{\frac{d_i\pi_j}{\pi_id_j},1\Big\}, & \mbox{gdy }j=i \\ \\ 0, & \mbox{gdy } j\not\sim i \mbox{ oraz } j\neq i \end{matrix} \right.$$\begin{enumerate}[a)]\item $1 \underset{?}{\geqslant} \sum\limits_{i\sim j} \frac{1}{d_i} \cdot \min \Big\{\frac{d_i\pi_j}{\pi_id_j},1\Big\}$ - prawda?\item $\mathbb{P}$ jest macierzą prawdopodobieństw przejścia\item Czy $\pi$ jest rozkładem stacjonarnym dla $\mathbb{P}$?\\$\pi_jp_{ij} = \pi_ip_{ij} \forall_{ij}$ ?\begin{itemize}\item $j \not\sim i \Rightarrow p_{ij} = 0 \Rightarrow$ warunek spełniony\item $j=i \Rightarrow p_{ii}=p_{ii} \ \wedge \ \pi_i = \pi_i \Rightarrow$ warunek spełniony\item $j \sim i, \ j \neq i$ załóżmy, że $\min \Big\{\frac{d_i\pi_j}{\pi_id_j},1\Big\}<1, \\ \pi_ip_{ij} = \pi_i \cdot \frac{1}{d_i} \cdot \frac{d_i\pi_j}{\pi_id_j} = \frac{1}{d_i} \cdot \pi_j$\\$\pi_jp_{ij}=\pi_j \cdot \frac{1}{d_j} \cdot 1 = \frac{\pi_j}{d_j} \Rightarrow$ warunek spełniony\end{itemize}\end{enumerate}\begin{wniosek}$\pi$ jest rozkładem stacjonarnym dla $\mathbb{P}$!\\Losujemy sąsiada według rozkładu jednostajnego (każdy sąsiad z prawdopodobieństwem $\frac{1}{d_i}$). Wybieramy wylosowanego sąsiada $j$ z prawdopodobieństwem $\min \Big\{\frac{d_i\pi_j}{\pi_id_j},1\Big\}$ lub pozostajemy w $i$ z prawdopodobieństwem $1-\min \Big\{\frac{d_i\pi_j}{\pi_id_j},1\Big\}$.\\\noindent$P(X_{n+1} = j \ | \ X_n=i)=\frac{1}{d_i} \cdot \min \Big\{\frac{d_i\pi_j}{\pi_id_j},1\Big\} \ \ \ \ \ \ \ \ $ dla $j \sim i\\P(X_{n+1} = j \ | \ X_n=i)=0 \ \ \ \ \ \ \ \ $ dla $j\not\sim i\\P(X_{n+1} = i \ | \ X_n=i)=\sum\limits_{i\sim j} \frac{1}{d_i} \cdot \min \Big\{1 - \frac{d_i\pi_j}{\pi_id_j},1\Big\} = 1- \sum\limits_{i\sim j} \frac{1}{d_i} \cdot \min \Big\{ \frac{d_i\pi_j}{\pi_id_j},1\Big\}$\\Kiedy $\mathbb{P}$ jest nieprzywiedlna? (graf łukowo spójny)\\Kiedy $\mathbb{P}$ jest nieokresowa?\end{wniosek}\begin{uwaga}Wystarczy znaleźć $\frac{\pi_i}{\pi_j}$. Np. w rozkładie Gibbsa z temperaturą $T:\pi\{x\}=\frac{e-\frac{f(x)}{T}}{Z_T}, \\ \frac{\pi\{x\}}{\pi\{y\}} = e^{-\frac{1}{T}(f(x)-f(y))}$.\end{uwaga}\end{przyklad}\begin{przyklad}$V_{\{0,1\}}$ - konfiguracja $\{0,1\}$\\\includegraphics[scale=0.7]{rys8.png}\\$x \in \{0,1\}^V, \ \ \ \mu(\{x\}) = \frac{1}{|\Omega| 1_{\Omega}(x)}, \ \ \ \Omega \in \{0,1\}^V$\\$X_{n+1}(v) = 1$ (jeśli wszyscy sąsiedzi są zerami) jeśli $X_n(v') = 0$ dla $v' \sim v$ i ,,wypadł orzeł''.\\$X_{n+1}(v) = 0$ w przeciwnym wypadku.\\$X_{n+1}(v'')=X_n(v'')$ dla $v''\neq v$\\$\pi_xp_{xy} = \pi_yp_{xy}$\begin{itemize}$p_{xy}=p_{yx}=0$$\frac{1}{|\Omega|} \cdot \frac{1}{|V|} \cdot \frac{1}{2} = \frac{1}{|\Omega|} \cdot \frac{1}{|V|} \cdot \frac{1}{2}$\\\begin{przyklad}Łańcuch Markowa ma $S^V$ dla rozkładu $\pi$ (na $S^V$). Mając ustaloną konfigurację $X \in S^V$, wybieramy wierzchołek losowo, w wierzchołku konfigurację zmieniamy zgodnie z rozkładem warunkowym $$\pi(x(v)) = (\cdot)\ | x(u) = X_n(u) \ \ \ \forall_{u\neq v}.$$ Reszta konfiguracji pozostaje niezmieniona.\end{przyklad}\end{itemize}\end{przyklad}\end{document}\end{document}