Continuous-Time Discrete-State Processes

Poisson Processes

Many scenarios are natural continuous-time discrete-state processes. Consider modeling the number of people waiting for the bus. People can arrive at the stop at any moment, but the number of people is certainly discrete. Sometimes a bus comes and picks everyone up.

We could discretize this process, in which case we must handle transitions for however many people arrive in the interval. We’d like to define how things interact as $dt\to 0$.

This should sound a lot like a Poisson process, which can be viewed as a counting process, $N(t)\to N(t)+1$ at a rate $\lambda$. In this case, the only relevant information is the time of the jumps $T_{k>0}$

We also look at $S_k=T_k-T_{k-1}$

Given the above definitions, we can write some useful equivalencies
$X(t)\ge m⟺T_m\le t⟺S_1+\cdots +S_m\le t$

A counting process can be defined by sampling $S_k$ from any distribution. However, it will only be a Markov process when we sample from the exponential distribution. The reason this isn’t true for any distribution is because the probability cannot depend on how long we’ve waited, even within an interval.

Definition: $(X(t){)}_{t\ge 0}$ is a Markov process $⟺$ $\forall s\ge 0$, the distribution of $X_{t+s}$ given $(X_u{)}_{u\le t}$ only depends on $X_t$. In other words, the future depends on the present, not the past.

$\mathbb{P}[X_{t+s}=k\mid X_u=f(u),u\le t]=\mathbb{P}[X_{t+s}=k\mid X_t=f(t)]$

A process is time-homogeneous if $\mathbb{P}[X_{t+s}=k\mid X_t=f(t)]=\mathbb{P}[X_s=k\mid X_0=f(t)]$

Definition: $S_1$ is memoryless if $\mathbb{P}[S_1\ge t+s\mid S_1\ge s]=\mathbb{P}[S_1\ge t]$

Theorem: This is a very strong condition. As we said above, the only distribution satisfying the memoryless property is the exponential distribution.

Assume $S$ is memoryless and let $f(t)=\mathbb{P}[S\ge t]={\int }_t^{\infty }p(u)du$
We use the condition from above, $f(t+s)=f(t)f(s)$

Differentiating on $s$ with $s=0$ yields $f^{\prime }(t)=f(t)f^{\prime }(0)$
$f^{\prime }(t)=Cf(t)$
Now it’s pretty clear that the only possible distributions satisfying this differential equation are exponential

Definition: The Poisson process is the counting process with intervals independent and exponential with $\lambda$

• $\mathbb{P}[N(t)=n]=\frac{(\lambda t{)}^n}{n!}{e}^{-\lambda t}$
• $P_{T_n}=\frac{{\lambda }^n{t}^{n-1}}{(n-1)!}{e}^{-\lambda t}$

Definition: $(X_t{)}_{t\ge 0}$ has stationary increments if $X_{t+s}-X_s$ has the same distribution as $X_t-X_0$ for all $t,s$
This implies time-homogeneity

Definition: $(X_t{)}_{t\ge 0}$ has independent increments if $X_{t+s}-X_s$ is independent of $X_{u+v}-X_u$ for all disjoint intervals $[s,t+s]\cap [u,u+v]=\varnothing$
This implies the Markov property

Definition: A Levy process is a process with independent, stationary increments. These are all Markov processes.

Theorem: The following statements are equivalent,

1. $N(t)$ is a Poisson process of rate $\lambda$
2. $N(t)$ has stationary, independent increments (Levy process) and $\mathbb{P}[N(t)=n]=\frac{(\lambda t{)}^n}{n!}{t}^{-\lambda t}$ follows the Poisson distribution
3. $N(t)$ is a Levy process, $\mathbb{P}[N(t+s)-N(t)=0]=1-\delta \lambda +o(\delta )$, $\mathbb{P}[N(t+s)-N(t)=1]=\delta \lambda +o(\delta )$, and $\mathbb{P}[N(t+s)-N(t)=0]=o(\delta )$. This says the probability of more than one jump approaches $0$ for small increments.

