Stochastic Processes & Markov Chains

Part of the Statistics for Machine Learning series.

Stochastic Processes

:::Remark

For these notes we assume that space is discrete finite or discrete infinite countable. The more general case can be read here.

:::

:::Definition (Stochastic process).

A sequence of random variables $(X_n){n \geq 0}$ is a discrete stochastic process if $n \in \mathbb{N}$ and a continuous stochastic process if $n \in \mathbb{R}^+$ with the initial state $X_0$. We have that each $X_i$ is independent and identically distributed, but there is some dependence on the previous $X$.

:::

:::Definition (Discrete-time Markov Chain).

A discrete-time Markov Chain consists of a tuple $(\lambda, P)$ over some probability space $(\Omega, \mathcal{E}, P)$ where

• the initial distribution is a probability measure $\lambda: S \to [0, 1]$ with $\sum_i \lambda_i = 1$ over a finite or countable state space $S$
• and the transition matrix $P = (p(x, y)){x,y \in S}$ with finite or continuous indices and with $p(x, y) \in [0,1]$ is called stochastic if and only if the sum of each row is one $\sum p(x, y) = 1$ for a fixed $x \in S$. We call $P$ homogenous if it doesn't change and inhomogenous $P_n$ if it changes at time $n$

is a stochastic process if and only if the following properties hold

• the initial state follows $P(X_0 = x) = \lambda(x)$ for some $x \in S$
• a state only depends on its predecessor, i.e. the so called Markov property holds $P(X_n = x_n \mid X_{n-1}=x_{n-1}) = p(x_{n-1}, x_n)$ for all $x_i \in S$

We then write $X = (X_n)_{n \geq 0} \sim \text{Markov}(\lambda, P)$.

:::

:::Proposition

The following proposition tells us the probability of states

$$P(X_0 = x_0, X_1 = x_1, \cdots, X_n=x_n) = \lambda(x_0) \prod_{i=1}^n p(x_{i-1}, x_i)$$

:::

:::Example (Time-n transition probability).

In the following a linear algebra perspective is useful. Suppose we wish to know what the probability of a state will be after $n$ steps.

:::