A generalization of the Poisson counting process

  • Recall that if \(N\) is a Poisson counting process, then it has exponential inter-arrival times all with the same rate; specifically, we may think of \[ N(t) = \sum_{k=1} ^{\infty} \mathbf{1}[T_k \leq t],\] where \(T_0= 0\) and \[T_k = \sum_{i=1} ^{k} X_i,\] where \(X_i\) are i.i.d. exponential random variables.

continued

  • We now allow for the possibility that the positive inter-arrival times \(X_i\) are i.i.d. random variables that are not necessary exponential, and we refer to \(N\) as a renewal proceess.

  • We will always assume that \(\mathbb{P}(X_1 = 0) =0\) and \(\mathbb{E} X_1= \mu <\infty\).

Basic limit theorems

  • Theorem (Law of large numbers): If \(N\) is a renewal process with mean inter-arrival time \(\mu\) then, \[N(t)/ t \to \mu^{-1}\] almost surely, as \(t \to \infty\).

  • Theorem (Central limit theorem): If \(N\) is a renewal process with inter-arrival times with finite mean \(\mu\) and variance \(\sigma^2\), then

\[ \frac{ N(t) - t/\mu}{ \sqrt{t \sigma^2 / \mu^3}}\] converges in distribution to a standard normal, as \(t \to \infty\).

Proof (Law of large numbers)

  • We make use of the observation that \[ T_{N(t)} \leq t < T_{N(t) +1}.\]
  • Hence

\[ \frac{N(t)}{T_{N(t) +1}} \leq \frac{N(t)}{ t} \leq \frac{N(t)}{ T_{N(t)}}.\]

continued

  • We also know that if \(X_i\) are inter-arrival times, then \[T_{N(t)} = \sum_{i=1} ^{N(t)} X_i\]

so that the regular strong law of large numbers gives that \[T_{N(t)} /N(t) \to \mu\] almost-surely, as \(t \to \infty\), since \(N(t) \to \infty\), as \(t \to \infty\).

  • Hence the desired result follows.

Central limit theorem

  • We can see why \(var(N(t)) \approx t \sigma^2 / \mu^3\).

  • The law of large numbers tells us that \[ N(t) \approx \frac{ T_{N(t)}}{\mu}\] so that \[ N(t) \approx \frac{1}{\mu} \sum_{i=1} ^{{N(t)}} X_i\] where the \(X_i\) are the inter-arrival times.

continued

  • We also have by the law of large numbers for renewal processes that \[{N(t)} \approx \frac{t}{\mu}\] thus

\[ var(N(t)) \approx var\big( \frac{1}{\mu} \sum_{i=1} ^{ \frac{t}{\mu}} X_i \big) \approx t \sigma^2 / \mu^3,\] where \(var(X_1) = \sigma\).

Renewal type arguments for Markov chains and the strong Markov property

  • We will prove a version of the law of large numbers (ergodic theorem) for Markov chains by breaking the chain up into independent parts.

  • Let \(X\) be a Markov chain on a state space \(S\).

  • Recall that we say that a state \(s \in S\) is recurrent if \[\mathbb{P}( \text{there exists } n\geq 1 \text{ such that } X_n=s \ | \ X_0=s)=1.\]

  • Furthermore, let \(X\) be a Markov chain started at \(s\) and \(T = \inf \{n \geq 1 : X_n=s\}\); we say that a recurrent state \(s\) is positive-recurrent if \(\mathbb{E} T < \infty\) and null-recurrent if \(\mathbb{E} T = \infty\).

Law of large numbers

  • Let \(X\) be an irreducible Markov chain on a countable state space \(S\).

  • Let \(P\) be the transition matrix for \(S\), and assume all the states are positive-recurrent.

  • Fix \(s \in S\). Start the chain \(X\) at \(s\).

continued

  • Let \(T_1 = \inf \{n \geq 1 : X_n=s\}\).

  • Let \[V_n = \sum_{k=0} ^{n} \mathbf{1}[X_k=s].\]

  • Then \[V_n/n \to (\mathbb{E} T_1)^{-1}\] almost surely.

Strong Markov property and stopping times

The starting point of the proof of this version of the law of large numbers is the following observation.

  • Let \(T_1 = \inf\{n >0: X_n =s\}\). Set \[T_{n} = \inf\{n >T_{n-1}: X_n=s\}.\]

  • Then \(T_n = \sum_{k=1} ^{n-1} (T_{k+1} - T_k) + T_1\) and \(Y_k = T_{k+1} - T_k\) are i.i.d. random variables.

  • This may appear obvious from the Markov property, but it is a seemingly stronger claim (that turns out is implied by the regular Markov property), since we need to argue that Markov chain renews itself each time it reaches the state \(s\), which is a random time, rather than a deterministic time.

continued

  • Let \(X = (X_i)_{i \in \mathbb{N}}\) be a random process taking values in \(S\).

  • If \(T\) is a nonnegative integer-valued random variable with the property that for all \(n \in \mathbb{N}\) there exists a deterministic function \(\phi_n: S^n \to \{0,1\}\) such that \[\mathbf{1}[T=n] = \phi_n(X_0, X_1, \ldots, X_n),\] then we say that \(T\) is a stopping time.

  • Thus \(T\) does not look into the future, to determine whether to stop or not. We will usually assume that \(\mathbb{P}(T < \infty) = 1\).

Strong Markov property

  • Let \(X\) be a Markov chain taking values in a state space \(S\) with a transition matrix \(P\).

  • If \(T\) is a stopping time, then conditional on the event \(\{X_T=s\}\) we have that \(Y=(X_{T+k})_{k=0} ^{\infty}\) is a Markov chain started at \(s\) with transition matrix \(P\) that is independent of \(Z=(X_k)_{k=0}^{T}\).

Proof of law of large numbers for Markov chains

  • By the Strong Markov property the random variables \(Y_k = T_{k+1} - T_k\) are i.i.d. random variables.

  • The law of large numbers gives that \(T_n/ n \to \mathbb{E} T_1\) almost surely.

  • Observe that \(V_{T_n} = n+1\), and thus \(V_{T_n} /T_n \to (\mathbb{E} T_1)^{-1}\). Hence \(V_n / n \to (\mathbb{E} T_1)^{-1}\), since \(T_n \to \infty\).

Corollary

Let \(\pi\) is the stationary distribution and \(T^s = \inf \{ n \geq 1: X_n =s | X_0 =s\}\). Then \[(\mathbb{E} T^s)^{-1} = \pi(s).\]

Proof (aperiodic irreducible finite state space):


  • We proved that \(V_n/ n \to \pi(s)\) in probability.

  • We also proved that \(V_n/ n \to (\mathbb{E} T^s)^{-1}\) almost surely, and thus also in probability.

  • Hence \((\mathbb{E} T^s)^{-1} = \pi(s)\).

Semi-Markov process

  • Recall that the holding times a continuous time Markov chain were chosen to be exponential, as to preserve the Markov property.

  • When we allow for the possibility that the holding times are not exponential, then resulting process is often referred to as a Semi-Markov or Markov-renewal process and the jump chain a hidden Markov chain.

Summary

  • We introduced varies relaxations of models that we previously studied.

  • In particular, we generalized the Poisson counting processes by allowing non-exponential inter-arrival times.

  • We observed basic limit theorems that follow from the law of the large numbers and the central limit theorem.

  • We also applied renewal type arguments to the study of Markov chains

Version: 23 November 2020