% 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.