From StatWiki

General

Given a probability space $(\Omega, \mathcal{A}, \mathbb{P}), \,$ a set $T \,$ called time space and a set $\mathcal{Z} \,$ called state space. A stochastic process $Z : T \times \Omega \to \mathcal{Z} \,$ is a function so that $Z(\cdot, \cdot) \,$ is jointly measurable, $Z(t, \cdot) \,$ is a random variable from $\Omega \,$ into $\mathcal{Z} \,$ and $Z(\cdot, \omega) \,$ is a measurable function called trajectory.

If $\mathcal{Z} \,$ is denumerable, the process is called discrete-state process, otherwise continuous-state process. If $T \,$ is denumerable one speaks of a process in discrete-time, otherwise of a process in continuous-time.

Discrete

A discrete-event process takes only a finite number of values in bounded time. A discrete-event process can be represented by a sequence $(\tau_n) \,$ and a process in discrete-time. $\tau_n \,$ are called jump times, $\tau_{n+1}-\tau_n \,$ are called sojourn times and the process in discrete-time is called embedded process.

Stationary & Homogenous

A process is strongly stationary if $X(t_1), X(t_2), \cdots \stackrel{d}{=} X(t_1+s), X(t_2+s), \cdots \,$ . A process is weakly stationary if it has constant expectation and variance over time. A process is homogeneous if it has stationary increments so that $X(t+u)\,|\,X(t) \,$ does not depend on $t \,$ . The expected visits of a process started in state $i \,$ to state $j \,$ is $v_{ij} = \sum_{n=0}^{\infty}p_{ij}^{(n)}. \,$ In matrix notation $V = \sum_{n=0}^{\infty}P^{(n)}. \,$ Let $T^{(i)} \,$ be the first return time $T^{(i)} = \inf\{n \ge 1: M_n = i\,|\, M_0=i\} \,$ .

State Properties

A state $i \,$ can have the following state-properties.

$j \,$ reachable: (written $j \rightharpoonup i \,$ ), if $\exists n: p_{ji}^{(n)} > 0 \,$ .
$j \,$ commuting: (written $j \rightleftharpoons i \,$ ), if $i = j \vee (i\rightharpoonup j \wedge j \rightharpoonup i) \,$ .
recurrent: if
- positive recurrent: if $E_i (T^{(i)}) < \infty \,$ .
- null recurrent: if $E_i (T^{(i)}) = \infty \,$
transient: if $\mathbb{P}_i(T^{(i)} < \infty) < 1 \,$ .

period $k \,$ : if $\mathcal{Z} \,$ is denumerable, $i \,$ is recurrent and $\gcd \{n: p_{ii}^{(n)} > 0\} = k \,$ .
periodic: if $i \,$ has period $k > 1 \,$ .
aperiodic: if $i \,$ does not have period $k > 1 \,$ ..
absorbing: if $\nexists j: i \rightharpoonup j \,$ .

$\rightleftharpoons \,$ defines partial-ordered equivalence classes on $\mathcal{Z}. \,$ A class $G_1 \,$ precedes $G_2 \,$ if $\exists i \in G_1, j \in G_2:i\rightharpoonup j \,$ . All states in a class possess the same state-property. A class has a class-properties if its states possess the corresponding state-property. A class is called maximal if it precedes no other class. A chain with only one class is irreducible, otherwise reducible. A positive recurrent, irreducible chain with period 1 is called ergodic. A process is called independent if $X(t) \perp X(s) \,$ . A random variable is called defective, it its distribution function does not converge to 1, so that $i \,$ is transient if $T^{(i)} \,$ is defective. A distribution $\pi \,$ is stationary if $\pi P = \pi \,$ , with $\pi_i = 0 \,$ if $i \,$ is transient.

Process Properties

