Title: Applied Probability

Q: Click process
A: A family of rvs $\{N(t): t > 0\}$ with $N(0)=0$ is called a \emph{click process} if $N(t)$ is non-negative, integer valued, non-decreasing and right-continuous.

Q: Poisson process: infinitesimal definition
A: A Poisson process with \emph{intensity} $\lambda$ is a click process $N=\{N(t): t\geq 0\}$ with
\[
\P(N(t+h)=n+m | N(t)=n) = \begin{cases}
1 - \lambda h + o(h) \quad & m =0 \\
\lambda h + o(h) \quad & m=1 \\
o(h) \quad & m > 1
\end{cases}
\]
and $N(t)-N(s)$ indep of prior arrivals for $s< t$.

Q: Distribution of Poisson process
A: If $\{N(t): t\geq 0 \}$ is a Poisson process, then $N(t)\sim \Po (\lambda t)$ for every $t\geq 0$.
\begin{proof}
By conditional probability, for $j\geq 1$
\begin{align*}
p_j(t+h) &= \sum_{i\leq j} \P(N(t+h) = j | N(t) = i) p_i(t) \\
&= (1-\lambda h) p_j(t) + \lambda h p_{j-1}(t)  + o(h) \\
p_j'(t) &= -\lambda p_j(t) + \lambda p_{j-1}(t).
\end{align*}
Whereas for $j=0$
\[
p_0'(t) = - \lambda p_0(t), \quad p_0(0)=1
\]
so $p_0(t)=e^{-\lambda t}$. By induction $p_n(t)=e^{-\lambda t} \frac{(\lambda t)^n}{n!}$.
Alternatively, define $G(s,t)=\sum_{j\geq 0} p_j(t) s^j$. Then the ODE becomes
\[
\frac{\partial G}{\partial t} = \lambda(s-1)G, \quad G(s,0)=1.
\]
So $G(s,t)=e^{\lambda(s-1)t}=e^{-\lambda t}\sum_{n\geq 0} \frac{(\lambda t)^n}{n!}$. Done by comparing coefficients.
\end{proof}

Q: Holding or inter-arrival times
A: Let $T_0=0$, $T_n=\inf_{t>0: N(t)=n}$ define the arrival times.
Then the holding times are given by $X_n=T_n-T_{n-1}$.
These determine $T_n=\sum_{i=1}^n X_i$ and $N(t)=\max\{n: T_n\leq t\}$.

Q: Holding time distribution for Poisson process
A: $(X_i)\sim \text{Exp} (\lambda)$ are iid.
\begin{proof}
For $n=1$:
\[
\P(X_1>t) = \P(N(t)=0) = e^{-\lambda t}.
\]
For $n=2$:
\begin{align*}
\P(X_2 > t | X_1 = t_1) &= \P(\text{no arrivals in }(t_1, t_1+t) | X_1 = t_1) \quad\text{(integrating cond pdf)} \\
&= \P(\text{no arrivals in }(t_1, t_1+t)) \quad\text{(Markov property)} \\
&= \P(\text{no arrivals in }(0, t)) \quad\text{(translation invariance)} \\
&= \P(N(t)=0)  \\
&= e^{-\lambda t}.
\end{align*}
Continue by induction.
\end{proof}

Q: Poisson process: characterisation by increments
A: \emph{Independent}: If $0<t_1< \cdots <t_n$, then $N(t_1), N(t_2)-N(t_1), \cdots N(t_n)-N(t_{n-1})$ are independent.
\emph{Stationary}: $N(s+t)-N(s)\sim N(t)-N(0)$.
Amongst processes which are rt-cts, non-dec, unit-jumping, then these two characterise the PP.

Q: Thinning
A: Let arrivals obey $\P(A)=\alpha, \P(B)=1-\alpha$. Then $A\sim pp(\alpha\lambda)$ and $B\sim pp((1-\alpha)\lambda)$ are independent.
\begin{proof}
The distribution is obvious:
\[
\P(A \text{ in }(0, h)) = \alpha \P(\text{arrival in }(0, h))=\alpha(\lambda h + o(h)).
\]
For independence, we reduce to fd (in fact $d=2$) case:
\begin{align*}
\P(A(t)=a, B(t)=b) &= \frac{(\lambda t)^{a+b}e^{-\lambda t}}{(a+b)!} {a + b \choose a} \alpha^a (1-\alpha)^b \\
&= \left[ \frac{(\alpha\lambda t)^{a}e^{-\alpha\lambda t}}{a!}  \right] \left[ \frac{((1-\alpha)\lambda t)^{b}e^{-(1-\alpha)\lambda t}}{b!}  \right] \\
&= \P(A(t)=a) \P(B(t)=b).
\end{align*}
\end{proof}

Q: Superposition
A: \[
\mathrm{PP}(\lambda_1) + \mathrm{PP}(\lambda_2) = \mathrm{PP}(\lambda_1 + \lambda_2)
\]
\begin{proof}
The probability of a single arrival in $(0,h)$ is
\[
\lambda_1 h + \lambda_2 h -\lambda_1\lambda_2 h^2 + o(h) = (\lambda_1 + \lambda_2) h + o(h).
\]
\end{proof}

Q: Conditional distribution of arrival times
A: Given $N(t)=n$, the arrival times $T=(T_1, \cdots T_n)$ are distributed as the $n$ order statistics of $U[0,t]$. That is
\[
f_{\mathbf{T}|N(t)=n}(\mathbf{t}) = \frac{n!}{t^n} \mathbbm{1} [t_1\leq \cdots \leq t_n \leq t].
\]
\begin{proof}
The interarrival times have joint pdf
\[
f_\mathbf{X}(\mathbf{x}) = \lambda^n \exp\left(-\lambda\sum_1^n x_i\right)
\]
where
\[
\mathbf{T} = \begin{pmatrix}
1 & 0 & 0 & \cdots & 0 \\
1 & 1 & 0 & \cdots & 0 \\
  &    &  \ddots  &   &  \\
1 & 1 & 1 & \cdots & 1
\end{pmatrix} \mathbf{X}.
\]
By change of variables
\[
f_\mathbf{T}(\mathbf{t}) = \lambda^n e^{-\lambda t_n} \mathbbm{1} [t_1\leq \cdots \leq t_n].
\]
By Bayes' Theorem
\begin{align*}
f_{\mathbf{T}|N(t)=n}(\mathbf{t}) &= \frac{ \cancel{e^{-\lambda(t-t_n)}}\mathbbm{1}[t_n\leq t]}{(\bcancel{\lambda} t)^n \cancel{e^{-\lambda t}}/n!}  \bcancel{\lambda}^n \cancel{e^{-\lambda t_n}} \mathbbm{1} [t_1\leq \cdots \leq t_n] \\
&= \frac{n!}{t^n} \mathbbm{1} [t_1\leq \cdots \leq t_n \leq t].
\end{align*}
\end{proof}

Q: Markov property
A: A process $\{X(t): t\geq 0 \}$ taking values in $S$ is a cts-time MC if $\forall i, t$:
\[
\P(X(t_n)=i_n | X(t_{n-1})=i_{n-1}, \cdots X(t_1)=i_1) = \P(X(t_n)=i_n | X(t_{n-1})=i_{n-1}).
\]

Q: Transition probabilities
A: For $i,j\in S, s\leq t$, define
\[
p_{ij}(s,t) = \P(X(t) = j | X(s) = i).
\]
For a homogeneous process we write $p_{ij}(t-s):=p_{ij}(s,t)$.

Q: Transition matrices
A: The family $\{P_t: t \geq 0\}$ is a stochastic semigroup. That is
\begin{enumerate}
\item Identity: $P_0=I$
\item Stochasticity: each $P_t$ is a stochastic matrix
\item Semigroup property: $P_{s+t}=P_{s}P_t$ (Chapman-Kolomogorov).
\end{enumerate}

Q: Right-continuous jump process
A: $X:\Omega \times [0,\infty) \to S$ is a rt-cts jump process if $\forall\omega\in\Omega, t \geq 0, \exists \varepsilon >0$ such that
\[
\forall s\in [t, t+\varepsilon]: X_s(\omega)=X_t(\omega).
\]

