Title: Part II / Applied Probability
Tags: Qualitative::properties::of::Markov Queueing::Theory Introduction::to::Markov Renewal::Theory Poisson::Processes Spatial::Poisson::Process

Q: Definition. The process \( X = (X_t)_{t \geq 0} \) is called a continuous-time Markov chain if [...]
A: for all \( x_1, \dots, x_n \in S \) and all times \( 0 \leq t_1 \leq t_2 \leq \dots \leq t_n \) we have \[ \mathbb{P}(X_{t_n} = x_n \mid X_{t_{n-1} } = x_{n-1}, \dots, X_{t_1} = x_1) = \mathbb{P}(X_{t_n} = x_n \mid X_{t_{n-1} } = x_{n-1}) \]whenever both sides are well defined.
Back Extra: If the right-hand side above only depends on the difference \( t_n - t_{n-1} \), then the chain is called time homogeneous. We write \( P(t) = (p_{xy}(t))_{x,y \in S} \), where \[ p_{xy}(t) = \mathbb{P}(X_t = y \mid X_0 = x). \]The family \( (P(t))_{t \geq 0} \) is called the transition semigroup of the continuous-time Markov chain. It is the continuous-time analogue of the iterates of the transition matrix in discrete time. In the same way as in discrete time, we can prove the Chapman-Kolmogorov equations for all \( x, y \) \[ p_{xy}(t + s) = \sum_z p_{xz}(t)p_{zy}(s). \] Hence the transition semigroup associated to a continuous-time Markov chain satisfies
1. \( P(t) \) is a stochastic matrix for all \( t \).
2. \( P(t + s) = P(t) P(s) \) for all \( s, t \).
3. \( P(0) = I \)

Q: Definition. The jump times of the continuous time Markov chain are given by \[[...]\]
The holding times are given by \[[...]\]The explosion time is given by \[[...]\]
A: J_0 = 0, \; \; \; J_{n+1} = \inf \{t \ge J_n : X_t \neq X_{J_n}\} \; \; \forall n \ge 0 \text{ where } \inf \emptyset = \infty; S_n = \begin{cases} J_n - J_{n-1} & \text{ if } J_{n-1} < \infty \\ \infty & \text{ otherwise}\end{cases}; \zeta = \sup_n J_n = \sum_{n=1}^{\infty} S_n
Back Extra: By right continuity \(S_n > 0\) for all n. If \(J_{n+1} = \infty\) for some n, then we set \(X_{\infty} = X_{J_n}\) as the final value otherwise we don't define it. The jump chain is defined by \[Y_n = X_{J_n}\]We will not consider what happens to a chain after explosion and set \(X_t = \infty\) for \(t \ge \zeta\). We call such a chain minimal.

Q: Theorem. Memoryless Property. Let S be a positive r.v. then S has the meaningless property ie. \(\forall s,t \ge 0\) \(\mathbb{P}(S > t+s | S > s) = \mathbb{P}(S > t)\) iff S has the exponential distribution.
A: (\(\implies\)) easy
(\(\impliedby\)) Set \(F(t) = \mathbb{P}(S > t)\) then \(F(t +s) = \mathbb{P}(S > t +s) = \mathbb{P}(S > t)\mathbb{P}(S > s) = F(t)F(s)\)
Since \(S > 0, \exists n \in \mathbb{N} \) s.t. \(F(1/n) = \mathbb{P}(S > 1/n) > 0\). Then \(F(1) = F(1/n + \dots 1/n) = F(1/n)^n > 0\)
Hence we can set \(F(1) = e^{-\lambda}\) for some \(\lambda \ge 0\). Then, \[\forall k \in \mathbb{N}, F(k) = F(1 + \dots + 1) = (F(1))^k = e^{-k \lambda}\]\[\forall p,q \in \mathbb{N}, (F(1/q))^q = F(1) = e^{-\lambda}\] so \(F(1/q) = e^{-\lambda/ q}\) \(F(p/q) = F(1/q + \dots + 1/q) = (F(1/q))^p = e^{-p\lambda / q}\)
For any \(t \ge 0\), find \(r,s \in \mathbb{Q}\) s.t. \(r \le t \le s\)
As F is decereasing, \[e^{-\lambda s} = F(s) \le F(t) \le F(r) = e^{-\lambda r}\]Let \(s \) tend to t from below and r tend to t from above with both rationals, to get \(F(t) = e^{- \lambda t}\)

Q: Theorem. Markov Property. Let \((X_t)_{t \geq 0}\) be a Poisson process of rate \(\lambda\). Then for all \(s \geq 0\) the process \((X_{s+t} - X_s)_{t \geq 0}\) is also a Poisson process of rate \(\lambda\) and is independent of \((X_r)_{r \leq s}\).
A: We set \(Y_t = X_{t+s} - X_s\) for all \(t \geq 0\). Let \(i \geq 0\) and condition on \(\{X_s = i\}\). Then the jump times for the process \(Y\) are \(J_{i+1}, J_{i+2}, \dots\) and the holding times are \[ T_1 = S_{i+1} - (s - J_i) \quad \text{and} \quad T_j = S_{i+j}, \quad \forall j \geq 2, \] where \(J\) are the jump times and \(S\) the holding times for \(X\). Since \[ \{X_s = i\} = \{J_i \leq s\} \cap \{S_{i+1} > s - J_i\}, \] conditional on \(\{X_s = i\}\) by the memoryless property of the exponential distribution, we see that \(T_1\) has the exponential distribution with parameter \(\lambda\). Moreover, the times \(T_j\) for \(j \geq 2\) are independent and independent of \(S_k\) for \(k \leq i\), and hence independent of \((X_r)_{r \leq s}\). They have the exponential distribution with parameter \(\lambda\), since \(X\) is a Poisson process.

Q: Theorem. Let \((X_t)\) be an increasing right-continuous process taking values in \(\{0,1,2,\dots\}\) with \(X_0 = 0\). Let \(\lambda > 0\). Then the following statements are equivalent:
(a)The holding times \(S_1, S_2, \dots\) are i.i.d. Exponentially distributed with parameter \(\lambda\) and the jump chain is given by \(Y_n = n\), i.e. \(X\) is a Poisson process.
(b)[infinitesimal] \(X\) has independent increments and as \(h \downarrow 0\) uniformly in \(t\) we have    \[\mathbb{P}(X_{t+h} - X_t = 1) = \lambda h + o(h)\]\[ \mathbb{P}(X_{t+h} - X_t = 0) = 1 - \lambda h + o(h)\]
(c)\(X\) has independent and stationary increments and for all \(t \geq 0\) we have \(X_t \sim \text{Poisson}(\lambda t)\).
A: (a)\(\Rightarrow\)(b) If (a) holds, then by the Markov property the increments are independent and stationary. Using stationarity we have uniformly in \(t\) as \(h \to 0\)
\[\mathbb{P}(X_{t+h} - X_t = 0) = \mathbb{P}(X_h = 0) = \mathbb{P}(S_1 > h) = e^{-\lambda h} = 1 - \lambda h + o(h)\]\[\mathbb{P}(X_{t+h} - X_t \geq 1) = \mathbb{P}(X_h \geq 1) = \mathbb{P}(S_1 \leq h) = 1 - e^{-\lambda h} = \lambda h + o(h)\]\[\mathbb{P}(X_{t+h} - X_t \geq 2) \leq \mathbb{P}(S_1 \leq h, S_2 \leq h) = (1 - e^{-\lambda h})^2 = o(h),\]
where \(S_1\) and \(S_2\) are two independent exponential random variables of parameter \(\lambda\). We thus showed that (b) holds.
(b)\(\Rightarrow\)(c) First note that if \(X\) satisfies (b), then \((X_{t+s} - X_s)_t\) also satisfies (b), and hence \(X\) has independent and stationary increments. It remains to prove that \(X_t \sim \text{Poisson}(\lambda t)\).
We set \(p_j(t) = \mathbb{P}(X_t = j)\). Since the increments are independent and \(X\) is increasing, we get for \(j \geq 1\)\[p_j(t + h) = \sum_{i=0}^{j} \mathbb{P}(X_t = j - i) \mathbb{P}(X_{t+h} - X_t = i) = p_j(t)(1 - \lambda h + o(h)) + p_{j-1}(t)(\lambda h + o(h)) + o(h).\]Rearranging we obtain\[\frac{p_j(t+h) - p_j(t)}{h} = -\lambda p_j(t) + \lambda p_{j-1}(t) + o(1).\]Since this holds uniformly in \(t\) we can set \(s = t + h\) and get\[\frac{p_j(s) - p_j(s - h)}{h} = -\lambda p_j(s - h) + \lambda p_{j-1}(s - h) + o(1).\]Hence from the above two equations we immediately get that \(p_j(t)\) is a continuous function of \(t\). Moreover, we can take the limit as \(h \to 0\) and get\[p_j'(t) = -\lambda p_j(t) + \lambda p_{j-1}(t).\]By differentiating \(e^{\lambda t} p_k(t)\) with respect to \(t\) and substituting the above we get\[(e^{\lambda t} p_k(t))' = \lambda e^{\lambda t} p_k(t) + e^{\lambda t} p_k'(t) = \lambda e^{\lambda t} p_{k-1}(t).\]For \(j = 0\), since in order to be at \(0\) at time \(t+h\) we must be at \(0\) at time \(t\), it follows similarly to above that\[p_0'(t) = -\lambda p_0(t),\]which gives that \(p_0(t) = e^{-\lambda t}\). We thus get \(p_1(t) = e^{-\lambda t} \lambda t\) and inductively we obtain\[p_n(t) = e^{-\lambda t} (\lambda t)^n / n!.\]It follows that \(X_t\) has the Poisson distribution with parameter \(\lambda t\).
(c)\(\Rightarrow\)(a) The Poisson process satisfies (c). But (c) determines uniquely the finite dimensional marginals for a right-continuous and increasing process. Therefore (c) implies (a). \(\square\)