The Chapman-Kolmogorov equation is a statement of the formula of the total probability modified by the Markov Property. It connects the distribution of a process at $t_3 \,$ with $t_1 \,$ through an intermediate time $t_2 \,$ , by $p_{ij}(t_1, t_3) = \sum_k p_{ik}(t_1, t_2) p_{kj}(t_2,t_3) \,$ . For homogeneous processes this implies $P^{(n)} = p^{(0)}P^{n} \,$ in discrete-time and $P(t+s)=P(t)P(s) \,$ in continuous-time. It is necessary but not sufficient for the Markov property, $X(t_{n+1})|X(t_{n}) \perp X(t_{n-1}), \dots, X(t_1) \,$ . A discrete-state Markov process is called Markov chain. A process has the Martingale property if $E(X(t_2)\,|\,X(t_1)) = X(t_1) \,$ .

Ergodic Coefficient

Define Dubrushin's coefficient of ergodicity as

$\rho_0(P) = \frac{1}{2} \sup_{i,j}\sum_k |p_{ik}-p_{jk}|$

with properties

$\rho_0(P) = \sup_{i,j}(1-\sum_k\min(p_{ik}, p_{jk})) \,$ .
$0 \le \rho_0(P) \le 1 \,$ .
the smaller $\rho \,$ the more independent (ergodic) the process. $\rho_0(P) = 0 \Leftrightarrow P \,$ has identical rows.
$\rho \,$ is sub-multiplicative. $\rho_0(P_1P_2) \le \rho_0(P_1)\rho_0(P_2) \,$

The following are equivalent

$P \,$ is ergodic.
$P \,$ has a unique stationary distribution.
$\exists n: \rho_0(P^{(n)}) < 1 \,$
$1/E_i(T^{(i)}) = \pi_i \,$ .
$P^n \rightarrow \mathbf{1}\pi \,$ . \quad (LLN)
$1/\sqrt{N}\sum_{n=1}^N X_n \mathop\rightarrow_d \pi \,$ exponentially fast. \quad (CLT)
$1/N \sum_{n=1}^N f(X_n) \mathop{\rightarrow}_{a.s.} \pi f \, \quad$ (Ergodic Theorem)

Continuous Time

By the Chapman-Kolmogorov equation, a homogeneous Markov chain in continuous time is determined by a semi-group of transition matrices. A semi-group $P(\cdot) \,$ is continuous if $\lim_{t\downarrow 0}p_{ii}(t) = 1 \,$ and equi-continuous if $\lim\inf_{t\downarrow 0} p_{ii}(t) = 1 \quad \forall i$

If $P \,$ is [equi-]continuous, than $p_{ij}(t) \,$ is uniformly [equi-]continuous. $P_{ii}(\cdot) \,$ is a sub-additative function.

For a small time interval $\Delta t\downarrow 0 \,$ , $p_{ij} = p_{ij}(\Delta t)=q_{ij}\Delta t + o(\Delta t) \,$ and $p_{ii}(\Delta t) = 1 + q_{ii} \Delta t + o(\Delta t) \,$ , so that the intensity matrix $Q \,$ has the form

$0 \le q_{ii} \le C \,$ for all $i \,$ and a constant $C \,$ .
$q_{ij} \ge 0 \,$ for $i \ne j \,$ .
$\sum_j q_{ij} = 0 \,$ for all $i \,$ .

with properties

$P(t) = \exp(Qt) = \sum_k (Qt)^k/k! \,$ .
$Q = \lim_{t\downarrow 0}(P(t)-P(0))/t=P'(t) \Bigr|_0 \quad \,$ (element-wise).
$q_{ii} = 0 \Leftrightarrow \forall t: p_{ii}(t) = 1 \Leftrightarrow i \,$ is absorbing.
The sojourn time at state $i \,$ is exponentially

distributed with rate $q_{ii} \,$ . Conditioned on leaving to state $j \,$ the sojourn time is exponential distributed with rate $q_{ij} \,$ .

The embedded process has transition matrix $S \,$ with