Here, $o(\delta )$ means “negligible compared to $\delta$”, a function of $\delta$ such that $\frac{o(\delta )}{\delta }\to 0$. We derive the probabilities listed by taking a look at the Taylor series.

Theorem: If $N_1(t)$ and $N_2(t)$ are independent Poisson processes with rates ${\lambda }_1$ and ${\lambda }_2$ then $N_1+N_2$ is a Poisson process with rate ${\lambda }_1+{\lambda }_2$

Theorem: One can “split” a process $N(t)$ into independent processes with $N_1(t)$ with $\lambda p$ and $N_2(t)$ with $\lambda (1-p)$ by assigning jumps to $N_1(t)$ with probability $p$

Defining a Continuous Process

An important fact to keep in mind is that the minimum between $n$ exponential variables with rates $b_i$ is an exponential variable with rate $\Sigma b_i$

The probability of the $i$th variable “triggering” is $\frac{b_i}{\Sigma b_i}$

To recap, we need a process with,

• Markov property: $\mathbb{P}\{X_t=y\mid X_r,0\le r\le s\}=\mathbb{P}\{X_t=y\mid X_s\}$
• Time-homogeneity: $\mathbb{P}\{X_t=y\mid X_s=x\}=\mathbb{P}\{X_{t-s}=y\mid X_0=x\}$

We assign $\alpha (x,y)$ for each transition $x\to y$, denoting the rate of an exponential random variable

$\alpha (x)={\sum }_{y\ne x}^{}\alpha (x,y)$ represents the rate at which the chain transitions from state $x$

$p_{xx}=P\{X_{t+\Delta t}=x\mid X_t=x\}=1-\alpha (x)\Delta t+o(\Delta t)$
$p_{xy}=P\{X_{t+\Delta t}=x\mid X_t=y\}=\alpha (y,x)\Delta t+o(\Delta t)$

Chapman-Kolmogorov: $p_{ij}(t)={\sum }_k^{}{p}_{ij}(t-s)p_{kj}(s)$
We derive differential equations by taking the limits $s\to 0^{+}$ and $s\to t^{-}$

$p_{ij}(t)={\sum }_{k\ne j}^{}{p}_{ik}(t-s)p_{kj}(s)+p_{ij}(t-s)p_{jj}(s)$
$={\sum }_{k\ne j}^{}{p}_{ik}(t-s)\alpha (k,j)s+p_{ij}(t-s)(1-\alpha (j)s)+o(s)$
$\frac{p_{ij}(t)-p_{ij}(t-s)}{s}={\sum }_{k\ne j}^{}{p}_{ik}(t-s)\alpha (k,j)-p_{ij}(t-s)\alpha (j)+\frac{o(s)}{s}$

We take the limit as $s$ approaches $0$ to derive $p_{ij}^{\prime }(t)=-p_{ij}(t)\alpha (j)+{\sum }_{k\ne j}^{}{p}_{ik}(t)\alpha (k,j)$ (this version is easier to understand)
We take the limit as $s$ approaches $t$ to derive $p_{ij}^{\prime }(t)=-\alpha (i)p_{ij}(t)+{\sum }_{k\ne j}^{}\alpha (i,k)p_{kj}(t)$ (this version is harder to understand but equivalent)

We may also write it with $p_x(t)=\mathbb{P}\{X_t=x\}$
$p_x^{\prime }(t)=-\alpha (x)p_x(t)+{\sum }_{y\ne x}^{}\alpha (y,x)p_y(t)$

Our initial condition is $p_x(0)$

In accordance with our equation, we define the infinitesimal generator $\mathbf{A}$ as the matrix whose $(x,y)$ entry is $\alpha (x,y)$ if $x\ne y$ and $-\alpha (x)$ if $x=y$. Note that row sums equal $0$, nondiagonal entries are nonnegative, and diagonal entries are nonpositive.

${\bar{p}}^{\prime }(t)=\bar{p}(t)\mathbf{A}$
$\bar{p}(t)=\bar{p}(0)e^{t\mathbf{A}}$