Q: Theorem. Superposition. Let \(X\) and \(Y\) be two independent Poisson processes with parameters \(\lambda\) and \(\mu\) respectively. Then \(Z_t = X_t + Y_t\) is also a Poisson process with parameter \(\lambda + \mu\).
A: We are going to use the infinitesimal definition of a Poisson process. Using the independence of \(X\) and \(Y\) we get uniformly in \(t\) as \(h \to 0\)
\[\mathbb{P}(Z_{t+h} - Z_t = 0) = \mathbb{P}(X_{t+h} - X_t = 0, Y_{t+h} - Y_t = 0) = \mathbb{P}(X_{t+h} - X_t = 0) \mathbb{P}(Y_{t+h} - Y_t = 0)\]
\[= (1 - \lambda h + o(h))(1 - \mu h + o(h)) = 1 - (\lambda + \mu)h + o(h).\]
We also have uniformly in \(t\) as \(h \to 0\)
\[\mathbb{P}(Z_{t+h} - Z_t = 1) = \mathbb{P}(X_{t+h} - X_t = 0, Y_{t+h} - Y_t = 1) + \mathbb{P}(X_{t+h} - X_t = 1, Y_{t+h} - Y_t = 0)\]
\[= (1 - \lambda h + o(h))(\mu h + o(h)) + (1 - \mu h + o(h))(\lambda h + o(h)) = (\lambda + \mu)h + o(h).\]
Clearly \(Z\) has independent increments, and hence it is a Poisson process of parameter \(\lambda + \mu\). \(\square\)

Q: Theorem. Thinning. Let \( X \) be a Poisson process of parameter \( \lambda \). Let \( (Z_i)_i \) be i.i.d. Bernoulli random variables with success probability \( p \). Let \( Y \) be a process with values in \( \mathbb{N} \), which jumps at time \( t \) if and only if \( X \) jumps and \( Z_t = 1 \). In other words, we keep every point of \( X \) with probability \( p \) independently over different points. Then \( Y \) is a Poisson process of parameter \( \lambda p \) and \( X - Y \) is an independent Poisson process of parameter \( \lambda (1 - p) \).
A: We will use the infinitesimal definition of a Poisson process to prove the result. The independence of increments for \( Y \) is clear. Since \[ \mathbb{P}(X_{t+h} - X_t \geq 2) = o(h) \]uniformly for all \( t \), we have \[ \mathbb{P}(Y_{t+h} - Y_t = 1) = p \mathbb{P}(X_{t+h} - X_t = 1) + o(h) = \lambda p h + o(h), \] \[ \mathbb{P}(Y_{t+h} - Y_t = 0) = \mathbb{P}(X_{t+h} - X_t = 0) + \mathbb{P}(X_{t+h} - X_t = 1) (1 - p) + o(h) \] \[ = 1 - \lambda h + o(h) + (\lambda h + o(h))(1 - p) = 1 - \lambda p h + o(h). \]This proves that \( Y \) is a Poisson process of rate \( \lambda p \). Since \( X - Y \) is a thinning of \( X \) with probability \( 1 - p \), it follows that it is also a Poisson process of rate \( \lambda (1 - p) \). To prove the independence, it is enough to check that the finite-dimensional marginals are independent, i.e., for \( t_1 \leq t_2 \leq \dots \leq t_k \) and \( n_1 \leq \dots \leq n_k \), \( m_1 \leq \dots \leq m_k \), \[ \mathbb{P}(Y_{t_1} = n_1, \dots, Y_{t_k} = n_k, X_{t_1} - Y_{t_1} = m_1, \dots, X_{t_k} - Y_{t_k} = m_k) \] \[ = \mathbb{P}(Y_{t_1} = n_1, \dots, Y_{t_k} = n_k) \mathbb{P}(X_{t_1} - Y_{t_1} = m_1, \dots, X_{t_k} - Y_{t_k} = m_k). \] We will only show it for a fixed \( t \), but the general case follows similarly. Using the independence of the \( Z_i \)'s, we get \[ \mathbb{P}(Y_t = n, X_t - Y_t = m) = \mathbb{P}(X_t = m + n, Y_t = n) \] \[ = \left( e^{-\lambda t} \frac{(\lambda t p)^n}{n!} \right) \left( e^{-\lambda t(1 - p)} \frac{(\lambda t (1 - p))^m}{m!} \right) = \mathbb{P}(Y_t = n) \mathbb{P}(X_t - Y_t = m). \] which shows that \( Y \) is independent of \( X_t - Y_t \) for all times \( t \). \(\square\)

Q: Theorem. Let \( X \) be a Poisson process. Conditional on the event \( \{X_t = n\} \), the jump times \( J_1, \dots, J_n \) have joint density function
\[f(t_1, \dots, t_n) = \frac{n!}{t^n} 1(0 \leq t_1 \leq \dots \leq t_n \leq t).\]
A: Since the times \( S_1, S_2, \dots, S_{n+1} \) are independent, their joint density is given by
\[\lambda^{n+1} e^{-\lambda(s_1+\dots+s_{n+1})} 1(s_1, \dots, s_{n+1} \geq 0).\]
The jump times \( J_1 = S_1, J_2 = S_1 + S_2, \dots, J_{n+1} = S_1 + \dots + S_n + S_{n+1} \) have joint density given by
\[\lambda^{n+1} e^{-\lambda t_{n+1}} 1(0 \leq t_1 \leq \dots \leq t_{n+1}).\]
This follows by induction on \( n \). For \( n = 2 \), we have
\[\mathbb{P}(S_1 \leq x_1, S_1 + S_2 \leq x_2) = \int_0^{x_1} \lambda e^{-\lambda x} \mathbb{P}(S_2 \leq x_2 - x) dx,\]
which upon differentiation gives the formula.
Now taking \( A \subseteq \mathbb{R}^n \), we compute
\[\mathbb{P}((J_1, \dots, J_n) \in A \mid X_t = n) = \frac{\mathbb{P}((J_1, \dots, J_n) \in A, X_t = n)}{\mathbb{P}(X_t = n)}.\]
For the numerator, using the density above, we obtain
\[\mathbb{P}((J_1, \dots, J_n) \in A, X_t = n) = \mathbb{P}((J_1, \dots, J_n) \in A, J_n \leq t \leq J_{n+1})\]
\[= \int_{(t_1, \dots, t_n) \in A}\int_{t}^{\infty} \lambda^{n+1} e^{-\lambda t_{n+1}} 1(0 \leq t_1 \leq \dots \leq t_n \leq t \;e t_{n+1}) dt_1 \dots dt_n dt_{n+1}\]
\[= \lambda^n e^{-\lambda t} \int_{(t_1, \dots, t_n) \in A} 1(0 \leq t_1 \leq \dots \leq t_n \leq t) dt_1 \dots dt_n.\]
Since \( X_t \sim \text{Poisson}(\lambda t) \), we have \( \mathbb{P}(X_t = n) = \frac{(\lambda t)^n e^{-\lambda t}}{n!} \). Dividing both sides, we get
\[\mathbb{P}((J_1, \dots, J_n) \in A \mid X_t = n) = \frac{n!}{t^n} \int_{(t_1, \dots, t_n) \in A} 1(0 \leq t_1 \leq \dots \leq t_n \leq t) dt_1 \dots dt_n,\]
which proves the density function for the jump times.

Q: Proposition. Let \(X\) be a birth process with rates \((q_i)\) with \(X_0 = 1\).
(1) If \(\sum_{i=1}^{\infty} \frac{1}{q_i} < \infty\), then \(\mathbb{P}(\zeta < \infty) = 1\).
(2) If \(\sum_{i=1}^{\infty} \frac{1}{q_i} = \infty\), then \(\mathbb{P}(\zeta = \infty) = 1\).
A: (1) If \(\sum_n \frac{1}{q_n} < \infty\), then we get \(\mathbb{E} \left[\sum_n S_n \right] = \sum_n \frac{1}{q_n} < \infty\), and hence \(\mathbb{P} \left(\sum_n S_n < \infty \right) = 1\).
(2) If \(\sum_n \frac{1}{q_n} = \infty\), then \(\prod_n \left(1 + \frac{1}{q_n} \right) = \infty\). By monotone convergence and independence, we get
\[\mathbb{E} \left[ \exp \left( - \sum_{n=1}^{\infty} S_n \right) \right] = \prod_{n=1}^{\infty} \mathbb{E} \left[ \exp (-S_n) \right] = \prod_{n=1}^{\infty} \left( 1 + \frac{1}{q_n} \right)^{-1} = 0.\]
Hence this gives that \(\sum_n S_n = \infty\) with probability 1.

Q: Theorem. Markov Property. Let \(X\) be a birth process of rates \((q_i)\). Then conditional on \(X_s = i\), the process \((X_{s+t})_{t \geq 0}\) is [...]
A: a birth process of rates \((q_i)\) starting from \(i\) and independent of \((X_r : r \leq s)\).

