Continuous-time Markov Chains

Lecture 1

Continuous-time stochastic process \(\{X(t),t\geq 0\}\)

  • state: finite/countable values, {0,1,2, …}
  • time: continuous, \(t\geq 0\)
  • transition prob (time stationary/homogeneous), \(\Pr(X(t+s)=j|X(s)=i, X(u), 0\leq u\lt s) = \Pr(X(t)=j|X(0)=i)\).
  • \(T_i\) denote the amount of time that the process stays in state i before making a transition into a different state
    • \(\Pr(T_i>s+t|T_i>s)=\Pr(T_i>t)\)
      • the process is in state i at time s
      • by the Markovian property, that the prob that it remains in that state during the interval [s,s+t] is just the (unconditional) prob that it stays in state i for at least t time.
    • \(T_i\) is memoryless
    • \(T_i\) must follow the exponential dist

Alternative definition of continuous-time MC

  • a stochastic process that moves from state to state in accordance with a (discrete-time) MC
    • \(P_{ii}=0, \sum_{j\neq i} P_{ij}=1\)
  • the amount of time it spends in state i, before proceeding to the next state, is exponentially distributed with rate \(v_i\)
  • the amount of time the process spends in state i, and the next state visited, must be independent random variables

Memoryless continuous random variable X

  • \(\Pr(X>t+s|X>s)=\Pr(X>t)\) <==> \(\Pr(X>t+s)=\Pr(X>t)\Pr(X>s)\)
  • survival function of X: \(G(t)=\Pr(X>t)\) (right continuous)
  • G(t+s)=G(t)G(s)
    • easy to check \(G(nt)=G(t)^n\), or \(G(t)=G(nt)^{1/n}\).
    • so \(G(1/p)=G(1)^{1/p}, G(q/p)=G(1/p)^q=G(1)^{q/p}\) for any integer p,q.
    • rational number can approximate any real number, so \(G(t)=G(1)^t=\exp(-\log(1/G(1))t)\), an exponential dist with rate \(\lambda=\log(1/G(1))\).
  • geometric dist is the discrete analog: survival prob \((1-p)^k\).
  • exponential dist with rate \(\lambda\): \(f(t)=\lambda e^{-\lambda t}, G(t)=e^{-\lambda t}\); mean \(E[T]=1/\lambda\), variance \(Var[T]=1/\lambda^2\).
  • minimum of independent exp is still exp (rate is the sum of individual rates).
    • \(\Pr(\min(X,Y)>t)=\Pr(X>t)\Pr(Y>t)=e^{-t\lambda_x-t\lambda_y}\)
      • \(\Pr(\min_iY_i>t)=\prod_i\Pr(Y_i>t)=e^{-t\sum_i\lambda_i^y}\)
    • Pr(an exp is the minimum among a set of independent exps) \(\propto\) its rate
      • \(\Pr(X\lt Y)=E[E[I(X\lt Y)|X]]=E[e^{-X\lambda_y}]=\lambda_x/(\lambda_x+\lambda_y)\)
      • \(\Pr(X\lt Y_1,\cdots,X\lt Y_m)=E[E[I(X\lt Y_i,\forall i)|X]]\)
        • = \(E[e^{-X\sum_i\lambda_{i}^y}]=\lambda_x/(\lambda_x+\sum_i\lambda_i^y)\)
  • sum of iid exp is gamma(n,\(\lambda\)).
  • Failure/hazard rate
    • r(t)=f(t)/G(t)
    • \(\Pr(X\in (t,t+dt)|X>t)=r(t)dt\).
    • \(G(t) = \exp(-\int_0^t r(t)dt)\).
    • \(r(t)=\lambda\) for exponential dist.

