Eingebettete Markow-Ketten; Simulationsalgorithmus

• Sei $E=\{1,2,\ldots,\ell\}$ und sei ${\mathbf{Q}}=(q_{ij})_{i,j\in E}$ eine beliebige Intensitätsmatrix, d.h., es gelte
  $$q_{ij}\ge0\;\;$$   $$\mbox{für beliebige $i\neq j$}$$   und$$\qquad \sum_{j\in E} q_{ij}=0\;\;$$$$\mbox{für jedes $i\in E$.}$$$$$$

• Wir diskutieren nun eine Methode zur Konstruktion von Markow-Prozessen mit vorgegebener Intensitätsmatrix ${\mathbf{Q}}$, wobei wir zunächst die folgende eingebettete Markow-Kette $\{\tilde X_n,n\ge 0\}$ (mit diskreter Zeit) betrachten.
  • Sei ${\boldsymbol{\alpha}}$ eine beliebige Anfangsverteilung, und sei $q(i)=\sum_{j\neq i} q_{ij}$ für jedes $i\in E$.
  • Außerdem sei die stochastische Matrix $\widetilde{\mathbf{P}}=(\widetilde p_{ij})$ gegeben durch

    $$\widetilde p_{ij}=\left\{\begin{array}{ll}\displaystyle\frac{q_{i... ...}\;, & \mbox{falls $i\neq j$,}\\ 0\,, & \mbox{falls $i=j$.} \end{array}\right.$$ (41)

    
    
    für beliebige $i,j\in E$ mit $q(i)>0$.
  • Falls $q(i)=0$, dann wird die $i$-te Zeile von $\widetilde{\mathbf{P}}$ gleich ${\mathbf{e}}_i^\top=(0,\ldots,0,1,0,\ldots,0)$ gesetzt, wobei die $i$-te Komponente von ${\mathbf{e}}_i$ gleich $1$ ist.
  • Sei $\{\widetilde X_n,n\ge 0\}$ eine Markow-Kette mit der Anfangsverteilung ${\boldsymbol{\alpha}}$ und der Übergangsmatrix $\widetilde{\mathbf{P}}$.
• Außerdem sei $\{Z_n, n\ge 0\}$ eine Folge von unabhängigen und Exp$(1)$-verteilten Zufallsvariablen, die von $\{\widetilde X_n\}$ unabhängig sind.
• Mit Hilfe der Folgen $\{Z_n, n\ge 0\}$ und $\{\widetilde X_n,n\ge 0\}$ konstruieren wir nun einen Markow-Prozess $\{X_t,t>0\}$, dessen Trajektorien die Form

  $$X_t=\sum_{n=0}^\infty \widetilde X_n{1\hspace{-1mm}{\rm I}}(S_n\le t<S_{n+1})$$ (42)

  
  
  haben, wobei $0=S_0<S_1<\ldots$ eine Folge von zufälligen (Sprung-) Zeitpunkten ist:

Schritt 1$\;$ Sei $S_0=0$ und $Z_0^\prime=Z_0/q(\widetilde X_0)$, wobei $Z_0^\prime=\infty$ gesetzt wird, falls $q(\widetilde X_0)=0$.

• Die Zufallsvariable $Z_0^\prime$ ist die Aufenthaltsdauer des zu konstruierenden Markow-Prozesses $\{X_t\}$ im (zufälligen) Anfangszustand $\widetilde X_0$, der zum Zeitpunkt $S_0=0$ gewählt wird.
• Dabei gilt $P(Z_0^\prime>x\mid \widetilde X_0=i)={\rm e}^{-q(i)x}$ für jedes $i\in E$ mit $P(\widetilde X_0=i)>0$; $\; x\ge 0$.

Schritt 2$\;$ Sei $S_1=S_0+Z_0^\prime$ und $X_t=\widetilde X_0$ für $S_0=0\le t<S_1$, wodurch die Trajektorie von $\{X_t\}$ bis zum ersten Sprungzeitpunkt $S_1$ gegeben ist.

Schritt 3$\;$ (analog zu Schritt 1) Sei $Z_1^\prime=Z_1/q(\widetilde X_1)$, wodurch

• die Aufenthaltsdauer von $\{X_t\}$ im Zustand $\widetilde X_1$ gegeben ist, der zum Zeitpunkt $S_1$ gewählt wird.
• Dabei gilt $P(Z_1^\prime>x\mid \widetilde X_1=i)={\rm e}^{-q(i)x}$, falls $P(\widetilde X_1=i)>0$.

Schritt 4$\;$ Sei $S_2=S_1+Z_1^\prime$ und $X_t= \widetilde X_1$ für $S_1\le t<S_2$.

$\;$ $\vdots$

Schritt ${\bf 2} {\mathbf{n}}{\bf +1}$$\;$ Wir nehmen nun an, dass die Größen $Z_0^\prime,Z_1^\prime,\ldots,Z_{n-1}^\prime,S_0,S_1,\ldots, S_n$ und $\{X_t,t\in[0,S_n)\}$ für ein $n\ge 1$ bereits definiert worden sind, und setzen $Z_n^\prime=Z_n/q(\widetilde X_n)$.

Schritt ${\bf 2} ({\mathbf{n}}+{\bf 1})$$\;$ Sei $S_{n+1}=S_n+Z_n^\prime$ und $X_t=\widetilde X_n$ für $S_n\le t<S_{n+1}$.

Beachte

$\;$

• Auf diese Weise lassen sich die Trajektorien von $\{X_t, t\ge 0\}$ für beliebige $t\ge 0$ konstruieren, weil man sich leicht überlegen kann, dass $P(\lim_{n\to\infty}S_n=\infty)=1$.
• Somit ist durch das oben beschriebene Konstruktionsprinzip ein Algorithmus zur Simulation des zeitstetigen Prozesses $\{X_t, t\ge 0\}$ gegeben, wobei vorausgesetzt wird, dass Algorithmen
  • zur Simulation der Folge $\{Z_n, n\ge 0\}$ von unabhängigen und Exp$(1)$-verteilten Zufallsvariablen sowie
  • der eingebetteten Marlow-Kette $\{\widetilde X_n,n\ge 0\}$ (vgl. Übungsaufgabe 3.7)
  vorhanden sind.
• Außerdem kann man zeigen, dass die endlich-dimensionalen Verteilungen des Prozesses $\{X_t, t\ge 0\}$ die Faktorisierungeigenschaft besitzen, die in der Definitionsgleichung (10) von Markow-Prozessen postuliert wird.

Theorem 2.18   Der in $(\ref{kon.mar.pro})$ gegebene stochastische Prozess $\{X_t, t\ge 0\}$ ist ein homogener Markow-Prozess.

Beweis

$\;$

• Der Einfachheit wegen geben wir hier lediglich eine Beweisskizze an.
  • Einen ausführlicheren Beweis kann man beispielsweise in Resnick (1992), S. 378-379 finden.
  • Dabei betrachten wir hier nur den folgenden Spezialfall: Sei $\alpha_i>0$ und $q_{ij}>0$ für beliebige $i,j\in\{1,\ldots,\ell\}$ mit $i\not= j$.
• Sei $\{N_t,\, t\ge 0\}$ der Zählprozess der Sprungzeitpunkte $S_1,S_2,\ldots$ mit $N_t=\max\{n:\,S_n\le t\}$.
• Dann ergibt sich unmittelbar aus dem Konstruktionsprinzip des stochastischen Prozesses $\{X_t,\,t\ge 0\}$, dass
  

  $${P(X_0=i_0,X_{t_1}=i_1,\ldots,X_{t_n}=i_n)}$$

  $$= \sum_{m_1,\ldots,m_n\ge 0}P(\tilde X_0=i_0, N_{t_1}=m_1,\tilde X_{m_1}=i_1,N_{t_2}=m_1+m_2,\tilde X_{m_1+m_2}=i_2,$$

  $$\hspace{4cm}\ldots, N_{t_n}=m_1+\ldots+m_n,\tilde X_{m_1+\ldots+m_n}=i_n)>0$$

  
  
  für beliebige $n=0,1,\ldots,\; i_0,i_1,\ldots,i_n\in E,\; 0\le t_1\le\ldots \le t_n$.
• Hieraus und aus der ,,Gedächtnislosigkeit'' der Exponentialverteilung ergibt sich, dass
  

  $${P(X_0=i_0,X_{t_1}=i_1,\ldots,X_{t_n}=i_n)}$$

  $$= \sum_{m_1,\ldots,m_n\ge 0}P(\tilde X_0=i_0)P( N_{t_1}=m_1,\tilde X_{m_1}=i_1\mid \tilde X_0=i_0)$$

  $$P(N_{t_2}=m_1+m_2,\tilde X_{m_1+m_2}=i_2\mid N_{t_1}=m_1,\tilde X_{m_1}=i_1)$$

  $$\vdots$$

  $$P(N_{t_n}=m_1+\ldots+m_n,\tilde X_{m_1+\ldots+m_n}=i_n\mid N_{t_{n-1}}=m_1+\ldots+m_{n-1},\tilde X_{m_1+\ldots+m_{n-1}}=i_{n-1})$$

  $$= \sum_{m_1,\ldots,m_n\ge 0}P(\tilde X_0=i_0)P( N_{t_1}=m_1,\tilde X_{m_1}=i_1\mid \tilde X_0=i_0)$$

  $$P(N_{t_2-t_1}=m_2,\tilde X_{m_2}=i_2\mid \tilde X_0=i_1)\; \ldots\; P(N_{t_n-t_{n-1}}=m_n,\tilde X_{m_n}=i_n\mid \tilde X_0=i_{n-1})$$

  $$= P(\tilde X_0=i_0) \sum_{m_1=0}^\infty P( N_{t_1}=m_1,\tilde X_{m_1}=i_1\mid \tilde X_0=i_0)$$

  $$\sum_{m_2=0}^\infty P(N_{t_2-t_1}=m_2,\tilde X_{m_2}=i_2\mid \til... ...n=0}^\infty P(N_{t_n-t_{n-1}}=m_n,\tilde X_{m_n}=i_n\mid \tilde X_0=i_{n-1})\,.$$

  
  

• Es gilt also

  $$P(X_0=i_0,X_{t_1}=i_1,\ldots,X_{t_n}=i_n)=\alpha_{i_0}p_{i_0i_1}(t_1)p_{i_1i_2}(t_2-t_1) \;\ldots\;p_{i_{n-1}i_n}(t_n-t_{n-1})\,,$$ (43)

  
  
  wobei $\alpha_i=P(\widetilde X_0=i)=P(X_0=i)$ und
  $$p_{ij}(h)=\sum_{m=0}^\infty P( N_{h}=m,\tilde X_m=j\mid \tilde X_0=i)\qquad \Bigl(=P(X_h=j\mid X_0=i)\Bigr)\,.$$

• Aus (43) ergibt sich insbesondere, dass $p_{ij}(h_1+h_2)=\sum_{k\in E} p_{ik}(h_1)\;p_{kj}(h_2)$ für beliebige $i,j\in E$ und $h_1,h_2\ge 0$.
• Damit ist gezeigt, dass die endlich-dimensionalen Verteilungen des Prozesses $\{X_t, t\ge 0\}$ die Faktorisierungeigenschaft (10) besitzen.
  
  $\Box$

Wir zeigen nun, dass der in diesem Abschnitt konstruierte stochastische Prozess $\{X_t,\,t\ge 0\}$ der ,,richtige'' Markow-Prozess ist, d.h., seine Intensitätsmatrix ist gleich der vorgegebenen Matrix ${\mathbf{Q}}$.

• Hierfür muss gezeigt werden, dass sich die Übergangswahrscheinlichkeiten $p_{ij}(h)$ des Markow-Prozesses $\{X_t,\,t\ge 0\}$ durch die ,,lokalen'' Charakteristiken $\{q(i)\}_{i\in E}$ und $\widetilde{\mathbf{P}}=(\widetilde p_{ij})_{i,j\in E}$ ausdrücken lassen.
• Dabei sagt man, dass $i\in E$ ein absorbierender Zustand ist, falls $q(i)=0$.

Theorem 2.19   Für beliebige $i,j\in E$ und $h\ge 0$ gilt

$$p_{ij}(h)=\delta_{ij}{\rm e}^{-q(i)h}+\int_0^hq(i){\rm e}^{-q(i)t} \sum_{k\neq i}\widetilde p_{ik}p_{kj}(h-t)\, {\rm d}t\,.$$ (44)

Insbesondere gilt $p_{ij}(h)=\delta_{ij}$ für beliebige $j\in E$ und $h\ge 0$, wenn $i\in E$ ein absorbierender Zustand ist.

Beweis

$\;$

• So wie im Beweis von Theorem 2.15 können wir ohne Einschränkung der Allgemeinheit annehmen, dass $P(X_0=i)>0$ für jedes $i\in E$.
• Es ist klar, dass sich die Übergangswahrscheinlichkeiten $p_{ij}(h)$ als Summe $p_{ij}(h)=I_{ij}(h)+I^\prime_{ij}(h)$ darstellen lassen, wobei
  $$I_{ij}(h)=P(X_h=j,S_1>h\mid X_0=i)$$   und$$\qquad I^\prime_{ij}(h)=P( X_h=j,S_1\le h\mid X_0=i)\,.$$

• Für die Zerlegungskomponenten $I_{ij}(h)$ und $I^\prime_{ij}(h)$ gilt dann
  $$I_{ij}(h)=\left\{\begin{array}{ll}P(Z^\prime_0>h\mid \widetilde X... ...,, & \mbox{falls $i=j$,}\\ 0\,, & \mbox{falls $i\neq j$,} \end{array}\right.$$
  und
  

  $$I^\prime_{ij}(h) = \sum_{k\neq i}\int_0^h \frac{P(X_h=j, S_1\in {\rm d}t,\widetilde X_1=k,\widetilde X_0=i)} {P(\widetilde X_0=i)}$$

  $$= \sum_{k\neq i}\int_0^h P(X_h=j\mid X_t=k)P\Bigl(\frac{Z_0}{q(i)} \in {\rm d}t\Bigr)P(\widetilde X_1=k\mid \widetilde X_0=i)$$

  $$= \int_0^hq(i){\rm e}^{-q(i)t}\sum_{k\neq i}\widetilde p_{ik} p_{kj}(h-t)\, {\rm d}t\,.$$

  
  

• Falls $i\in E$ ein absorbierender Zustand ist, dann verbleibt der in diesem Abschnitt konstruierte Prozess $\{X_t, t\ge 0\}$ für immer im Zustand $i$, sobald er diesen Zustand zum ersten Mal erreicht. Somit gilt $p_{ij}(h)=\delta_{ij}$ für beliebige $j\in E$ und $h\ge 0$.
  
  $\Box$

Korollar 2.3   Für beliebige $i,j\in E$ gilt

$$p_{ij}^{(1)}(0+)=q_{ij}=\left\{\begin{array}{ll} -q(i)\,, & \mbox... ...s $i=j$},\\ \widetilde p_{ij}q(i) & \mbox{falls $i\neq j$.} \end{array}\right.$$ (45)

Beweis

$\;$ Um (45) zu beweisen, genügt es, in (44) die Ableitung bezüglich $h$ zu bilden und danach den Grenzwert für $h\downarrow 0$ zu betrachten.

$\Box$

Beachte

$\;$ Wenn man die Formeln (13) und (45) miteinander vergleicht, dann erkennt man, dass die Intensitätsmatrix des in diesem Abschnitt konstruierten Markow-Prozesses $\{X_t, t\ge 0\}$ mit der vorgegebenen Matrix ${\mathbf{Q}}$ übereinstimmt.

Beispiel

$\;$

• Der in diesem Abschnitt konstruierte Markow-Prozess $\{X_t, t\ge 0\}$ heißt Geburts- und Todesprozess, wenn $\widetilde p_{i,i-1}+\widetilde p_{i,i+1}=1$ für beliebige $1<i<\ell$ und $\widetilde p_{12}= \widetilde p_{\ell,\ell-1}=1$ gilt.
• Die Produkte $\widetilde p_{i,i+1}q(i)$ und $\widetilde p_{i,i-1}q(i)$ heißen Geburtsrate bzw. Sterberate.
• Diese Begriffsbildungen lassen sich damit begründen, dass die Größen $\widetilde p_{i,i+1}q(i)$ und $\widetilde p_{i,i-1}q(i)$ gemäß Korollar 2.3 mit den Übergangsintensitäten $q_{i,i+1}$ und $q_{i,i-1}$ für die Übergänge $i\to i+1$ bzw. $i\to i-1$ im Sinne der Definitionsgleichung (13) übereinstimmen.