% Upper-case    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
% Lower-case    a b c d e f g h i j k l m n o p q r s t u v w x y z
% Digits        0 1 2 3 4 5 6 7 8 9
% Exclamation   !           Double quote "          Hash (number) #
% Dollar        $           Percent      %          Ampersand     &
% Acute accent  '           Left paren   (          Right paren   )
% Asterisk      *           Plus         +          Comma         ,
% Minus         -           Point        .          Solidus       /
% Colon         :           Semicolon    ;          Less than     <
% Equals        =           Greater than >          Question mark ?
% At            @           Left bracket [          Backslash     \
% Right bracket ]           Circumflex   ^          Underscore    _
% Grave accent  `           Left brace   {          Vertical bar  |
% Right brace   }           Tilde        ~

% ---------------------------------------------------------------------|
% --------------------------- 72 characters ---------------------------|
% ---------------------------------------------------------------------|
%
% Optimal Foraging Theory Revisited: Appendix. Renewal Theory
% (this material not included in final version of document)
%
% (c) Copyright 2007 by Theodore P. Pavlic
%

\chapter{Renewal Theory}
\label{app:renewal_theory}

The Poisson random counting process is of great interest when modeling a
system that includes independent arrivals of tasks to process. It is a
well-known \emph{continuous-time Markov renewal process}.

\section{Counting Processes}

Take an experiment modeled by probability space $(\set{U},\Sigma,\Pr)$.
Define a (continuous-time) random process $(N(t): t \in \R_{\geq 0})$
such that for each $t \in \R_{\geq0}$,
%
\begin{equation*}
        \range( N(t) ) = \W
\end{equation*}
%
and for each $\zeta \in \set{U}$ and each $t_a,t_b \in \R_{\geq0}$ with
$t_b \geq t_a$,
%
\begin{equation*}
        N(t_b) \geq N(t_a)
\end{equation*}
%
which could also be written $N(t_b)(\zeta) \geq N(t_a)(\zeta)$ to
emphasize that this is for each particular $\zeta \in \set{U}$. In other
words, $(N(t):t \in \R_{\geq0})$ is a random process whose elements are
random variables that only take whole number values and are
monotonically increasing in time for any particular outcome. The random
process $(N(t): t \in \R_{\geq0})$ is called a \emph{counting process}.
For any $\zeta \in \set{U}$, $N(t)$ may be viewed as a count of the
number of events that have occurred during the interval of time $[0,t]$.
There are a number of related random variables and processes that are
usually of interest in the analysis of counting processes.
%
\begin{itemize}
        \item For any $t_a,t_b \in \R_{\geq 0}$ such that $t_b \geq
                t_a$, define the random variable $I(t_b,t_a): \set{U}
                \mapsto \extR$ by
                %
                \begin{equation*}
                        I(t_b,t_a) \triangleq N(t_b) - N(t_a)
                \end{equation*}
                %
                for every $\zeta \in \set{U}$ (\ie, $I(t_b,t_a)(\zeta)
                \triangleq N(t_b)(\zeta) - N(t_a)(\zeta)$). That is,
                $I(t_b,t_a)$ represents the number of events that have
                occurred between times $t_a$ and $t_b$. In particular,
                take $t \in \R_{>0}$ and $n \in \N$ and $(n+1)$-tuple
                $(t_0,t_1,\dots,t_n)$ such that $0 = t_0 < t_1 < \cdots
                < t_n = t$. Then, for any given $\zeta \in \set{U}$,
                %
                \begin{equation*}
                        N(t) 
                        = \sum\limits_{i=1}^n I(t_i,t_{i-1})
                        = \sum\limits_{i=1}^n ( N(t_i) - N(t_{i-1}) )
                \end{equation*}
                %
                The random variable $I(t_b,t_a)$ is called the
                \emph{increment of the counting process in $[t_a,t_b)$}
                (\ie, the increment between times $t_b$ and $t_a$).
        \item Take the sequence $(A_n)$ where $A_n: \set{U} \mapsto
                \R_{\geq 0}$ is a random variable that is defined so
                that for any $\zeta \in \set{U}$, 
                %
                \begin{enumerate}[(i)]
                        \item $A_i < A_j$ for all $i,j \in \N$ with $i
                                < j$
                        \item for all $i \in \N$, for all $t
                                \in [0,A_i)$, $N(t) < N(A_i)$
                        \item for all $t \in \R$ where for all $t_0 \in
                                [0,t)$, $N(t_0) < N(t)$, there exists
                                some $i \in \N$ such that $A_i = t$
                \end{enumerate}
                %
                In other words, for each $\zeta \in \set{U}$, $(A_n)$ is
                a collection of times that correspond to each rise in
                the value of $N(t)$. Because $(A_n)$ is a collection of
                random time points that correspond to a particular
                outcome $\zeta$, it is known as a \emph{point process}.
                Because simultaneous events can occur, for any $n \in
                \N$, $A_n$ should \emph{not} be viewed as the time of
                the $n\th$ event. That is, simultaneous events will
                cause a single jump at one time point even though the
                jump will be greater than one. Thus, we call $(A_n)$ the
                \emph{arrival process}. For later ease of notation, also
                define $A_0 \triangleq 0$.
        \item Introduce and a new sequence $(S_n)$ where $S_n: \set{U}
                \mapsto \extR$ is a random variable that is defined so
                that for any $\zeta \in \set{U}$,
                %
                \begin{equation*}
                        S_n \triangleq A_n - A_{n-1}
                \end{equation*}
                %
                for all $n \in \N$. Thus, $(S_n)$ is a process
                representing the \emph{interarrival times} of the jumps
                in the counting process. That is, these are the times
                between each jump in the number of events. Again,
                because simultaneous events can occur, for any $n \in
                \N$, $S_n$ should \emph{not} be viewed as the time
                between events $n$ and $n-1$. In fact, for all $n \in
                \N$, $S_n > 0$. 
        \item Take the sequence $(B_N)$ where $B_N: \set{U} \mapsto
                \R_{\geq 0}$ is a random variable that is defined so
                that for any $\zeta \in \set{U}$, 
                %
                \begin{enumerate}[(i)]
                        \item $B_i \leq B_j$ for all $i,j \in \N$ with
                                $i < j$
                        \item for all $i \in \N$, for all $t
                                \in [0,A_i)$, $N(t) + 1 = N(B_i)$
                        \item for all $t \in \R$ where for all $t_0 \in
                                [0,t)$, $N(t_0) + 1 = N(t)$, there
                                exists some $i \in \N$ such that $B_i =
                                t$
                \end{enumerate}
                %
                In other words, for each $\zeta \in \set{U}$, $(B_N)$ is
                a collection of times that correspond to each rise in
                the value of $N(t)$ by \emph{one}. For any $N \in \N$,
                $B_N$ \emph{can} be viewed as the time of the $N\th$
                event. That is, events $N$ and $N+1$ are simultaneous if
                and only if $B_{N}=B_{N+1}$. Thus, we call $(B_N)$ the
                \emph{encounter process}. For ease of notation, also
                define $B_0 \triangleq 0$. Note that for any $\zeta \in
                \set{U}$ and any $t \in \R_{\geq0}$,
                %
                \begin{equation*}
                        N(t)
                        =
                        \sup\{ N \in \W : B_N \leq t \}
                \end{equation*}
                %
                In fact, some authors introduce the process $(B_N)$ and
                then use this expression as a definition for the process
                $(N(t): t \in \R_{\geq0})$. Of course, also note that
                for any $\zeta \in \set{U}$ and $t \in \R_{\geq0}$,
                %
                \begin{equation*}
                        t \geq B_{N(t)}
                \end{equation*}
                %
                where $t = B_N$ implies that $N = N(t)$.
        \item Introduce and a new sequence $(T_N)$ where $T_N: \set{U}
                \mapsto \extR$ is a random variable that is defined so
                that for any $\zeta \in \set{U}$,
                %
                \begin{equation*}
                        T_N \triangleq B_N - B_{N-1}
                \end{equation*}
                %
                for all $N \in \N$. Thus, $(T_N)$ is a process
                representing the \emph{interevent times} of the
                encounters in the counting process. That is, these are
                the times between each jump of one in the number of
                events.  More simply, for each $N \in \N$, $T_N$ can be
                viewed as the time between events $N$ and $N-1$. Of
                course, for any $N \in \N$, it may be that $T_N = 0$,
                which would indicate that event $N$ occurred at the same
                time as event $N-1$. Notice that for any $\zeta \in
                \set{U}$,
                %
                \begin{equation*}
                        A_1 = B_1 = S_1 = T_1
                \end{equation*}
                %
                Also note that for any $\zeta \in \set{U}$ and $t \in
                \R_{\geq 0}$, 
                %
                \begin{equation*}
                        t \geq \sum\limits_{i=1}^{N(t)} T_i
                \end{equation*}
                %
                Additionally, for any $\zeta \in \set{U}$ and any $t \in
                \R_{\geq 0}$,
                %
                \begin{equation*}
                        N(t) 
                        =
                        \sup\{ N \in \W : B_N \leq t \}
                        =
                        \sup\left\{ 
                        N \in \N 
                        : 
                        \sum\limits_{i=1}^N T_i \leq t \right\}
                \end{equation*}
                %
                and $N(t) \geq \sup\{ n \in \N : A_n \leq t \}$. For
                these reasons, the subscript on the $(B_N)$ and $(T_N)$
                processes will often be the same as the letter used to
                represent the counting process (\eg, notice how the
                subscript $n$ is used instead of $N$ for $(A_n)$ and
                $(S_n)$).
\end{itemize}

\section{Markov Renewal Processes}
\label{app:math_markov_renewal_processes}

A counting process with \iid{}\ interarrival times of non-zero finite
mean will be called a \emph{(Markov) renewal process}. This process can
be very useful.

\subsection{The Standard Renewal Process}

Take an experiment modeled by probability space $(\set{U},\Sigma,\Pr)$.
Let $(N(t): t \in \R_{\geq 0})$ be a counting process on this space with
the associated arrival process $(A_n)$, interarrival process $(S_n)$,
encounter process $(B_N)$, and interevent process $(T_N)$. Now, assume
that $(S_n)$ is a sequence of \iid{}\ random variables and $0 < \E(S_n)
< \infty$ for all $n \in \N$. In other words, each arrival can be viewed
in some way as a cycle being renewed. Thus, we will call this the
\emph{renewal property} (of a counting process). In this case,
%
\begin{itemize}
        \item $( N(t): t \in \R_{\geq 0} )$ is known as a \emph{renewal
                process}
        \item $(A_n)$ are known as \emph{renewal times} or \emph{jump
                times}
        \item $(S_n)$ are known as \emph{holding times}
        \item for all $n \in \N$, $[S_n,S_{n-1}]$ is known as a
                \emph{renewal interval}
        \item $(B_N)$ are known as \emph{encounter times}
        \item $(T_N)$ are known as \emph{interevent times}
\end{itemize}
%
It is the case that renewal processes have the Markov property, and so
given the present state of the process, the history of the process makes
no impact on the future conditional probability. Thus, sometimes renewal
processes are called \emph{Markov renewal processes} and depicted as in
\longref{fig:generic_markov_renewal_process} where a solid dot
represents a point that \emph{renews} at each jump of the process (\ie,
a \emph{renewal point}).
%
\begin{figure}[!ht]\centering
        %\begin{center}
        \begin{picture}(265,55)(0,0)
                \thinlines
                \put(0,20){\vector(1,0){50}}
                \put(55,20){\makebox(0,0)[l]{Holding Time}}
                \put(120,20){\line(1,0){145}}
                %
                \put(265,20){\line(0,-1){20}}
                \put(265,0){\line(-1,0){265}}
                \put(0,0){\line(0,1){20}}
                %
                \put(47.5,30){\circle*{5}}
                \put(47.5,40){\makebox(0,0)[bc]%
                        {\shortstack{Arrival\\Instant}}}
        \end{picture}
        %\end{center}
        \caption{Generic Markov Renewal Process}
        \label{fig:generic_markov_renewal_process}
\end{figure}
%
It can easily be shown that for a Markov renewal process
%
\begin{equation*}
        \aslim\limits_{t \to \infty} N(t) = \infty
\end{equation*}
%
Additionally, as discussed by \citet{JohnsMiller63}, it can be shown
that
%
\begin{equation}
        \aslim\limits_{t \to \infty} \frac{ N(t) }{t} = 
        \lim\limits_{t \to \infty} \frac{ \E( N(t) ) }{t} = 
        \aslim\limits_{N \to \infty} \frac{ N }{ B_N } =
        \frac{1}{ \E(S_1) }
        \label{eq:generic_renewal_limits}
\end{equation}
%
\Citeauthor{JohnsMiller63} also show that if there exists some $M \in
\N$ such that $\E( 1/A_M ) < \infty$ then
%
\begin{equation}
        \lim\limits_{N \to \infty} \E\left( \frac{ N }{ B_N } \right) =
        \frac{1}{ \E(S_1) }
        \label{eq:generic_renewal_limits_special}
\end{equation}
%
These are useful results.

\subsection{Renewal-Reward Processes}
\label{app:math_markov_reward_processes}

Take an experiment modeled by probability space $(\set{U},\Sigma,\Pr)$.
Let $(N(t): t \in \R_{\geq 0})$ be a (Markov) renewal process on this
space with the associated arrival process $(A_n)$, interarrival process
$(S_n)$, encounter process $(B_N)$, and interevent process $(T_N)$.
However, introduce three more random processes.
%
\begin{itemize}
        \item Let $(G_N)$ be a sequence where $G_N: \set{U} \mapsto
                \extR$ is a random variable representing some
                \emph{gain} at \emph{event} $N$ for each $N \in \N$. In
                other words, for a given $\zeta \in \set{U}$, $G_N$
                (possibly negative) is gained after $\sum\limits_{i=1}^N
                T_i$ time. We call the random process $(G_N)$ the
                \emph{gain process}. The process $(W_n)$, which we
                introduce next, will have assumptions that also
                constrain this process. 
                %
        \item Let $(W_n)$ be a sequence where $W_n: \set{U} \mapsto
                \extR$ is a random variable representing the \emph{total
                gain} at \emph{arrival} $n$ for each $n \in \N$. In
                other words, note that for each $\zeta \in \set{U}$, for
                each $n \in \N$, there exists an $M,N \in \N$ that
                %
                \begin{equation*}
                        T_{M-1} \neq S_n
                        \quad \text{ and } \quad
                        T_M = S_n
                        \quad \text{ and } \quad
                        \sum_{i=M+1}^N T_i = 0
                        \quad \text{ and } \quad
                        T_{N+1} \neq 0
                \end{equation*}
                %
                and define $W_n$ by
                %
                \begin{equation*}
                        W_n = \sum\limits_{i=M}^N G_i
                \end{equation*}
                %
                where $M \neq N$ only when $M-N+1$ events arrive
                simultaneously at time $A_n$. That is, for each $\zeta
                \in \set{U}$ and each $n \in \N$, $W_n$ is the sum of
                all gains from all events that occurred at that arrival.
                Thus, for a given $\zeta \in \set{U}$, $W_n$ (possibly
                negative) is rewarded after $\sum\limits_{i=1}^n S_i$
                time. It is important to assume that $(W_n)$ is a
                sequence of \iid{}\ random variables where $\E(|W_1|) <
                \infty$. Thus, $(W_n)$ is a random process that we call
                the \emph{reward process}. 
        \item Finally, introduce random process $(\phi_N)$ such that
                for each $\zeta \in \set{U}$,
                %
                \begin{equation*}
                        \phi_N \triangleq \sum\limits_{i=1}^N G_i
                \end{equation*}
                %
                and a random process $(G(t): t \in \R_{\geq
                0})$ such that for each $\zeta \in \set{U}$ and each $t
                \in \R_{\geq 0}$,
                %
                \begin{equation*}
                        G(t) 
                        \triangleq \phi_{N(t)}
                        = \sum\limits_{i=1}^{ N(t) } G_i
                \end{equation*}
                %
                In other words, for any $\zeta \in \set{U}$, $\phi_N$
                represents the total gain rewarded up to the $N\th$
                encounter and $G(t)$ represents the total gain rewarded
                by time $t$. We call $(\phi_N)$ the \emph{cumulative
                gain process}. The random process $(G(t) : t \in
                \R_{\geq 0})$ is called a \emph{(Markov) renewal-reward
                process}. 
\end{itemize}
%
As before, \longref{eq:generic_renewal_limits} holds. However,
\citet{JohnsMiller63} also show that
%
\begin{equation}
        \aslim\limits_{t \to \infty} \frac{ G(t) }{t} = 
        \lim\limits_{t \to \infty} \frac{ \E( G(t) ) }{t} = 
        \aslim\limits_{N \to \infty} \frac{ \phi_N }{ B_N } =
        \frac{ \E(W_1) }{ \E(S_1) }
        \label{eq:generic_renewal_reward_limits}
\end{equation}
%
In fact, \citeauthor{JohnsMiller63} also show that if there exists some
$M \in \N$ such that $\E( 1/A_M ) < \infty$ then
%
\begin{equation}
        \lim\limits_{N \to \infty} 
        \E\left( \frac{ \phi_N }{ B_N } \right) =
        \frac{ \E(W_1) }{ \E(S_1) }
        \label{eq:generic_renewal_reward_limits_special}
\end{equation}
%
These are useful results (that depend on $\E(|W_1|) < \infty$).

\paragraph{The Gain Process:} Take the renewal-reward process and all
related processes given above. It is clear that given a base Poisson
counting process, the gain process $(G_N)$ completely specifies the
renewal-reward process. This is the meaning of associating a gain
process with a Poisson process without the discussion of a
renewal-reward process. Therefore, if a gain process is given with a
Poisson process, a Markov renewal-reward process is implicitly being
constructed as well.

\subsection{Renewal-Reward-Cost Processes}

This definition is simply a modification of the notation in a
renewal-reward process. In fact, this is not a standard definition; it
is our own construction. However, it is completely redundant as it is
not practically any different than a renewal-reward process. Take an
experiment modeled by probability space $(\set{U},\Sigma,\Pr)$. Let
$(N(t): t \in \R_{\geq 0})$ be a (Markov) renewal process on this space
with the associated arrival process $(A_n)$, interarrival process
$(S_n)$, encounter process $(B_N)$, and interevent process $(T_N)$.
Additionally, assume that $(G(t): t \in \R_{\geq 0})$ is a Markov
renewal-reward process associated with $(N(t): t \in \R_{\geq 0})$ with
the associated gain process $(G_N)$ and reward process $(W_n)$. However,
introduce three more random processes.
%
\begin{itemize}
        \item Let $(C_N)$ be a sequence where $C_N: \set{U} \mapsto
                \extR$ is a random variable representing some
                \emph{cost} of \emph{event} $N$ for each $N \in \N$. In
                other words, for a given $\zeta \in \set{U}$, $C_N$
                (possibly negative) is paid after $\sum\limits_{i=1}^N
                T_i$ time. We call the random process $(C_N)$ the
                \emph{cost process}. The process $(L_n)$, which we
                introduce next, will have assumptions that also
                constrain this process.
        \item Let $(L_n)$ be a sequence where $L_n: \set{U} \mapsto
                \extR$ is a random variable representing the \emph{total
                cost} at \emph{arrival} $n$ for each $n \in \N$. In
                other words, note that for each $\zeta \in \set{U}$, for
                each $n \in \N$, there exists an $M,N \in \N$ that
                %
                \begin{equation*}
                        T_{M-1} \neq S_n
                        \quad \text{ and } \quad
                        T_M = S_n
                        \quad \text{ and } \quad
                        \sum_{i=M+1}^N T_i = 0
                        \quad \text{ and } \quad
                        T_{N+1} \neq 0
                \end{equation*}
                %
                and define $L_n$ by
                %
                \begin{equation*}
                        L_n = \sum\limits_{i=M}^N C_i
                \end{equation*}
                %
                where $M \neq N$ only when $M-N+1$ events arrive
                simultaneously at time $A_n$. That is, for each $\zeta
                \in \set{U}$ and each $n \in \N$, $L_n$ is the sum of
                all costs from all events that occurred at that arrival.
                Thus, for a given $\zeta \in \set{U}$, $L_n$ (possibly
                negative) is lost after $\sum\limits_{i=1}^n S_i$
                time. It is important to assume that $(L_n)$ is a
                sequence of \iid{}\ random variables where $\E(|L_1|) <
                \infty$. Thus, $(L_n)$ is a random process that we call
                the \emph{loss process}. 
        \item Finally, introduce random process $(C(t): t \in \R_{\geq
                0})$ such that for each $\zeta \in \set{U}$,
                %
                \begin{equation*}
                        \theta_N \triangleq \sum\limits_{i=1}^N G_i
                \end{equation*}
                %
                and a random process $(C(t): t \in \R_{\geq
                0})$ such that for each $\zeta \in \set{U}$ and each $t
                \in \R_{\geq 0}$,
                %
                \begin{equation*}
                        C(t) 
                        \triangleq \theta_{N(t)}
                        = \sum\limits_{i=1}^{ N(t) } C_i
                \end{equation*}
                %
                In other words, for any $\zeta \in \set{U}$, $\theta_N$
                represents the total cost paid up to the $N\th$
                encounter and $C(t)$ represents the total cost paid by
                time $t$. We call $(\theta_N)$ the \emph{cumulative cost
                process}. The random process $(C(t) : t \in \R_{\geq
                0})$ is called a \emph{(Markov) renewal-reward-cost
                process}.
\end{itemize}
%
Of course, \longrefs{eq:generic_renewal_limits} and
\shortref{eq:generic_renewal_reward_limits} still hold. However,
\citet{JohnsMiller63} also show that
%
\begin{equation}
        \aslim\limits_{t \to \infty} \frac{ C(t) }{t} = 
        \lim\limits_{t \to \infty} \frac{ \E( C(t) ) }{t} = 
        \aslim\limits_{N \to \infty} \frac{ \theta_N }{ B_N } =
        \frac{ \E(C_1) }{ \E(S_1) }
        \label{eq:generic_renewal_reward_cost_limits}
\end{equation}
%
In fact, \citeauthor{JohnsMiller63} also show that if there exists some
$M \in \N$ such that $\E( 1/A_M ) < \infty$ then
%
\begin{equation}
        \lim\limits_{N \to \infty} 
        \E\left( \frac{ \theta_N }{ B_N } \right) =
        \frac{ \E(C_1) }{ \E(S_1) }
        \label{eq:generic_renewal_reward_cost_limits_special}
\end{equation}
%
These are useful results (that depend on $\E(|C_1|) < \infty$).

\paragraph{Relaxation of Constraints:} Take the same processes as above;
however, now assume that
%
\begin{itemize}
        \item it need not be that $\E(|W_1|) < \infty$
        \item it need not be that $(W_N)$ is a sequence of
                \iid{}\ random variables
        \item it need not be that $\E(|L_1|) < \infty$
        \item it need not be that $(L_N)$ is a sequence of
                \iid{}\ random variables
\end{itemize}
%
However, assume that $(W_N - L_N)$ is an \iid{}\ sequence of random
variables where $\E(|W_1 - L_1|) < \infty$. In this case, $(G(t)-C(t): t
\in \R_{\geq 0})$ is a Markov renewal-reward process. Therefore, 
%
\begin{equation}
        \aslim\limits_{t \to \infty} \frac{ G(t) - C(t) }{t} =
        \lim\limits_{t \to \infty} \frac{ \E( G(t) - C(t) ) }{t} =
        \aslim\limits_{N \to \infty} \frac{ W_N - L_N }{ B_N } =
        \frac{ \E(W_1) - \E(L_1) }{ \E(S_1) }
        \label{eq:generic_renewal_reward_gaincost_limits}
\end{equation}
%
and if there exists some $M \in \N$ such that $\E( 1/A_M ) < \infty$
then
%
\begin{equation}
        \lim\limits_{N \to \infty} 
        \E\left( \frac{ W_N - L_N }{ B_N } \right) =
        \frac{ \E(W_1) - \E(L_1) }{ \E(S_1) }
        \label{eq:generic_renewal_reward_gaincost_limits_special}
\end{equation}
%
Of course, if $(C(t): t \in \R_{\geq 0})$ is a Markov
renewal-reward-cost process then $(G(t) - C(t): t \in \R_{\geq 0})$ is
necessarily a renewal-reward process and
\longrefs{eq:generic_renewal_reward_gaincost_limits} and
\shortref{eq:generic_renewal_reward_gaincost_limits_special} will
certainly hold.

\subsection{Special Case: Independent Gain Processes}
\label{app:math_markov_independent_gain}

Take an experiment modeled by probability space $(\set{U},\Sigma,\Pr)$.
Let $(N(t): t \in \R_{\geq 0})$ be a (Markov) renewal process on this
space with the associated arrival process $(A_n)$, interarrival process
$(S_n)$, encounter process $(B_N)$, and interevent process $(T_N)$.
Additionally, take $(G(t): t \in \R_{\geq 0})$ to be a Markov
renewal-reward process associated with $(N(t): t \in \R_{\geq 0})$ where
$(G_N)$ and $(\phi_N)$ are the gain and cumulative gain processes
respectively. However, also assume that
%
\begin{itemize}
        \item $(G_N)$ is an \iid{}\ sequence of random variables 
        \item $\E(|G_1|) < \infty$ 
        \item assume that $(T_N)$ is an \iid{}\ sequence of random
                variables 
\end{itemize}
%
Note that all of these are true if $\Pr(T_N=0)=0$ (\ie, simultaneous
encounters occur with probability zero). It is clear that for all $N \in
\N$,
%
\begin{equation*}
        \E( B_N )
        =
        \E\left(
        \sum\limits_{i=1}^N T_i
        \right)
        = \sum\limits_{i=1}^N \E( T_i )
        = \sum\limits_{i=1}^N \E( T_1 )
        = N \E( T_1 )
\end{equation*}
%
Therefore, if $\E(T_1) > 0$ then
%
\begin{equation*}
        \frac{ \E(N) }{ \E( B_N ) }
        = \frac{ N }{ N \E( T_1 ) }
        = \frac{ 1 }{ \E( T_1 ) }
\end{equation*}
%
for all $N \in \N$. These examples motivate two interesting cases.
%
\begin{description}
        \item\emph{Expectation of Cumulative Gain Processes:} Clearly,
                %
                \begin{equation*}
                        \E( \phi_N )
                        = \E\left( \sum\limits_{i=1}^N G_i \right)\\
                        = \sum\limits_{i=1}^N \E(G_i)\\
                        = \sum\limits_{i=1}^N \E(G_1)\\
                        = N \E(G_1)
                \end{equation*}
                %
                and thus if $\E(T_1)>0$ then
                %
                \begin{equation*}
                        \frac{ \E( \phi_N ) }{ \E( B_N ) }
                        =
                        \frac{ N \E(G_1) }{ N \E(T_1) }
                        =
                        \frac{ \E(G_1) }{ \E(T_1) }
                \end{equation*}
                %
                for all $N \in \N$.
                %
        \item\emph{Expectation of Renewal-Reward Processes:} Now, take
                $t \in \R_{\geq0}$. By
                \longref{eq:expectation_to_condexp},
                %
                \begin{align*}
                        \E( G(t) )
                        &=
                        \E\left( \sum\limits_{i=1}^{ N(t) } G_i \right)
                        =
                        \E\left( \E\left(
                        \sum\limits_{i=1}^{ N(t) } G_i \middle| N(t) 
                        \right) \right)
                \end{align*}
                %
                However, $\range(N(t)) = \W$ (\ie, the range of $N(t)$
                is countable). Thus,
                %
                \begin{align*}
                        \E( G(t) )
                        &=
                        \sum\limits_{N=0}^\infty
                        \Pr( N(t) = N )
                        \E\left(\sum\limits_{i=1}^{ N } G_i \right)\\
                        &=
                        \sum\limits_{N=0}^\infty
                        \Pr( N(t) = N )
                        \sum\limits_{i=1}^{ N } \E(G_i)
                \end{align*}
                %
                Again, $\E(G_N) = \E(G_1)$ for all $N \in \N$, so
                %
                \begin{align*}
                        \E( G(t) )
                        &=
                        \sum\limits_{N=0}^\infty
                        \Pr( N(t) = N )
                        \sum\limits_{i=1}^{ N } \E(G_1)\\
                        &=
                        \E(G_1) \sum\limits_{N=0}^\infty
                        \Pr( N(t) = N )
                        \sum\limits_{i=1}^{ N } 1\\
                        &= 
                        \E(G_1) 
                        \sum\limits_{N=0}^\infty \Pr( N(t) = N ) N
                \end{align*}
                %
                However, by definition of $\E( N(t) )$,
                %
                \begin{align*}
                        \E( G(t) ) = \E( N(t) ) \E( G_1 )
                \end{align*}
                %
                Since $t$ was chosen arbitrarily, this holds for all $t
                \in \R_{\geq0}$. If $t \in \R_{>0}$ then
                %
                \begin{align*}
                        \frac{ \E(G(t)) }{ t }
                        =
                        \frac{ \E(N(t)) }{ t } \E( G_1 )
                \end{align*}
                %
                Thus, a great deal can be said about a Poisson
                renewal-reward process given $\E(G_1)$. 
\end{description}
%
In other words, for all $N \in \N$ and $t \in \R_{\geq0}$,
%
\begin{equation*}
        \E(\phi_N) 
        =
        \E(G(t)|N(t)=N)
\end{equation*}
%
which is an intuitive result. Recall that by definition, for all $t \in
\R_{\geq0}$ and all $\zeta \in \set{U}$,
%
\begin{equation*}
        G(t) = \phi_{N(t)}
\end{equation*}
%
Similarly, with an abuse of notation,
%
\begin{equation*}
        \phi_N = ( G(t) | N(t) = N )
\end{equation*}
%
for all $N \in \N$ and $\zeta \in \set{U}$. 

\paragraph{Renewal-Reward-Cost Processes:} Take the processes defined
above. Now, assume that $(C(t): t \in \R_{\geq 0})$ is a Markov
renewal-reward-cost process associated with $(N(t): t \in \R_{\geq 0})$
with the associated cost process $(C_N)$ and cumulative cost process
$(\theta_N)$. However, 
%
\begin{itemize}
        \item $(C_N)$ is an \iid{}\ sequence of random variables 
        \item $\E(|C_1|) < \infty$ 
\end{itemize}
%
In this case, for all $N \in \N$,
%
\begin{equation*}
        \E( \theta_N ) = N \E( C_1 )
        \quad \text{ and } \quad
        \frac{\E( \theta_N )}{\E( B_N )} = \frac{\E(C_1)}{\E(T_1)}
\end{equation*}
%
where the latter is true if $\E(T_1)>0$. Additionally, for all $t \in
\R_{\geq0}$,
%
\begin{equation*}
        \E( C(t) ) = \E( N(t) ) \E( C_1 )
        \quad \text{ and } \quad
        \frac{ \E(C(t)) }{ t } = \frac{ \E(N(t)) }{ t } \E( C_1 )
\end{equation*}
%
where the latter is true if $t \neq 0$. Of course,
%
\begin{equation}
        \E( \phi_N - \theta_N ) = N ( \E(G_1) - \E( C_1 ) )
        \label{eq:expected_cumulative_markov_gain}
\end{equation}
%
and
%
\begin{equation}
        \frac{\E( \phi_N - \theta_N )}{\E( B_N )} 
        = \frac{\E(G_1) - \E(C_1)}{\E(T_1)}
        \label{eq:expected_cumulative_markov_gain_rate}
\end{equation}
%
where the latter is true if $\E(T_1)>0$. Additionally, for all $t \in
\R_{\geq0}$,
%
\begin{equation}
        \E( G(t) - C(t) ) = \E( N(t) ) ( \E(G_1) - \E( C_1 ) )
        \label{eq:expected_markov_netreward}
\end{equation}
%
and
%
\begin{equation}
        \frac{ \E(G(t)) - \E(C(t)) }{ t } 
        = \frac{ \E(N(t)) }{ t } ( \E(G_1) - \E( C_1 ) )
        \label{eq:expected_markov_netreward_rate}
\end{equation}
%
In fact, even if $(G_N)$ and $(C_N)$ are not \iid{}\ sequences of finite
expectation random variables,
\longrefs{eq:expected_cumulative_markov_gain},
\shortref{eq:expected_cumulative_markov_gain_rate},
\shortref{eq:expected_markov_netreward}, and
\shortref{eq:expected_markov_netreward_rate} will be true provided that
$(G_N-C_N)$ is an \iid{}\ sequence of random variables with
$\E(|G_N-C_N|) < \infty$.  In other words, for all $N \in \N$ and $t \in
\R_{\geq0}$,
%
\begin{equation*}
        \E(\theta_N)
        =
        \E(C(t)|N(t)=N)
        \quad \text{ and } \quad
        \E(\phi_N - \theta_N) 
        =
        \E(G(t) - C(t)|N(t)=N)
\end{equation*}
%
which are intuitive results. Recall that by definition, for all $t \in
\R_{\geq0}$ and all $\zeta \in \set{U}$,
%
\begin{equation*}
        C(t) = \theta_{N(t)}
        \quad \text{ and } \quad
        G(t) - C(t) = \phi_{N(t)} - \theta_{N(t)}
\end{equation*}
%
Similarly, with an abuse of notation,
%
\begin{equation*}
        \theta_N = ( C(t) | N(t) = N )
        \quad \text{ and } \quad
        \phi_N - \theta_N = ( G(t) - C(t) | N(t) = N )
\end{equation*}
%
for all $N \in \N$ and $\zeta \in \set{U}$. 

\section{Poisson Counting Processes}

Take an experiment modeled by probability space $(\set{U},\Sigma,\Pr)$.
Let $(N(t): t \in \R_{\geq 0})$ be a counting process on this space with
the associated arrival process $(A_n)$, interarrival process $(S_n)$,
encounter process $(B_N)$, and interevent process $(T_N)$. Recall that
for a counting process, for any $t_a,t_b \in \R_{\geq 0}$ such that $t_b
\geq t_a$, we define the \emph{increment of the process in $[t_a,t_b)$}
as the random variable $I(t_b,t_a): \set{U} \mapsto \extR$ by
%
\begin{equation*}
        I(t_b,t_a) \triangleq N(t_b) - N(t_a)
\end{equation*}
%
for every $\zeta \in \set{U}$ (\ie, $I(t_b,t_a)(\zeta) \triangleq
N(t_b)(\zeta) - N(t_a)(\zeta)$). Assume that the following are true.
%
\begin{enumerate}[(i)]
        \item $\{ N(0) = 0 \}$ with probability one.
        \item For any $n \in \N$ and $n$-tuple $(t_1,t_2,\dots,t_n)$
                such that $t_i \in \R_{\geq 0}$ for all $i \in
                \{1,2,\dots,n\}$ and $t_1 < t_2 < \cdots < t_n$, 
                %
                \begin{equation*}
                        (I(t_2,t_1),I(t_3,t_2),\dots,I(t_n,t_{n-1}))
                \end{equation*}
                %
                is a family of mutually independent random variables.
                A counting process with this property is said to have
                \emph{independent increments}.
                \label{item:poisson_indep_increments}
        \item The parameter $\lambda \in \R_{\geq 0}$ is such that for
                any $t_a,t_b \in \R_{\geq 0}$ with $t_b > t_a$,
                %
                \begin{align*}
                        f_{I(t_b,t_a)}(x)
                        &=
                        \begin{cases}
                                \exp( -\lambda( t_b - t_a ) )
                                \frac{ (\lambda( t_b - t_a ))^x }{x!}
                                &\text{if } x \in \W\\
                                0
                                &\text{otherwise}
                        \end{cases}\\
                        &=
                        \sum\limits_{k=0}^\infty
                        \exp( -\lambda( t_b - t_a ) )
                        \frac{ (\lambda( t_b - t_a ))^k }{k!}
                        \delta(x-k)
                \end{align*}
                %
                (\ie, $I(t_b,t_a)$ is Poisson distributed with parameter
                $\lambda(t_b - t_a)$). Additionally, note that all
                intervals with the same length are identically
                distributed. This property is known as having
                \emph{identically distributed increments}. Thus,
                together with property
                (\shortref{item:poisson_indep_increments}), $(N(t): t
                \in \R_{\geq 0})$ is said to have
                \emph{\iid{}\ increments}.
\end{enumerate}
%
In this case, $(N(t): t \in \R_{\geq 0})$ is called a \emph{(homogenous)
Poisson process} or a \emph{(homogenous) Poisson counting process}, and
$\lambda$ is called the \emph{rate} or \emph{intensity} of the process.
Of course, any Poisson process is a counting process, and so any Markov
renewal process can be built with a Poisson process at its base.

\subsection{Alternate Formulation of Poisson Process}
\label{app:alternate_formulation_poisson_process}

The structure of this formulation is based on the one given by
\citet{Viniotis98}; however, this is a standard interpretation of the
Poisson process. Take an experiment modeled by probability space
$(\set{U},\Sigma,\Pr)$. Take the desired Poisson process parameter
$\lambda \in \R_{>0}$ and a time $t \in \R_{>0}$ corresponding to some
time interval $[0,t)$. For any $n \in \N$, the interval $[0,t)$ can be
divided into $n$ equal subintervals where we define the $i\th$
subinterval $\set{I}^n_i$ by
%
\begin{equation*}
        \set{I}^n_i
        \triangleq
        \left[ (i-1) \frac{t}{n}, i \frac{t}{n} \right)
\end{equation*}
%
for all $i \in \{1,2,\dots,n\}$. Now, for all $n \in \{1,2,\dots,n\}$,
let $(X^n_i)_{i=1}^n$ be an \iid{}\ family of Bernoulli random variables
with parameter $p_n$ defined by
%
\begin{equation*}
        p_n \triangleq \frac{ \lambda t }{ n }
\end{equation*}
%
Thus, for all $n \in \N$, $X^n_i$ can be viewed as a Bernoulli trial
(\eg, a weighted coin toss) performed during interval $\set{I}^n_i$ for
all $i \in \{1,2,\dots,n\}$. If an outcome of $1$ on a Bernoulli trial
is considered a success then the probability of a success $p_n$
decreases as the number of trials $n$ increases. Next, define a new
random variable $N_n(t): \set{U} \mapsto \extR$ by
%
\begin{equation*}
        N_n(t) \triangleq \sum\limits_{i=1}^n X_i
\end{equation*}
%
for all $n \in \N$ and $\zeta \in \set{U}$. Thus, $N_n$ is a count of
the $n \in \N$ Bernoulli trials in interval $[0,t)$ that resulted in a
success.  Finally, define random variable $N(t): \set{U} \mapsto \extR$
by
%
\begin{equation*}
        N(t) \triangleq \lim\limits_{n \to \infty} N_n(t)
\end{equation*}
%
for all $\zeta \in \set{U}$. That is, $N(t)$ roughly represents the
number of successful trials (\eg, coin tosses that result in
\emph{heads}) in interval $[0,t)$ given that a trial with nearly zero
chance of success occurred at every $t_0 \in [0,t)$ (\ie, an uncountable
number of trials). The resulting random process $(N(t): t \in \R_{\geq
0})$ is a Poisson process. It is important to note that by construction,
each interval $[0,t)$ can be viewed as having far more failed trials
than successful trials. 

\subsection{Poisson Process Properties}

There are a surprising number of interesting properties that result from
the relatively few restrictions on the Poisson process. For all of the
following, take an experiment modeled by probability space
$(\set{U},\Sigma,\Pr)$, and let $(N(t): t \in \R_{\geq 0})$ be a Poisson
process on this space with rate parameter $\lambda \in \R_{>0}$ and the
associated arrival process $(A_n)$, interarrival process $(S_n)$,
encounter process $(B_N)$, interevent process $(T_N)$, and increment
variables $\{I(t_b,t_a) : t_a,t_b \in \R_{\geq0} \text{ with } t_b \geq
t_a\}$.

\paragraph{Statistics of Increments:} For any $t_a,t_b \in \R_{\geq 0}$
with $t_b > t_a$,
%
\begin{align*}
        \E(I(t_b,t_a)) = \E(N(t_b)-N(t_a)) = \lambda (t_b - t_a)
\end{align*}
%
and
%
\begin{equation*}
        \var(I(t_b,t_a)) = \var(N(t_b)-N(t_a)) = \lambda (t_b - t_a)
\end{equation*}
%
In particular, take some $t \in \R_{ \geq 0 }$ and recall that $\Pr(
N(0)=0 ) = 1$. Thus,
%
\begin{equation*}
        \E( N(t) ) = \E( N(t) - N(0) ) = \E( I(t,0) ) = \lambda t
\end{equation*}
%
and, similarly, $\var( N(t) ) = \lambda t$.

\paragraph{Markov Property:} As a consequence of the independent
increments property of a Poisson process, all Poisson processes have the
Markov property.

\paragraph{Exponentially Distributed Interarrival Times:} The sequence
$(S_n)$ is an \iid{}\ sequence of random variables where
%
\begin{equation*}
        f_{S_n}(x)
        =
        \begin{cases}
                \lambda \exp( -\lambda x ) &\text{if } x \geq 0\\
                0 &\text{if } x < 0
        \end{cases}
\end{equation*}
%
for all $n \in \N$. That is, $(S_n)$ is an \iid{}\ sequence of
exponentially distributed random variables with parameter $\lambda$.
Therefore,
%
\begin{equation*}
        \E( S_n ) = \frac{1}{\lambda}
        \quad \text{ and } \quad 
        \var(S_n) = \frac{1}{\lambda^2}
\end{equation*}
%
for all $n \in \N$. Of course, the memoryless property will also hold.
We will discuss this below.

\paragraph{Erlang Distribution of Arrival Times:} Since $(S_n)$ is an
\iid{}\ sequence of exponentially distributed random variables then it
can be shown that for all $n \in \N$,
%
\begin{equation*}
        f_{A_n}(x)
        =
        \begin{cases}
                \frac{\lambda(\lambda x)^{n-1}\exp(-\lambda x)}{(n-1)!}
                &\text{if } x \geq 0\\
                0 &\text{if } x < 0
        \end{cases}
\end{equation*}
%
That is, for all $n \in \N$, the time of the $n\th$ arrival is
Erlang-$n$ distributed with parameter $\lambda$. Therefore,
%
\begin{equation*}
        \E( A_n ) = \frac{n}{\lambda}
        \quad \text{ and } \quad 
        \var( A_n ) = \frac{n}{\lambda^2}
\end{equation*}
%
for all $n \in \N$.

\paragraph{Uniformly Distributed Conditional Arrival Times:} Take some
$M \in \N$ and times $t_a,t_b \in \R_{\geq 0}$ such that $t_b > t_a$.
Assume that it is certain that $M$ arrivals have occurred in the time
interval $[t_a,t_b]$. That is, define the event set $\set{E}_M$ as
%
\begin{equation*}
        \set{E}_M 
        \triangleq
        \{ N(t_b) - N(t_a) = M \}
\end{equation*}
%
and generate a conditional probability space $( \set{E}_M,
\Sigma_{\set{E}_M}, \Pr|_{\set{E}_M})$. Take $B: \set{U} \mapsto \extR$
to be a random variable representing the arrival time associated with
one of those $M$ arrivals. Random variable $B$ will have density
function
%
\begin{equation*}
        f_B(x)
        =
        \begin{cases}
                \frac{1}{t_b-t_a} &\text{if } x \in [t_a,t_b]\\
                0 &\text{otherwise}
        \end{cases}
\end{equation*}
%
That is, $B$ will be uniformly distributed on $[t_a,t_b]$. In other
words, given that $M$ Poisson arrivals are certain in a specific time
interval, it should not be expected that those arrival times should
cluster in any particular subset of the interval; the arrival times will
be entirely random. This is an interesting result considering that the
arrival times in the unconditioned probability space are Erlang
distributed.

\paragraph{Interarrivals Have Memoryless Property:} Since $(S_n)$ is an
\iid{}\ sequence of exponentially distributed random variables then for
any $n \in \N$ and $a,b \in \R_{>0}$,
%
\begin{equation*}
        \Pr(S_n > a + b | S_n > b) = \Pr(S_n > a)
\end{equation*}
%
In other words, the interarrival times have the memoryless property
because they are exponentially distributed. Thus, if a holding time is
known to be at least $10$ seconds, the probability that it will be at
least $13$ seconds is equal to the probability that an interarrival time
that is at least $0$ seconds will be at least $3$ seconds. Thus, the
history of a particular holding interval has no impact on the future of
that holding interval.

\paragraph{Poisson Arrivals See Time Averages:} Assume that $(X(t) : t
\in \R_{\geq 0})$ is an additional random process defined on the same
probability space. However, for any time, assume that the future Poisson
jumps do not depend on past values of the $( X(t) : t \in \R_{\geq 0})$
process. It is always the case that,
%
\begin{equation*}
        \aslim\limits_{n \to \infty} \frac{1}{n} \sum\limits_{i=1}^n
        X(A_i)
        =
        \aslim\limits_{T \to \infty} \frac{1}{T} \int_0^T X(s) \total s
\end{equation*}
%
Consider a particular $\zeta \in \set{U}$. For this outcome, $X(t)$ is a
function of time. This property states that with probability one the
outcome $\zeta$ will be such that if $X(t)$ is averaged at each of the
instants in $(A_n)$, the limiting result will be equal to the limiting
result of the time average of $X(t)$ (where \emph{time average} is the
integral in the above expression). Not only is this an interesting
result that follows from a Poisson process, but it is \emph{only} true
with a Poisson process. Therefore, if some other process has this
property, it must be Poisson.

\paragraph{Orderliness and Interevent Properties:} One key property of a
Poisson process is the \emph{orderliness property}. Given that a process
has independent increments, this property reduces to the
\emph{regularity} property discussed by \citet{CoxLewis70}, which states
that
%
\begin{equation*}
        \lim\limits_{h \to {0+}} 
        \left| \frac{ \Pr( I(t+h,t) > 1 ) }{h} \right| = 0
\end{equation*}
%
Among other things, this implies that simultaneous encounters occur with
probability zero. This roughly means that encounters should not cluster
at one arrival. It is important to note that simultaneous encounters
still can occur in an experiment even if that outcome is in an event set
of probability zero; however, they will not occur with much regularity.
This implies that
%
\begin{equation*}
        \Pr( T_N = 0 ) = 0
\end{equation*}
%
for all $N \in \N$. In fact,
%
\begin{equation*}
        \Pr( A_n = B_n ) = 1
        \quad \text{ and } \quad
        \Pr( T_n = S_n ) = 1
\end{equation*}
%
for all $n \in \N$. Thus, while we were careful when defining a counting
process to differentiate between the sequences $(T_N)$ and $(S_n)$ and
between the sequences $(B_N)$ and $(A_n)$, we will consider them to be
probabilistically equivalent. In other words, 
%
\begin{itemize}
        \item any results about the probabilistic distributions of the
                random variables in the sequence $(S_n)$ will also apply
                to the random variables in the sequence $(T_N)$
        \item any results about the probabilistic distributions of the
                random variables in the sequence $(A_n)$ will also apply
                to the random variables in the sequence $(B_N)$
\end{itemize}
%
For example, notice that for all $N \in \N$,
%
\begin{equation*}
        \frac{ 1 }{ \E(T_N) }
        =
        \frac{ 1 }{ \E(S_N) }
        =
        \frac{ 1 }{ \frac{1}{\lambda} }
        =
        \lambda
\end{equation*}
%
This is because $(T_N)$ must be an \iid{}\ sequence of random variables
where $\E(T_1)=\E(S_1)=1/\lambda$. These facts will be used extensively
in \longref{app:math_renewal_rates_rewards}.

\subsection{Renewal Processes, Rates, and Expected Rewards}
\label{app:math_renewal_rates_rewards}

Take an experiment modeled by probability space $(\set{U},\Sigma,\Pr)$,
and let $(N(t): t \in \R_{\geq 0})$ be a Poisson process on this space
with rate parameter $\lambda \in \R_{>0}$ and the associated arrival
process $(A_n)$, interarrival process $(S_n)$, encounter process
$(B_N)$, interevent process $(T_N)$, and increment variables
$\{I(t_b,t_a) : t_a,t_b \in \R_{\geq0} \text{ with } t_b \geq t_a\}$.
The following are clearly the case.
%
\begin{itemize}
        \item The process $(N(t): t \in \R_{\geq 0})$ is a counting
                process by definition.
        \item The process $(N(t): t \in \R_{\geq 0})$ has the Markov
                property.
        \item The sequence $(S_n)$ contains \iid{}\ random variables
                where $0 < \E(S_n) < \infty$ for all $n \in \N$ (\ie,
                $\E(S_n) = 1/\lambda$ where $\lambda > 0$).
\end{itemize}
%
Therefore, $(N(t): t \in \R_{\geq 0})$ is a Markov renewal process. In
fact, recall that
%
\begin{equation*}
        \frac{ \E(N(t)) }{t} = \lambda
\end{equation*}
%
for all $t \in \R_{>0}$. However, since $\E(S_1) = 1/\lambda$, this
means that
%
\begin{equation*}
        \frac{ \E(N(t)) }{t} = \frac{1}{\E(S_1)}
\end{equation*}
%
for all $t \in \R_{>0}$. Of course, this agrees with
\longref{eq:generic_renewal_limits} even without limits. In fact, as
with all Markov renewal processes, $\aslim_{t \to \infty} N(t) =
\infty$, which is not surprising since $\E(N(t))=\lambda t$ for all $t
\in \R_{\geq0}$.

\paragraph{Renewal-Reward Processes:} Because any Poisson process is a
Markov renewal process, any Poisson process can be used as the base for
a Markov renewal-reward process or a Markov renewal-reward-cost process.
This also means that all results on Markov renewal processes also hold
for Poisson processes. A Markov renewal-reward process built on a
Poisson process will be called a \emph{Poisson renewal-reward process}.
Similarly, a Markov renewal-reward-cost process built on a Poisson
process will be called a \emph{Poisson renewal-reward-cost process}.

\paragraph{Special Limiting Case:} Take the Poisson process and related
processes as defined above. Recall that for any $n \in \N$,
%
\begin{equation*}
        \E\left( \frac{1}{A_n} \right)
        =
        \int_{-\infty}^{\infty}
        \frac{1}{x}
        f_{A_n}(x)
        \total x
        =
        \int_{0}^{\infty}
        \frac{1}{x}
        \frac{\lambda(\lambda x)^{n-1}\exp(-\lambda x)}{(n-1)!}
        \total x
\end{equation*}
%
Now, take $n=2$. Thus,
%
\begin{align*}
        \E\left( \frac{1}{A_2} \right)
        &=
        \int_{-\infty}^{\infty}
        \frac{1}{x}
        f_{A_2}(x)
        \total x\\
        &=
        \int_{0}^{\infty}
        \frac{1}{x}
        \lambda(\lambda x)
        \exp(-\lambda x)
        \total x
        =
        \int_{0}^{\infty}
        \lambda^2
        \exp(-\lambda x)
        \total x
        =
        \lambda
\end{align*}
%
Since $\lambda < \infty$, there exists some $n \in \N$ such that $\E(
1/A_n ) < \infty$. Therefore,
\longrefs{eq:generic_renewal_limits_special},
\shortref{eq:generic_renewal_reward_limits_special},
\shortref{eq:generic_renewal_reward_cost_limits_special}, and
\shortref{eq:generic_renewal_reward_gaincost_limits_special} are all
valid where applicable.

\paragraph{Orderliness Consequences:} Use the Poisson process $(N(t):t
\in \R_{\geq0})$ defined above as the base counting process for the
following. Take $(G(t): t \in \R_{\geq0})$ to be a Markov renewal-reward
process with $(G_N)$, $(W_n)$, and $(\phi_N)$ as the corresponding gain,
reward, and cumulative gain processes respectively. Recall that for all
$N \in \N$ and all $t \in \R_{\geq0}$
%
\begin{equation*}
        \E( N ) = N
        \quad \text{ and } \quad
        \E( N(t) ) = \lambda t
\end{equation*}
%
This is the motivation the important results here. By the orderliness of
the Poisson counting process, for all $N \in \N$,
%
\begin{equation*}
        \Pr( \{S_N = T_N\} ) = 1
\end{equation*}
%
Therefore,
%
\begin{equation*}
        \E(S_N)=\E(T_N)
\end{equation*}
%
However, since $(S_n)$ is an \iid{}\ sequence of random variables with
$\E(S_1)=1/\lambda$ then $(T_N)$ is an \iid{}\ sequence of random
variables with $\E(T_1)=1/\lambda$. In other words, the orderliness of
the Poisson process allows $T_N$ to be substituted for $S_N$ for all $N
\in \N$. Note that this implies
%
\begin{equation*}
        \E( N(t) ) 
        = \lambda t 
        = \frac{ t }{ \E(S_1) } 
        = \frac{ t }{ \E(T_1) }
\end{equation*}
%
for all $t \in \R_{\geq0}$. Also, $B_N$ can be substituted for $A_N$ for
all $N \in \N$. However, note that by the orderliness of the
Poisson counting process, for all $N \in \N$,
%
\begin{equation*}
        \Pr( \{W_N = G_N\} ) = 1
\end{equation*}
%
Therefore,
%
\begin{equation*}
        \E(W_N)=\E(G_N)
\end{equation*}
%
for all $N \in \N$. However, recall that $(W_n)$ is an \iid{}\ sequence
of random variables such that $\E(|W_1|) < \infty$ (\ie, it has
\emph{finite expectation}). Therefore, $(G_N)$ is also an \iid{}\
sequence of random variables with $\E(|G_1|) < \infty$. In this case,
all of the results from \longref{app:math_markov_independent_gain} hold.
In particular, for all $N \in \N$ and $t \in \R_{\geq0}$,
%
\begin{equation*}
        \E( \phi_N ) = N \E( G_1 )
\end{equation*}
%
and
%
\begin{equation*}
        \E( G(t) ) 
        = \E(G_1) \E( N(t) ) 
        = \lambda t \E(G_1)
        = t \frac{ \E(G_1) }{ \E(S_1) }
        = t \frac{ \E(G_1) }{ \E(T_1) }
\end{equation*}
%
Thus, a great deal can be said about a Poisson renewal-reward process
given $\E(G_1)$. Additionally, take $(C(t): t \in \R_{\geq0})$ to be a
Markov renewal-reward-cost process with $(C_N)$, $(L_n)$, and
$(\theta_N)$ as the corresponding cost, loss, and cumulative cost
processes respectively. Again, due to orderliness, $\E(C_N)=\E(L_N)$ for
all $N \in \N$ and $(C_N)$ is an \iid{}\ sequence of random variables
with $\E(|C_N|) < \infty$. By the results in
\longref{app:math_markov_independent_gain}, for all $N \in \N$ and $t
\in \R_{\geq0}$,
%
\begin{equation*}
        \E( \theta_N ) = N \E( C_1 )
\end{equation*}
%
and
%
\begin{equation*}
        \E( C(t) ) 
        = \E(C_1) \E( N(t) ) 
        = \lambda t \E(C_1)
        = t \frac{ \E(C_1) }{ \E(S_1) }
        = t \frac{ \E(C_1) }{ \E(T_1) }
\end{equation*}
%
In fact, 
%
\begin{equation*}
        \E( \phi_N - \theta_N ) = N ( \E(G_1) - \E( C_1 ) )
\end{equation*}
%
and
%
\begin{align*}
        \E(G(t) - C(t))
        &= \E( N(t) ) \E(G_1 - C_1)
        = \lambda t ( \E(G_1) - \E(C_1) )\\
        &= t \frac{ \E(G_1) - \E(C_1) }{ \E(S_1) }
        = t \frac{ \E(G_1) - \E(C_1) }{ \E(T_1) }
\end{align*}
%
for all $t \in \R_{\geq0}$. This last identity is true as long as
$(G_N-C_N)$ is an \iid{}\ sequence of random variables with
$\E(|G_N-C_N|) < \infty$; that is, $(G_N)$ and $(C_N)$ need not be
\iid{}\ sequences of random variables with finite expectation.

\paragraph{Ratio of Expectations:} Take the Poisson, renewal-reward, and
renewal-reward-cost processes as defined above. Recall that for this
Poisson process,
%
\begin{equation*}
        \E( T_1 ) = \frac{1}{\lambda}
\end{equation*}
%
and for all $N \in \N$,
%
\begin{equation*}
        \E( B_N ) = \frac{N}{\lambda}
\end{equation*}
%
Thus,
%
\begin{equation*}
        \frac{ N }{ \E(B_N) } 
        = \frac{ \E( N(t) ) }{ t }
        = \lambda
\end{equation*}
%
which, again, agrees with \longref{eq:generic_renewal_limits} even
without limits. This is the motivation for the following results. For
any $N \in \N$, and any $t \in \R_{\geq0}$,
%
\begin{equation*}
        \frac{ \E( \phi_N ) }{ \E( B_N ) } 
        = \frac{ \E( G(t) ) }{ t } 
        = \frac{ \E(G_1) }{ \E( T_1 ) }
        = \lambda \E(G_1)
\end{equation*}
%
and
%
\begin{equation*}
        \frac{ \E( \theta_N ) }{ \E( B_N ) } 
        = \frac{ \E( C(t) ) }{ t } 
        = \frac{ \E(C_1) }{ \E( T_1 ) }
        = \lambda \E(C_1)
\end{equation*}
%
and
%
\begin{equation*}
        \frac{ \E( \phi_N - \theta_N ) }{ \E( B_N ) } 
        = \frac{ \E( G(t) - C(t) ) }{ t } 
        = \frac{ \E(G_1 - C_1) }{ \E( T_1 ) }
        = \lambda ( \E(G_1) - \E(C_1) )
\end{equation*}
%
where the last identity only requires that $(G_N-C_N)$ is an \iid{}\
sequence of random variables with finite expectation. 

\paragraph{Asymptotic Renewal Rates:} Take the Poisson, renewal-reward,
and renewal-reward-cost processes as defined above. By combining all of the
above results, it is clearly the case that for all $Q \in \N$ and $q \in
\R_{\geq0}$,
%
\begin{align*}
        \aslim\limits_{t \to \infty} \frac{ N(t) }{t} 
        &= \lim\limits_{t \to \infty} \frac{ \E( N(t) ) }{t} 
        = \aslim\limits_{N \to \infty} \frac{ N }{ B_N }\\
        &= \lim\limits_{N \to \infty} \E\left( \frac{ N }{ B_N } \right)
        = \frac{ Q }{ \E( B_Q ) }\\
        &= \frac{ \E( N(q) ) }{ q } 
        = \frac{ 1 }{ \E(T_1) }\\
        &= \lambda
\end{align*}
%
It also holds that for all $Q \in \N$ and $q \in \R_{\geq0}$,
%
\begin{align*}
        \aslim\limits_{t \to \infty} \frac{ G(t) }{t} 
        &= \lim\limits_{t \to \infty} \frac{ \E( G(t) ) }{t}
        = \aslim\limits_{N \to \infty} \frac{ \phi_N }{ B_N }\\
        &= \lim\limits_{N \to \infty} 
        \E\left( \frac{ \phi_N }{ B_N } \right)
        = \frac{ \E( \phi_Q ) }{ \E( B_Q ) }\\
        &= \frac{ \E( G(q) ) }{ q }
        = \frac{ \E(G_1) }{ \E(T_1) }\\
        &= \lambda \E(G_1)
\end{align*}
%
and
%
\begin{align*}
        \aslim\limits_{t \to \infty} \frac{ C(t) }{t}
        &= \lim\limits_{t \to \infty} \frac{ \E( C(t) ) }{t}
        = \aslim\limits_{N \to \infty} \frac{ \theta_N }{ B_N }\\
        &= \lim\limits_{N \to \infty} 
        \E\left( \frac{ \theta_N }{ B_N } \right)
        = \frac{ \E( \theta_Q ) }{ \E( B_Q ) }\\
        &= \frac{ \E( C(q) ) }{ q }
        = \frac{ \E(C_1) }{ \E(T_1) }\\
        &= \lambda \E(C_1)
\end{align*}
%
Of course, it is also true that for all $Q \in \N$ and $q \in
\R_{\geq0}$,
%
\begin{align*}
        \aslim\limits_{t \to \infty} \frac{ G(t) - C(t) }{t} 
        &= \lim\limits_{t \to \infty} \frac{ \E( G(t) - C(t) ) }{t}
        =
        \aslim\limits_{N \to \infty} \frac{ \phi_N - \theta_N }{ B_N }\\
        &= \lim\limits_{N \to \infty} 
        \E\left( \frac{ \phi_N - \theta_N }{ B_N } \right)
        = \frac{ \E( \phi_Q ) - \E( \theta_Q ) }{ \E( B_Q ) }\\
        &= \frac{ \E( G(q) ) - \E( C(q) ) }{ q }
        = \frac{ \E(G_1) - \E(C_1) }{ \E(T_1) }\\
        &= \lambda ( \E(G_1) - \E(C_1) )
\end{align*}
%
In fact, this last identity is true even when $(G_N)$ and $(C_N)$ are
not \iid{}\ sequences of finite expectation random variables as long as
$(G_N - C_N)$ is an \iid{}\ sequence of random variables with $\E(|G_1 -
C_1|) < \infty$. The equality of all of these ratios and limits is
convenient when reasoning about the behavior of Poisson processes.

\subsection{Merged Poisson Processes}
\label{app:math_merged_poisson_process}

Take an experiment modeled by probability space $(\set{U},\Sigma,\Pr)$.
Also take $M \in \N$ and a family $( (N_i(t): t \in \R_{\geq
0}))_{i=1}^n$ where $( N_i(t) : t \in \R_{\geq 0})$ is a Poisson process
on this space with rate parameter $\lambda_i \in \R_{>0}$ for each $i
\in \{1,2,\dots,n\}$. Assume that the random processes in the family $(
(N_i(t): t \in \R_{\geq0}) )_{i=1}^n$ are all independent of each other
and let $(N(t): t \in \R_{\geq0})$ be another random process on this
space defined by
%
\begin{equation*}
        N(t) \triangleq \sum\limits_{i=1}^M N_i(t)
\end{equation*}
%
for all $t \in \R_{\geq 0}$ and all $\zeta \in \set{U}$. It can be
shown that $(N(t): t \in \R_{\geq0})$ is also a Poisson process with
rate parameter $\lambda$ such that
%
\begin{equation*}
        \lambda = \sum\limits_{i=1}^M \lambda_i
\end{equation*}
%
The random process $(N(t): t \in \R_{\geq 0})$ is called a \emph{merged
Poisson process}. Now let $(B_N)$ be the encounter process associated
with $(N(t):t \in \R_{\geq 0})$ and let $(B^i_N)$ be the encounter
process associated with $(N_i(t):t \in \R_{\geq 0})$ for all $i \in
\{1,2,\dots,n\}$. Consider the following.
%
\begin{itemize}
        \item An encounter is defined to be a time when a counting
                process increases by exactly one.
        \item For any $i \in \{1,2,\dots,n\}$, an encounter on process
                $(N_i(t):t \in \R_{\geq0})$ will generate an encounter
                on (merged) process $(N(t):t \in \R_{\geq0})$.
        \item Any encounter on $(N(t):t \in \R_{\geq0})$ must be the
                result of an encounter on $(N_i(t):t \in \R_{\geq0})$
                for some $i \in \{1,2,\dots,n\}$.
\end{itemize}
%
Thus, for any $i \in \{1,2,\dots,n\}$ and $N \in \N$, 
%
\begin{equation*}
        \Pr
        \left(
        \bigcup \left\{ \{ B_N = B^i_M \} : M \in \N \right\}
        \right)
        =
        \frac{\lambda_i}{\lambda}
        =
        \frac{\lambda_i}{\sum\limits_{j=1}^n \lambda_j}
\end{equation*}
%
That is, for any $i \in \{1,2,\dots,n\}$ and any $N \in \N$, the
probability that there exists an $M \in \N$ such that $B_N = B^i_M$ is
$\lambda_i / \lambda$. In other words, given that an encounter has
occurred on the merged process, the probability that the encounter was
generated by any particular one of the processes being merged is the
ratio of that process's rate with the merged rate.

\paragraph{Merging of Rewards:} Take the processes and sequences as
defined above. However, take $(B_N)$ to be the encounter process for the
merged process and take $B^i_N$ to be the encounter process for process
$(N_i(t):t \in \R_{\geq0})$ for each $i \in \{1,2,\dots,n\}$.
Additionally, assume that for all $i \in \{1,2,\dots,n\}$ there is a
renewal-reward process $(G_i(t):t \in \R_{\geq0})$ and corresponding
gain process $(G^i_N)$ each associated with Poisson process $(N_i(t):t
\in \R_{\geq0})$. Take $N \in \N$ and $N_i \in \N$ for each $i \in
\{1,2,\dots,n\}$, and build a new gain process $(G_N)$ as follows. Take
$\zeta \in \set{U}$.
%
\begin{enumerate}[1.]
        \item Let $N = 1$ and $N_i = 1$ for all $i \in \{1,2,\dots,n\}$.
        \item If there is no $i \in \{1,2,\dots,n\}$ such that
                $B^i_{N_i} = B_N$ then skip to step
                \shortref{item:next_gainmerge_iteration}.
                \label{item:start_gainmerge_iteration}
        \item Take $i \in \{1,2,\dots,n\}$ such that $B^i_{N_i}=B_N$ and
                set $G_N = G^i_{N_i}$.
        \item Set $N_i = N_i + 1$.
        \item Skip to step \shortref{item:start_gainmerge_iteration}.
        \item Set $N = N + 1$. 
                \label{item:next_gainmerge_iteration}
        \item Skip to step \shortref{item:start_gainmerge_iteration}.
\end{enumerate}
%
The resulting process $(G_N)$ is simply a merged version of each
$(G^i_N)$ process for each $i \in \{1,2,\dots,n\}$ such that the order
of encounters is maintained. Thus, define the renewal-reward process
$(G(t):t \in \R_{\geq0})$ by
%
\begin{equation*}
        G(t) \triangleq \sum\limits_{i=1}^{N(t)} G_N
\end{equation*}
%
for all $t \in \R_{\geq0}$ and all $\zeta \in \set{U}$. This can be
called a \emph{merged Poisson renewal-reward process} and $(G_N)$ is its
gain process. There is an identical construction for a
renewal-reward-cost process.

\subsection{Bernoulli Splitting of Poisson Processes}
\label{app:math_bernoulli_split_poisson_process}

Take an experiment modeled by probability space $(\set{U},\Sigma,\Pr)$,
and let $(N(t): t \in \R_{\geq 0})$ be a Poisson process on this space
with rate parameter $\lambda \in \R_{>0}$. Also take some $p \in (0,1)$
and let $(X_N)$ be a sequence of \iid{}\ random variables such that
%
\begin{align*}
        f_{X_N}(x) = (1-p) \delta(x) + p \delta(x-1)
\end{align*}
%
for each $N \in \N$. That is, $(X_N)$ is an \iid{}\ sequence of
Bernoulli random variables distributed with parameter $p$. Recall that
this means $\range(X_N) = \{0,1\}$ for each $N \in \N$. Now, introduce
random process $(N_p(t): t \in \R_{\geq 0})$ such that for each $\zeta
\in \set{U}$ and each $t \in \R_{\geq0}$,
%
\begin{equation*}
        N_p(t) \triangleq \sum\limits_{j=1}^{N(t)} X_N
\end{equation*}
%
Clearly, $(N_p(t): t \in \R_{\geq0})$ is a Markov renewal-reward
process. However, in this special case, it can be shown that $(N_p(t): t
\in \R_{\geq0})$ is a Poisson process with rate parameter $\lambda_p$
defined by
%
\begin{equation*}
        \lambda_p \triangleq p \lambda
\end{equation*}
%
This new Poisson process is called a \emph{split Poisson process} or a
\emph{thinned Poisson process}. In fact, we will refer to $(N_p(t): t
\in \R_{\geq0})$ as the result of $(N(t):t \in \R_{\geq0})$ being
\emph{thinned by $p$} or being \emph{thinned by $(X_N)$}. We also call
$(X_N)$ the \emph{Bernoulli sequence} associated with split Poisson
process $(N_p(t):t \in \R_{\geq0})$. Of course, $\E(X_1)=p$.

\paragraph{Thinning Interpretation:} Take the processes and sequences as
defined above. Also take any outcome $\zeta \in \set{U}$. For each each
$N \in \N$, consider $X_N$ to be a property of encounter $N$ from
Poisson process $(N(t):t \in \R_{\geq0})$, where $X_N=1$ is a favorable
property and $X_N=0$ is an unfavorable property. Therefore, the $N_p(t)$
is simply a count of all of the favorable encounters up to time $t \in
\R_{\geq0}$. In fact, it can be shown that
%
\begin{equation*}
        N(t) \geq N_p(t)
\end{equation*}
%
for all $t \in \R_{\geq0}$; this is consistent with the interpretation
of $N_p(t)$ being the count of all favorable encounters up to time $t
\in \R_{\geq0}$ since all encounters can either be favorable or
unfavorable. Thus, $(N_p(t):t \in \R_{\geq0})$ is a version of the
$(N(t):t \in \R_{\geq0})$ process after being \emph{thinned} of its
unfavorable encounters.

\paragraph{Independence of Split Poisson Processes:} Take Poisson
process $(N(t):t \in \R_{\geq0})$ as defined above. Take $n \in \N$ and
family $(p_i)_{i=1}^n$ where $p_i \in (0,1)$ for all $i \in
\{1,2,\dots,n\}$. Now define a family of split Poisson processes $(
(N_i(t):t \in \R_{\geq0}))_{i=1}^n$ where $(N_i(t):t \in \R_{\geq0})$ is
the result of $(N(t):t \in \R_{\geq0})$ being thinned by $p_i$. The
family $( (N_i(t):t \in \R_{\geq0}) )_{i=1}^n$ is a family of
independent Poisson processes.

\paragraph{Thinning of Rewards:} Take the processes and sequences as
defined above. However, assume there is a renewal-reward process
$(G(t):t \in \R_{\geq0})$ and a corresponding gain process $(G_N)$ each
associated with Poisson process $(N(t):t \in \R_{\geq0})$. Build a new
gain process $(G^p_N)$ as follows. Take a $\zeta \in \set{U}$. Define
the family of sets $(\set{N}_N)_{N=0}^\infty$ so that
%
\begin{itemize}
        \item $\set{N}_0 \triangleq \{ N \in \N : X_N = 1 \}$
        \item $\set{N}_{N} \triangleq \set{N}_{N-1} \setdiff \{\min
                \set{N}_{N-1}\}$ for all $N \in \N$
\end{itemize}
%
Therefore, 
%
\begin{itemize}
        \item $\min \set{N}_0$ is the first $N \in \N$ such that $X_N =
                1$
        \item $\min \set{N}_1$ is the second $N \in \N$ such that $X_N =
                1$
        \item $\min \set{N}_{N}$ is the $(N+1)\th$ $N \in \N$ such that $X_N =
                1$
\end{itemize}
%
Now, build the sequence $(G^p_N)$ for this $\zeta \in \set{U}$ so that
%
\begin{equation*}
        G^p_N \triangleq G_{\min \set{N}_{N-1}}
\end{equation*}
%
for all $N \in \N$. In other words, the sequence $(G^p_N)$ is simply the
$(G_N)$ sequence with elements corresponding to unfavorable encounters
removed. Therefore, the process $(G_p(t): t \in \R_{\geq0})$ defined by
%
\begin{equation*}
        G_p(t) 
        \triangleq 
        \sum\limits_{i=1}^{N_p(t)} G^p_i
        =
        \sum\limits_{j=1}^{N(t)} X_j G_j
\end{equation*}
%
for all $t \in \R_{\geq0}$ and all $\zeta \in \set{U}$ can be called a
\emph{split (or thinned) Poisson renewal-reward process} that is
\emph{thinned by $p$} or \emph{thinned by $(X_N)$}, and $(G^p_N)$ is its
gain process. There is an identical construction for a
renewal-reward-cost process.