Birth and Death Processes

  • Birth and death process
    • a system whose state at any time is represented by the number of people in the system at that time
    • whenever there are n people in the system
      • new arrivals enter the system at an exponential rate \(\lambda_n\) (birth/arrival rate)
      • people leave the system at an exponential rate \(\mu_n\) (departure/death rate)
        • time until the next arrival is exponentially distributed with mean \(1/\lambda_n\),
        • independent of the time until the next departure, which is itself exponentially distributed with mean \(1/\mu_n\).
    • a continuous-time MC with states {0,1,…} for which transitions from state n may go only to either state n-1 or state n+1
      • \(\nu_0=\lambda_0, \nu_i=\lambda_i+\mu_i, i>0\).
      • \(P_{01}=1,P_{i,i+1}=\lambda_i/(\lambda_i+\mu_i), P_{i,i-1}=\mu_i/(\lambda_i+\mu_i), i>0\)
    • Poisson process with rate \(\lambda\)
      • \(\mu_n=0,\lambda_n=\lambda\)
    • Sampling Poisson process \(N(t)\) (rate \(\lambda\)) with prob \((p,1-p)\)
      • leading to two independent Poisson processes: \(N_1(t)\) with rate \(\lambda p\) and \(N_2(t)\) with rate \(\lambda(1-p)\)
      • \(X(t)=N_1(t)-N_2(t)\) can be treated as a birth and death process
        • constant birth rate \(\lambda_n=\lambda p\) and death rate \(\mu_n=\lambda (1-p)\)
        • transition matrix \(P_{i,i+1}=p, P_{i,i-1}=1-p\)
  • Linear growth model with immigration (Ex 6.4, Page 361)
    • \(\mu_n=n\mu, n\geq 1; \lambda_n=n\lambda+\theta, n\geq 0\).
      • each member independently gives birth with rate \(\lambda\), and dies with rate \(\mu\)
      • external source of immigration with constant rate \(\theta\)
    • Deriving M(t)=E[X(t)]
      • Considering M(t+h)=E[X(t+h)]=E[E[X(t+h)|X(t)]]
      • for small h, 3 values for X(t+h) conditional on X(t)
        • X(t)+1, prob=\([\theta+X(t)\lambda]h+o(h)\)
        • X(t)-1, prob=\(X(t)\mu h+o(h)\)
        • X(t), prob = 1- the first two
      • so \(E[X(t+h)|X(t)]=X(t)+[\theta+X(t)\lambda-X(t)\mu]h + o(h)\)
        • expectation: \(M(t+h)=M(t)+(\lambda-\mu)M(t)h+\theta h+o(h)\)
        • \((M(t+h)-M(t))/h = (\lambda-\mu)M(t)+\theta+o(h)/h\)
        • as \(h\to 0\), \(M'(t)=(\lambda-\mu)M(t)+\theta := h(t)\)
        • \(h'(t)=(\lambda-\mu)M'(t)\) and \(h'(t)=(\lambda-\mu)h(t)\)
        • \(h(t) = Ke^{(\lambda-\mu)t}\) and \(\theta+(\lambda-\mu)M(t)=Ke^{(\lambda-\mu)t}\)
      • note \(M(0)=i\)
        • \(\lambda\neq\mu\): \(M(t)=\theta/(\lambda-\mu)[e^{(\lambda-\mu)t}-1]+ie^{(\lambda-\mu)t}\)
        • \(\lambda=\mu\): \(M(t)=\theta t+i\)
  • General birth-death process with birth rate \(\lambda_n\) and death rate \(\mu_n\) with \(\mu_0=0\)
    • \(T_i\) denote the time, starting from state i, it takes for the process to enter state i+1, \(i\geq 0\)
    • \(X_i\): time until the transition from i occurs: Exp dist with rate \(\lambda_i+\mu_i\)
    • Deriving \(E[T_i]\)
      • note \(E[T_0]=1/\lambda_0\) since \(\nu_0=\lambda_0\).
      • Define
        • \(I_i=1\) if the first transition from i is to i+1
        • \(I_i=0\) if the first transition from i is to i-1
        • \(\Pr(I_i=1)=\Pr(\mbox{birth before death})=\lambda_i/(\lambda_i+\mu_i)\)
      • independent of whether the first transition is from a birth or death, the time until it occurs is exponential with rate \(\lambda_i+\mu_i\)
      • \(E[T_i|I_i=1] = 1/(\lambda_i+\mu_i)\)
        • if the first transition is a birth, then the population size is at i+1, so no additional time is needed
        • \(E[T_i|I_i=1]=E[X_i|I_i=1] = E[X_i]\)
          • time until transition and next state visited are independent!
        • => \(Var(T_i|I_i=1)=1/(\lambda_i+\mu_i)^2\)
      • \(E[T_i|I_i=0] = 1/(\lambda_i+\mu_i) + E[T_{i-1}] +E[T_i]\)
        • if the first event is death, then the population size becomes i-1,
        • the additional time needed to reach i+1 is equal to the time it takes to return to state i (mean \(E[T_{i-1}]\))
        • plus the additional time it then takes to reach i+1 (mean \(E[T_i]\))
        • => \(Var(T_i|I_i=0)=1/(\lambda_i+\mu_i)^2+Var(T_{i-1})+Var(T_i)\)
      • ==> \(E[T_i] = 1/(\lambda_i+\mu_i)+\mu_i/(\lambda_i+\mu_i)(E[T_{i-1}]+E[T_i])\)
        • \(E[T_i]=1/\lambda_i+\mu_i/\lambda_iE[T_{i-1}]\)
    • expected time to go from state i to state j where i<j
      • \(E[T_i]+E[T_{i+1}]+\cdots+E[T_{j-1}]\)
    • For \(\lambda_n=\lambda, \mu_n=\mu\)
      • \(E[T_0]=1/\lambda\)
      • \(E[T_i]=1/\lambda+\mu/\lambda E[T_{i-1}]=(1+\mu E[T_{i-1}])/\lambda\)
      • \(E[T_1]=(1+\mu/\lambda)/\lambda, E[T_2] = (1+\mu/\lambda+[\mu/\lambda]^2)/\lambda\)
        • \(\lambda\neq \mu\): \(E[T_i] = (1-(\mu/\lambda)^{i+1})/(\lambda-\mu), i\geq 0\).
        • \(\lambda=\mu\): \(E[T_i] = (i+1)/\lambda\)
      • E[time to go from k to j]=\(\sum_{i=k}^{j-1}E[T_i]\), k<j.
        • \(\lambda\neq \mu\): \((j-k)/(\lambda-\mu)-(\mu/\lambda)^{k+1}/(\lambda-\mu)[1-(\mu/\lambda)^{j-k}]/(1-\mu/\lambda)\)
        • \(\lambda=\mu\): \((j(j+1)-k(k+1)/2/\lambda\)
    • Deriving \(Var[T_i]\)
      • Note \(E[T_i|I_i]=1/(\lambda_i+\mu_i)+(1-I_i)(E[T_{i-1}]+E[T_i])\)
        • \(I_i\) ~ Bernoulli(\(\lambda_i/(\lambda_i+\mu_i)\))
        • => \(Var(E[T_i|I_i])=(E[T_{i-1}]+E[T_i])^2Var(I_i)=(E[T_{i-1}]+E[T_i])^2\mu_i\lambda_i/(\mu_i+\lambda_i)^2\)
      • \(Var(T_i|I_i)=1/(\lambda_i+\mu_i)^2+(1-I_i)[Var(T_{i-1})+Var(T_i)]\)
        • => \(E[Var(T_i|I_i)]=1/(\lambda_i+\mu_i)^2+\mu_i\lambda_i/(\mu_i+\lambda_i)^2[Var(T_{i-1})+Var(T_i)]\)
      • ==> \(Var(T_i)=1/(\lambda_i(\lambda_i+\mu_i))+\frac{\mu_i}{\lambda_i}Var(T_{i-1})+\frac{\mu_i}{\mu_i+\lambda_i}(E[T_{i-1}]+E[T_i])^2\)
      • note \(Var(T_0)=1/\lambda_0^2\)
      • Var[time to go from k to j]=\(\sum_{i=k}^{j-1}Var[T_i]\), k<j.

Lecture 2

Negative binomial dist: NB(r,p)

  • number of successes in a sequence of iid Bernoulli trials before a specified number of failures occurs
  • \(\Pr(X=k) = \binom{k+r-1}{k} p^k(1-p)^r\)
    • \(r=1\): geometric dist (memoryless)
    • sum of iid geometric dist rvs is negative binomial dist
  • here binomial coeff \(\binom{k+r-1}{k}=\frac{(k+r-1)!}{k!(r-1)!}=\frac{(k+r-1)(k+r-2)\cdots(r)}{k!}\)
    • generally \(\Gamma(n)=(n-1)!\), so also \(\frac{\Gamma(k+r)}{\Gamma(r)\Gamma(k+1)}\)
    • it can also be written as \((-1)^k\frac{(-r)(-r-1)\cdots(-r-k+1)}{k!}=(-1)^k\binom{-r}{k}\) (negative binomial)
  • \(E[X+r]=r/(1-p), E[X]=rp/(1-p)\)
    • \(1/(1-p)\): average number of trials needed to have one failure
  • \(Var(X)=rp/(1-p)^2\)
    • in general \(Var(X)>E(X)\) (over-dispersion)
  • Consider \(r\to\infty\) and \(rp/(1-p)\to \lambda\), i.e., \(p=\frac{\lambda}{r+\lambda}\)
    • density is \(\frac{\Gamma(r+k)}{\Gamma(r)}\frac{\lambda^k}{k!}\frac{1}{(1+\lambda/r)^r}\)
    • as \(r\to\infty\), \((1+\lambda/r)^r\to e\), and \(\Gamma(r+k)/\Gamma(r)\to 1\)
    • so \(\Pr(X=k)\to \frac{\lambda^k}{k!} e^{-\lambda}\), i.e., Possion dist with mean \(\lambda\)
    • \(NB(r,\lambda/(\lambda+r))\to \mbox{Poisson}(\lambda)\) as \(r\to\infty\)
  • Poisson-Gamma mixture: can be treated as a mixture of Poisson dist with Gamma dist mixing
    • Poisson mean heterigeneity hence over-dispersion
    • \(Y\sim\mbox{Poisson}(\lambda)\)
      • \(\Pr(Y=k)\sim e^{-\lambda}\lambda^k/k!\)
      • \(E(Y|\lambda)=Var(Y|\lambda)=\lambda\)
    • \(\lambda\sim\mbox{Gamma}(r,p/(1-p))\) (shape \(r\) and scale \(p/(1-p)\))
      • \(f(\lambda) = \lambda^{r-1}\frac{e^{-\lambda(1-p)/p}}{\Gamma(r)(p/(1-p))^r}\)
      • \(E(\lambda)=rp/(1-p), Var(\lambda)=rp^2/(1-p)^2\)

Transition Probability Function

  • transition probabilities of a continuous-time MC
    • \(P_{ij}(t)=\Pr[X(t+s)=j|X(s)=i]\)

Pure birth process

  • Suppose that the process is presently in state i, and let j > i
    • \(X_k\) denote the time the process spends in state k before making a transition into state k+1
    • \(\sum_{k=i}^{j-1}X_k\) is the time it takes until the process enters state \(j\)
    • \(X(t)\lt j \leftrightarrow \sum_{k=i}^{j-1}X_k>t\)
    • \(\Pr[X(t)\lt j|X(0)=i]=\Pr[\sum_{k=i}^{j-1}X_k>t]\)
      • \(X_k\) are independent exps with rate \(\lambda_k\)
      • sum of independent exps with distinct rates (hypoexponential dist)
      • = \(\sum_{k=i}^{j-1}e^{-\lambda_kt}\prod_{r\neq k,r=i}^{j-1}\frac{\lambda_r}{\lambda_r-\lambda_k}\) (assuming \(\lambda_i\neq\lambda_j, \forall i\neq j\))
    • \(\Pr[X(t)=j|X(0)=i]=\Pr[X(t)\lt j+1|X(0)=i]-\Pr[X(t)\lt j|X(0)=i]\)
    • \(P_{ii}(t)=\Pr(X_i>t)=e^{-\lambda_it}\) (Exp dist surv prob)
  • When birth rate is linear: \(\lambda_n=n\lambda\)
    • \(P_{1j}(t)=e^{-\lambda t}(1-e^{-\lambda t})^{j-1}\) (geometric dist)
      • number of successes in a sequence of iid Bernoulli trials before a failure occurs
      • derivation: …
    • \(P_{ij}(t)=\binom{j-1}{i-1} e^{-i\lambda t}(1-e^{-\lambda t})^{j-1}\) (negative binomial dist)
      • each individual starts its own independent birth process.
      • sum of \(i\) independent geometric rvs

Lecture 3

Instantaneous transition rates: \(q_{ij}=\nu_iP_{ij}\)

  • \(q_{ij}\) is the rate, when in state i, at which the process makes a transition into state j
  • \(\nu_i=\sum_jq_{ij}\), \(P_{ij}=q_{ij}/\sum_jq_{ij}\)
  • birth-death process
    • birth rate \(\lambda_i\) and death rate \(\mu_i\)
    • \(\nu_i=\lambda_i+\mu_i\), \(P_{i,i+1}=\lambda_i/(\lambda_i+\mu_i)\)
    • \(q_{i,i+1}=\lambda_i\) (birth-rate), \(q_{i,i-1}=\mu_i\) (death-rate)
  • Lemma 6.2 \(\lim_{h\to 0}\frac{1-P_{ii}(h)}{h}=\nu_i\), \(\lim_{h\to 0}\frac{P_{ij}(h)}{h}=q_{ij}, i\neq j\)
    • \(\nu_i\) is the hazard rate of exp dist
    • \(1-P_{ii}(h)\): the probability that a process in state i at time 0 will not be in state i at time h, equals the probability that a transition occurs within time h plus something small compared to h
      • \(1-P_{ii}(h)=\nu_i h+o(h)\)
    • \(P_{ij}(h)\): the probability that the process goes from state i to state j in a time h, equals the probability that a transition occurs in this time multiplied by the probability that the transition is into state j plus something small compared to h
      • \(P_{ij}(h)=h\nu_iP_{ij}+o(h)\)
  • Chapman–Kolmogorov equations: \(P_{ij}(t+s)=\sum_{k=0}^{\infty}P_{ik}(t)P_{kj}(s), \forall s\geq 0, t\geq 0\)
    • Condition on \(X(t)=k\): \(P_{ij}(t+s)=\Pr[X(t+s)=j|X(0)=i]=\sum_k \Pr[X(t+s)=j, X(t)=k|X(0)=i]\)
    • In matrix notation: \(P(t+s)=P(t)P(s)\) (for discrete MC: \(P^{(n+m)}=P^{(n)}.P^{(m)}\))
    • Kolmogorov’s Backward Equations: \(P'_{ij}(t)=\sum_{k\neq i} q_{ik}P_{kj}(t)-v_iP_{ij}(t)\)
      • \(P_{ij}(h+t)-P_{ij}(t)=\sum_{k\neq i}P_{ik}(h)P_{kj}(t)-[1-P_{ii}(h)]P_{ij}(t)\)
      • taking limit \(h\to 0\) and interchange limit and summation
    • Kolmogorov’s Forward Equations: \(P'_{ij}(t)=\sum_{k\neq j} q_{kj}P_{ik}(t)-v_jP_{ij}(t)\)
      • \(P_{ij}(t+h)-P_{ij}(t)=\sum_{k\neq j}P_{ik}(t)P_{kj}(h)-[1-P_{jj}(h)]P_{ij}(t)\)
      • taking limit \(h\to 0\) and interchange limit and summation (under suitable regularity conditions)
  • Pure birth process
    • Backward equation
      • \(P_{ij}'(t)=\lambda_i[P_{i+1,j}(t)−P_{ij}(t)]\)
    • Forward equation
      • \(P_{ii}'(t)=-\lambda_iP_{ii}(t)\)
        • \(P_{ii}(t)=e^{-\lambda_i t}\)
      • \(P_{ij}'(t)=\lambda_{j-1}P_{i,j-1}(t)-\lambda_jP_{ij}(t)\)
        • \(P_{ij}(t)=\lambda_{j-1}e^{-\lambda_j t}\int_0^t e^{\lambda_j s}P_{i,j-1}(s)ds\)
        • treating \(e^{\lambda_j t}P_{ij}(t)\) as one function
  • Birth and death process
    • Backward equation
      • \(P_{0j}'(t)=\lambda_0[P_{1j}(t)−P_{0j}(t)]\)
      • \(P_{ij}'(t)=\lambda_iP_{i+1,j}(t)+\mu_iP_{i−1,j}(t)−(\lambda_i+\mu_i)P_{ij}(t)\)
    • Forward equation
      • \(P_{i0}'(t)=\mu_1P_{i1}(t)−\lambda_0P_{i0}(t)\)
      • \(P_{ij}'(t)=\lambda_{j-1}P_{i,j-1}(t)+\mu_{j+1}P_{i,j+1}(t)−(\lambda_j+\mu_j)P_{ij}(t)\)

Continuous-Time Markov Chain Consisting of Two States (Example 6.11, Page 371)

  • A machine works for an exponential amount of time having mean \(1/\lambda\) before breaking down; and it takes an exponential amount of time having mean \(1/\mu\) to repair the machine
    • two states: 1 (not working, being repaired), 0 (working)
    • A birth-death process
      • birth rate: \(\lambda_0=\lambda\) (0->1, rate of breaking down when it is working), \(\lambda_1=0\) (can only go from 1->0)
      • death rate: \(\mu_1=\mu\) (1->0, rate of being repaired), \(\mu_0=0\) (can only go from 0->1)
    • \(P_{00}(0)=1, P_{10}(0)=0\)
    • Differential equations
      • Backward equation
        • \(P_{0j}'(t)=\lambda_0[P_{1j}(t)−P_{0j}(t)]\)
        • j=0: \(P_{00}'(t)=\lambda [P_{10}(t)−P_{00}(t)]\)
      • Forward equation
        • \(P_{i0}'(t)=\mu_1P_{i1}(t)−\lambda_0P_{i0}(t)\)
        • i=0: \(P_{00}'(t)=\mu P_{01}(t)−\lambda P_{00}(t)\)
      • hence \(\lambda P_{10}(t)=\mu P_{01}(t)\)
        • so \(P_{00}'(t)=\mu P_{01}(t)− \lambda P_{00}(t) = \mu - (\mu+\lambda) P_{00}(t)\)
        • consider function \(h(t)=P_{00}(t)-\mu/(\mu+\lambda)\)
        • we have \(h'(t)=-(\mu+\lambda)h(t)\) and hence \(h(t)=Ke^{-(\mu+\lambda)t}\)
        • \(P_{00}(t)=Ke^{-(\mu+\lambda)t}+\mu/(\mu+\lambda)\)
        • \(P_{00}(t)=1\), so \(K=\lambda/(\mu+\lambda)\)
      • \(P_{00}(t)=\frac{\lambda}{\lambda+\mu}e^{-(\lambda+\mu)t}+\frac{\mu}{\lambda+\mu}\)
      • \(P_{10}(t)=\mu/\lambda[1-P_{00}(t)]=-\frac{\mu}{\lambda+\mu}e^{-(\lambda+\mu)t}+\frac{\mu}{\lambda+\mu}\)
    • some results
      • continuous-time MC: \(\nu_0=\lambda, \nu_1=\mu\). \(\lim_{t\to 0} P_{10}(t)/t=\mu, \lim_{t\to 0}P_{01}(t)/t=\lambda\)
      • embeded discrete MC: transition prob \(P_{10}=P_{01}=1\); stationary dist \(\pi_0=\pi_1=0.5\)
      • limiting prob of continuous-time MC: \(\lim_{t\to\infty}P_{10}(t)=\mu/(\mu+\lambda)=P_0\)

Lecture 4

Limiting Probabilities

  • \(P_{ij}(t)\) often converges to a limiting value that is independent of the initial state \(i\).
    • let \(P_j=\lim_{t\to\infty}P_{ij}(t)\), \(\sum_jP_j=1\) (stationary probabilities)
      • \(P_{ij}(t)\) will be constant if we start from the limiting prob.
    • Forward equation: \(P'_{ij}(t)=\sum_{k\neq j} q_{kj}P_{ik}(t)-\nu_jP_{ij}(t)\)
      • \(q_{kj}=v_kP_{kj}\)
      • \(\lim_{t\to\infty}P'_{ij}(t)=\sum_{k\neq j}q_{kj}P_k-\nu_jP_j\)
        • note \(\lim_{t\to\infty}P'_{ij}(t)=0\) (if not, \(P_{ij}(t)\) will go to infinity)
    • So \(\nu_jP_j=\sum_{k\neq j}q_{kj}P_k\) (balance equations)
      • Sufficient condition for \(P_j\) existing (ergodic chain)
        • all states of the MC communicate in the sense that starting in state i there is a positive probability of ever being in state j, for all i, j and
        • the MC is positive recurrent in the sense that, starting in any state, the mean time to return to that state is finite
      • \(P_j\) being the long-run proportion of time that the process is in state \(j\)
      • \(\nu_jP_j\) = rate at which the process leaves state j
        • when the process is in state j, it leaves at rate \(\nu_j\)
        • \(P_j\) is the proportion of time it is in state j
      • \(\sum_{k\neq j}q_{kj}P_k\) = rate at which the process enters state j
        • \(q_{kj}P_j\) = rate at which transitions from k to j occur
      • hence equality of the rates at which the process enters and leaves state j
  • Birth and death process
    • birth rate \(\lambda_n\), death rate \(\mu_n\)
      • embeded discrete-time MC: \(P_{n,n+1}=\lambda_n/(\lambda_n+\mu_n), P_{n,n-1}=\mu_n/(\lambda_n+\mu_n)\) (two competing Exp rvs)
      • rate \(v_n=\lambda_n+\mu_n\) (minimum of two Exp rvs)
      • \(q_{n,n+1}=\lambda_n, q_{n,n-1}=\mu_n\)
      • state 0: leaving rate \(\lambda_0P_0\); entering rate \(\mu_1P_1\)
      • state \(n\geq 1\): leaving rate \((\lambda_n+\mu_n)P_n\); entering rate \(\mu_{n+1}P_{n+1}+\lambda_{n-1}P_{n-1}\)
      • hence \((\lambda_n+\mu_n)P_n=\mu_{n+1}P_{n+1}+\lambda_{n-1}P_{n-1}\)
        • i.e., \(\lambda_nP_n - \lambda_{n-1}P_{n-1} = \mu_{n+1}P_{n+1} - \mu_nP_n\)
        • note for \(n=0\): \(\lambda_0P_0=\mu_1P_1\)
        • sum over 0,…,n: \(\lambda_nP_n=\mu_{n+1}P_{n+1}, n\geq 0\)
      • hence \(P_n=\frac{\prod_{i=1}^n\lambda_{i-1}}{\prod_{i=1}^n\mu_i}P_0\), and \(P_0=\frac{1}{1+\sum_{n=1}^{\infty}\frac{\prod_{i=1}^n\lambda_{i-1}}{\prod_{i=1}^n\mu_i}}\)
        • limiting prob exists iff \(\sum_{n=1}^{\infty}\frac{\prod_{i=1}^n\lambda_{i-1}}{\prod_{i=1}^n\mu_i}<\infty\)
    • linear growth model with immigration
      • \(\lambda_n=n\lambda+\theta, \mu_n=n\mu\)
      • previous condition reduces to \(\sum_{n=1}^{\infty}\frac{\prod_{i=1}^n(\theta+(i-1)\lambda)}{n!\mu^n}<\infty\)
        • consider the limit of ratio of two adjacent terms: \(\lim_n\frac{\theta+n\lambda}{(n+1)\mu}=\frac{\lambda}{\mu}\)
        • therefore when \(\lambda<\mu\), the limiting prob exists!
    • a birth-death process with \(\mu_n=\mu, n\geq 1\), \(\lambda_n=(M-n)\lambda, n\leq M\), \(\lambda_n=0, n>M\)
      • Continuous-Time Markov Chain Consisting of Finite States (Ex 6.13, Page 373)
      • \(P_n=\frac{(\lambda/\mu)^nM!/(M-n)!}{1+\sum_{n=1}^M(\lambda/\mu)^nM!/(M-n)!}, n=0,\ldots,M\)

Lecture 5

Time Reversibility

  • For a continuous-time ergodic MC with limiting \(P_j\)
    • consider its discrete-time transition matrix \(P_{ij}\)
      • its limiting prob \(\pi_i\): \(\pi_i=\sum_j\pi_jP_{ji}\)
    • Claim: \(P_i=\pi_i/\nu_i/(\sum_j\pi_j/\nu_j)\)
      • \(\nu_iP_i=\sum_{j\neq i} P_jq_{ji}\)
      • note \(P_{ii}=0\)
    • Going backward in time, the amount of time the process spends in state \(i\) is also exp with the same rate
      • assume the chain is already in limiting dist
      • \(\Pr(\mbox{process is in state i throughout } [t−s,t]|X(t)=i)\)
        • = \(\Pr(\mbox{process is in state i throughout } [t−s,t])/\Pr(X(t)=i)=\Pr(X(t-s)=i)e^{-\nu_is}/\Pr(X(t)=i)=e^{-\nu_is}\)
      • sequence of states visited by the reversed process constitutes a discrete-time MC with transition probabilities \(Q_{ij}=\pi_jP_{ji}/\pi_i\)
      • reversed process is a continuous-time MC with the same transition rates as the forward-time process and with one-stage transition probabilities \(Q_{ij}\)
    • Continuous-time MC is time reversible if \(\pi_iP_{ij}=\pi_jP_{ji}\)
      • time reversible, in the sense that the process reversed in time has the same probabilistic structure as the original process, when the embedded chain is time reversible
      • <=> \(P_iq_{ij}=P_jq_{ji}\)
      • \(P_i\) is the proportion of time in state i and \(q_{ij}\) is the rate when in state i that the process goes to j
      • the rate at which the process goes directly from state i to state j is equal to the rate at which it goes directly from j to i
  • Proposition 6.5 An ergodic birth and death process is time reversible
    • the rate at which a birth and death process goes from state i to state i+1 is equal to the rate at which it goes from i+1 to i
    • In any length of time t the number of transitions from i to i+1 must equal to within 1 the number from i+1 to i
      • since between each transition from i to i+1 the process must return to i, and this can only occur through i+1, and vice versa.
  • Proposition 6.7 If for some \(\{P_i\geq 0\}\), \(\sum_iP_i=1\), and \(P_iq_{ij}=P_jq_{ji}, \forall i\neq j\), then the continuous-time MC is time reversible and \(P_i\) is the limiting probability of being in state i.
    • \(\sum_{j\neq i}P_iq_{ij}=\sum_{j\neq i}P_jq_{ji}\)
    • note \(\nu_i=\sum_{j\neq i}q_{ij}\)
    • so \(v_iP_i=\sum_{j\neq i}P_jq_{ji}\) (balance equation)
  • Proposition 6.8 A time reversible chain with limiting prob \(P_j,j\in S\) that is truncated to the set \(A\in S\) and remains irreducible is also time reversible and has limiting probabilities \(P_j^A\) given by \(P_j^A=\frac{P_j}{\sum_{i\in A}P_i}, j\in A\).

Uniformization

  • Consider a continuous-time Markov chain with \(\nu_i=\nu, \forall i\)
    • N(t) denote the number of state transitions by time t, then \(\{N(t),t\geq 0\}\) will be a Poisson process with rate \(\nu\).
      • N(t) \(\sim\) Poisson(\(\nu t\))
    • \(P_{ij}(t)=\Pr(X(t)=j|X(0)=i)=\sum_{n=0}^{\infty}\Pr(N(t)=n|X(0)=i)\Pr(X(t)=j|X(0)=i,N(t)=n)\)
      • \(\Pr(N(t)=n|X(0)=i)=e^{-\nu t}(\nu t)^n/n!\) (Poisson rv)
      • \(\Pr(X(t)=j|X(0)=i,N(t)=n)=P_{ij}^n\)
        • knowing that N(t) = n gives us no information about which states were visited, since the distribution of time spent in each state is the same for all states
        • \(P_{ij}^n\) is the n-stage transition probability associated with the discrete-time MC with transition prob \(P_{ij}\)
    • So \(P_{ij}(t)=\sum_{n=0}^{\infty}P_{ij}^{n}e^{-\nu t}(\nu t)^n/n!\)
      • approximate \(P_{ij}(t)\) by taking a partial sum and then computing the n stage probabilities \(P_{ij}^n\).
  • uniformizing the rate in which a transition occurs from each state by introducing transitions from a state to itself
    • assume \(\nu_i\leq\nu, \forall i\)
    • Define \(P_{ij}^{\ast}\): \(1-\nu_i/\nu\) for \(j=i\) and \(\nu_i/\nu P_{ij}\) for \(j\neq i\).
    • \(P_{ij}(t)=\sum_{n=0}^{\infty}P_{ij}^{\ast n}e^{-\nu t}(\nu t)^n/n!\)

Computing the Transition Probabilities

  • Define \(r_{ij}\): \(q_{ij}\) if \(i\neq j\), and \(-\nu_i\) if \(i=j\).
    • Kolmogorov backward equations: \(P'_{ij}(t)=\sum_k r_{ik}P_{kj}(t)\)
    • Kolmogorov forward equations: \(P'_{ij}(t)=\sum_k r_{kj}P_{ik}(t)\)
  • Define corresponding matrix \(\textbf{R}, \textbf{P}(t), \textbf{P}'(t)\)
    • \(\textbf{P}'(t)=\textbf{R}\textbf{P}(t)=\textbf{P}(t)\textbf{R}\)
      • so \(\textbf{P}(t)=\textbf{P}(0)e^{\textbf{R}t}=e^{\textbf{R}t}\), since \(\textbf{P}(0)=\textbf{I}\).
      • \(e^{\textbf{R}t}=\sum_{n=0}^{\infty}\textbf{R}^nt^n/n!\)
  • Approximation of \(\textbf{P}(t)\)
    • \(e^{\textbf{R}t}=\lim_{n\to\infty}(\textbf{I}+\textbf{R}t/n)^n\)
      • taking \(n=2^k\): approximating by matrix square (multiplication)
      • for large n, \(\textbf{I}+\textbf{R}t/n\) all nonnegative elements
    • \(e^{-\textbf{R}t}=\lim_{n\to\infty}(\textbf{I}-\textbf{R}t/n)^n\)
      • \((\textbf{I}-\textbf{R}t/n)^{-1}\) nonnegative elements