$s_{ij} = \begin{cases} 1 & i = j \wedge q_{ij} = 0 \\ 0 & i \ne j \wedge q_{ij} = 0 \\ 0 & i = j \wedge q_{ij} < 0 \\ \frac{q_{ij}}{-q_{ii}} & i \ne j \wedge q_{ij} < 0 \\ \end{cases}$

$\pi Q = 0 \Leftrightarrow \pi \,$ is stationary for $P(t) \,$ for all $t \,$ $\Rightarrow \nu_i \propto -q_{ii}\pi_i \,$ where $\nu \,$ is the stationary distribution of $S \,$ .

Death / Birth Process

A Markov chain in continuous time is called birth/death process if $\mathcal{Z} = \mathbb{N}_0 \,$ and

$q_{ij} = \begin{cases} -(\lambda_i+\mu_i) & i = j \\ \lambda_i & j = i + 1 \\ \mu_i & j = i - 1 \\ 0 & |i - j| > 1. \end{cases}$

A Poisson process is a birth/death process with $\lambda_i = \lambda \,$ and $\mu_i = 0 \,$ . A $M/M/1 \,$ queue is a birth/death process with $\lambda_i = \lambda \,$ and $\mu_i = \mu \,$ . Its embedded process is

positive recurrent for $p < 1/2 \,$ .
negative recurrent for $p = 1/2 \,$ .
transient for $p > 1/2 \,$ .

The $M/M/1 \,$ queue has the following properties.

$1/\lambda \,$ expected length of idle period.
$1/(\mu-\lambda) \,$ expected length of busy period.
$\mu/(\mu-\lambda) \,$ expected number of costumers in busy period.
$(\mu-\lambda)/\mu \,$ probability of being immediately severed.
$\lambda^2/(\mu^2-\mu\lambda) \,$ expected length of the queue.
$1/(\mu-\lambda) \,$ expected waiting time for not immediately served customers.
$\lambda/(\mu^2-\mu\lambda) \,$ expected overall waiting time.

Continuous Time & States

Assume that for a certain person the observed time $t \,$ till this persons death is the realization of a random variable $T \,$ with density $f(t) \,$ and distribution function $F(t) = P(T <t) = \int_0^t f(u) du.\,$ Then the survivor function, $S(t)\,$ is the probability that the survival time for this person is greater or equal to $t \,$ , so that $S(t) = P(T \ge t) = 1 - F(t). \,$ Also define the hazard function $h(t) \,$ as probability that an individual dies at time $t \,$ , given that the person has survived up to time $t, \,$

$h(t) = \lim_{\Delta t \downarrow 0} \left(\frac{ P(t \le T < t + \Delta t \,|\, T \ge t)} {\Delta t} \right),$

and the cumulative hazard function as $H(t) = \int_0^t h(u) du. \,$ Now using the definition of the condition probability and $\lim_{\Delta t \to 0} (F(t+\Delta t)-F(t))/\Delta t = f(t), \,$ can be written as $h(t) = f(t)/S(t)\,$ and $H(t) = - \log(S(t)) \,$

If $X_1, X_2, \dots \stackrel{\text{iid}}{\sim} DU(\{-1,1\}) \,$ than one defines a Wiener process $W(t) \,$ , starting from a random walk with step-size $\Delta x \,$ and step-frequency $\Delta t \,$ with $n=\lfloor t/\Delta t\rfloor \,$ steps in time span $t \,$ , by setting $\Delta x = \sqrt{\Delta t} \,$ and letting $\Delta t \to 0 \,$ , so that $W(t) = \lim_{\Delta t \to 0} \sum_{i=1}^{\lfloor t/\Delta t\rfloor} \sqrt{\Delta t} X_i \,$ . Define the Ornstein-Uhlenbeck process $U \,$ and Brownian bridge $B \,$ as $U(t)= \exp(-\alpha t)W(\exp(2\alpha t)) \,$ and $B(t) = W(t)\,|\,(W(1)=0) \,$ .