Alternatively, let $p_t(x,y)=\mathbb{P}\{X_t=y\mid X_0=x\}$
$\frac{d}{dt}{\mathbf{P}}_t={\mathbf{P}}_t\mathbf{A}$, ${\mathbf{P}}_0=\mathbf{I}$
${\mathbf{P}}_t=e^{t\mathbf{A}}$

Example: $\alpha (0,1)=1$ and $\alpha (1,0)=2$
$\mathbf{A}=\left[\begin{array}{cc}-1& 1\\ 2& -2\end{array}\right]=\mathbf{QD}{\mathbf{Q}}^{-1}$
$\mathbf{D}=\left[\begin{array}{cc}0& 0\\ 0& -3\end{array}\right]$, $\mathbf{Q}=\left[\begin{array}{cc}1& 1\\ 1& -2\end{array}\right]$, ${\mathbf{Q}}^{-1}=\left[\begin{array}{cc}2/3& 1/3\\ 1/3& -1/3\end{array}\right]$
${\mathbf{P}}_{\mathbf{t}}=e^{t\mathbf{A}}={\sum }_{n=0}^{\infty }\frac{(t\mathbf{A}{)}^n}{n!}={\sum }_{n=0}^{\infty }\frac{\mathbf{Q}(t\mathbf{D}{)}^n{\mathbf{Q}}^{-1}}{n!}=\mathbf{Q}\left[\begin{array}{cc}1& 0\\ 0& e^{-3t}\end{array}\right]{\mathbf{Q}}^{-1}$
$=\left[\begin{array}{cc}2/3& 1/3\\ 2/3& 1/3\end{array}\right]+e^{-3t}\left[\begin{array}{cc}1/3& -1/3\\ -2/3& 2/3\end{array}\right]$

${\lim }_{n\to \infty }{\mathbf{P}}_t=\left[\begin{array}{c}\bar{\pi }\\ \bar{\pi }\end{array}\right]$ so $\bar{\pi }=(2/3,1/3)$

Note that the right eigenvector of $\mathbf{Q}$ which is all $1$s corresponds to the stationary distribution, the left eigenvector in ${\mathbf{Q}}^{-1}$

In other words, we are looking for a limiting probability ${\lim }_{t\to \infty }{\mathbf{P}}_t={\Pi }_t=\left[\begin{array}{c}\bar{\pi }\\ ⋮\\ \bar{\pi }\end{array}\right]$
$\bar{\pi }\mathbf{A}=\bar{0}$

Suppose $\mathbf{A}$ is irreducible, then there is a unique probability vector satisfying $\bar{\pi }\mathbf{A}=\bar{0}$, and all other eigenvalues of $\mathbf{A}$ have negative real part

If the chain is reducible, we analyze each communication class
Periodicity does not occur

We can analyze the chain similar to a discrete state chain. Compute the mean passage time to a fixed state $z$, $b(x)=\mathbb{E}(\text{inf}\{t:X_t=z\}\mid X_0=x)$
$b(z)=0$

Let $T$ be the first time that the chain changes state, $\mathbb{E}(Y\mid X_0=x)=\mathbb{E}(T\mid X_0=x)+\sum _{y\in S}\mathbb{P}\{X_t=y\mid X_0=x\}\mathbb{E}(Y\mid X_0=y)$
This simplifies to $\alpha (x)b(x)=1+{\sum }_{y\ne x,z}^{}\alpha (x,y)b(y)$

Say $\tilde{\mathbf{A}}$ is the matrix obtained by deleting the row and column associated with $z$, then we get $\bar{0}=\bar{1}+\tilde{\mathbf{A}}\bar{b}$. This is an invertible matrix.

$\bar{b}=[-\tilde{\mathbf{A}}{]}^{-1}\bar{1}$

We can also view the invariant measure in terms of the embedded Markov chain. If the embedded Markov chain has invariant measure $\pi$, then the associated continuous time process has invariant measure $p_i=\frac{{\pi }_i/\alpha (i)}{\Sigma {\pi }_j/\alpha (j)}$

A continuous process is reversible $⟺$ $p_i\alpha (i,j)=p_j\alpha (j,i)$