Q: Memoryless property
A: $X>0$ is exponentially distrubuted $\iff$ it has the memoryless property.
\begin{proof}
($\Rightarrow$) For $X\sim\Exp (\lambda)$, using Bayes' Theorem
\[
\P(X> u + v | X > u) = \frac{e^{-\lambda(u+v)}}{e^{-\lambda u}} = e^{-\lambda v} = \P(X>v).
\]
($\Leftarrow$) Write $G(u)=\P(X>u)$. Then using Bayes' Theorem
\[
\P(X> u + v | X > u) = \frac{G(u+v)}{G(u)} = G(v) = \P(X>v).
\]
So $G$ is multiplicative, rt-cts, non-increasing and $G(0)=1$. Then for $n\in\N$: $G(n)=G(1)^n$. For $p,q\in\N$:
\[
G\left(\frac{p}{q}\right) \cdots G\left(\frac{p}{q}\right) = G(p) = G(1)^p.
\]
So $G(\frac{p}{q}) = G(1)^{p/q}$.
By density of $\Q$, $G(u)=G(1)^u$ for $u\geq 0$. Hence $G(u)=e^{-\lambda u}$ for some $\lambda >0$.
\end{proof}

Q: Holding time distribution for MCs
A: By homogeneity, $H$ satisfies the memoryless property. So $H$ is exponentially distributed.

Q: Generator matrix
A: Let $Y_n=X(T_n)$ be a jump chain with transitional probabilities $g_{ij}/g_i$. Then for $i,j\in S$, defining $g_{ii} = -g_i$:
\begin{align*}
p_{i,j}(h) &= g_{ij}h + o(h) \\
p_{ii}(h) &= 1 - \sum_{j\neq i} p_{ij}(h) \\
&= 1 -h \sum_{j\neq i} g_{ij} + o(h) \\
&= 1 - g_i h + o(h) \\
&= 1 + g_{ii}h + o(h).
\end{align*}
Then $G=(g_{ij})=\lim_{t\to 0} \frac{P_t-I}{t}=P_0'$ is the generator or $Q$-matrix. The non-positive diagonal makes the row sums vanish.

Q: Kolmogorov equations
A: Kolmogorov's forward equation is
\begin{align*}
p_{ij}(t+h) &= \sum_{k\in S} p_{ik}(t)p_{kj}(h) \\
&= p_{ij}(t)(1+g_{jj}h) + \sum_{k\neq j} p_{ik}(t)g_{kj}h + o(h)\\
p_{ij}'(t) &= \sum_{k\in S} p_{ik}(t) g_{kj} \\
P_t'&=P_t G. \\
\intertext{Similarly, the backward equation is}
P_t' &= GP_t.
\end{align*}
This has solution $P=P_0e^{tG} = e^{tG}$. The minimal non-negative solution to either equation with b.c. $P_0=I$ recovers the transition probabilities.

Q: Solving Kolmogorov's equations
A: \begin{enumerate}
\item Solve the coupled ODEs $P_t'=P_tG$ with BCs $P_0=0$. These can be simplified by defining $G(s,t)=\sum_{j\geq 0} p_j(t) s^j$.
\item Diagonalising $G=A\Lambda A^{-1}$, we have
\begin{align*}
P_t &= e^{tG} \\
&= \sum \frac{1}{n!} t^n A \Lambda^n A^{-1} \\
&= A(e^{t\Lambda})A^{-1} \\
&= A \diag(e^{\lambda_i t}) A^{-1}.
\end{align*}
Therefore
\[
p_{ij}(t) = \sum_k e^{\lambda_k t} c_k(i, j).
\]
\end{enumerate}

Q: Irreducibility dichotomy
A: Let $i,j\in S$. Either $p_{ij}=0$ or $p_{ij}>0$ on $\R^+$.
\begin{proof}
Assume $p_{ij}(T)>0$ for some $T>0$. Then for $t>T$:
\[
p_{ij}(t) \geq p_{ij}(T) \P_j(X_j > t - T) > 0.
\]
For $t<T$, simply observe there must exist a finite sequence of jumps from $i$ to $j$ in time T. That is, $\exists i_1, \cdots i_n \in S$ with $g_{i,i_1} \cdots g_{i_n,j}>0$. Moreover, holding times are exponential so
\[
p_{ij}(t) \geq p_{i,i_1}(\tfrac{t}{n+1}) \cdots p_{i_n, j}(\tfrac{t}{n+1}) >0.
\]
\end{proof}

Q: Irreducible chain
A: The chain $X$ on state space $S$ is irreducible if $\forall i, j \in S$: $p_{ij}>0$ on $\R^+$.

Q: Invariant distribution
A: Let $X$ be irreducible and recurrent. A distribution $\pi$ on $S$ is invariant, stationary or equilibrium distribution if $\pi=\pi P_t$ for $t \geq 0$. Equivalently, $\pi G = 0$.
\begin{proof}
Differentiating gives $\pi G = 0$. For the converse, using $P_t=e^{tG}$:
\begin{align*}
\pi G = 0 & \iff \forall n \in \N: \pi G^n = 0 \\
& \iff \pi \sum_{n\geq 0} \frac{t^nG^n}{n!} \equiv \pi \\
& \iff \pi P_t \equiv \pi.
\end{align*}
Alternatively using the backward equation
\[
\pi P_t' = (\pi G) P_t = 0.
\]
So $\pi P_t=\pi P_0 = \pi$.
\end{proof}

Q: Uniqueness and convergence of invariant distributions
A: Let $X$ be irreducible and $\pi$ an invariant distribution. Then the invariant distribution is unique and $\forall j\in S$: $p_{ij}(t) \to \pi_j$ as $t\to\infty$.
\begin{proof}
Let $h>0$ and $Y_n=X(nh)$ be a \emph{skeleton} of $X$.
Since $X$ is irreducible, $Y$ is irreducible and aperiodic. The discrete case gives uniqueness and that $p_{ij}(nh) \to \pi_j$ as $n\to\infty$. The conclusion follows by cty of $p_{ij}(\ph)$.
\end{proof}

Q: Continuity of transition probabilities
A: The functions $p_{ij}(\ph)$ are (uniformly) cts.
\begin{proof}
By the Kolomogorov backward equation
\begin{align*}
p_{ij}(t+h) - p_{ij}(t) &= \sum_{k\in S} p_{ik}(h)p_{kj}(t) - p_{ij}(t) \\
&= \sum_{k\neq i} p_{ik}(h) \underbrace{p_{kj}(t)}_{\leq 1} - \underbrace{p_{ij}(t)}_{\leq 1}(1 - p_{ii}(h)) \\
\left| p_{ij}(t+h) - p_{ij}(t) \right| &\leq 2(1-p_{ii}(h)) \\
&= 2(1-e^{-g_i h})) \\
&\to 0 \text{ uniformly in $t$ as } h \to 0.
\end{align*}
\end{proof}

Q: Explosion
A: The jump times $T_n = \sum_{i=0}^{n-1} X_i$, where $X_i\sim\Exp(g_i)$, are monotonic so $(T_n)\nearrow T_\infty$.
We say the chain \emph{explodes} if $\P(T_\infty < \infty)>0$.
Otherwise we let $S'=S\cup\{\infty\}$ where $\{\infty\}$ is an absorbing state called the \emph{cemetery state}. Then the chain is called \emph{minimal}. [Can alternatively define an \emph{entry law} for the chain to return to $S$].

Q: No explosion criteria
A: The continuous time MC $X$ constructed via holding times $U_i\sim\Exp(g_i)$ does not explode if (a) $|S|<\infty$, (b) $\sup_i g_i<\infty$ or (c) $X(0)$ is a recurrent state of the jump chain $Z$.
\begin{proof}
(a)$\implies$(b). (b) Assume $\gamma:= \sup_i g_i<\infty$. Then $g_{Z_i}U_i\sim\Exp(1)$ are iid and hence
\[
\gamma \sum U_i \geq \sum g_{Z_i} U_i = \infty \text{ a.s.}
\]
(c) Assume infinitely many $n$ such that $Z_n=i$ a.s. Hence
\[
T_\infty \geq \sum \Exp(g_i) = \infty \text{ a.s.}
\]
\end{proof}

