Markov Chains and Stochastic Processes

Standard Brownian motion

A standard Brownian motion \{W(t)\}_{t\ge 0} is a continuous-time Gaussian process with W(0)=0, independent increments, and W(t)-W(s)\sim N(0,\,t-s) for 0\le s<t. Most computations reduce to two facts: W(t)\sim N(0,t), and for 0\le s\le t the covariance is \operatorname{Cov}(W(s),W(t))=\min(s,t). The second fact follows from writing W(t)=W(s)+[W(t)-W(s)], where the second term is independent of W(s). Hence E[W(s)W(t)]=\min(s,t) and E[W(t)]=0.

For a linear combination aW(s)+bW(t) with s<t, expand the variance with the covariance formula: \operatorname{Var}(aW(s)+bW(t))=a^2s+b^2t+2ab\,s. For example, \operatorname{Var}(W(1)+3W(4))=1+9\cdot 4+2\cdot 3\cdot 1=43. Such a combination is normal with mean zero, so a probability of the form P(aW(s)+bW(t)>c) equals 1-\Phi\bigl(c/\sqrt{\text{variance}}\bigr), where \Phi is the standard normal cdf.

Conditioning uses the same independence. Given W(s)=x, the variable W(t) is N(x,\,t-s), so E[W(t)\mid W(s)=x]=x and E[W(t)^2\mid W(s)=x]=(t-s)+x^2. For instance, E[W(6)^2\mid W(3)=-1]=3+1=4.

A product such as W(1)W(2) needs a moment calculation. Write W(1)W(2)=Z_1(Z_1+Z_2) with independent standard normals Z_1,Z_2. Then E[Z^2]=1 and E[Z^4]=3 give E[W(1)W(2)]=1 and E[(W(1)W(2))^2]=3+1=4, so the variance is 4-1=3.

When the mean is zero, the second moment equals the variance, since \operatorname{Var}(X)=E[X^2]-(EX)^2. The second moment exceeds the variance by the squared mean whenever the mean is nonzero. For W(2)+W(3), the mean is zero and \operatorname{Var}=2+3+2\cdot 2=9, which is also E[(W(2)+W(3))^2].

For the correlation between sums, expand the covariance bilinearly and use one \min term per pair of times. For X=W(1)+W(3) and Y=W(2)+W(4), \operatorname{Cov}(X,Y)=1+1+2+3=7, \operatorname{Var}(X)=6, and \operatorname{Var}(Y)=10, so \rho=7/\sqrt{60}.

Poisson process

A Poisson process with rate \lambda is a counting process \{N(t)\} with N(0)=0, independent increments, and N(t)-N(s)\sim\text{Poisson}(\lambda(t-s)). Its pmf is P(N(t)=n)=e^{-\lambda t}(\lambda t)^n/n!, so the rate can be read off from the coefficient of t in the exponent-free part of the mean.

For s\le t, N(t)=N(s)+[N(t)-N(s)] with an independent second term, so \operatorname{Cov}(N(s),N(t))=\operatorname{Var}(N(s))=\lambda\min(s,t).

Counts over disjoint intervals are independent Poisson variables, and an independent sum of Poisson variables is Poisson with the summed mean: if Y\sim\text{Poisson}(\mu_1) and Z\sim\text{Poisson}(\mu_2) are independent, then Y+Z\sim\text{Poisson}(\mu_1+\mu_2). Counts over overlapping intervals are correlated, and \operatorname{Cov}\bigl(N(b)-N(a),\,N(d)-N(c)\bigr)=\lambda\,|(a,b]\cap(c,d]|, the rate times the overlap length. Independent non-degenerate Poisson variables Y,Z satisfy \Pr(Y=Z)=\sum_k p_k^2<1.

For a count, P(N(t)\le 1)=e^{-\lambda t}(1+\lambda t). Probabilities for several disjoint intervals are products of the single-interval probabilities.

Given N(t)=n, the arrival times are distributed as n independent uniform points on (0,t], so for s<t, N(s)\mid N(t)=n\sim\text{Binomial}(n,s/t). Waiting-time statements follow from the memoryless property: after time t, each further arrival takes an independent \text{Exp}(\lambda) time, so E[S_{n+k}\mid N(t)=n]=t+k/\lambda.

The first arrival T_1 is \text{Exp}(\lambda) with E[T_1]=1/\lambda, so the mean is the reciprocal of the rate, not the rate itself. Given N(t)=n, T_1 is the minimum of n independent uniform points, with E[T_1\mid N(t)=n]=t/(n+1).

In a birth–death setting with arrival rate \lambda and each of n present items leaving at rate \mu, the next event is an arrival with probability \lambda/(\lambda+n\mu). For example, with \lambda=2, \mu=1 and n=3, the probability is 2/5. Probabilities of a sequence of events multiply along the path.

Stationary distributions of Markov chains

A stationary distribution is a probability vector \pi with \pi P=\pi, that is, \pi_j=\sum_i \pi_i P_{ij} for all j. Stationary mass sits on recurrent states, and each closed class supports its own stationary distribution. If a finite chain is irreducible, the stationary distribution is unique and strictly positive. If there are several closed classes, every mixture of their stationary distributions is again stationary. For example, two absorbing states give the family (a,0,1-a), 0\le a\le 1, so the stationary distribution is not unique.

To check a candidate \pi, multiply the row vector by P entry by entry, since (\pi P)_j=\sum_i\pi_iP_{ij}. Equivalently, \pi P=\pi is the same as P^{T}\pi^{T}=\pi^{T}, so a stationary row vector is an eigenvector of P^{T} with eigenvalue 1. Multi-step probabilities come from powers of P, for example P(X_3=j\mid X_1=i)=(P^2)_{ij}.

For a birth–death chain with birth rates \lambda_n and death rates \mu_n, detailed balance \pi_n\lambda_n=\pi_{n+1}\mu_{n+1} gives \pi_{n+1}/\pi_n=\lambda_n/\mu_{n+1}. Multiply these ratios, then normalise. For states \{0,1,2\} with \lambda_0=2, \lambda_1=1, \mu_1=1, \mu_2=2, the unnormalised weights are 1,2,1, so \pi=(1/4,1/2,1/4).

A chain whose states split into several closed classes plus transient states can still have a unique stationary distribution when only one closed class exists. Transient states receive zero stationary mass.

Two-state Markov chain transitions

A two-state chain on \{0,1\} is determined by a=P_{01} and b=P_{10}, with P_{00}=1-a and P_{11}=1-b. The stationary condition \pi_0a=\pi_1b together with \pi_0+\pi_1=1 gives \pi_0=\dfrac{b}{a+b} and \pi_1=\dfrac{a}{a+b}. Thus the long-run share of time in a state is proportional to the rate of leaving the other state. For example, with a=0.2 and b=0.6, the long-run share of state 1 is 0.2/0.8=0.25. Such two-state questions often present the chain in everyday language, so identify which state is which before applying the formula.