% Steffen Gr?nneberg (steffeng@math.uio.no)


\documentclass[a4paper, norsk,12pt]{amsart}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage[section]{placeins}
\usepackage{amsmath, amssymb, a4, graphicx, verbatim, listings, alltt, babel, paralist, mathrsfs, ae, varioref, natbib, epic} %includes most standard packages

\def\eps{\varepsilon}

\renewcommand{\labelenumi}{\alph{enumi})} % Our ``enumerate''-enviroment should enumerate according to the lower-case alphabet

%Defining which way theorems etc should be counted:

\theoremstyle{plain} % use "default" font

\newtheorem{theorem}{Teorem}
% Should be \newtheorem{theorem}{Theorem}[section] if we would like the numbering to take the section number into account.
\newtheorem{lemma}[theorem]{Lemma}

% In this way, all other enviroments use the same counter:
\newtheorem{corollary}[theorem]{Korollar}

\theoremstyle{definition} % use "definition-style" font for the rest
\newtheorem{definition}[theorem]{Definisjon}
\newtheorem{example}[theorem]{Eksempel}

% Sets the paragraphindent to zero and the paragraph-skip to 3mm.
\setlength{\parindent=0mm}
\setlength{\parskip = 3mm plus 0.5mm minus 0.5mm}

\begin{document}

\title{Forelesning i stk1130}
\author{Steffen Gr?nneberg (steffeng@math.uio.no)}
\date{March 07, 2007}
\begin{abstract}
Det anbefales at man \TeX'er den kommende obligen, og her er et lite eksempel p? relevant \TeX-kode. \TeX \ er uten tvil det fremtidige masteroppgaver og STK2010/MAT-STK2010-prosjekter kommer til ? skrives i, s? det er lurt ? hoppe i det s? fort som mulig. Her brukes amstex-pakken, som er en macropakke for \TeX \ og \LaTeX, og er vanlig ? bruke i mange matematiske publikasjoner.
\end{abstract}
\maketitle

\section{Temaer for dagen}
\begin{itemize}
\item To viktige definisjoner
\item Generatormatriser
\item Innebygde kjeder
\item Klassifikasjon av Markovprosesser
\end{itemize}

\section{To viktige definisjoner}
Minner om f?lgende. En funksjon $f$ er $o(\Delta t)$ hvis
$$
\lim_{\Delta t \rightarrow 0} \frac{f(\Delta t)}{\Delta t} = 0,
$$
alts? g?r $f$ fortere mot null enn $\Delta t$.