Q: Infinite sum of exponential RVs
A: Let $(X_i)_{i\in\N}\sim \Exp(\lambda_i)$ be iid and $T_\infty= \sum_{i=1}^\infty X_i$. Then
\[
\P(T_\infty < \infty) = \begin{cases} 0 \quad & \sum_i \frac{1}{\lambda_i} = \infty \\
1 \quad & \sum_i \frac{1}{\lambda_i} < \infty.
\end{cases}
\]
\begin{proof}
If $ \sum_i \frac{1}{\lambda_i} < \infty$, then by MCT
\[
\E[T_\infty] = \E\left[ \sum_i X_i\right] = \sum_i \frac{1}{\lambda_i}<\infty.
\]
So $T_\infty<\infty$ a.s.
If $ \sum_i \frac{1}{\lambda_i} = \infty$, then again by MCT
\[
\E[e^{-T_\infty}] = \E\left[ \prod e^{-X_i}\right] = \prod \E[e^{-X_i}] = \prod \left(\frac{1}{1+\lambda_i^{-1}}\right) = 0.
\]
So $e^{-T_\infty} =0$ and thus $T_\infty=\infty$ a.s.
\end{proof}

Q: Recurrence in cts time
A: State $i$ of cts time MC $X$ is recurrent if
\[
\P_i(\{ t\geq 0: X(t)=i \} \text{ unbounded}\}= 1.
\]
Similarly $i$ is transient if
\[
\P_i(\{ t\geq 0: X(t)=i \} \text{ unbounded}\}= 0.
\]

Q: Recurrence condition theorem
A: Let $X$ be a MC with JC $Z$. If $g_i=0$, then $i$ is recurrent. Otherwise $i$ is recurrent for $X$ $\iff$ $i$ is recurrent for $Z$ $\iff$ $\int_0^\infty p_{ii}(t) \; \d t = \infty$.
\begin{proof}
Assume $g_i>0$. Write $N$ for the last return of $Z$ to state $X(0)=i$.
If $i$ is transient for $Z$, then $N<\infty$ $\P_i$-a.s. Hence $X(t)\neq i$ for $t>T_{N+1}$ $\P_i$-a.s. So $i$ is transient for $X$.
If $i$ is recurrent for $Z$, then $N=\infty$ $\P_i$-a.s. By the no explosion criteria, $\{T_n: Z_n=i \}$ is unbounded $\P_i$-a.s. Hence $i$ is recurrent for $X$.
Finally we integrate using Fubini and use the discrete-time result
\begin{align*}
\int_0^\infty p_{ii}(t) \; \d t &= \int_0^\infty \E_i[\mathbbm{1}_{X(t)=i}] \; \d t \\
&= \E_i\left[\int_0^\infty \mathbbm{1}_{X(t)=i} \; \d t\right] \\
&= \E_i\left[\sum_{k=0}^\infty U_k \mathbbm{1}_{Z_k=i} \; \d t\right] \\
&=\frac{1}{g_i} \sum_{k=0}^\infty \P_i(Z_k=i)  \\
&= \infty \text{ iff $i$ is recurrent}.
\end{align*}
\end{proof}

Q: Birth process
A: A cts time MC with generator
\[
g_{n,m} = \begin{cases}
\lambda_n  \quad & m=n+1\\
0 \quad & m\neq n, n+1.
\end{cases}
\]

Q: Simple birth process
A: Let $N_t$ be the number of cells during mitosis. Then, as chains of length $>1$ are $o(h)$, we have
\begin{align*}
\P(N_{t+h}=n+m | N_t=n) &= {n\choose m} (\lambda h +o(h))^m(1-\lambda h +o(h))^{n-m}+o(h) \\
&= \begin{cases}
1-n\lambda h + o(h) \quad &m=0 \\
n\lambda h + o(h) \quad &m=1 \\
o(h) \quad &m\geq 2.
\end{cases}
\end{align*}
Hence $N_t$ is a birth process with $\lambda_n=n\lambda$.

Q: Birth process uniqueness for forward equation
A: For a birth process, the forward equation
\[
p_{i, j}'(t) = \lambda_{j-1} p_{i,j-1}(t) - \lambda_{j} p_{i, j} \qquad(j> i)
\]
with BCs
\[
p_{ii}'(t) = - \lambda_i p_{ii}(t), \quad p_{ii}(0)=0
\]
has a unique solution. Moreover, the solution satisfies the backward equation.
\begin{proof}
BCs give $p_{ii}(t)=e^{-\lambda_i t}$. For $j=i+1$:
\[
p_{i, i+1}'(t) = \lambda_i p_{i,i}(t) - \lambda_{i+1} p_{i, i+1}.
\]
So $p_{i, i+1}$ is uniquely specified (and can be calculated explicitly) by induction.
Taking LT of the fwd equation \vspace{-0.7cm}
\begin{align*}
\theta \hat{p}_{i, j} &= \lambda_{j-1} \hat{p}_{i,j-1} - \lambda_{j} \hat{p}_{i, j} \\
(\theta+  \lambda_{j}) \hat{p}_{i, j}  &=\lambda_{j-1} \hat{p}_{i,j-1} \\
\hat{p}_{i, j}  &= \frac{1}{\lambda_j} \left( \frac{\lambda_j}{\lambda_j+\theta} \cdots  \frac{\lambda_i}{\lambda_i+\theta}\right).
\end{align*}
This solution also works for the transformed backward equation.
\end{proof}

Q: Birth process backward equation
A: The forward equations have a unique solution $p_{ij}(t)$ which is the minimal solution to the backward equations, i.e. $\forall \pi_{ij}(t)$ solving the backward equation
\[
p_{ij}(t) \leq \pi_{ij}(t) \quad (\forall i, j, t).
\]
In particular, the backward equations of a non-exploding birth process have a unique solution.
\begin{proof}
Theorem 1.24 Sousi.
\end{proof}

Q: Strong Markov property
A: Let $X\sim\Markov(G, \lambda)$ with stopping time $T$. Given $X(T)=x$ and $T<T_\infty$, we have that
\[
\{ X(T+t): t\geq 0\} \sim\Markov(G, \delta_x)
\]
and is independent of $\{ X(s): s\leq T\}$.
\begin{proof}
p. 96 J. R. Norris. Markov chains, volume 2 of Cambridge Series in Statistical and Probabilistic
Mathematics. Cambridge University Press, Cambridge, 1998. Reprint of 1997 original.
\end{proof}

Q: Hitting probability (cts time)
A: Since $H_A<\infty \iff T_A<\infty$, we have that $h_A$ is the minimal non-negative solution to
\[
h_A(i) = \begin{cases}
1 \quad & i\in A \\
\sum_{j\neq i} \frac{g_{ij}}{g_i} h_A(j) \quad & i \not\in A
\end{cases}
\]
or equivalently
\[
 \begin{cases}
h_A(i) =1 \quad & i\in A \\
Gh_A(i) = 0 & i \not\in A.
\end{cases}
\]

Q: Mean hitting time (cts time)
A: $k_A(i)=\E_i[T_A]$ is the minimal non-negative solution to
\[
k_A(i) = \begin{cases}
0 \quad & i \in A \\
\frac{1}{g_i} + \sum_{j\neq i} \frac{g_{ij}}{g_i} k_A(j) \quad & i\not\in A
\end{cases}
\]
or equivalently
\[
 \begin{cases}
k_A(i) =0 \quad & i \in A \\
Gk_A(i) = -1 \quad & i\not\in A.
\end{cases}
\]

Q: Hitting probability (discrete time)
A: $(h_i^A: i \in S)$ is the minimal non-negative solution to
  \[
    h_i^A =
    \begin{cases}
      1 & i \in A\\
      \sum_{j \in S}p_{i, j}h_j^A & i \not \in A.
    \end{cases}
  \]
\begin{proof}
Suppose $x = (x_i: i \in S)$ is a non-negative solution. For $i \not\in A$
  \begin{align*}
    x_i &= \sum_{j\in S} p_{i, j}x_j \\
    &= \sum_{j \in A}p_{i, j}x_j + \sum_{j \not\in A}p_{i, j}x_j \\
    &= \sum_{j \in A}p_{i, j} + \sum_{j \not\in A}p_{i, j}x_j \\
    &= \sum_{j \in A} p_{i, j} + \sum_{j \not\in A} p_{i, j}\left(\sum_{k\in S} p_{i, k} x_k\right) \\
    &= \sum_{j \in A} p_{i, j} + \sum_{j \not\in A} p_{i, j}\left(\sum_{k\in A} p_{i, k} x_k + \sum_{k \not\in A} p_{i, k}x_k\right)\\
    &\geq \P_i (H^A = 1) + \sum_{j \not \in A, k \in A}p_{i, j}p_{j, k}\\
    &= \P_i(H^A = 1) + \P_i(H^A = 2).
  \end{align*}
  By induction, we obtain
  \[
    x_i \geq \P_i(H^A \leq n)
  \]
  for all $n$. Taking the limit as $n \to \infty$, we get
  \[
    x_i \geq \P_i(H^A < \infty) = h_i^A.
  \]
