VO Stochastic Processes - Zusammenfassung Prüfung

From StatWiki
Jump to: navigation, search

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 <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) \,.

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 \,.