# VO Stochastic Processes - Zusammenfassung Prüfung

Von einer netten anonymen Quelle

# 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 $\mathbb{P}_i(T^{(i)} < \infty) = 1 \,$
• 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 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) \,$.

$W,U \,$ and $B \,$ Gaußprocess with expectation 0 and covariance $t_1 \,$, $\exp(-\alpha(t_2-t_1)) \,$ and $t_1(1-t_2) \,$.

• $W,U \,$ and $B \,$ are Markov processes.
• Only $W \,$ has Martingale property.
• Only $W \,$ has identical distributed increments.
• Only $B \,$ has dependent increments.
• Only $U \,$ is stationary.
• The loglikelihood-ratio test-static is asympothically $W \,$.
• The Kolmogorov-Smirnov test is asymptoically $B \,$.