\end{proof}

Q: Positive recurrence is a class property
A: Let $X\sim G$ be irreducible, JC $Y\sim H$. Then TFAE
\begin{enumerate}
\item every state is PR
\item some state is PR, i.e. $\exists i\in S: m_i=\E[U_i]<\infty$
\item $X$ is non-explosive with inv distn $\pi$.
\end{enumerate}
\begin{proof}
(i) $\implies$ (ii) obvious. (ii) $\implies$ (iii): $Y$ is irreducible recurrent so $X$ is recurrent and in particular non-explosive. We split $m_i = \sum_j \mu_j$ where
\[
\mu_j := \E_i \left[\int_0^{U_i} \mathbbm{1}\{X(s)=j\} \; \d s\right]= \frac{\nu_i(j)}{g_j}
\]
and $\nu_i(j)=\E_i$[visits to $j$ before $i$]. Recall $\nu = \nu_i$ is $Y$-invariant so
\begin{align*}
(\mu G)_k &= \sum_j \mu_j G_{jk} \\
&= \sum_j \frac{\nu(j)}{g_j} (h_{jk} - \delta_{jk})g_j \\
&= \nu(k) - \nu(k)
\end{align*}
vanishes. Hence $\pi_j = \frac{\mu_j}{m_i}$ is an inv distn for $X$.
(iii) $\implies$ (i): Define $\rho = (\pi_j g_j: j\in S)$ and compute
\[
(\rho H)_k = \sum_{j} (\pi_j g_j) (\frac{g_{jk}}{g_j}+\delta_{jk}) = \pi_k g_k = \rho_k.
\]
By irreducibility $\pi, \rho>0$. By uniqueness of invariants
\[
\nu(j) =\frac{\rho_j}{\pi_i g_i}= \frac{\pi_j g_j}{\pi_i g_i}.
\]
Subsituting this in
\[
m_i = \sum_j \frac{\nu(j)}{g_j} = \frac{1}{\pi_i g_i}<\infty.
\]
So $i$ is PR and $\pi_i = \frac{1}{m_ig_i}$.
\end{proof}

Q: Uniqueness of invariant measure
A: If $Z$ is an irreducible, recurrent, discrete-time MC, then there exists an invariant measure and it is unique up to multiplication by scalars.

Q: Invariant measure of birth-death chain from SRW
A: Let $X$ be a MC on $\Z_{\geq}$ with
\[
g_{n,n+1} = \lambda g_n, \quad g_{n,n-1} = \mu g_n
\]
where $\lambda + \mu = 1$ and $g_n>0$.
Then the JC is a SRW which is recurrent $\iff\lambda \leq \mu$ and PR $\iff \lambda < \mu$. The invariant measure is $(\frac{\lambda}{\mu})^i(1-\frac{\lambda}{\mu})$.
Hence $X$ has invariant measure $\frac{(\lambda / \mu)^i}{g_i}$. Depending on the values of $g_i$, an invariant distribution may or may not exist.

Q: Reversal of continuous time MC
A: Let $X\sim\Markov(\pi, G)$ be irreducible, non-exploding with $\pi$ invariant. Fix $T>0$ and write
\[
\tilde{X}(t)=X(T-t).
\]
Then $\tilde{X}\sim\Markov(\pi, \tilde{G})$ is irreducible, non-exploding with $\pi$ invariant and $\tilde{G}$ given by the detailed balance equations
\[
\pi_i g_{ij} = \pi_j \tilde{g}_{ji} \quad i, j \in S. \tag{$*$}
\]
\begin{proof}
$\tilde{G}$ is an irreducible generator as $\tilde{g}_{ji} = \frac{\pi_i}{\pi_j} g_{ij}> 0$ for $i\neq j$ and
\[
\sum_{i\in S} g_{ji} =  \frac{1}{\pi_j} \sum_{i\in S} \pi_ig_{ij} = 0.
\]
By Bayes' Theorem
\[
\tilde{p}_{ij}(t) = \frac{\pi_j p_{ji}(t)}{\pi_i}. \tag{$*$}
\]
Using $(*)$ repeatedly, $\tilde{X}\sim\Markov(\pi, \tilde{P})$ since
\begin{align*}
\P(\tilde{X}_{t_0}=i_0, \cdots \tilde{X}_{t_n} = i_n) &= \P(X_0=i_n, X_{s_n}=i_{n-1}, \cdots X_{s_n+\cdots +s_1}=i_0) \\
&=\pi_{i_n} p_{i_n, i_{n-1}}(s_n) \cdots p_{i_1, i_0}(s_1) \\
&=\pi_{i_0}  \tilde{p}_{i_0, i_1}(s_1) \cdots\tilde{p}_{i_{n-1}, i_n}(s_n) .
\end{align*}
Fwd eqn for $P$ $\rightarrow$ bwd eqn for $\tilde{P}$:
\begin{align*}
\tilde{p}_{ij}'(t) &= \frac{\pi_j p_{ji}'(t)}{\pi_i} \\
&= \frac{\pi_j}{\pi_i}\sum_{k} p_{jk}(t) g_{ki} \\
&= \frac{\pi_j}{\pi_i}\sum_{k} \left( \frac{\pi_k}{\pi_j}\tilde{p}_{kj}(t) \right)\left( \frac{\pi_i}{\pi_k}\tilde{g}_{ik}(t) \right) \\
&=\sum_{k} \tilde{p}_{kj}(t) \tilde{g}_{ik}.
\end{align*}
For non-explosivity, we check the total probability is
\[
\sum_j \tilde{p}_{ij}(t) = \frac{1}{\pi_i} \sum_j \pi_j p_{ji}(t) = \frac{1}{\pi_i} \pi_i = 1.
\]
\end{proof}

Q: Reversible chain
A: $X\sim\Markov(\pi, G)$ is reversible if $\forall T>0$, the reversed process $\tilde{X}$ has the same distribution as $X$. Equivalently, $(\pi, G)$ is in detailed balance, i.e.
\[
\pi_i g_{ij} = \pi_j g_{ji}.
\]

Q: Balanced $\implies$ invariant
A: If $(\pi, G)$ is in detailed balance, then $\pi$ is an invariant distribution.
\begin{proof}
We compute
\[
\sum_{i} \pi_i g_{ij} = \pi_j \sum_i g_{ji} = 0.
\]
\end{proof}

Q: Birth-death chain detailed balance equations
A: Let $g_{i,i-1}=\mu_ig_i, g_{i,i+1}=\lambda_i g_i, g_{0,-1}=0$. Then the detailed balance equations give for $i\geq 0$:
\begin{align*}
\pi_i(\lambda_ig_i) &= \pi_{i+1}(\mu_{i+1}g_{i+1}) \\
\pi_{i+1} &= \frac{\lambda_i g_i}{\mu_{i+1}g_{i+1}} \pi_i \\
&= \frac{\lambda_i \cdots \lambda_0 g_0}{\mu_{i+1}\cdots \mu_1 g_{i+1}} \pi_0.
\end{align*}

Q: Queue notation
A: $A/B/k$ is the queue with interarrival times $\sim A$, service times $\sim B$, $k=$\#(servers).
$M_\lambda\sim \Exp(\lambda)$
$\mathcal{D}\sim$ deterministic
$G\sim$ general distribution.

Q: Traffic intensity
A: Let $A/B/k$ be a queue. Let $X,S$ be typical interarrival, service times resp. Then define
\[
\rho = \frac{\E S}{k\E X}.
\]
If $\rho>1$, then the queue grows. If $\rho<1$, the queue converges to equilibrium.