Q: Theorem. Let \(X\) be an increasing, right-continuous process with values in \(\{1,2,\dots\} \cup \{\infty\}\).
Let \(0 \leq q_j < \infty\) for all \(j \geq 0\). Then the following three conditions are equivalent:
A: (1) (jump chain/holding time definition) condition on \(X_0 = i\), the holding times \(S_1, S_2, \dots\) are independent exponential random variables of parameters \(q_i, q_{i+1}, \dots\) respectively and the jump chain is given by \(Y_n = i + n\) for all \(n\);
(2) (infinitesimal definition) for all \(t,h \geq 0\), conditional on \(X_t = i\), the process \((X_{t+h})_h\) is independent of \((X_s : s \leq t)\) and as \(h \downarrow 0\) uniformly in \(t\),
\[\mathbb{P}(X_{t+h} = i \mid X_t = i) = 1 - q_i h + o(h),\]
\[\mathbb{P}(X_{t+h} = i+1 \mid X_t = i) = q_i h + o(h);\]
(3) (transition probability definition) for all \(n = 0,1,2,\dots\), all times \(0 \leq t_0 \leq \dots \leq t_{n+1}\) and all states \(i_0, \dots, i_n, i_{n+1}\),
\[\mathbb{P}(X_{t_{n+1}} = i_{n+1} \mid X_0 = i_0, \dots, X_{t_n} = i_n) = p_{i_n i_{n+1}}(t_{n+1} - t_n),\]
where \((p_{i,j}(t) : i,j = 0,1,2,\dots)\) is the unique solution of the forward equations \(P'(t) = P(t)Q\).

Q: Definition. Let S be a countable set. Then a Q-matrix on S is a matrix \(Q = (q_{ij}: i,j \in S)\) satisfying the following:[...]
A: - \(0 \le -q_{ii} < \infty\) for all i
- \(q_{ij} \ge 0\) for all \(i \neq j\)
- \(\sum_{j} q_{ij} = 0\) for all i

Q: Given a Q-matrix how do we define the jump matrix?
A: For \(x\neq y\) with \(q_x \neq 0\) we set \[p_{xy} = \frac{q_{xy}}{-q_{xx}} = \frac{q_{xy}}{q_x}\]and \(p_{xx} = 0\)
If \(q_{x} = 0\) we set \(p_{xy} = \mathbf{1}(x = y)\)

Q: Definition. A Markov chain X with initial distribution λ and infinitesimal generator Q, which is a Q-matrix, is [...] We write (Xt) = Markov(Q, λ).
A: a stochastic process with jump chain \(Y_n = X_{J_n}\) being a discrete time Markov chain with \(Y_0 \sim \lambda\) and transition matrix P such that conditional on Y0, Y1, . . . , Yn the holding times S1,S2,...,Sn+1 are independent Exponential random variables with rates q(Y0),...,q(Yn).

Q: Theorem. Let X be Markov\((Q, \lambda)\) on S. Then \(\mathbb{P}(\zeta = \infty) = 1\) if any of the following holds:
1. S is finite
2. \(\sup_x q_x < \infty\)
3. \(X_0 = x\) and x is recurrent for the jump chain
A: Since (1) implies (2), we will prove it for (2).
Set \(q = \sup_x q_x\). The holding times satisfy \(S_n \ge T_n /q\), where \(T_n \sim \text{Exp}(1)\) and are iid. By the strong law of large numbers we now obtain \[\zeta = \sum_{n=1}^{\infty} S_n \ge \frac{1}{q} \cdot \sum_{n=1}^{\infty} T_n= \infty \text{ with probability 1}\]Suppose that (3) holds and let \((N_i)_{i \ge 1}\) be the times when the jump chain Y visits x. By the strong law of large numbers again we get \[\zeta \ge \sum_{i=1}^{\infty} S_{N_i} = \frac{1}{q_x} \sum_{i=1}^{\infty}T_{N_i} = \infty \text{ with probability 1}\]

Q: Theorem. Let X be a minimal right continuous process with values in a countable set S. Let Q be a Q-matrix with jump matrix P. Then what are the equivalent conditions to describe this?
A: - X is a continuous time Markov chain with generator Q
- for all \(n \ge 0, 0 \le t_0 \le \dots \le t_n \) and all states \(x_0, \dots , x_{n+1}\) \[\mathbb{P}(X_{t_{n+1}} = x_{n+1}| X_{t_n} = x_{n}, \dots , X_{t_0} = x_0) = p_{x_n x_{n+1}}(t_{n+1} - t_n)\]where \((p_{xy}(t))\) is the minimal non-negative solution to the backward equation \[P'(t) = QP(t), P(0) = I\]

Q: Theorem. Let \( Q \) be a \( Q \)-matrix on a finite set \( S \) and let \( P(t) = e^{tQ} \). Then \( (P(t))_t \) has the following properties:
1. \( P(t+s) = P(t)P(s) \) for all \( s, t \);
2. \( (P(t)) \) is the unique solution to the forward equation \[ \frac{d}{dt} P(t) = P(t)Q \] and \( P(0) = I \);
3. \( (P(t)) \) is the unique solution to the backward equation \[ \frac{d}{dt} P(t) = Q P(t) \] and \( P(0) = I \);
4. For \( k = 0, 1, \dots \) we have \[ \left( \frac{d}{dt} \right)^k \bigg|_{t=0} P(t) = Q^k. \]
A: 1. Since the matrices \( sQ \) and \( tQ \) commute for all \( s, t \geq 0 \), the first property is immediate.
2. - 3. Since the sum defining \( e^{tQ} \) has infinite radius of convergence, we can differentiate term by term and get that
   \[\frac{d}{dt} P(t) = \sum_{k=1}^{\infty} \frac{t^{k-1}}{(k-1)!} Q^{k-1} \cdot Q = P(t) Q.\]
   Obviously \( P(0) = I \). Suppose that \( \tilde{P} \) is another solution. Then
   \[\frac{d}{dt} (\tilde{P}(t)e^{-tQ}) = \tilde{P}'(t)e^{-tQ} + \tilde{P}(t) \frac{d}{dt} (e^{-tQ}) = \tilde{P}(t) Q e^{-tQ} - \tilde{P}(t) Q e^{-tQ} = 0\]
   and since \( \tilde{P}(0) = I \), it follows that \( \tilde{P} = P \).
   The case of the forward equation follows in exactly the same way.
4. Differentiating term by term gives the claimed identity. s

Q: Theorem. Let \( S \) be a finite state space and let \( Q \) be a matrix. Then it is a \( Q \)-matrix if and only if \( P(t) = e^{tQ} \) is a stochastic matrix for all \( t \geq 0 \).
A: For \( t \downarrow 0 \) we can write
\[P(t) = I + tQ + O(t^2).\]
Hence for all \( x \neq y \) we get that \( q_{xy} \geq 0 \) if and only if \( p_{xy}(t) \geq 0 \) for all \( t \geq 0 \) sufficiently small. Since \( P(t) = P(t/n)^n \) for all \( n \), we obtain that \( q_{xy} \geq 0 \) for \( x \neq y \) if and only if \( p_{xy}(t) \geq 0 \) for all \( t \geq 0 \) and all \( x, y \).
Assume now that \( Q \) is a \( Q \)-matrix. Then \( \sum_y q_{xy} = 0 \) for all \( x \) and
\[\sum_y q_{xy}(n) = \sum_y \sum_z q_{xz}(n-1) q_{zy} = \sum_z q_{xz}(n-1) \sum_y q_{zy} = 0,\]
i.e. also \( Q^n \) has zero sum rows. Hence we obtain
\[\sum_y p_{xy}(t) = 1 + \sum_{k=1}^{\infty} \frac{t^k}{k!} \sum_y q_{xy}(k) = 1,\]
which means that \( P(t) \) is a stochastic matrix.
Assume now that \( P(t) \) is a stochastic matrix. Then
\[\sum_y q_{xy} = \frac{d}{dt} \bigg|_{t=0} \sum_y p_{xy}(t) = 0,\]
which shows that \( Q \) is a \( Q \)-matrix. \(\square\)

Q: Theorem. Let \(X\) be a right continuous process with values in a finite set \(S\) and let \(Q\) be a \(Q\)-matrix on \(S\). Then the following are equivalent:
1. The process \(X\) is Markov with generator \(Q\);
2. *[Infinitesimal definition]* Conditional on \(X_s = x\), the process \((X_{s+t})_{t \geq 0}\) is independent of \((X_r)_{r \leq s}\) and uniformly in \(t\) as \(h \downarrow 0\) for all \(x, y\),
   \[P(X_{t+h} = y \mid X_t = x) = \mathbf{1}(x = y) + q_{xy} h + O(h)\]
3. For all \(n \geq 0\), \(0 \leq t_0 \leq \dots \leq t_n\) and all states \(x_0, \dots, x_n\),
   \[P(X_{t_n} = x_n \mid X_{t_{n-1}} = x_{n-1}, \dots, X_{t_0} = x_0) = p_{x_{n-1} x_n}(t_n - t_{n-1})\]
   where \(p_{xy}(t)\) is the solution to the forward equation
   \[P'(t) = P(t) Q \quad \text{and} \quad P(0) = I\]
A: (c) \(\Rightarrow\) (b): Since the state space is finite, from Theorem 1.28 we obtain that \(P(t) = e^{tQ}\) and it is the unique solution to both the forward and backward equation. Then as \(t \downarrow 0\), we get
   \[P(t) = I + tQ + O(t^2)\]So for all \(t > 0\) as \(h \downarrow 0\) for all \(x, y\),
   \[P(X_{t+h} = y \mid X_t = x) = \mathbf{1}(x = y) + q_{xy} h + O(h)\](b) \(\Rightarrow\) (c): For all \(x, y \in S\), we have uniformly for all \(h \downarrow 0\),
   \[p_{xy}(t + h) = \sum_{z} P(X_{t+h} = y, X_t = z) = \sum_{z} (\mathbf{1}(x = y) + q_{xy} h + O(h)) p_{xz}(t)\]and rearranging we get
\[\frac{p_{xy}(t+h) - p_{xy}(t)}{h} = \sum_z q_{zy}p_{xz}(t) + O(h)\]since the state space is finite. Because this holds uniformly for all \(t\), we can replace \(t + h\) by \(t - h\) as in the proof of Theorem 1.24 and thus like before we can differentiate and deduce\[p_{xy}'(t) = \sum_{z}p_{xz}(t)q_{zy}\]
which shows that \((p_{xy}(t))\) satisfies the forward equation and this finishes the proof. \(\square\)

Q: Definition. Let \(x,y \in S\). We say that x leads to y and denote it by \(x \to y\) if [...]. We say that x and y communicate if [...]
A: \(\mathbb{P}_x (X_t = y \text{ for some } t\ge 0) > 0\); \(x \to y\) and \(y \to x\)

Q: Theorem. Let \(X\) be a continuous-time Markov chain with generator \(Q\) and transition semigroup \(P(t)\). For any two states \(x\) and \(y\), the following are equivalent:
1. \( x \to y \)
2. \( x \to y \) for the jump chain
3. \( q_{x_0 x_1} \cdots q_{x_{n-1}x_n} > 0 \) for some \( x = x_0, \dots, x_n = y \)
4. \( p_{xy}(t) > 0 \) for all \( t > 0 \)
5. \( p_{xy}(t) > 0 \) for some \( t > 0 \)
A: The implications \( (iv) \Rightarrow (v) \Rightarrow (i) \Rightarrow (ii) \) are immediate.
\( (ii) \Rightarrow (iii) \): Since \( x \to y \) for the jump chain, there exist \( x_0 = x, x_1, \dots, x_n = y \) such that
\[p_{x_0 x_1} \cdots p_{x_{n-1} x_n} > 0.\]
By the definition of the jump matrix, it follows that \( q_{x_i x_{i+1}} > 0 \) for all \( i = 0, \dots, n - 1 \), proving (iii).
\( (iii) \Rightarrow (iv) \): If \( q_{wz} > 0 \), then
\[p_{wz}(t) \geq \mathbb{P}_w(J_1 \leq t, Y_1 = z, S_2 > t) = (1 - e^{-q_w t}) \frac{q_{wz}}{q_w} e^{-q_z t} > 0.\]
Using this, we obtain
\[p_{xy}(t) \geq p_{x_0 x_1}(t/n) \cdots p_{x_{n-1}x_n}(t/n) > 0 \quad \forall t > 0.\]
Thus, the theorem is proved.

Q: Theorem. Let \( A \subseteq S \). The vector of hitting probabilities \( (h_A(x))_{x \in S} \) is the minimal non-negative solution to the system of linear equations:
- \( h_A(x) = 1 \) for all \( x \in A \)
- \( Q h_A(x) = \sum_{y \in S} q_{xy} h_A(y) = 0 \) for all \( x \notin A \).
A: For the jump chain, we have that \( h_A(x) \) is the minimal non-negative solution to
\[h_A(x) = 1 \quad \forall x \in A\]
\[h_A(x) = \sum_{y \neq x} h_A(y) p_{xy} \quad \forall x \notin A.\]
Rewriting the second equation:
\[q_x h_A(x) = \sum_{y \neq x} h_A(y) q_{xy} = \sum_{y} h_A(y) q_{xy} = 0 \Rightarrow Q h_A(x) = 0.\]
The proof of minimality follows from the discrete case. \( \square \)

Q: Theorem. Let \( X \) be a continuous-time Markov chain with generator \( Q \) and \( A \subseteq S \). Suppose that \( q_x > 0 \) for all \( x \notin A \). Then \( k_A(x) = \mathbb{E}_x[T_A] \) is the minimal non-negative solution to:
- \( k_A(x) = 0 \) for all \( x \in A \)
- \( Q k_A(x) = \sum_{y} q_{xy} k_A(y) = -1 \) for all \( x \notin A \).
A: If \( x \in A \), then \( T_A = 0 \), so \( k_A(x) = 0 \).
If \( x \notin A \), then by the Markov property,
\[\mathbb{E}_x[T_A - J_1 \mid Y_1 = y] = \mathbb{E}_y[T_A].\]
Conditioning on \( Y_1 \), we obtain
\[k_A(x) = \mathbb{E}_x[J_1] + \sum_{y \neq x} p_{xy} \mathbb{E}_y[T_A] = \frac{1}{q_x} + \sum_{y \neq x} \frac{q_{xy}}{q_x} k_A(y).\]
Rearranging, we get \( Q k_A(x) = -1 \), proving the result. \( \square \)

Q: Definition. We call a state x recurrent if \([...]\). We call x transient if \([...]\).
A: P_x(\{ t : X_t = x\} \text{ is unbounded}) = 1; P_x(\{ t : X_t = x\} \text{ is unbounded}) = 0

Q: Theorem. Let \( X \) be a continuous-time Markov chain and \( Y \) its jump chain. Then:
1. If \( x \) is recurrent for \( Y \), then \( x \) is recurrent for \( X \).
2. If \( x \) is transient for \( Y \), then \( x \) is transient for \( X \).
3. Every state is either recurrent or transient.
4. Recurrence and transience are class properties.
A: 1. Suppose that \( x \) is recurrent for \( Y \) and \( X_0 = x \). Then \( X \) cannot explode, meaning \( \mathbb{P}_x(\zeta = \infty) = 1 \), or equivalently \( J_n \to \infty \) with probability 1 starting from \( x \). Since \( X_n = Y_n \) for all \( n \) and \( Y \) visits \( x \) infinitely many times, it follows that the set \( \{t \geq 0 : X_t = x\} \) is unbounded, proving that \( x \) is recurrent for \( X \).
2. If \( x \) is transient for \( Y \), then \( q_x > 0 \), otherwise \( x \) would be absorbing for \( Y \). Define
   \[N = \sup \{n : Y_n = x\} < \infty\]
   Since \( (Y_n : n \leq N) \) cannot contain any absorbing state, we have \( J_{N+1} < \infty \), so \( x \) is transient for \( X \).
3. The fact that every state is either recurrent or transient follows from the discrete-time case.
4. Recurrence and transience are class properties in the discrete setting, so they also hold in the continuous setting. \( \square \)

Q: Theorem. The state \( x \) is recurrent for \( X \) if and only if
\[\int_0^\infty p_{xx}(t) dt = \infty.\]
The state \( x \) is transient for \( X \) if and only if
\[\int_0^\infty p_{xx}(t) dt < \infty.\]
A: If \( q_x = 0 \), then \( x \) is recurrent and \( p_{xx}(t) = 1 \) for all \( t \), so
\[\int_0^\infty p_{xx}(t) dt = \infty.\]
If \( q_x > 0 \), it suffices to show that
\[\int_0^\infty p_{xx}(t) dt = \frac{1}{q_x} \sum_{n=0}^{\infty} p_{xx}(n),\]
since the result then follows from the discrete-time dichotomy. Using (2.1), we obtain
\[\int_0^\infty p_{xx}(t) dt = \mathbb{E}_x \left[ \int_0^\infty 1(X_t = x) dt \right]\]
\[= \mathbb{E}_x \left[ \sum_{n=0}^{\infty} S_{n+1} 1(Y_n = x) \right] = \sum_{n=0}^{\infty} \mathbb{E}_x [S_{n+1} \mid Y_n = x] p_{xx}(n).\]
Using Fubini and the fact that \( S_{n+1} \) is exponentially distributed with parameter \( q_x \), we get
\[\int_0^\infty p_{xx}(t) dt = \frac{1}{q_x} \sum_{n=0}^{\infty} p_{xx}(n).\]
Thus, the theorem is proved. \( \square \)

Q: Definition. Let Q be the geneartor of a continuous time Markov chain and let \(\lambda\) be a measure. It is called invariant if [...]
A: \(\lambda Q = 0\).

Q: Theorem. Let \( X \) be a continuous time chain with generator \( Q \) and let \( Y \) be its jump chain. The measure \( \pi \) is invariant for \( X \) if and only if the measure \( \mu \) defined by \( \mu_x = q_x \pi_x \) is invariant for \( Y \).
A: First note that \( q_x (p_{xy} - \mathbf{1}(x = y)) = q_{xy} \) and so we get
\[\sum_x \pi(x)q_{xy} = \sum_x \pi(x)q_x(p_{xy} - \mathbf{1}(x = y)) = \sum_x \mu(x)(p_{xy} - \mathbf{1}(x = y)).\]
Therefore, \( \mu P = \mu \Leftrightarrow \pi Q = 0 \). \(\square\)

Q: Theorem. Let \( X \) be an irreducible continuous time Markov chain with generator \( Q \). The following statements are equivalent:
[...]
[...]
[...]
A: (i) every state is positive recurrent;; (ii) some state is positive recurrent;; (iii) \( X \) is non-explosive and has an invariant distribution \( \lambda \).
Back Extra: Furthermore, when (iii) holds, then \( \lambda(x) = (q_x m_x)^{-1} \) for all \( x \).

Q: Theorem. Let \( Y \) be a discrete time Markov chain which is irreducible and recurrent and let \( x \) be a state. Then the measure
\[\nu(y) = [...]\]
is invariant for \( Y \) and for all \( y \) it satisfies \( 0 < \nu(y) < \infty \) and \( \nu(x) = 1 \).
A: \mathbb{E}_x \left[ \sum_{n=0}^{H_x-1} \mathbf{1}(Y_n = y) \right]

Q: Theorem. Let \( X \) be an irreducible and recurrent continuous time Markov chain with generator \( Q \). Then \( X \) has an invariant measure which is unique up to scalar multiplication.
A: Since the chain is irreducible, it follows that \( q_x > 0 \) for all \( x \) (except if the state space is a singleton, which is a trivial case).
The jump chain \( Y \) will then also be irreducible and recurrent, and hence the measure \( \nu \) defined in Theorem 2.11 is invariant for \( Y \) and it is unique up to scalar multiplication.
Since we assumed that \( q_x > 0 \), from Theorem 2.10 we get that the measure \( \pi(x) = \nu(x)/q_x \) is invariant for \( X \) and it is unique up to scalar multiples.

Q: Theorem. Let \( X \) be a continuous time Markov chain with generator \( Q \) on a finite state space \( S \). Then \(\pi P(t) = \pi \ \forall t \geq 0 \Leftrightarrow \pi\) is invariant.
A: The transition semigroup satisfies \( P'(t) = P(t)Q = QP(t) \). Differentiating \(\pi P(t) = \pi\) with respect to \( t \) we get
\[\frac{d}{dt}(\pi P(t)) = \pi P'(t) = \pi QP(t) = \pi P(t)Q,\]
where in the first equality we were able to interchange differentiation and sum, because \(|S| < \infty\). Therefore if \(\pi P(t) = \pi\) for all \( t \), then from the above equality we obtain
\[0 = \frac{d}{dt}(\pi P(t)) = \pi P(t)Q = \pi Q.\]
If \(\pi Q = 0\), then \(\frac{d}{dt}(\pi P(t)) = 0\) and thus \(\pi P(t) = \pi P(0) = \pi\) for all \( t \).

Q: Lem..a Let \( X \) be a continuous time Markov chain and let \( t > 0 \) be fixed. Set \( Z_n = X_{nt} \).
(i) If \( x \) is recurrent for \( X \), then \( x \) is recurrent for \( Z \) too.
(ii) If \( x \) is transient for \( X \), then \( x \) is transient for \( Z \) too.
A: Part (ii) is obvious, since if the set of times that \( X \) visits \( x \) is bounded, then \( Z \) cannot visit \( x \) infinitely many times.
Suppose now that \( x \) is recurrent for \( X \). We will use the criterion for recurrence in terms of the convergence of the sum \( \sum_{n=0}^{\infty} p_{xx}(n) \). We divide time into intervals of length \( t \). Then we have
\[\int_0^{\infty} p_{xx}(s) \, ds = \sum_{n=0}^{\infty} \int_{tn}^{t(n+1)} p_{xx}(s) \, ds.\]
For \( s \in (tn, t(n+1)) \) by the Markov property we have \( p_{xx}((n+1)t) \geq e^{-q_x t} p_{xx}(s) \). Therefore, we deduce
\[\int_0^{\infty} p_{xx}(s) \, ds \leq te^{q_x t} \sum_{n=0}^{\infty} p_{xx}((n+1)t).\]
Since \( x \) is recurrent for \( X \), by Theorem 2.8 we obtain that the integral on the left hand side above is infinite, and hence
\[\sum_{n=0}^{\infty} p_{xx}(nt) = \infty\]
and this finishes the proof.

Q: Lemma. Let \( Q \) be a \( Q \)-matrix with semigroup \( P(t) \). Then
\[|p_{xy}(t + h) - p_{xy}(t)| \leq 1 - e^{-q_x h}.\]
A: By Chapman Kolmogorov we have
\[|p_{xy}(t + h) - p_{xy}(t)| = \left| \sum_z p_{xz}(h)p_{zy}(t) - p_{xy}(t) \right| = \left| \sum_{z \neq x} p_{xz}(h)p_{zy}(t) + p_{xx}(h)p_{xy}(t) - p_{xy}(t) \right|\]
\[= \left| \sum_{z \neq x} p_{xz}(h)p_{zy}(t) - p_{xy}(t)(1 - p_{xx}(h)) \right|\]
\[\leq 1 - p_{xx}(h) \leq \mathbb{P}_x(J_1 \leq h) = 1 - e^{-q_x h}\]
and this finishes the proof.

Q: Theorem. Convergence to Equilibrium. Let \( X \) be an irreducible non explosive continuous time chain on \( S \) with generator \( Q \). Suppose that \( \lambda \) is an invariant distribution. Then for all \( x, y \in S \) we have
\[p_{xy}(t) \to \lambda(y) \quad as \quad t \to \infty.\]
A: Fix \( h > 0 \) such that \( 1 - e^{-q_x h} \leq \varepsilon / 2 \) and let \( Z_n = X_{nh} \) be a discrete time chain with transition matrix \( P(h) \). Since \( X \) is irreducible, Theorem 2.1 gives that \( p_{xy}(h) > 0 \) for all \( x, y \) which shows that \( Z \) is irreducible and aperiodic.
Since \( X \) is irreducible, non-explosive and has an invariant distribution, Theorem 2.15 gives that \( X \) is positive recurrent. Thus we can apply Theorem 2.19 to get that \( \lambda \) is an invariant distribution for \( Z \). Hence applying the convergence to equilibrium theorem for discrete time chains we obtain for all \( x, y \)
\[p_{xy}(nh) \to \lambda(y) \quad as \quad n \to \infty.\]
This means that for all \( \varepsilon > 0 \), there exists \( n_0 \) such that for all \( n \geq n_0 \) we have
\[|p_{xy}(nh) - \lambda(y)| \leq \frac{\varepsilon}{2}.\]
Let \( t \geq n_0 h \). Then there must exist \( n \in \mathbb{N} \) with \( n \geq n_0 \) such that \( nh \leq t < (n + 1)h \). Therefore by the choice of \( h \) we deduce
\[|p_{xy}(t) - \lambda(y)| \leq |p_{xy}(t) - p_{xy}(nh)| + |p_{xy}(nh) - \lambda(y)| \leq 1 - e^{-q_x(t-nh)} + \frac{\varepsilon}{2} \leq \varepsilon.\]
Hence this shows that \( p_{xy}(t) \to \lambda(y) \) as \( t \to \infty \).

Q: Definition. Let X be a Markov chain with generator Q. It is called reversible if [...] A measure \(\lambda\) and a Q-matrix Q are said to be in detailed balance if [...]
A: for all \(T>0\) the processees \((X_t)_{0 \le t \le T}\) and \((X_{T-t})_{0 \le t \le T}\) have the same distribution.; for all x,y we have \[\lambda(x)q_{xy} = \lambda(y)q_{yx}\]

Q: Lemma. Suppose that Q and \(\lambda\) are in detailed balance. Then \(\lambda\) is an invariant measure for Q
A: We need to show that \(\lambda Q = 0\). Taking the sum \[\sum_x \lambda(x)q_{xy} = \sum_x \lambda(y)q_{yx} = 0\]

Q: Theorem. Let \( X \) be irreducible and non-explosive with generator \( Q \) and let \( \pi \) be a probability distribution with \( X_0 \sim \pi \). Then \( \pi \) and \( Q \) are in detailed balance \( \Leftrightarrow (X_t)_{t \geq 0} \) is reversible.
A: If \( \pi \) and \( Q \) are in detailed balance, then \( \widehat{Q} = Q \), where \( \widehat{Q} \) is the matrix defined in Theorem 2.23 and \( \pi \) is the invariant distribution of \( \widehat{Q} \). Therefore, from Theorem 2.23 again, the reversed chain has the same distribution as \( X \), and hence \( X \) is reversible.
Suppose now that \( X \) is reversible. Then \( \pi \) is an invariant distribution. Then from Theorem 2.23 we get that \( \widehat{Q} = Q \), which immediately gives that \( \pi \) and \( Q \) are in detailed balance.

Q: Lemma. A measure \(\pi\) is invariant for a birth and death chain if and only if it solves the detailed balance equations.
A: If \(\pi\) solves the detailed balance equations, then \(\pi\) is invariant by Lemma 2.25.
Suppose that \(\pi\) is an invariant measure for \(X\). Then \(\pi Q = 0\) or equivalently \(\sum_i \pi_i q_{i,j} = 0\) for all \(j\). If \(j \geq 1\) this means
\[\pi_{j-1} \lambda_{j-1} + \pi_{j+1} \mu_{j+1} = \pi_j (\lambda_j + \mu_j) \Leftrightarrow \pi_{j+1} \mu_{j+1} - \pi_j \lambda_j = \pi_j \mu_j - \pi_{j-1} \lambda_{j-1}.\]
For \(j = 0\) we have \(\pi_0 \lambda_0 = \pi_1 \mu_1\). Plugging this into the right hand side of the above equation and applying induction gives that for all \(j\) we have
\[\pi_j \lambda_j = \pi_{j+1} \mu_{j+1},\]
i.e. the detailed balance equations hold.

Q: Theorem. Let \(\rho = \lambda/\mu\) for a M/M/1 queue. Then X is transient iff \(\rho > 1\) and recurrent iff \(\rho \le 1\), and is positive recurrent iff \(\rho < 1\). In the latter case X has an equilibrium distribution given by \[\pi(n) = (1-\rho)\rho^n\]Suppose that \(\rho < 1\), the queue is in equilbrium, i.e. \(X_0 \sim \pi\) and W is the waiting time of a customer that arrives at time t. Then the distribution of W is \(\text{Exp}(\mu - \lambda)\)
A: The jump chain is given by a biased random walk on the integers with reflection at 0: the probability of jumping to the right is \( p = \lambda / (\lambda + \mu) \). Hence the chain \( X \) is transient if and only if \( p > 1/2 \) or equivalently \( \lambda > \mu \), and recurrent otherwise. Concerning positive recurrence, observe that \(\sup_i q_i < \infty\) so by Theorem II.20 there is a.s. no explosion. Therefore by Theorem 2.15 positive recurrence is equivalent to the existence of an invariant distribution. Furthermore, since \( X \) is a birth and death chain, by Lemma 2.29 it suffices to solve the Detailed Balance Equations, which read:
\[\pi(n)\lambda = \pi(n+1)\mu\]
for all \( n \geq 0 \). We thus find \( \pi(n+1) = (\lambda/\mu)^{n+1}\pi(0) \) inductively and deduce the desired form for \( \pi(n) \). Note that \( \pi \) is the distribution of a (shifted) geometric random variable. (Shifted because it can be equal to 0).
Suppose now that \( \rho < 1 \) and \( X_0 \sim \pi \). Suppose a customer arrives at time \( t \) and let \( N \) be the number of customers already in the queue at this time. Since \( X_0 \sim \pi \), it follows that the distribution of \( N \) is \( \pi \). Then
\[W = \sum_{i=1}^{N+1} T_i,\]where (Ti) is an i.i.d. sequence of exponential random variables with parameter μ and independent of N . We also have that N + 1 is a geometric variable that starts from 1. Therefore, using Exercise 2 from Example Sheet 1, we deduce that W is exponential with parameter μ(1 − ρ) = μ − λ.

Q: Theorem. For a \(M/M/\infty\) queue, the queue length \(X_t\) is a positive recurrent Markov chain for all \(\lambda, \mu > 0\). Furthermore the invariant distribution is Poisson with parameter \(\rho = \lambda / \mu\).
A: The rates are \( q_{i,i+1} = \lambda \) and \( q_{i,i-1} = i\mu \) (since when there are \( i \) customers in the queue, the first service will be completed after an exponential time with rate \( i\mu \)). Thus \( X \) is a birth and death chain; hence for an invariant distribution it suffices to solve the Detailed Balance Equations:
\[\lambda \pi_{n-1} = n \mu \pi_n \quad \forall \, n \Leftrightarrow \pi_n = \frac{1}{n} \frac{\lambda}{\mu} \pi_{n-1} = \ldots = \frac{1}{n!} \left( \frac{\lambda}{\mu} \right)^n \pi_0.\]
Hence the Poisson distribution with parameter \( \rho = \lambda / \mu \) is invariant. It remains to check that \( X \) is not explosive. This is not straightforward as the rates are unbounded. However, we will show that the jump chain \( Y \) is recurrent, and so using Theorem II.20 this means that \( X \) is non-explosive.
Here is another way of proving that \( Y \) is recurrent. We now set
\[\gamma_i = \frac{p_{i,i-1}p_{i-1,i-2} \cdots p_{1,0}}{p_{i,i+1}p_{i-1,i} \cdots p_{1,2}}.\]
From IB Markov chains (see for instance [2, page 16]) we know that if \(\sum_i \gamma_i = \infty\), then the chain is recurrent. Indeed, in this case we have
\[\sum_i \gamma_i \geq A \sum_{i \geq k} 2^{i-k+2} = \infty,\]
and hence \( Y \) is recurrent and therefore \( X \) is non-explosive. This concludes the proof.

Q: Theorem. Consider a \(M/M/1\) queue and assume \(\rho = \lambda / \mu < 1\) so there is an invariant distribution. Let \(D_t\) denote the number of customers who have departed the queue up to time t. At equilibrium, \(D_t\) is a Poisson process with rate \(\lambda\), independently of \(\mu\). Furthermore, \(X_t\) is independent from \((D_s, s \le t)\).
A: The proof consists of a really nice time-reversal argument. Recall that \( X \) is a birth and death chain and has an invariant distribution. So at equilibrium, \( X \) is reversible: thus for a given \( T > 0 \), if \( \hat{X}_t = X_{T-t} \) we know that \( (\hat{X}_t, 0 \leq t \leq T) \) has the same distribution as \( (X_t, 0 \leq t \leq T) \). Hence \( \hat{X} \) experiences a jump of size +1 at constant rate \( \lambda \). But note that \( \hat{X} \) has a jump of size +1 at time \( t \) if and only if a customer departs the queue at time \( T - t \). Therefore, departures from \( X \) become arrivals for \( \hat{X} \), i.e. if \( \hat{A} \) stands for the arrival process of \( \hat{X} \), then for all \( t \leq T \) we have
\[\hat{A}_t = D_T - D_{T-t}.\]
Since the time reversal of a Poisson process is a Poisson process, we deduce that \( (D_t, t \leq T) \) is itself a Poisson process with rate \( \lambda \).
Thus we showed that for all \( T > 0 \) the process \( D \) restricted to \( [0, T] \) is a Poisson process of rate \( \lambda \). To show that \( D \) is a Poisson process on \( \mathbb{R}^+ \) we will use part (c) of Theorem II.7. Indeed, for any finite collection \( 0 \leq t_1 \leq t_2 \leq \ldots \leq t_k \) find \( T \) such that \( t_k \leq T \). Then since \( (D_t, t \leq T) \) is a Poisson process, the increments \( D_{t_i} - D_{t_{i-1}} \) are independent with the Poisson distribution.
For the last assertion of the theorem, it is obvious that \( X_0 \) is independent from arrivals between time 0 and \( T \). Reversing the direction of time this shows that \( X_T \) is independent from departures between 0 and \( T \)

Q: Theorem. Let \(X_t, Y_t\) denote the queue lengths in the first and second queue respectively. The process \((X,Y)\) is a positive recurrent Markov chain if and only if \(\lambda < \mu_1\) and \(\lambda < \mu_2\). In this case the invariant distribution is given by \[\pi(m,n) = (1- \rho_1)\rho_1^m (1-\rho_2)\rho_2^n\]where \(\rho_1 = \lambda / \mu_1, \rho_2 = \lambda / \mu_2\). In other words, \(X_t \) and \(Y_t\) are independent at equilibrium and are distributed according to shifted geometric random variables with parameters \(1- \rho_1 , 1 - \rho_2\).
A: We first compute the rates. From \((m, n)\) the possible transitions are
\[(m, n) \rightarrow \begin{cases} (m + 1, n) & \text{with rate } \lambda \\ (m - 1, n + 1) & \text{with rate } \mu_1 \text{ if } m \geq 1 \\ (m, n - 1) & \text{with rate } \mu_2 \text{ if } n \geq 1. \end{cases}\]
We can check by direct computation that \(\pi Q = 0\) if and only if \(\pi\) has the desired form. Moreover, the rates are bounded so almost surely the chain does not explode. Hence it is positive recurrent.
An alternative, more elegant or conceptual proof, uses Burke’s theorem. Indeed, the first queue is an \(M/M/1\) queue so no positive recurrence is possible unless \(\lambda < \mu_1\). In this case we know that the equilibrium distribution is \(\pi^1(m) = (1 - \rho_1)\rho_1^{m}\). Moreover we know by Burke’s theorem that (at equilibrium) the departure process is a Poisson process with rate \(\lambda\). Hence when the first queue is in equilibrium, the second queue is also an \(M/M/1\) queue. Thus no equilibrium is possible unless \(\lambda < \mu_2\) as well. In which case the equilibrium distribution of \(Y\) is \(\pi^2(n) = (1 - \rho_2)\rho_2^{n}\). It remains to check independence. Intuitively this is because \(Y_t\) depends only on \(Y_0\) and the departure process \((D_s, s \leq t)\). But this is independent of \(X_t\) by Burke’s theorem.
More precisely, if \(X_0 \sim \pi^1\) and \(Y_0 \sim \pi^2\) are independent, then Burke’s theorem implies that the distribution of \((X_t, Y_t)\) is still given by two independent random variables with distributions \(\pi^1\) and \(\pi^2\). Hence, since \((X, Y)\) is irreducible, it follows from Remark 2.20 that the product of \(\pi^1\) and \(\pi^2\) is the invariant distribution of \((X, Y)\).

Q: Definition. We say that a vector \((\overline{\lambda_1} , \dots , \overline{\lambda_N})\) satisfies the traffic equations if for all \(i \le N\) we have \[[...]\]
A: \overline{\lambda}_i = \lambda_i + \sum_{j \neq i} \overline{\lambda}_j p_{ji}

Q: Lemma. There exists a unique solution to the traffic equations?
A: Existence: Observe that the matrix \( P = (p_{ij}) \) with \( p_{00} = 1 \) defines a stochastic matrix on \(\{0, \ldots, N\}\). The corresponding (discrete) Markov Chain \((Z_n)\) is transient in the sense that it is eventually absorbed at zero. Suppose \(\mathbb{P}(Z_0 = i) = \lambda_i / \lambda\), for \(1 \leq i \leq N\), where \(\lambda = \sum_i \lambda_i\). Since \(Z\) is transient, the number of visits \(V_i\) to state \(i\) by \(Z\) satisfies \(\mathbb{E}[V_i] < \infty\). But observe that
\[\mathbb{E}[V_i] = \mathbb{P}(Z_0 = i) + \sum_{n=0}^{\infty} \mathbb{P}(Z_{n+1} = i) = \frac{\lambda_i}{\lambda} + \sum_{n=0}^{\infty} \sum_{j=1}^{N} \mathbb{P}(Z_n = j; Z_{n+1} = i)\]
\[= \frac{\lambda_i}{\lambda} + \sum_{n=0}^{\infty} \sum_{j=1}^{N} \mathbb{P}(Z_n = j) p_{ji} = \frac{\lambda_i}{\lambda} + \sum_{j=1}^{N} p_{ji} \mathbb{E}[V_j].\]
Multiplying by \(\lambda\), we see that if \(\bar{\lambda}_i = \lambda \mathbb{E}[V_i]\), then
\[\bar{\lambda}_i = \lambda_i + \sum_{j=1}^{N} \bar{\lambda}_j p_{ji}\]
which is the same thing as (3.3) as \(p_{ii} = 0\).
Uniqueness: see example sheet 3.

Q: Lemma. Partial Detailed Balance. Suppose that \(X_t\) is a Markov chain on some state space S, and that \(\pi(x) \ge 0\) for all \(x \in S\). Assume that for each \(x \in S\) we can find a partition of \(S \setminus \{x\}\), into say \(S_1^x \dots\) such that for all \(i \ge 1\) \[\sum_{y \in S_i^x} \pi(x)q(x,y) = \sum_{y \in S_i^x} \pi(y) q(y,x)\]Then \(\pi\) is an invariant distribution.
A: \[\sum_x \pi(x)q(x,y) = \sum_{x \neq y} \pi(x)q(x,y) + \pi(y)q(y,y) = \sum_i \sum_{x \in S_i^y} \pi(x) q(x,y) + \pi(y)q(y,y)\]\[= \sum_i \sum_{x \in S_i^y}\pi(y) q(y,x) + \pi(y) q(y,y) = \pi(y)\sum_x q(y,x) - \pi(y)q(y,y) + \pi(y)q(y,y) = 0\]so \(\pi Q(y) = 0\) for all \(y \in S\)

Q: Theorem. Jackson's Theorem. Assume that the traffic equations have a solution \(\overline{\lambda_i}\) such that \(\overline{\lambda}_i < \mu_i \) for every \(1 \le i \le N\). Then the Jackson network is positive recurrent and \[\pi(n) = \prod_{i=1}^N (1 - \overline{\rho_i})\overline{\rho_i}^{n_i}\]defines an invariant distribution, where \(\overline{\rho}_i = \overline{\lambda}_i / \mu_i\). At equilibium, the processes of departures to the outside from each queue form independent Poisson processes with rates \(\overline{\lambda}_i p_{i0}\)
A: Use partial detailed balance. Let \(\pi(n) = \prod_{i=1}^n \overline{\rho}_i^{n_i}\) and define \[\tilde{q}(n,m) = \frac{\pi(m)}{\pi(n)}q(m,n)\]You partition into \[A = \{e_i ; 1 \le i \le N\}\]which is arrival of a customer in the system at some queue, nd \[D_j = \{e_i - e_j ; i \neq j\} \cup \{-e_j\}\]which is a customer leaving queue j. Show that these satisfy \[\sum_{m \in D_j}q(n,n+m) = \sum_{m \in D_j}\tilde{q}(n,n+m)\]and same for A. Then we have that \(\pi\) is invariant. Since rates are bounded there is no explosion, and hence if \(\overline{\rho}_i <1\) for every \(i \ge 1\), we get an invariant distribution for the chain and hence it is positive recurrent.

Q: Proposition. The process \((X(D_n), n \geq 1)\) forms a (discrete) Markov chain with transition probabilities given by
\[\begin{pmatrix} p_0 & p_1 & p_2 & \cdots \\ p_0 & p_1 & p_2 & \cdots \\ 0 & p_0 & p_1 & p_2 & \cdots \\ 0 & 0 & p_0 & p_1 & p_2 & \cdots \end{pmatrix}\]
where \(p_k = \mathbb{E}[\exp(-\lambda \xi)(\lambda \xi)^k / k!]\), for all \(k \geq 0\).
A: Assume \(X(D_n) > 0\). Then the \((n+1)\)-th customer begins his service immediately at time \(D_n\). During his service time \(\xi_{n+1}\), a random number \(A_{n+1}\) of customers arrive in the queue. Then we have
\[X(D_{n+1}) = X(D_n) + A_{n+1} - 1.\]
If however \(X(D_n) = 0\), then we have to wait until the \((n+1)\)-th customer arrives. Then during his service, a random number \(A_{n+1}\) of customers arrive, and we have
\[X(D_{n+1}) = X(D_n) + A_{n+1}.\]
Either way, by the Markov property of the Poisson process of arrivals, the random variables \(A_n\) are i.i.d. and, given \(\xi_n\), \(A_n\) is Poisson \((\lambda \xi_n)\). Hence
\[\mathbb{P}(A_n = k) = \mathbb{E}[\mathbb{P}(A_n = k|\xi_n)] = \mathbb{E}\left[\exp(-\lambda \xi)(\lambda \xi)^k / k!\right] = p_k\]
as in the statement. The result follows.

Q: Lemma. Let \((\xi_i)_{i \geq 1}\) be i.i.d. integer valued random variables and let \(S_n = \xi_1 + \ldots + \xi_n\) be the corresponding random walk starting from 0. Suppose that \(\mathbb{E}[|\xi_1|] < \infty\). Then \(S\) is recurrent if and only if \(\mathbb{E}[\xi_1] = 0\).
A: By the strong law of large numbers if \(\mathbb{E}[\xi_1] > 0\), then \(S_n \to \infty\) as \(n \to \infty\) almost surely. Similarly if \(\mathbb{E}[\xi_1] < 0\), then \(S_n \to -\infty\) as \(n \to \infty\) almost surely. Hence if \(\mathbb{E}[\xi_1] \neq 0\), then the walk is transient.
Suppose now that \(\mathbb{E}[\xi_1] = 0\). By the strong law of large numbers, we then get that almost surely
\[\frac{S_n}{n} \to 0 \quad \text{as } n \to \infty.\]
Let \(\varepsilon > 0\). Then for \(n\) sufficiently large we get that
\[\mathbb{P}\left( \max_{i \leq n} |S_i| \leq \varepsilon n \right) \geq \frac{1}{2}. \tag{3.7}\]
Let \(G_n(x)\) denote the expected number of visits to \(x\) by time \(n\), i.e.
\[G_n(x) = \mathbb{E}_0\left[ \sum_{k=0}^n \mathbf{1}(X_k = x) \right].\]
Then clearly we have that for all \(x\)
\[G_n(x) \leq G_n(0).\]
Combining this with (3.7) we get
\[2n\varepsilon G_n(0) \geq \sum_{|x| \leq n\varepsilon} G_n(x) \geq \frac{1}{2}n.\]
Hence we obtain
\[G_n(0) \geq \frac{1}{4\varepsilon}.\]
Letting \(\varepsilon \to 0\) shows that \(G_n(0) \to \infty\) as \(n \to \infty\), thus establishing recurrence.

Q: Theorem. For an M/G/1 queue, if \(\rho \le 1\) then the queue is recurrent: i.e., it will empty out almost surely. If \(\rho > 1\) then it is transient, meaning that there is a positive probability it will never empty out.
A: Of course \( X \) is transient/recurrent in the sense of the theorem if and only if \( X(D_n) \) is transient/recurrent (in the sense of Markov chains). But note that while \( X(D_n) > 0 \) it has the same transition probabilities as a random walk on the integers \( \mathbb{Z} \) with step distribution \( A_n - 1 \). Note that
\[\mathbb{E}[A_n] = \mathbb{E}[\mathbb{E}[A_n | \xi_n = k]] = \lambda \mathbb{E}[\xi] = \rho.\]
Hence we can apply Lemma 3.21 to get that the walk is transient if and only if \( \mathbb{E}[A_n - 1] > 0 \) or equivalently \( \mathbb{E}[A_n] > 1 \). So the result follows.

Q: Definition. The busy period is [...]
A: the time period measured between the time that a customer arrives to an empty system until the time a customer departs leaving behind an empty system.

Q: Definition. Let \((\xi_i , i \ge 1) \) be i.i.d non-negative random variables with \(\mathbb{P}(\xi > 0) > 0\). We set \(T_n = \sum_{i = 1}^n \xi_i\) and \[N_t= [...]\]The process \((N_t, t \ge 0 )\) is called the renewal process associated with \(\xi_i\).
A: \max \{n \ge 0 : T_n \le t\}
Back Extra: We think of \(\xi_i\) as the interval of time seperating two successive renewals; \(T_n\) is the time of the n-th renewal and \(N_t\) counts the number of renewals up to time t.

Q: Theorem. If \(1/\lambda = \mathbb{E}[\xi] < \infty\) then we have as \(t \to \infty \)\[\frac{N_t}{t} \to \lambda \; a.s. \quad \text{and } \frac{\mathbb{E}[N_t]}{t} \to \lambda\]
A: We only prove the first assertion. We note that we have \[T_{N(t)} \le t < T_{N(t) + 1}\]Dividing by \(N(t)\) we get \[\frac{T_{N(t)}}{N(t)} \le \frac{t}{N(t)} < \frac{T_{N(t) + 1}}{N(t)}\]Since \(N(t) \to \infty\) a.s. and since \(T_n / n \to \mathbb{E}[\xi] = 1/\lambda\) by the law of large umbers, this term converges to \(1/\lambda\). The same reasoning applied to the term on the RHS. We deduce, by comparison that almost surely \[\frac{t}{N(t)} \to \frac{1}{\lambda} \quad as \; t \to \infty\]and the result follows

Q: Definition. Let X be a nonnegative random variable with distribution \(\mu\) and \(\mathbb{E}[X] = m < \infty\)
Then the size biased distribution \(\hat{\mu}\) is the probability distribution given by \[[...]\]
A: \hat{\mu}(dy) = \frac{y}{m}\mu(dy)
Back Extra: A random variable \(\hat{X}\) with that distribution is said to have the size-biased distribution of X.
\[\hat{f}(x) = xf(x)/m\]
\[\int_0^{\infty}\hat{\mu}(dy) = \int_0^{\infty}(y/m)\mu(dy) = m/m = 1\]

Q: Definition. Let \[A(t) = [...]\]be the age process, i.e, the time that has elapsed since the last renewal at time t. Let \[E(t) = [...]\]be the excess at time t or residual life; i.e., the time that remains until the next renewal. Finally let \[L(t) = [...]\]be the length of the current renewal.
A: t - T_{N(t)}; T_{N(t) + 1} - t; A(t) + E(t)

Q: Definition. A random variable \(\xi\) is called arithmetic if [...]
A: \(\mathbb{P}(\xi \in k\mathbb{Z}) = 1\) for some k maximal with this property.
Back Extra: If \(\xi\) is not arithmetic for any k, then it is called non-arithmetic.

Q: Theorem. Suppose that \(\xi\) is non-arithmetic. Let \(\mathbb{E}[\xi] = 1/\lambda\). Then \[L(t) \to [...]\]in distribution as \(t \to \infty\). Moreover, for all \(y\ge 0\), \[\mathbb{P}(E(t) \le y) \to [...]\]as \(t \to \infty\) and the same result holds with \(A(t)\) in place of \(E(t)\). In fact, \[(L(t), E(t)) \to [...]\]in distribution as \(t \to \infty,\) where \(U\) is uniform on \((0,1)\) and is independent from \(\hat{\xi}\). The same result holds with the pair \((L(t), A(t))\) instead of \((L(t), E(t))\).
A: \hat{\xi}; \lambda \int_0^y \mathbb{P}(\xi > x)dx; (\hat{\xi}, U \hat{\xi})

Q: Theorem. Suppose that \(\xi\) is non-arithmetic. Let \(E[\xi] = 1/\lambda\). Then\[L(t) \to \hat{\xi}\]in distribution as \(t \to \infty\). Moreover, for all \(y \geq 0\),\[\mathbb{P}(E(t) \leq y) \to \lambda \int_{0}^{y} \mathbb{P}(\xi > x) dx\]as \(t \to \infty\) and the same result holds with \(A(t)\) in place of \(E(t)\). In fact,\[(L(t), E(t)) \to (\hat{\xi}, U\hat{\xi})\]in distribution as \(t \to \infty\), where \(U\) is uniform on \((0, 1)\) and is independent from \(\hat{\xi}\). The same result holds with the pair \((L(t), A(t))\) instead of \((L(t), E(t))\).
A: (\(\xi\) discrete). We prove the theorem, in the case where \(\xi\) is a discrete random variable taking values in \(\mathbb{N}\). We start by proving the second formula which is slightly easier.Then, as suggested by Figure 3, \((E(t), t = 0, 1, \ldots)\) forms a discrete time Markov chain with transitions\[p_{i,i-1} = 1\]for \(i \geq 1\) and\[p_{0,n} = \mathbb{P}(\xi = n + 1)\]for all \( n \geq 0 \). It is clearly irreducible and recurrent, and an invariant measure satisfies:\[\pi_n = \pi_{n+1} + \pi_0\mathbb{P}(\xi = n + 1)\]thus by induction we deduce that\[\pi_n := \sum_{m \geq n+1} \mathbb{P}(\xi = m)\]is an invariant measure for this chain. This can be normalised to be a probability measure if \(\mathbb{E}[\xi] < \infty\) in which case the invariant distribution is\[\pi_n = \lambda\mathbb{P}(\xi > n).\]We recognise the formula (4.2) in the discrete case where \( t \) and \( y \) are restricted to be integers. Using the assumption that \( \xi \) is non-arithmetic gives that the Markov chain \( E \) is aperiodic. Since it is also irreducible, we can apply the convergence to equilibrium theorem to get (4.2).
We now consider the slightly more delicate result (4.3), still in the discrete case \( \xi \in \{1, 2, \ldots\} \). Of course, once this is proved, (4.1) follows. Observe that \(\{(L(t), E(t)); t = 0, 1, \ldots\}\) also forms a discrete time Markov chain in the space \( \mathbb{N} \times \mathbb{N} \) and more precisely in the set\[S = \{(n, k) : 0 \leq k \leq n - 1\}.\]The transition probabilities are given by
\[p_{(n, k) \to (n, k - 1)} = 1\]
if \( k \geq 1 \) and
\[p_{(n, 0) \to (k, k - 1)} = \mathbb{P}(\xi = k).\]
This is an irreducible recurrent chain for which an invariant measure is given by \(\pi(n, k)\) where:
\[\pi(n, k - 1) = \pi(n, k)\]
for \( 0 \leq k \leq n - 1 \) and
\[\pi(k, k - 1) = \sum_{m=0}^{\infty} \pi(m, 0)\mathbb{P}(\xi = k).\]
So taking \(\pi(n, k) = \mathbb{P}(\xi = n)\) works. This can be rewritten as
\[\pi(n, k) = n\mathbb{P}(\xi = n) \times \frac{1}{n} \{0 \leq k \leq n - 1\}.\]
After normalisation, the first factor becomes \(\mathbb{P}(\xi = n)\) and the second factor tells us that \(E(t)\) is uniformly distributed on \(\{0, \ldots n - 1\}\) given \(L(t) = n\) in the limit. The theorem follows.

Q: Definition. A process \((X_t : t \ge 0)\) is called regenerative if [...]
A: there exist random times \(\tau_n\) such that the process regenerates, i.e. the law of the process \((X_{T + \tau_n})_{t \ge 0}\) is identical to \((X_t)_{t \ge 0}\) and independent of \((X_t)_{t \le \tau_n}\)
Back Extra: For example X could be an M/G/1 queue and \(\tau_1\) is the end of the first busy period

Q: Theorem. Little's Formula. Suppose we have a queue X starting from 0 which has regerenation times \(\tau_n\). Let N be the arrival process, i.e. \(N_t\) counts the total number of customers that arrived before time t. Let \(W_i\) denote the waiting time of the i-th customer, which is the time that he spends waiting in the queue plus the service time. If \(\mathbb{E}[\tau_1] < \infty\) and \(\mathbb{E}[N_{\tau_1}] < \infty\), then almost surely the following limits exist and are deterministic:\[(a)\text{ Long-run mean queue size} \quad L := \lim_{t \to \infty}\int_0^t X_s ds\]\[(b)\text{ Long-run average waiting time} \quad W := \lim_{n \to \infty} \frac{1}{n}\sum_{i=1}^n W_i\]\[(c) \text{Long-run average arrival rate} \quad \lambda = \lim_{t \to \infty}\frac{N_t}{t}\]Moreover, we have \( L = \lambda W\)
A: For every \( n \) we define\(Y_n = \sum_{i=1}^{N_{\tau_n}} W_i.\)
Let now \(\tau_n \leq t < \tau_{n+1}\). Note that by the regeneration property, at time \(\tau_n\) there are no customers in the queue, hence all the customers that have entered the queue before \(\tau_n\) have finished their service. Then we have\[\frac{Y_n}{\tau_{n+1}} \leq \frac{1}{t} \int_0^t X_s \, ds \leq \frac{Y_{n+1}}{\tau_n}\]We can write \( Y_n = \sum_{i=1}^n (Y_i - Y_{i-1})\), since we take \( Y_0 = 0 \). By the regenerative property we have that the increments \( Y_i - Y_{i-1} \) are i.i.d. and hence we can apply the strong law of large numbers to obtain\[\lim_{n \to \infty} \frac{Y_n}{\tau_n} = \frac{\mathbb{E}[Y_1]}{\mathbb{E}[\tau_1]}.\]Therefore, taking the limits of the left and right hand side of (4.7) we get that
\[L := \lim_{t \to \infty} \frac{1}{t} \int_0^t X_s \, ds = \frac{\mathbb{E}[Y_1]}{\mathbb{E}[\tau_1]}.\]Similarly, using the assumption that \(\mathbb{E}[N_{\tau_1}] < \infty\), one can show that the following limit exists\(\lim_{t \to \infty} \frac{N_t}{t} = \lambda.\)
For \( N_{\tau_n} \leq k < N_{\tau_{n+1}} \) we also have\[\frac{Y_n}{N_{\tau_{n+1}}} \leq \frac{1}{k} \sum_{i=1}^k W_i \leq \frac{Y_{n+1}}{N_{\tau_n}}.\]Finally we conclude that almost surely\[\lim_{n \to \infty} \frac{Y_n}{N_{\tau_{n+1}}} = \frac{L}{\lambda} \quad \text{and} \quad \lim_{n \to \infty} \frac{Y_{n+1}}{N_{\tau_n}} = \frac{L}{\lambda}\]and this finishes the proof.

Q: Definition. A random countable subset \(\Pi \subset \mathbb{R}^d\) is a Poisson process with constant intensity \(\lambda > 0\) if[...]
A: \(\forall A \in B(\mathbb{R}^d)\)
\[(a) \quad N(a) := \# (A \cap \Pi) \sim \text{Poi}(\lambda |A|)\]\[(b) \quad \text{For any } A_1, \dots , A_n \in B(\mathbb{R}^d) \text{ disjoint,} N(A_1) , \dots , N(A_n) \text{ are independent}\]
Back Extra: If \(|A| = \infty\), we interepret (a) as \(N(A) = \infty\) almost surely.

Q: Definition. Let \(\lambda : \mathbb{R}^d \to \mathbb{R}\) be a non-negative function s.t. \(\Lambda (A) = \int_A \lambda (x) dx < \infty\) for every bounded \(A \in B(\mathbb{R}^d)\). Then \(\Pi\) is a non-homoheneous P.P with intensity function \(\lambda\) if [...]
A: \(\forall A \in B(\mathbb{R}^d)\), \[(a) \quad N(A) = \#(\Pi \cap A) \sim \text{Poi}(\Lambda(A))\]\[(b) \quad \text{For any } A_1 , \dots , A_n \text{ disjoint, }N(A_1) , \dots , N(A_2) \text{ are independent }\]
Back Extra: \(\Lambda\) is called the "mean measure" of the Poisson process.

Q: What is the superposition theorem in spatial processes?
A: Let \(\Pi_1, \Pi_2\) be two independent poisson processes with intensity functions \(\lambda_1, \lambda_2\) then \(\Pi = \Pi_1 \cup \Pi_2\) is a Poisson process with intensity function \(\lambda = \lambda_1 + \lambda_2\)

Q: What is the Mapping Theorem for spatial Poisson processes?
A: Let \(\Pi\) be a non-homogeneous Poisson process with intensity function \(\lambda\). Assume \(f:\mathbb{R}^d \to \mathbb{R}^s\) satisfies \[\Lambda(f^{-1}\{y\}) = 0 \quad \forall y \in \mathbb{R}^s\]and \(\mu(B) = \Lambda(f^{-1}B) = \int_{f^{-1}B} \lambda(x)dx < \infty\) for all founded \(B \in \mathbb{B}(\mathbb{R}^s)\)
Then \(f(\Pi)\) is a non-homogeneous Poisson process on \(\mathbb{R}^s\) with mean measure \(\mu\)

Q: What is the Conditioning Property in spatial processes?
A: Let \(\Pi\) be a P.P. on \(\mathbb{R}^d\) with intensity function \(\lambda\) and \(A \in B(\mathbb{R}^d)\) be s.t. \(0 < \Lambda(A) < \infty\). Conditional on \(\# \{\Pi \cap A\} = n\), the n points in \(\Pi \cap A\) have the same distribution as n points chosen independently according to the probability distribution \[\nu (B) = \frac{\Lambda(B)}{\Lambda(A)} = \int_B \frac{\lambda(x)}{\Lambda(A)}dx\]In particular, when \(\Pi\) has constant intensity then the n points are iid Uniform in A.

Q: What is the Colouring Theorem in spatial processes?
A: Let \(\Pi\) be a non-homogeneous P.P. on \(\mathbb{R}^d\) with intensity function \(\lambda : \mathbb{R}^d \to \mathbb{R}\). Colour the points \(x \in \Pi\) independently as follows
A point \(x \in \Pi\) is red with probaiblity \(\gamma(x)\) and blue with probability \(1 - \gamma(x)\)
Let \(\Gamma \subset \Pi\) be the set of red points and let \(\Sigma \subset \Pi\) be the set of blue points
Then \(\Gamma\) and \(\Sigma\) are independent Poisson processes on \(\mathbb{R}^d\) with intensity function \(\gamma(x) \lambda(x)\) and \((1- \gamma(x))\lambda(x)\) respectively.