0x402 Stochastics
- 1. Markov Process
- 2. Stationary Process
- 3. Renewals
- 4. Queues
- 5. Martingales
- 6. Diffusion Process
- 7. Reference
1. Markov Process
1.1. Markov Chain
Definition (Markov chain) The process \(X\) is a Markov chain if it has the Markov property:
Definition (homogeneous) A Markov chain \(X\) is called homogeneous if
The transition matrix \(P=(p_{ij})\) is the \(|S| \times |S|\) matrix of transition probabilities \(p_{ij} = P(X_{n+1} = j | X_n = i)\)
Theorem (Chapman-Kolmogorov) The n-step transition matrix \(P(m, m+n) = (p_{ij}(m, m+n)) = P^n\) where \(p_{ij}(m, m+n) = P(X_{m+n} = j | X_m = i)\)
Evolution of the chain is determined by the transition matrix \(P\) and initial mass function \(\mu\), many questions about the chain is thus largely reducible to the study of matrices.
1.1.1. Notations
1.1.1.1. State Notations
Let \(P_i, E_i\) denote the probability conditional on \(X(0) = i\):
Definition (recurrent state, transient state) State \(i\) is called recurrent if
The probability of eventual return to \(i\), starting from \(i\) is 1. Otherwise it is called transient
Definition (positive) For a recurrent state \(i\), \(i\) is called positive if the mean recurrence time \(\mu_i < \infty\), otherwise it is called null
where \(f_{i,j}(n) = P_i(X_1 \neq j, X_2 \neq j, ..., X_{n-1} \neq j, X_n = j)\) is the first passage times
Definition (periodic) The period \(d(i)\) of a state \(i\) is defined by \(d(i) = gcd \{ n: p_{ii}(n) > 0 \}\), \(i\) is periodic if \(d(i) > 1\) otherwise aperiodic
Definition (ergodic) A state is called ergodic if it is recurrent, positive and aperiodic
ergodicity
Ergodicity is a more general concept whose statement is the time average of trajectory almost equals the ensemble average
1.1.1.2. Chain Notations
Defintion (communication) \(i\) is said to communicate with \(j\) with notation \(i \to j\) if the chain visits state \(j\) with strictly positive prob starting from \(i\). and they intercommunicate if \(i \to j\) and \(j \to i\)
Defintion (closed, irreducible) A set \(C\) of states is called
- closed: if \(p_{i,j} = 0\) for all \(i \in C, j \notin C\)
- irreducible: if \(i,j\) intercommunicate for all \(i,j \in C\)
Theorem (decomposition) The state space \(S\) can be partitioned uniquely as
where \(IT\) is the set of transient states, and \(C_i\) are irreducible closed sets of recurrent states
1.1.2. Random Walk
The simple random walk on the integers have state space \(S = \{ 0, 1, -1, 2, -2, ... \}\) and transition probabilities:
Gambler's ruin
A gambler starts with \(k\) units and ends with either \(0\) or \(N\). Every turn it increases money by 1 units with probability \(p\), otherwise decrease 1 unit with probability \(q=1-p\). Let \(p_k\) be the probability of ultimate ruin starting from \(k\), then using the law of total probability (i.e \(P(A) = \sum_i P(A|B_i)P(B_i)\)), we know
Solving this gives the solution
when \(p=1/2\), this simplifies to \(p_k = 1 - k/N\)
Mean time \(D_k\) to reach the absorbing barriers has similar formula
Solving this gives the solution
One useful technique for simple random walk is to count the number of sample paths
Let \(S_n = a + \sum_{i=1}^n X_i\) where \(S_0 = a\) and move with \(n\) steps. It is easy to see
where the first term \(N_n(a,b)\) is the number of path from \((0, a)\) to \((n,b)\)
Theorem (reflection) among all paths from \((0,a)\) to \((n,b)\) the number of paths which contain some point \((k,0)\) can be written as
This can be seen by reflecting the path along the x-axis
1.2. Continuous-time Markov Process
Now generalize the discrete time to the continuous time: \(X = \{ X(t) | t \geq 0 \}\), states are still countable
Definition (Markov property) The process \(X\) satisfies Markov property if
when \(t_i\) is an increasing sequence
Definition (transition probability)
It is homogeneous if \(p_{ij}(s, t) = p_{ij}(0, t-s)\) for all \(i,j,s,t\) and we only write \(p_{ij}(t-s)\) to denote \(p_{ij}\)
2. Stationary Process
Definition (strongly stationary) The process \(X = \{ X(t) | t \geq 0 \}\), taking values in \(R\), is called strongly stationary if the families
have the same joint distribution, for all given \(t_1, ..., t_n\) and \(h > 0\)
Instead of the finite-dimensional joint distribution (or fdds), covariance also characterize the joint distribution, which gives the weakly stationary
Definition (weakly stationary) The process \(X = \{ X(t) | t \geq 0 \}\) is called weakly stationary if for all \(t_1, t_2\), \(h > 0\)
3. Renewals
Definition (renewal process) A renewal process \(N= \{ N(t): t \geq 0 \}\) is a process for which
where \(T_0=0\) and
and \(X_i\) are iid non-negative random variables
3.1. Poisson Process
If the \(X_i\) are exponentially distributed, then \(N\) is a Poisson process.
Definition (Poisson process) A Poisson process with intensity \(\lambda\) is a process \(N = \{ N(t) : t \geq 0 \}\) taking values in \(S = \{ 0, 1, 2, ... \}\) such taht
Additionally \(N(0) = 0, N(s) \leq N(t)\) for \(s < t\) and \(N(t) - N(s)\) is independent of the times of emissions during \([0, s]\)
Bernoulli process and Poisson process
It can also be interpreted as a generalization of Bernoulli process to the continuous space
Definition (Bernoulli process) Let \(S = \{ 0, 1, 2 ... \}\) and define the Markov chain \(Y\) by
Theorem (distribution of Poisson process) The random variable \(N(t)\) has the Poisson distribution with parameter \(\lambda t\)
An alternative formulation is to use the arrival times: \(T_0, T_1, ...\) where \(T_n\) is the time of the n-th arrival
The interarrival times are random variables \(U_0, U_1, ...,\)
The random variables \(U_0, U_1, ...\) are independent, each having the exponential distribution with parameter \(\lambda\)
3.2. Limit Theorems
4. Queues
5. Martingales
Definition (martingale) A sequence \(Y = \{ Y_n : n \geq 0 \}\) is a martingale with respect to the sequence \(X = \{ X_n : n \geq 0 \}\) if, for all \(n \geq 0\)
Note a Markov chain might not be Martingales, and vice versa
simple martingale
Let \(X_1, X_2, ...\) be independent variables with zero means. The sequence of partial sum \(S_n = X_1 + X_2 + ... + X_n\) is a martingale wrt \(X\)
6. Diffusion Process
Diffusion process is indexed by continuous time and taking values in real line.
6.1. Brownian Motion, Wiener Process
Brownian Motion can be seen as the limit of the random walks
Definition (Brownian Motion, Wiener process) A Wiener process \(W = \{ W(t) : t \geq 0 \}\) has to satisfy
- \(W\) has independent increments
- \(W(s+t) - W(s)\) is distributed as \(N(0, \sigma^2 t)\) for all \(s,t \geq 0\)
- sample paths of \(W\) is almost surely continuous
It can be shwon to have the following properties:
- the sample paths are continuous functions of \(t\)
- almost all sample paths are nowhere diffeerntiable functions of \(t\)
7. Reference
- CMU 36410 Introduction to Probability Modeling notes
- Probability and Random Processes