Q: Kolmogorov equation for $M_\lambda/M_\mu/1$
A: The queue size $Q_t$ is a MC on $\Z_\geq 0$ with
\[
g_{i,j} =
\begin{cases}
\lambda \quad j=i+1 \\
\mu \quad j=i-1\geq 0 \\
0 \quad \text{otherwise}.
\end{cases}
\]
$\sup_ig_i<\infty$ $\implies$ no explosion. Write $p_{0n}=p_n$. The fwd eqns are
\[
p_n' = \begin{cases}
\lambda p_{n-1} -(\lambda + \mu) p_n + \mu p_{n+1} \quad & n \geq 1 \\
-\lambda p_0 + \mu p_1 \quad & n = 0.
\end{cases}
\]
Taking LT
\[
\theta\hat{p}_n = \begin{cases}
\lambda \hat{p}_{n-1} - (\lambda + \mu) \hat{p}_n + \mu\hat{p}_{n+1}  \quad & n\geq 1\\
1 + \lambda\hat{p}_0 - \mu\hat{p}_1 \quad & n=0.
\end{cases}
\]
Note $p_n$ bounded $\implies$ $\hat{p}_n$ bounded cts. Hence take -ve root of the AQ.

Q: Invariant measure for $M_\lambda/M_\mu/1$
A: The queue size $Q_t$ is a MC on $\Z_\geq $ with
\[
g_{i,j} =
\begin{cases}
\lambda \quad j=i+1 \\
\mu \quad j=i-1\geq 0 \\
0 \quad \text{otherwise}.
\end{cases}
\]
$\sup_ig_i<\infty$ $\implies$ no explosion. $\pi G=0$ gives
\[
\lambda\pi_{n-1} - (\lambda + \mu) \pi_n + \pi_{n+1}=0
\]
with roots $\{1, \rho=\frac{1/\lambda}{1/\mu}=\frac{\lambda}{\mu} \}$ and general solution
\[
\pi_n = \begin{cases}
A+B \rho^n \quad &\rho\neq 1 \\
A+Bn \quad & \rho = 1.
\end{cases}
\]
So $(\pi_n)$ is a distribution iff $\rho<1$, $\pi_n=B\rho^n=\rho^n(1-\rho)^{-1}\sim \Geo(\rho)$.
Finally for $\lambda, \mu >0, \rho<1$, we have that $Q$ is irreducible, non-explosive and positive recurrent.

Q: Burke's Theorem
A: Let $Q_t$ be the queue size for $M_\lambda/M_\mu/1$. Let $\rho<1$ and $Q_0\sim \pi$. Let $D_t$ be the \emph{departure process}. Then $D_t\sim pp(\lambda)$ and $Q_t$ is independent of $\{ D_s: s\leq t\}$.
\begin{proof}
Let $T>0$ and write $\tilde{Q}_u = Q_{T-u}$. By reversibility $\tilde{Q}\sim Q$.
Departures in $Q$ correspond to arrivals in $\tilde{Q}$ (and vice versa).
Hence $D\sim$ $Q$-arrivals $\sim pp(\lambda)$.
For independence observe
\begin{align*}
Q_0 & \text{ is independent of $Q$-arrivals in $(0,T]$.} \\
\intertext{Reversing gives that}
\tilde{Q}_T & \text{ is independent of $\tilde{Q}$-departures.} \\
\intertext{By reversibility}
Q_T & \text{ is independent of $\{ D_s: s\leq T\}$.}
\end{align*}
\end{proof}

Q: Markov unlimited servers
A: Let $Q_t$ be the queue process for $M/M/\infty$ with $g_{i,i+1}=\lambda, g_{i,i-1}=i\mu$.
\emph{Non-explosive}. The number of jumps is bounded by 2 $pp(\lambda)$ processes.
\emph{Invariant distribution}. The detailed balance equations give
\begin{align*}
i\mu \pi_i &= \lambda \pi_{i-1} \\
\pi_i &= \frac{\lambda}{i\mu} \pi_{i-1} \\
&= \left(\frac{\lambda}{\mu}\right)^i \frac{1}{i!} \pi_0 \\
&= \left(\frac{\lambda}{\mu}\right)^i \frac{1}{i!} e^{-\lambda/\mu}.
\end{align*}
So $Q_t$ is \emph{positive recurrent}.

Q: Baulking
A: When customers leave a queue depending on a random process determined by the queue size.

Q: Semi-Markovian queue: embedded MC
A: Let $Q\sim M/G/1$. Let $D_n$ be the departure time of the $n$th customer. Then $Q(D_n^+)$ is a discrete-time MC.
\begin{proof}
Writing $U_n=|\{\text{arrivals} \in (n+1)\text{th service}\}|$, $h=\mathbbm{1}_{>0}$ gives
\begin{align*}
Q(D_{n+1}) &= \begin{cases}
Q(D_n) + U_n \quad & Q(D_n)=0 \\
Q(D_n) - 1 + U_n \quad & Q(D_n)\geq 1
\end{cases} \\
&= Q(D_n) + U_n-h(Q(D_n))
\end{align*}
where $U_n$ depends only on the length of the $(n+1)$th service so is independent of $Q(D_1), \cdots Q(D_n)$.
\end{proof}

Q: Semi-Markovian Queue: PGF equation
A: Let $Q\sim M/G/1$, $Q(D_{n+1})=Q(D_n) + U_n-h(Q(D_n))$ and $S\sim G$. Then the PGF of $U_n$ is
\[
\Delta(s):=G_{U_n}(s) = M_S(\lambda(s-1)).
\]
\begin{proof} We can compute the distribution
\[
\delta_j:= \P(U_n=j) = \E[\P(U_n=j | S)] = \E\left[ \frac{e^{-\lambda S}(\lambda S)^j}{j!} \right].
\]
Hence by Fubini
\begin{align*}
G_{U_n}(s) &= \sum_j s^j \P(U_n=j) \\
&= \E\left[ \sum_j \frac{(\lambda s S)^j e^{-\lambda S}}{j!}\right] \\
&= \E[e^{-\lambda S + \lambda s S}] \\
&= \E[e^{\lambda(s-1)S}] \\
&= M_S(\lambda(s-1)).
\end{align*}
\end{proof}