Videre er
$$
\delta_{ji} = \left\{ \begin{array}{ll} 1, & i = j\\ 0, & i \neq j \end{array} \right.
$$
\emph{Kroneckers deltasymbol}.

\section{Generatormatriser}
La
$$
X = \{ X(t) : 0 \leq t < \infty \}
$$
v?re en Markovprosess som tar verdier i et diskret (dvs tellbart) indekssett $I$. F.eks $I = \{ 0,1,2, \ldots, N\}$,  $I = \{ 0,1,2,\ldots \}$, $I = \{ 0, 1, -1, 2, -2, \ldots \}$, $I = \mathbb{Z}^2$, $I= \mathbb{Q}$.

Husk at
$$
p_{ji}(t) = Pr \{ X(t) = j | X(0) = i \}
$$
er \emph{overgangssannsynlighetene} for prosessen og
$$
P(t) = (p_{ji}(t))
$$
er \emph{overgangsmatrisen} (av st?rrelse $I\times I$). Mer at $p_{ji}$ er \emph{funksjoner}!

En \emph{generatormatrise} $Q$ er et slags differensial av $P(t)$. Den er en $I \times I$-matrise $(q_{ji})$ (av tall!) hvor $q_{ij}$ representerer \emph{overgangsintensiteten} fra $j$ til $i$ n?r $j \neq i$.

\begin{definition}
Generatormatrisen $Q$ er gitt ved
$$
q_{ji} =  p_{ji}'(0) =_{\text{def}} \lim_{\Delta t \rightarrow 0^+} \frac{p_{ji}(\Delta t) - p_{ji}(0)}{\Delta t}.
$$
\end{definition}

For ? komme til passende generelle resultater gj?r vi f?lgende antagelser.
\newtheorem*{standardantagelser}{Standardantagelser} % Defines a new theorem-like enviroment which should not be numbered (thereby the star)

\begin{standardantagelser}
La $s,t > 0$.
\begin{enumerate}
\item $p_{ji}(t) \geq 0$
\item $\sum_{j \in I} p_{ji}(t) = 1$
\item $\sum_{k \in I} p_{jk}(s) p_{ki}(t) = p_{ji}(s+t)$ (\emph{Chapman-Kolmogorov})
\item $p_{ji}$ er kontinuerlig for $t>0$ og
$$
\lim_{t \rightarrow 0^+} p_{ji}(t) =  \delta_{ji} = \left\{ \begin{array}{ll} 1, & i = j\\ 0, & i \neq j \end{array} \right.
$$
\end{enumerate}
\end{standardantagelser}

\begin{theorem}
Under standardantagelsene finnes $Q$ (hvor diagonalelementene har lov til ? v?re $-\infty$).
\end{theorem}
\begin{proof}
Ikke pensum. Bruker noe analyse, men kun definisjonen av $\limsup$ og $\liminf$ trengs! Finnes i \citet[Chap. 14]{karlin81}.
\end{proof}

Merk at definisjonen til $p_{ji}(t)$ gir
$$
p_{ji}(0) = \delta_{ji} = \left\{ \begin{array}{ll} 1, & i = j\\ 0, & i \neq j \end{array} \right. .
$$

Anta s? $i \neq j$. Har
$$
q_{ji} =_{\text{def}} p_{ji}'(0) =_{\text{def}} \lim_{\Delta t \rightarrow 0^+} \frac{p_{ji}(\Delta t) - p_{ji}(0)}{\Delta t} = \lim_{\Delta t \rightarrow 0^+} \frac{p_{ji}(\Delta t)}{\Delta t}
$$
og
\begin{multline*}
q_{ii} =_{\text{def}} p_{ii}'(0) =_{\text{def}} \lim_{\Delta t \rightarrow 0^+} \frac{p_{ii}(\Delta t) - p_{ii}(0)}{\Delta t}\\
 = \lim_{\Delta t \rightarrow 0^+} \frac{p_{ii}(\Delta t) -1}{\Delta t} = - \lim_{\Delta t \rightarrow 0^+} \frac{1 - p_{ii}(\Delta t)}{\Delta t}.
\end{multline*}

La $i \neq j$. Merk s? at hvis vi definerer $r_{ji}(\Delta t)$ slik at
$$
p_{ji}(\Delta t) = q_{ji} \Delta t + r_{ji}(\Delta t)
$$
er det en slags rest. Har at $r_{ji}(\Delta t) = o(\Delta t)$ siden
$$
\lim_{\Delta t \rightarrow 0^+} \frac{p_{ji}(\Delta t)}{\Delta t} = q_{ji} + \lim_{\Delta t \rightarrow 0^+} \frac{r_{ji}(\Delta t)}{\Delta t}
$$
som gir
$$
\lim_{\Delta t \rightarrow 0^+} \frac{r_{ji}(\Delta t)}{\Delta t} = 0.
$$
Alts? kan vi g? litt videre med utregningen av $q_{ii}$. Har
\begin{multline*}
q_{ii} = - \lim_{\Delta t \rightarrow 0^+} \frac{1 - p_{ii}(\Delta t)}{\Delta t} = - \lim_{\Delta t \rightarrow 0^+} \frac{1}{\Delta t} \sum_{j \neq i} p_{ji}(\Delta t) = - \lim_{\Delta t \rightarrow 0^+} \frac{1}{\Delta t} \sum_{j \neq i} q_{ji} \Delta t + r_{ji}(\Delta t)\\
= - \sum_{j \neq i} q_{ji} + \lim_{\Delta t \rightarrow 0^+} \frac{\sum_{j \neq i} r_{ji}(\Delta t)}{\Delta t}.
\end{multline*}
Hvis
$$
\sum_{j \neq i} r_{ji}(\Delta t) = o(\Delta t)
$$
(f.eks hvis indekssettet $I$ er endelig), f?r vi alts? 
$$
q_{ii} = - \sum_{j \neq i} q_{ji}.
$$

\subsection{Oppsummering}
Hvis $q_{ii}$ er endelig kan man oppsummere de foreg?ende resultatene ved
$$
p_{ji}(\Delta t) = \delta_{ji} + q_{ji} \Delta t + o(\Delta t)
$$
fra samme logikk som argumentet der $r_{ji}$ ble brukt. (Husk at $q_{ii} \leq 0$!)

Dette gj?r det er lett ? finne $Q$ hvis fordelingen av en prosess er gitt p? infinitdesimalform!

\subsection{Eksempel med Poisson-prosessen}
Har
$$
p_{ji}(\Delta t) = \left\{ \begin{array}{ll} \lambda \Delta t + o(\Delta t), & j = i+1\\ 1 - \lambda \Delta t + o(\Delta t), & j = i\\ o(\Delta t), & j \geq i +2\\ 0, & \text{ellers} \end{array} \right.
$$
Ser at $q_{ii} = p_{ii}'(0) = \left. \frac{\partial}{\partial t} e^{-\lambda t} \right|_{t = 0} = - \lambda > - \infty$, s? fra oppsummerende kommentar ser man at
$$
q_{ji} = \left\{ \begin{array}{ll} - \lambda, & i = j\\ \lambda, & j = i+1 \end{array} \right. = (-1)^{\delta_{ji}} \lambda .
$$
(Poenget er at dette \emph{ikke} blir noe vanskelig n?r man har en infinitdesimalbeskrivelse av prosessen.)
% Hvis man skulle skrive ned matriseformen for $Q$ kunne man skrive
%% \subsection{F?dsel og d?dsprosesser}
%% For en F?dsel og d?dsprosess med immigrasjon har man at
%% $$
%% p_{i+j,i}(\Delta t) = \left\{ \begin{array}{ll} 
%% \mu i \Delta t + o(\Delta t), & j=-1\\
%% (\nu + \lambda i) \Delta t + o(\Delta t), & j = 1\\
%% 1 - [\nu + (\lambda + \mu)i]\Delta t + o(\Delta t), & j = 0\\
%% o(\Delta t), & ellers
%% \end{array} \right. .
%% $$
%% Man kunne kanskje tro at ? finne $Q$-matrisen n? ble komplisert - men fra den oppsummerende kommentaren er dette enkelt.

\section{Innebygde kjeder}

En Markovprosess $X$ som tar verdier p? en diskret mengde (f.eks $\{ 0,1,2, \ldots \}$) ser typisk slik ut.

\begin{figure}[htb]
\begin{center}
\input{process.epic}
\end{center}
\caption{En stokastisk prosess $X$}
\label{fig::process}
\end{figure}

Defin?r
$$
Y_n = X(W_n),
$$
som er en \emph{diskret Markovkjede}! (Markovegenskapen overf?res fra den kontinuerlige prosessen).

Har at
$$
W_0 = 0, \qquad{} W_{n+1} = \inf \{ t \geq W_n : X(t) \neq X(W_n) \}
$$

P? eksemplet er $Y_0 = 0$, $Y_1 = 1$, $Y_2 = 2$, $Y_3 = 1$.

Dette er den \emph{innebygde kjeden} til $X$. Ved ? kjenne simultantettheten til $\{Y_n \}$ og $\{W_n \}$ kan man svare p? alle sp?rsm?l ``av passende detaljniv?'' (hvis definisjon krever noe mer matte). Dessuten kan mange sp?rsm?l svares p? ved hjelp av $Y$ alene! Alts? kan vi overf?re kapittel 2-kunnskaper til den n?v?rende settingen -- uten avansert matematikk!

\begin{example}
La oss finne overgangsmatrisen til den innebygde kjeden for Poisson-prosessen.

{\bf{Merk:}} Poisson-prosessen virker kanskje litt kjedelig, men faktisk kan alle de kontinuerlig-tid Markovprosessene vi skal se p? konstueres utifra nettopp denne prosessen. Den er den kanoniske Markovprosessen med diskret tilstandsrom og kan generaliseres i mange interessante retninger.

Siden Poissonprosessen g?r opp ett og ett skritt etter en viss (endelig!) tid, f?r vi
$$
T = \left[ \begin{array}{cccc} 0 & \ldots & & \\ 1 & 0 & \ldots &\\ \vdots & 1 & 0 & \ldots\\ &\vdots &1 & \ldots \\ && \vdots& \ddots \end{array} \right].
$$
\end{example}

Vi gir n? definisjonen av den innebygde kjeden. Kaller overgangsmatrisen til den innebygde kjeden $T = (t_{ji})$.

F?rst, merk at 
$$
t_{ii} = \left\{ \begin{array}{ll} 0, & q_{ii} \neq 0 \\ 1, & q_{ii} = 0 \end{array} \right.
$$
fra v?r definisjon av den innebygde kjeden. (Fra at den kun blir v?rende i $i$ hvis den tilstanden er absorberende: Husk at $q_{ji}$ tolkes som \emph{intensiteter}!)

Videre lar vi
$$
t_{ji} = \lim_{\Delta t \rightarrow 0^+} \frac{p_{ji}(\Delta t)}{1 - p_{ii}(\Delta t)},
$$
motivert fra at $p_{ji}(\Delta t)/(1 - p_{ii}(\Delta t))$ er sannsynligheten for bevege seg fra $i$ til $j$, betinget p? at man beveger seg.

Dette er videre lik
$$
- \lim_{\Delta t \rightarrow 0^+} \frac{p_{ji}(\Delta t)/\Delta t}{ (p_{ii}(\Delta t) -1)/\Delta t} = - \frac{q_{ji}}{q_{ii}}
$$

Merk at hvis
$$
q_{ii} = -\sum_{j \neq i} q_{ji}
$$
er den innebygde kjedens overgangsmatrise $T$ bare en renormalisering av $Q$ for ? f? den til ? bli en stokastisk matrise!

Man kan vise at dette er den passende definisjonen, og at man kan g? fra ? kjenne fordelingsaspekter til ventetider og den innebygde kjeden til ? kjenne fordelingsaspekter til Markovprosessen -- og den andre veien.

\section{Klassifikasjon av Markovprosesser}
F?rst gis litt grunnleggende definisjoner, s? oppsummerer vi resultater for ? overf?re v?r diskret-Markovkjede kunnskap til denne settingen -- helt uten bevis. Bevis finnes i \citet{norris97} og krever ikke veldig mye matte (spesifikt kreves ikke m?lteori for de aller fleste resultatene).

\begin{definition}
En tilstand $j \in I$ \emph{kan n? en tilstand} $i \in I$, (skriver $i \rightarrow j$) hvis $p_{ji}(t) > 0$ for en $t \geq 0$.

To tilstander $i,j \in I$ \emph{kommuniserer} hvis $i \rightarrow j$ og $j \rightarrow i$. Skriver $i \leftrightarrow j$.
\end{definition}

Kommunikasjonsklasser, irredusiblitet og lukkede klasser er identisk definert som for Markovkjeder n?r man bytter ut definisjonen av $ i \rightarrow j$ med den over.

\begin{lemma} (Teorem 3.2.1 i \citet{norris97}\\
$p_{ji}(t) > 0$ for alle $t >0$ er \emph{ekvivalent} med at $p_{ji}(t) > 0$ for en $t > 0$.
\end{lemma}

Hvis
$$
p_{ji}(\Delta t) = \delta_{ji} + q_{ji} \Delta t + o(\Delta t)
$$
ser vi at to klasser kommuniserer hvis deres tilh?rende tilstander i den innebygde kjeden kommuniserer!

Dette gjelder ogs? generelt, selv n?r $p_{ji}$ ikke kan skrives p? den gitte m?ten.

La
$$
T_{ii} = \inf \{ t > W_1, X(t) = i| X(0) = i \}
$$
v?re f?rste tilbakekomsttid for tilstand $i \in I$. Hvis
$$
Pr \{ T_{ii} < \infty | X(0) = i \} = 1
$$
kalles tilstanden \emph{rekurent}, ellers er den \emph{transient}. (Merk at dette er en dikotomi!)

\begin{theorem}
En tilstand $i$ i Markovprosessen $X$ er rekurent hvis og bare hvis den er rekurent i den innebygde kjeden.
\end{theorem}

Dette medf?rer at rekurens (og dermed transiens) er en klasseegenskap ogs? for Markovprosesser.

Hvis en tilstand er rekurent (dvs har en endelig f?rste tilbakekomst-tid med sannsynlighet $1$) er vi interessert i om forventet f?rste tilbakekomst-tid er endelig. Da forventet lengde til tilbakekomst avhenger av ventetidene, trenger man mer enn kjennskap til den innebygde Markovkjeden.

\begin{theorem}
Anta Markovprosessen $X$ er ikke-eksplosiv med overgangsmatrise $P(t) = (p_{ij}(t))$ og generatormatrise $Q$.
Hvis $Q$ er irredusibel og positivt rekurent, vil
\begin{equation} \label{equ::mulim}
\lim_{t \rightarrow \infty} p_{ji}(t) = - \frac{1}{q_{jj} \mu_{jj}},
\end{equation}
hvor
$$
\mu_{ii} = \mathbb{E} \, T_{ii} = \mathbb{E} \left[ \, \inf \{ t > W_1, X(t)| X(0) = i \} \right] .
$$
Spesifikt, hvis tilstandsrommet er endelig er prosessen ikke-eksplosiv og grensen i likning \eqref{equ::mulim} finnes. Hvis grensen er positiv er $Q$ irredusibel.
\end{theorem}

Merk at per definisjon av den innebygde kjedens overgangsmatrise $T$ har samme redusibilitetsegenskaper som $Q$, og at man kan lett se om $Q$ er irredusibel ved ? tegne opp overgangsdynamikken til den innebygde kjeden.

\begin{corollary}
En Markovprosess p? et endelig tilstandsrom med en irredusibel generatormatrise er positivt rekurent.
\end{corollary}
\bibliography{references}
\bibliographystyle{biometrika}

\end{document}