Q: Semi-Markovian Queue: invariant distribution
A: Let $Q\sim M/G/1$ and $S\sim G$. If $\rho<1$, then $Q(D)$ is PR with invariant PGF
\[
G(s) = \frac{(1-\Delta'(1))(s-1)M_S(\lambda(s-1))}{s-M_S(\lambda(s-1))}.
\]
Also $\rho=1$ $\implies$ null recurrent; $\rho>1$ $\implies$ transient.
\begin{proof}
The transition matrix of $Q(D)$ is
\[
P=\begin{pmatrix}
\delta_0 & \delta_1 & \delta_2 & \cdots \\
\delta_0 & \delta_1 & \delta_2 & \cdots \\
0 & \delta_0 & \delta_1 &  \ddots \\
\end{pmatrix}.
\]
Writing $\varepsilon_n = 1-\sum_{j=0}^n \delta_j > 0$, $\pi P=\pi$ gives
\begin{align*}
\pi_j &= \pi_0\delta_j + \sum_{i=1}^{j+1} \pi_i \delta_{j-i+1} \qquad (j\geq 0). \tag{$*$} \\
\sum_{j=0}^n \pi_j &= \pi_0(1-\varepsilon_n) + \sum_{i=1}^{n+1}\pi_i \sum_{j=i-1}^n \delta_{j-i+1} \qquad\text{(summing over $j$)}\\
&= \pi_0(1-\varepsilon_n) + \pi_{n+1}\delta_0 + \sum_{i=1}^{n}\pi_i (1-\varepsilon_{n-i+1}) \\
\pi_{n+1}\delta_0 &= \pi_0\varepsilon_n + \sum_{i=1}^n (\pi_i\varepsilon_{n-i+1}) \tag{$\dagger$}.
\end{align*}
By induction on ($\dagger$): $\pi_0>0 \implies \pi_j>0$. Multiply by $s^j$ and sum ($*$):
\begin{align*}
G &= \pi_0 \Delta + (G-\pi_0)\Delta s^{-1} \qquad\text{(convolution)} \\
G&= \frac{(s-1)\pi_0\Delta}{s-\Delta}. \\
G(1) &= \lim_{s\to 1} \frac{\pi_0\Delta + (s-1)\pi_0\Delta'}{1-\Delta'} \qquad\text{(L'H\^opital)} \\
1 &= \frac{\pi_0}{1-\Delta'(1)}
\end{align*}
provided $\Delta'(1)=\lambda M_S'(0)=\rho<1$.
\end{proof}

Q: Waiting time MGF
A: Assume $\rho<1$ and $Q(D)$ is in equilibrium with PGF $G$. Let $W+S$ be the lifetime of a typical customer. Then $G$ is related to $M_W, M_S$ by
\begin{align*}
G(s) &= \E[s^{Q(D)}] \\
&=\E [\E[s^{Q(D)} | W+S]] \\
&=\E[e^{\lambda(W+S)(s-1)}] \qquad \text{(Poisson PGF)}\\
&= \E[e^{\lambda W(s-1)}] \E[e^{\lambda S(s-1)}] \\
&= M_W(\lambda(s-1)) M_S(\lambda(s-1)).
\end{align*}

Q: Busy periods
A: Let $B$ be a busy period of $M/G/1$.
Then $\E[B]<\infty \iff Q(D)$ is PR $\iff \rho<1$.
Define the children of $I$ to be the arrivals during $I$'s service time $S$.
Then $\E[\text{children}]=\E[\E[\text{arrivals}] | S]=\E[\lambda S] = \rho$.
So this branching process is a.s. finite $\iff \rho\leq 1$.
Moreover $B$ is the sum of service times in this tree so
\begin{align*}
M_B(s) &= \E[\E[e^{s(S+\sum_{i=1}^A B_i)} | S]] \\
&= \E[e^{sS} G_{\Po (\lambda S)}(M_B)] \\
&= \E[e^{sS} e^{\lambda S (M_B - 1)}] \\
&= M_S(s+\lambda(M_B-1)).
\end{align*}
This gives a unique solution for $M_B$ when $\rho<1$.

Q: Jackson networks
A: Let $S=\{s_1, \cdots s_c\}$ be a network of $G/M/1$ queues of sizes $Q_i(t)=n_i$. The generator is
\begin{align*}
g_{\mathbf{n}, \mathbf{n}-\mathbf{e}_i+\mathbf{e}_j} &= \lambda_{ij}\varphi_i(n_i) \qquad\text{(transfer)}\\
g_{\mathbf{n}, \mathbf{n}-\mathbf{e}_i} &= \mu_i\varphi_i(n_i) \qquad\text{(emigration)} \\
g_{\mathbf{n}, \mathbf{n}+\mathbf{e}_j} &= \nu_j \qquad\text{(immigration)}.\\
\end{align*}
If $\mu=\nu=0$, then the network is \emph{closed}, i.e. $\|\mathbf{n}\|_1$ $=$ constant. Otherwise it is \emph{open}.

Q: Simple closed network
A: Assume $\forall i: \varphi_i(1)=1$ and a single customer. The customer's position is a MC with jump rates
\[
g_{ij} = \lambda_{ij} \quad (i\neq j).
\]
The invariant distribution $\alpha$ satisfies $\alpha G=0$, i.e.
\[
\sum_j \alpha_j\lambda_{ji} =\alpha_i \sum_j \lambda_{ij} \qquad (i\in S, \lambda_{jj}=0).
\]

Q: Closed network invariant distribution
A: The invariant distribution $\gamma = (\gamma(\mathbf{n}): \sum n_i=N)$ obeys $\gamma G=0$, i.e.
\[
\sum_{i,j} \gamma(\mathbf{n}-\mathbf{e}_i+\mathbf{e}_j) \lambda_{ji} \varphi_j(n_j+1) = \gamma(\mathbf{n}) \sum_{i,j} \lambda_{ij}\varphi_i(n_i).
\]
The \emph{partial balance equations} are satisfied for all $i\leq c$ by
\[
\gamma(\mathbf{n}) = B\prod_{i=1}^c \left[\frac{\alpha_i^{n_i}}{\prod_{r=1}^{n_i} \varphi_i(r)} \right]
\]
where $B$ is a normalising constant and $\alpha$ is the solution for $N=1$.
\begin{proof}
For $n_i\geq 1$:
\[
\frac{\gamma(\mathbf{n}-\mathbf{e}_i+\mathbf{e}_j)}{\gamma(\mathbf{n})} = \frac{\alpha_j\varphi_i(n_i)}{\alpha_i\varphi_j(n_j+1)}.
\]
So the partial balance equations become
\[
\sum_j \alpha_j\lambda_{ji} = \sum_j \alpha_i\lambda_{ij}.
\]
\end{proof}

Q: Open network
A: Add station $\infty$ with jump rates
\[
g_{ij} = \begin{cases}
\lambda_{ij} \quad & 1\leq i, j \leq c \\
\mu_i \quad & 1\leq i \leq c, j=\infty \\
\nu_j \quad & i=\infty, 1 \leq j \leq c.
\end{cases}
\]
The invariant distribution for $N=1$ is $\beta=(\beta_j: j=1, 2 \cdots c, \infty)$ obeys $\beta G=0$, i.e.
\[
\beta_\infty \nu_i + \sum_{j\leq c} \beta_j \lambda_{ji} = \beta_i\left( \mu_i + \sum_{j\leq c} \lambda_{ij} \right).
\]
Write $\alpha_i = \beta_i / \beta_\infty$. Then the invariant distribution is $\pi(\mathbf{n})=\prod_{i=1}^c \pi_i(n_i)$ where
\[
\pi_i(n_i) = \frac{B\alpha_i^{n_i}}{\prod_{i=0}^{n_i} \varphi_i(r)}
\]
where $B$ is normalising and assuming $\sum_j \mu_j=\sum_j \nu_j$.
\begin{proof}
Similar to closed networks.
\end{proof}

Q: Renewal process
A: Let $(X_i)\subseteq L^1$ be $(0,\infty)$ iid rvs and $T_n=\sum_{i\leq n} X_i$.
Then $N(t)=\max\{ n: T_n\leq t\}$ is a \emph{renewal process}.

Q: Renewal distribution functions
A: Let $F_k$ be the cdf of $T_k$. Then we obtain $F_k$ by L-S convolutions
\begin{align*}
T_{k+1} &= T_k + X_{k+1} \\
F_{k+1} &= F_k * F. \\
\intertext{Hence we obtain the mass function}
\P(N(t) = k) &= \P(T_k \leq t < T_{k+1}) \\
&= F_k(t) - F_{k+1}(t). \\
\intertext{Taking expectations}
m(t) &= \E[N(t)] \\
&= \sum_{k\in\N} \P(N(t)\geq k) \\
&= \sum_{k\in\N} \P(T_k \leq t) \\
&= \sum_{k\in\N} F_k(t).
\end{align*}

Q: Renewal equation
A: $m=\E[N(t)]$ satisfies the \emph{renewal equation}
\[
m(t) = F(t) + \int_0^t m(t-x) \; \d F(x).
\]
\begin{proof}
By tower property of expectation
\begin{align*}
m(t) &= \E[\E[N(t) | X_1]] \\
&= \int_\R \mathbbm{1}_{[x < t]} \left[ 1 + m(t-x) \right]\; \d F(x) \\
&= F(t) + \int_0^t m(t-x) \d F(x).
\end{align*}
\end{proof}

Q: Renewal type equation
A: In Laplace-Stieljes notation, the equation
\[
\mu = H + \mu * F \tag{$*$}
\]
has solution
\[
\mu = H + H* m \tag{$\dagger$}
\]
which is unique assuming $H$ is bounded on finite intervals.
\begin{proof}
Convolving $(\dagger)$ with $F$
\begin{align*}
\mu * F &= H * F + H * m * F \\
&= H*F + H*(m-F) \qquad \text{(renewal eqn)} \\
&= \mu - H \kern 4cm (\text{using }\dagger).
\end{align*}
\end{proof}

Q: Renewal pointwise theorem
A: Let $N(t)$ be a renewal process with $\mu=\E[X]$. Then
\[
\frac{N(t)}{t} \xrightarrow{a.s.} \frac{1}{\mu}.
\]
\begin{proof}
By definition
\[
T_{N(t)} \leq t < T_{N(t)+1}.
\]
Dividing by $N(t)$:
\[
\underbrace{\frac{T_{N(t)}}{N(t)}}_{\to \mu \text{ by SLLN}} \leq \frac{t}{N(t)} < \underbrace{\frac{T_{N(t)+1}}{N(t)+1}}_{\to \mu \text{ by SLLN}} \underbrace{\left[ \frac{N(t)+1}{N(t)}\right]}_{\to 1}.
\]
Done by squeeze theorem.
\end{proof}

Q: Renewal stopping time
A: $M=N(t)+1$ is a stopping time for $X$.
\begin{proof}
For any $m\in\N$:
\begin{align*}
\{ M \leq m \} &= \{ N(t) \leq m - 1\} \\
&= \left\{ \sum_1^m X_i > t \right\} \\
&\in \sigma(X_1, \cdots X_m).
\end{align*}
\end{proof}

Q: Wald's equation
A: If $M$ is a stopping time for $X=(X_i)\geq 0$ iid, then
\[
\E\left[\sum_{i=1}^M X_i \right] = \E[M]\E[X].
\]
\begin{proof}
Applying MCT and Fubini
\begin{align*}
\E\left[\sum_{i=1}^M X_i \right] &= \E\left[\sum_{i=1}^\infty X_i \mathbbm{1}_{\{M\geq i\}}\right] \\
&= \E\left[\sum_{i=1}^\infty X_i \mathbbm{1}_{\{M\leq i - 1\}^c}\right] \\
&= \sum_{i=1}^\infty\E[ X_i] \P(M\geq i)\\
&= \E[X]\E[M].
\end{align*}
\end{proof}

Q: Renewal Theorem
A: For $N(t)$ a renewal process, with $\E[X]=\mu$, we have the $L^1$ convergence
\[
\frac{m(t)}{t} \to \frac{1}{\mu}.
\]
\begin{proof}
By definition
\[
T_{N(t)} \leq t< T_{N(t)+1}.
\]
($\geq$) By Wald
\[
t < \E[ T_{N(t)+1} ] = \mu(m(t)+1).
\]
Rearranging gives
\[
\frac{m(t)}{t} > \frac{1}{\mu} - \frac{1}{t} \to \frac{1}{\mu}.
\]
($\leq$) By Wald again
\[
t \geq \E[ T_{N(t)+1} - X_{N(t)+1}] = \mu(m(t)+1) - \E[X_{N(t)+1}]. \tag{$*$}
\]
Define truncated $X_i^a = X_i \wedge a$ for $a>0$. Applying ($*$) to $N^a$ gives
\begin{align*}
t &\geq  \mu^a(m^a(t)+1) - \E[X_{N(t)+1}] \\
&\geq \mu^a (m(t) + 1) - a \\
\frac{m(t)}{t} & \leq \frac{1}{t} \left( \frac{t+a}{\mu^a} - 1\right) \\
&\xrightarrow{t\to\infty} \frac{1}{\mu^a}\\
& \xrightarrow{a\to \infty} \frac{1}{\mu} \qquad \text{(MCT)}.
\end{align*}
\end{proof}

Q: Excess life
A: \emph{Excess life} $E(t):=T_{N(t)+1} - t$.
\emph{Current life} $C(t):=t - T_{N(t)}$.
\emph{Total life} $L(t) = E(t) + C(t) = X_{N(t)+1}$.

Q: Excess life distribution
A: Write $\mu(t)=\P(E(t)>y)$ and $H(t)=1-F(t+y)$. Then
\[
\mu(t) = H(t) + \int_0^t H(t-x) \; \d m(x).
\]
\begin{proof}
Conditioning on $X_1$
\[
\P(E(t)>y | X_1=x) = \begin{cases}
\P(E(t-x) > y) \quad & 0\leq x\leq t \\
0 \quad & t < x \leq t+y \\
1 \quad &  t+y < x < \infty.
\end{cases}
\]
Integrating gives the renewal-type equation
\[
\mu(t) = H(t) + \int_0^t \mu(t-x) \; \d F(x).
\]
\end{proof}

Q: Arithmetic random variable
A: A rv $X$ is \emph{arithmetic} if $\exists\lambda >0$ such that $X\in\lambda\Z$ a.s.
The maximal such $\lambda$ is the \emph{span} of $X$.

Q: Excess life stationary distribution
A: If $X$ is non-arithmetic and $\mu = \E[X]<\infty$, then
\[
\P(E(t) \leq y) \to \frac{1}{\mu} \int_0^y \left[ 1 - F(x)\right] \; \d x.
\]
\begin{proof}
Corollary of key-renewal theorem.
\end{proof}

Q: Reward function
A: The accumulated reward by time $t$ is
\[
C(t) = \sum_{i=1}^{N(t)} R_i
\]
and the expectation is the \emph{reward function}
\[
c(t) = \E[C(t)].
\]

Q: Renewal-reward theorem
A: If $0<\E[X]<\infty$, $\E |R|<\infty$, then
\[
\frac{C(t)}{t} \to \frac{\E[R]}{\E[X]}
\]
in $L^1$ and a.s.
\begin{proof}
By SLLN and renewal theorem
\[
\frac{C(t)}{t} = \left( \frac{\sum_{i=1}^{N(t)} R_i}{N(t)} \right) \left( \frac{N(t)}{t} \right) \xrightarrow{a.s.} \frac{\E[R]}{\E[X]}.
\]
Using Wald's equation
\begin{align*}
c(t) &= \E\left[ \sum_{i=1}^{N(t)+1} R_i \right] - \E[R_{N(t)+1}] \\
&= (m(t)+1)\E[R] - \E[R_{N(t)+1}] \\
\frac{c(t)}{t} &= \frac{m(t)+1}{t}\E[R] - \frac{\E[R_{N(t)+1}]}{t}.
\end{align*}
By renewal thm ets $ \frac{r(t)}{t}:=\frac{\E[R_{N(t)+1}]}{t}\to 0$. Indeed, conditioning on $X_1$
\[
r(t) = H(t) + \int_0^t r(t-x) \; \d F(x),
\]
where $H(t)=\E [ R_1\mathbbm{1}_{X_1 > t} ] \to 0$ by DCT, with solution
\[
r(t) = H(t) + \int_0^t H(t-x) \; \d m(x).
\]
Given $\varepsilon>0$, $\exists T>0$ such that $\forall t \geq T$: $|H(t)|<\varepsilon$. Hence $\forall t \geq T$:
\begin{align*}
\left| \frac{r(t)}{t} \right| &\leq \frac{1}{t} \left[ |H(t)| + \int_0^{t-T} |H(t-x)| \d m(x) + \int_{t-T}^t |H(t-x)| \; \d m(x) \right] \\
& \leq \frac{1}{t} \left[ \varepsilon + \varepsilon ( m(t-T) - m(0)) + \E |R| [\underbrace{m(t) - m(t-T)}_{\leq 1 +m(T)} ]\right] \\
&\to 0 + \frac{\varepsilon}{\E[X]} + 0 \quad \text{as $t\to\infty$ (by renewal thm)}.
\end{align*}
\end{proof}

Q: Invariant distribution by renewal-reward
A: Let $X$ be a cts-time, PR, irreducible, strictly-positive-rate MC. Then
\[
\frac{\int_0^t p_{ii}(u) \; \d u}{t} \to \frac{1}{g_im_i}.
\]
\begin{proof}
Define
\[
C(t) = \int_0^t \mathbbm{1}_{\{X(u)=i\}} \; \d u.
\]
Done by r-r thm.
\end{proof}

Q: Little's Theorem
A: Assume queueing system such that
\begin{enumerate}
\item customers arrive sequentially with waiting time $W_n$ (including service)
\item $\exists T$ finite a.s. (a \emph{regeneration point}) such that $Q(t-T)\sim Q(t)$ (immediately there are infinitely many)
\item $Q(0)=0=Q(T)$.
\end{enumerate}
Intervals $[T_{i-1}, T_i)$ are called \emph{cycles}, with length $X_i$ and arrivals $N_i$ iid. Assume $N,T,NT\in L^1$. Write $M_i = \sum_{j\leq i} N_i$.
Let the long-run averages be $L$ for queue length, $\lambda$ for arrival rate and $W$ for waiting time. Then $L=\lambda W$.
\begin{proof}
Take renewals $T_i, T_i, M_i$ and rewards
\[
R_i := \int_{T_{i-1}}^{T_i} Q, \quad N_i, \quad \sum_{j=M_{i-1}}^{M_i} W_{j}=R_i.
\]
Applying rr thm 3 times
\begin{align*}
\frac{1}{t} \int_0^t Q &\xrightarrow{a.s.} \frac{\E[R]}{\E[T]} =L \\
\frac{N(t)}{t} &\xrightarrow{a.s.} \frac{\E[N]}{\E[T]} =\lambda \\
\frac{1}{n} \sum_{k=1}^n W_k & \xrightarrow{a.s.} \frac{\E[R]}{\E[N]} = W.
\end{align*}
\end{proof}

Q: Wright-Fisher model
A: Assume diploid with $2N$ alleles from $\{ A,a \}$ with $X_n$ of type $A$.
Assume \emph{separation of generations}, i.e. next generation obtained by sampling $2N$ times with replacement. Then $(X_n)$ is a MC with
\[
p_{ij} = {2N \choose j} \alpha_i^j (1-\alpha_i)^{2N-j}
\]
where $\alpha_i = i / 2N$. Moreover $(X_n)$ is a martingale:
\[
\E[X_n| X_{n-1}] = X_{n-1}.
\]

Q: Fixation: pure expectation formula
A: Let $\tau$ be the hitting time of $\{0,N\}$ in the Moran model. Then
\[
\P_i(X_\tau = N) = \frac{i}{N}
\]
and
\[
\E_i[\tau] = \sum_{j=1}^{i-1} \frac{N-i}{N-j} + \sum_{j=i}^{N-1} \frac{i}{j}.
\]
\begin{proof}
Since $\tau<\infty$ a.s. and $|X_\tau|\leq N$, we can apply OST to obtain
\[
N\P_i(X_\tau = N) =\E_i[X_\tau] = \E_i[X_0]  = i.
\]
Write $\tau = \sum_{j=1}^N \tau_j$ where $\tau_j$ is the total time spent in $j$. Recognising the geometric distribution
\[
\E_j[\tau_j] = \frac{1}{g_j}\E_j[\# \text{ visits to } j ] = \frac{1}{g_j}\P_j[\text{no return to } j ] ^{-1}.
\]
Conditioning on the first step and using Gambler's ruin
\begin{align*}
P_j[\text{no return to } j ]&= \frac{1}{2}\P_{j-1}(T_0<T_j) +  \frac{1}{2}\P_{j+1}(T_N<T_j) \\
&= \frac{1}{2}\frac{1}{j} +  \frac{1}{2}\frac{1}{N - j}.
\end{align*}
Substituting in
\begin{align*}
\E_j[\tau_j] &=  \frac{1}{g_j}\frac{2j(N-j)}{N} = 1 \\
\E_i[\tau] &= \sum_j \E_i[\tau_j] \\
&= \sum_j \P_i(\text{hit }j) \E_j[\tau_j] \\
&=\sum_{j<i} \frac{N-i}{N-j} + \sum_{j\geq i} \frac{i}{j}.
\end{align*}
\end{proof}

Q: Moran model
A: At rate 1, each individual dies and is replaced by a random member of the population. Hence the replacements $(N_t^{i,j}: 1\leq i, j \leq N)$ are iid pp($1/N$).
Assuming two alleles, the number of individuals $X_t$ of each type forms a MC with generator
\[
g_{i,i+1} = g_{i,i-1} = \frac{i(N-i)}{N}
\]
and JC the SRW on $\{0, \cdots N\}$.

Q: Infinite sites model
A: Bi-infinite Moran model with \emph{neutral} (i.e. independent) mutation rate $u>0$. Write $\theta=uN$ for the \emph{total} mutation rate.

Q: Site frequency spectrum
A: The function $\theta\mapsto\frac{\theta}{j}$ is called the site frequency spectrum of the infinite sites model. Let $M_j(n)$ be the number of sites with $j$ mutants in a sample of size $n$. Then
\[
\E[M_j(N)] = \frac{\theta}{j}.
\]
The Single Nucleotide Polymorphism (SNP) $S_n:=\sum_{j=1}^n M_j(n)$, i.e. the number of sites with a mutant, has expectation
\[
\E[S_n] = \theta \sum_{j=1}^n \frac{1}{j} \sim \theta \log n.
\]
\begin{proof}
Conditioning on the first mutation times
\begin{align*}
\E[M_j(N)] &= \int_0^\infty p_{1j}(t) \; \theta \d t \\
&= \theta \E_1\left[\int_0^\infty \mathbbm{1}_{ \{X_t=j\}} \; \d t \right]  \\
&= \theta \E_1[\tau_j] \\
&= \theta \P_1(\text{hit }j)\E_j[\tau_j] \\
&= \theta \left( \frac{1}{j} \right).
\end{align*}
\end{proof}

Q: Kingman's $n$-coalescent
A: Define the \emph{ancestral partition} $\Pi_t^{(n)}$ of $\{1, \cdots n\}$ such that $i,j$ are in the same block iff $i,j$ have the same ancestor at time $-t$. Then Kingman's $n$-coalescent $(\Pi_{Nt/2}^{(n)})$ is a MC on $\mathcal{P}_n$ with generator
\[
g_{\pi, \pi'} = \begin{cases}
1 \quad & \text{$\pi'$ obtained from $\pi$ by coalescing two blocks} \\
- {k \choose 2} \quad & \text{$\pi'=\pi$ has $k$ blocks} \\
0 \quad & \text{otherwise}.
\end{cases}
\]
The state $\{1, \cdots n\}$ is the Most Recent Common Ancestor (\emph{MRCA}).
\begin{proof}
The rate at which two individuals in the Moran model coalesce is $2/N$.
\end{proof}

Q: Kingman's infinite coalescent
A: \emph{Compatibility} or \emph{sampling consistency}: $\Pi_t^{(n)}|_{[n-1]}\sim \Pi_t^{(n-1)}$.
Kolmogorov's Extension Theorem gives a unique $(\Pi_t)$ on $\mathcal{P}(\N)$ such that $\Pi_t|_{[n]}\sim \Pi_t^{(n)}$.
$|\Pi_t|<\infty$ for any $t>0$ a.s. In particular, there is a MRCA.
\begin{proof}
Write $\tau_j\sim \Exp(\binom{j}{2})$ for the time in which $|\Pi_t^{(n)}|$ drops from $j$ to $j-1$.
\begin{align*}
\P(|\Pi_t| \geq M) &= \lim_{n\to\infty} \P(|\Pi_t^{(n)}| \geq M) \quad \text{(MCT)} \\
&= \lim_{n\to\infty} \P \left( \sum_{j=M+1}^n \tau_j \geq t \right) \\
 &\leq \frac{1}{t}\E\left[ \sum_{j=M+1}^\infty \tau_j \right] \quad \text{(Markov)} \\
&=\frac{1}{t} \sum_{j=M+1}^\infty \frac{1}{\binom{j}{2}} \\
&=\frac{2}{t}\sum_{j=M+1}^\infty \frac{1}{j(j-1)} \\
&\to 0 \text{ as }M\to\infty.
\end{align*}
\end{proof}

Q: Fixation: conditional formula
A: Let $\tau_y$ be the time spent in state $y$ given absorbing set $A$. Write $h(x)=\P_x(T_A<\infty)$. Then
\[
h(x)\E_x[\tau_y | T_A<\infty] = h(y) \E_x[\tau_y], \qquad \E_y[\tau_y|T_A<\infty]=\E_y[\tau_y].
\]
\begin{proof}
Conditioning on hitting $y$
\begin{align*}
\E_x[\tau_y | T_A<\infty] &= \frac{1}{h(x)} \E_x[\tau_y \mathbbm{1}_{T_A<\infty}] \\
&= \frac{1}{h(x)} \E_x[\tau_y \mathbbm{1}_{T_A<\infty} | T_y<T_A]\P_x(T_y<T_A) \\
&= \frac{1}{h(x)} \E_y[\tau_y \mathbbm{1}_{T_A<\infty} ]\P_x(T_y<T_A) \\
&= \frac{h(y)}{h(x)} \E_y[\tau_y | T_A<\infty]\P_x(T_y<T_A).
\end{align*}
For the second part, $\E[\tau_y]=\frac{1}{g_y}\E[\Geo(\P(T_A<T_y))]$ where by SMP
\[
\P_y( T_y<T_A | T_A<\infty) =  \frac{ \P_y( T_y<T_A<\infty)}{\P_y(T_A<\infty)} =  \P_y( T_y<T_A).
\]
\end{proof}