# A Two-Part Controller Synthesis Approach for Nonlinear Stochastic Systems
Perturbed by Lévy Noise
Using Renewal Theory and HJB-Based Impulse Control

SooJean Han SooJean Han and John C. Doyle are with the Department of Computing
and Mathematical Sciences, California Institute of Technology, Pasadena, CA
91125, USA. Emails<EMAIL_ADDRESS><EMAIL_ADDRESS>Soon-Jo Chung
Soon-Jo Chung is with the Department of Computing and Mathematical Sciences
and Department of Aerospace, California Institute of Technology, Pasadena, CA
91125, USA. Email<EMAIL_ADDRESS>
###### Abstract

We are motivated by the lack of discussion surrounding methodological control
design procedures for nonlinear shot and Lévy noise stochastic systems to
propose a hierarchical controller synthesis method with two parts. The first
part is a primitive pattern-learning component which recognizes specific state
sequences and stores in memory the corresponding control action that needs to
be taken when the sequence has occurred. The second part is a modulation
control component which computes the optimal control action for a pattern when
it has occurred for the first time. Throughout our presentation of both
components, we provide a self-contained discussion of theoretical concepts
from Poisson processes theory, renewal theory, and impulse control, all of
which are necessary as background. We demonstrate application of this
controller to the simplified, concrete case studies of fault-tolerance and
vehicle congestion control.

##  1 Introduction

The study of dynamical systems in the field of control theory utilizes
mathematical models to describe the evolution of a certain set of system
quantities over time. In its most abstract form, a dynamical system is
traditionally written as the following ODE:

$\displaystyle d{\bf x}(t)=f(t,{\bf x})dt$ (1)

where $f:\mathbb{R}^{+}\times\mathbb{R}^{n}\to\mathbb{R}^{n}$ is a
deterministic function in $\mathcal{C}^{(1,2)}$, i.e., $f$ is continuously-
differentiable in time and twice continuously-differentiable in state, and the
state dimension is $n\in\mathbb{Z}^{+}$. Core theoretical foundations for
dynamical system models have been studied for decades and gathered in numerous
comprehensive references such as [25, 43, 45, 52] over time.

While much of basic control theory is studied under the condition that $f$ in
(1) is a deterministic function of $t$ and ${\bf x}$, many dynamical systems
in practice are also affected by some amount of randomness, which prevents
future states of the system from being able to be predicted precisely. These
stochastic (dynamical) systems come in many different types and arise in a
wide number of disciplines; some examples include voltage fluctuations in
metallic conductors [5] in fields of physics, photon-counting in the field of
optics [8], and the regulation of control circuits in biomolecular systems
[34]. Motivated by the existence of these systems, there has been a vast
literature of references, such as [32, 36, 23, 24], dedicated to the rigorous
study of stochastic systems and random processes.

When considering the problem of control or state-estimation for stochastic
systems, many designs for controllers or observers, especially model-based
designs, typically aim for robustness against specifically additive Gaussian
white noise (AWGN). The model of such a stochastic system is expressed as the
following SDE:

$\displaystyle d{\bf x}(t)=f(t,{\bf x})dt+\sigma(t,{\bf x})dW(t)$ (2)

where

  * •

$W:\mathbb{R}^{+}\to\mathbb{R}^{d}$ is a $d$-dimensional standard Brownian
motion process.

  * •

$\sigma:\mathbb{R}^{+}\times\mathbb{R}^{n}\to\mathbb{R}^{n\times d}$,
$\sigma\in\mathcal{C}^{(1,2)}$ is the variation of the Gaussian white noise.

There are many applications such as vision-based localization/mapping [51],
spacecraft navigation [7], and motion-planning [21] where using Gaussian white
noise processes in the model is justifiable in practice. From a theoretical
perspective, Gaussian white noise processes are appealing to study because
their convenient properties (e.g., continuity of sample paths, normality of
the distribution, the Central Limit Theorem) make the stochastic system easier
to analyze than non-Gaussian stochastic systems. Consequently, there is a
wealth of literature that has been devoted towards analyzing the stability of
systems with AWGN perturbations, and designing controllers and observers for
them. Some classical model-based methods are the Linear Quadratic Gaussian
(LQG) model [6, 15], as well as Kalman filtering [22] and its extensions [39,
48]. More recent methods of model-based controller and observer designs for
Gaussian white noise include the path integral approach [46], convex
optimization-based approaches [38, 31], as well as a number of reinforcement
learning based approaches [30, 14].

However, there is a major lack of generality with the assumption of Gaussian
white noise. Because it is small in magnitude and continuous in the sense that
changes occur gradually over a measurable duration of time, it is unable to
account for sudden impulsive perturbations. One particular class of non-
Gaussian noise which is suitable for modeling impulsive perturbations is
Poisson shot noise [3]. The dynamics of a stochastic system where shot noise
is injected additively is written as the following SDE:

$\displaystyle d{\bf x}(t)=f(t,{\bf x})dt+\int_{\mathbb{R}^{\ell}}\xi(t,{\bf
x},{\bf z})N(dt,d{\bf z})$ (3)

where

  * •

$N(dt,d{\bf z})$ is a $r$-dimensional standard Poisson process with some
intensity $\lambda\in\mathbb{R}^{r}$.

  * •

$\xi:\mathbb{R}^{+}\times\mathbb{R}^{n}\times\mathbb{R}^{\ell}\to\mathbb{R}^{n\times
r}$, $\xi\in\mathcal{C}^{(1,2,1)}$ is a function which assigns weights to the
individual components of $N$, since the standard Poisson process itself has
unit weights. Essentially, $\xi$ is a function that describes the impulsive
jumps that occurs in the system.

Poisson shot noise arises in a wide diversity of real-world applications
almost just as frequently as Gaussian white noise does. Some examples include
the high fluctuations in stock prices within the field of finance [9], as well
as the neuronal spikes that come from monitoring brain activity within the
field of neuroscience [35] are better modeled as impulsive perturbations than
as Gaussian noise. In applications of robotics, shot noise may arise in the
the form of massive proprioceptive measurement errors, large disturbances due
to obstacle collisions, or natural external factors in the environment such as
a large gust of wind. Despite this prevalence, there are little to no
analytical controller or observer synthesis procedures dedicated towards
robustness against shot noise perturbations. In fact, for any non-Gaussian
noise processes, machine-learning-based methods [17, 44, 47] are often the go-
to methods used to learn the model from scratch, but a downside of these
approaches are the massive amounts of time and training data they consume.

On the other hand, in the field of applied mathematics, there is an abundance
of literature [1, 33] which provides many theoretical results on Poisson
random measures and jump-diffusion systems, which are relevant to addressing
the controller and observer design procedures for shot-noise stochastic
systems (3). A particularly useful theoretical result known as the Lévy-
Khintchine Decomposition Theorem, stated formally in Theorem 1.6 of [50],
Theorem 2.7 of [4], or Theorem 1.2.14 of [2], leads to a direct extension of
(3) by uniting it with the Gaussian white noise case, yielding stochastic
systems of the form:

$\displaystyle d{\bf x}(t)=f(t,{\bf x})dt+\sigma(t,{\bf
x})dW(t)+\int_{\mathbb{R}^{\ell}}\xi(t,{\bf x},{\bf z})N(dt,d{\bf z})$ (4)

This affine decomposition of bounded-measure Lévy noise processes allows us to
combine the controller and observer design procedures of (2) and (3) to obtain
a design procedure for (4).

In this paper, we are motivated by two factors:

  1. 1.

the lack of discussion surrounding methodological control synthesis procedures
for stochastic systems involving shot and Lévy noise processes

  2. 2.

the often inefficient way in which learning-based approaches are applied to
any stochastic system perturbed by general non-Gaussian noise

We take a step towards addressing both issues by proposing a hierarchical
controller synthesis method composed of the following two parts:

  1. 1.

a primitive pattern-learning component which recognizes specific state
sequences and stores in memory the corresponding control action applied to the
system when a sequence has occurred

  2. 2.

a modulation control component which computes the control action to be taken
when a specific state sequence is first encountered

We note that in applications such as fault-tolerance, an independent lower-
level controller can be used for the majority of the time, and the two-part
controller is only applied when the system is destabilized. This requires some
form of general stability analysis to determine a bound on when this two-part
controller should be applied; in particular, we demonstrate how to determine
this bound using the incremental stability analysis approach described in our
previous paper [19]. Moreover, most traditional methodological control design
approaches do not include the first part, and we motivate our choice of its
inclusion in our proposed method as follows. In applications where the
magnitude of the jumps in the impulsive part of the noise process can be
grouped into discrete values, there is potential for the system to observe re-
occurring sequences. Hence, there is no need to devote time and computational
energy to redundantly compute a control action for a scenario that has been
observed before. We leverage results from the well-known theory of renewal
processes [40, 41, 10, 11] and the problem of “pattern occurrence” to obtain
criteria, such as the expected time that elapses between two consecutive
instances of the same pattern, to aid in designing the learning component. We
illustrate the proposed scheme using two particular case studies:

  1. 1.

fault-tolerance control: we are inspired by fault-tolerance control
applications such as spacecraft control [16, 49, 27] to investigate a simple
system which uses the two-part controller as a means of fault-tolerance to
steer the system back to some predetermined, certified safety bound; when the
trajectory is already within the safety bound in the absence of the random
jump disturbances, an independent lower-level controller is used for
stabilization.

  2. 2.

congestion control: the proposed two-part controller is used to optimally
drive the state of the system towards increasingly lower energy states under a
certain set of constraints. We consider the specific case study of controlling
vehicle traffic at an intersection.

###  1.1 Paper Outline

We begin in Section 2 by laying out the renewal theory background relevant to
the first part of the controller synthesis problem for shot noise stochstic
systems (3) and Lévy noise stochastic systems (4). The subsection 2.2 then
formally establishes the so-called pattern occurrence problem, which derives a
way to compute the expected time between two consecutive occurrences of a
specific pattern sequence in a string of renewals. Section 2.1 then provides
an important unifying limiting theorem, called Blackwell’s theorem, that is
satisfied by all renewal processes and their corresponding extensions. Then
Section 3 introduces the impulse control method to be employed in designing
the actual action for the second part of the stochastic controller synthesis
problem. We begin in Section 3.1 with a brief review of stochastic processes
theory, the variations of Itô’s formula, and the Poisson random measure in
order to concretely establish the meaning and notation of the math we will be
using for shot noise stochstic systems (3) and Lévy noise stochastic systems
(4), since these concepts may be unfamiliar to the reader. We then introduce
the specific type of control known as impulse control in Section 3.2, which
will be used for the case studies of Section 4. Finally, in Section 4, we
illustrate the control process on two sample case studies, the simple 1D
linear stochastic process perturbed by Lévy noise, and the vehicle traffic at
an intersection used to intuitively motivate our paper throughout the
Introduction.

##  2 The Pattern-Learning Component

In this section, we discuss the first part of the controller synthesis
procedure: the primitive learning component to recognize previously-occurred
states so that the corresponding optimal control action can be recycled. To
achieve this, we borrow elements from renewal theory, and in particular, the
pattern occurrence problem to compute the expected time between consecutive
patterns of renewals. Before we introduce the pattern occurrence problem in
Section 2.2, we lay out some definitions and theoretical foundations at the
core of renewal theory relevant for our discussion of stochastic control
design in Section 2.1. Most of these definitions have been presented in
standard random processes references such as [40] and [41], but we discuss
them here to ensure that the material is self-contained. More importantly, the
form of the theorems expressed in [40] or [41] are written for a general
context, but we adapt the discussion for what is pertinent for the paper’s
proposed controller synthesis approach. For a more comprehensive treatment of
our adapted discussion, we refer to our textbook preprint [18].

###  2.1 Basic Definitions and Results from Renewal Theory

######  Definition 1 (Counting Process).

Suppose that we have a stochastic process $\\{N(t),t\geq 0\\}$ which satisfies
the following conditions:

  * •

the process takes nonnegative, integer values: $N(t)\geq 0$ and
$N(t)\in\mathbb{Z}$

  * •

the process is non-decreasing with respect to time: if $s\leq t$ then
$N(s)\leq N(t)$

Then $N(t)$ is referred to as a counting process.

######  Definition 2 (Renewal Process).

Let $\\{N(t),t\geq 0\\}$ be a counting process and let $A_{n}:=T_{n}-T_{n-1}$
be the interarrival times, where $T_{n}$ denotes the time of the $n$th arrival
time. If $\\{A_{i}\\}_{i=1}^{\infty}$ is iid, then $N(t)$ is a called a
renewal process.

Note that

$\displaystyle\mathbb{P}(N(t)=n)=\mathbb{P}(N(t)\geq n)-\mathbb{P}(N(t)\geq
n+1)=\mathbb{P}(T_{n}\leq t)-\mathbb{P}(T_{n+1}\leq t)$ (5)

There are numerous extensions to renewal processes which can be made in order
to model a broader class of real-world phenomena. To model aspects of our
controller synthesis procedure, we look at three specific extensions: 1)
renewal reward processes, 2) delayed renewal processes, and 3) regenerative
reward processes. Analysis of these three types of renewal processes requires
using the following well-known result.

######  Lemma 1 (Wald’s Equation).

Let $\\{A_{i}\\}_{i=1}^{\infty}$ be iid sequence such that
$\mathbb{E}[A_{i}]:=\mathbb{E}[A]<\infty$ for all $i$, and let $N$ be a
stopping time such that $\mathbb{E}[N]<\infty$. Then the following equality
holds:

$\displaystyle\mathbb{E}\left[\sum\limits_{n=1}^{N}A_{n}\right]=\mathbb{E}[N]\mathbb{E}[A]$
(6)

The proof of this elementary result is straightforward and has been deferred
to [18] to keep the content of the paper focused. Instead, we present and
prove a more crucial result which examines an important limiting property for
renewal processes, namely its time-average renewal rate. We will see later in
Blackwell’s theorem the three corresponding extensions of the time-average
renewal rate for each of the three types of renewal processes mentioned above.

######  Theorem 1.

Let $N(t)$ be a renewal process with $\\{A_{i}\\}_{i=1}^{\infty}$ be iid
sequence of interarrival times such that
$\mathbb{E}[A_{i}]:=\mathbb{E}[A]=\mu<\infty$ for all $i$. Then the time-
average renewal rate has the following limiting relationship:

$\displaystyle\frac{m(t)}{t}\to\frac{1}{\mu}\text{ as }t\to\infty$ (7)

where $m(t):=\mathbb{E}[N(t)]$ is referred to as the mean process.

###### Proof of Theorem 1..

We carry out this proof through two parts, we show that
$\lim_{t\to\infty}\frac{m(t)}{t}\geq\frac{1}{\mu}$, then show that
$\lim_{t\to\infty}\frac{m(t)}{t}\leq\frac{1}{\mu}$.

Note that $T_{N(t)+1}$ denotes the time of the first renewal after time $t$,
which can alternatively be represented as

$\displaystyle T_{N(t)+1}=t+\Delta T_{N(t)}$ (8)

where we refer to $\Delta T_{N(t)}$ as the “excess” time from $t$ until the
next renewal.

By Wald’s equation, note that

$\displaystyle\mathbb{E}[T_{N(t)+1}]=\mathbb{E}\left[\sum\limits_{n=1}^{N(t)+1}A_{n}\right]=\mathbb{E}[A]\mathbb{E}[N(t)+1]=\mu(m(t)+1)$

which, in combination with (8), yields

$\displaystyle\mu(m(t)+1)=t+\mathbb{E}[\Delta T_{N(t)}]\ \Longrightarrow\
\frac{m(t)}{t}+\frac{1}{t}=\frac{1}{\mu}+\frac{\mathbb{E}[\Delta
T_{N(t)}]}{t\mu}$ (9)

where the second equality follows from dividing through by $t\mu$. Since
$\Delta T_{N(t)}\geq 0$, it follows that

$\displaystyle\frac{m(t)}{t}\geq\frac{1}{\mu}-\frac{1}{t}\ \Longrightarrow\
\lim_{t\to\infty}\frac{m(t)}{t}\geq\frac{1}{\mu}$ (10)

To prove the other half, suppose there exists a value $C<\infty$ such that
$\mathbb{P}(A_{i}<C)=1$. This implies that $\Delta T_{N(t)}<C$, and so (9)
implies

$\displaystyle\frac{m(t)}{t}\leq\frac{1}{\mu}+\frac{C}{t\mu}-\frac{1}{t}\
\Longrightarrow\ \lim_{t\to\infty}\frac{m(t)}{t}\leq\frac{1}{\mu}$ (11)

Thus, when the interarrival times are bounded, Theorem 1 holds. In the case
where they are unbounded, again fix $C>0$, and define $\\{N_{C}(t),t\geq 0\\}$
to be the renewal process with interarrival times $\min(A_{n},C),n\geq 1$.
Since $\min(A_{n},C)\leq A_{n}$ for all $n\geq 0$, $N_{C}(t)\geq N(t)$ for all
$t\geq 0$ since the interarrival times are shorter. Consequently:

$\displaystyle\lim_{t\to\infty}\frac{\mathbb{E}[N(t)]}{t}\leq\lim_{t\to\infty}\frac{\mathbb{E}[N_{C}(t)]}{t}=\frac{1}{\mathbb{E}[\min(A_{n},C)]}$
(12)

where the second equality follows from the first case, where the interarrival
times are bounded. Since
$\lim_{C\to\infty}\mathbb{E}[\min(A_{n},C)]=\mathbb{E}[A_{n}]=\mu$, (12)
becomes

$\displaystyle\lim_{t\to\infty}\frac{m(t)}{t}\leq\frac{1}{\mu}$

The two cases together, in combination with (10) yields the desired result
(7). ∎

Three natural extensions of renewal processes are described in the definition
below.

######  Definition 3.

Let $\\{N(t),t\geq 0\\}$ be a renewal process with state space
$\mathbb{Z}^{+}$ and interarrival times $\\{A_{i}\\}_{i=1}^{\infty}$.

  1. 1.

Let $\\{R_{n}\\}_{n=1}^{\infty}$ be an iid sequences of random variables such
that the $n$th renewal of $N(t)$ obtains a reward of $R_{n}$. Then $N(t)$ is
said to be a renewal reward process.

  2. 2.

$N(t)$ is said to be a delayed renewal process if the first interarrival time
of the process is distributed differently from all future interarrival times.

  3. 3.

$N(t)$ is said to be a regenerative renewal process if there exist times
$\\{T_{i}^{(0)}\\}_{i=1}^{\infty}$ at which the process restarts itself with
probability $1$, i.e., $\mathbb{P}(N(T_{i}^{(0)}))=1$.

Renewal processes and their extensions from Definition 3 can be used to model
elements of the case studies we investigate in Section 4. For instance, within
the context of the congestion control problem, the cost that the system incurs
by being at a certain level of congestion can be assigned a value using an
appropriately-chosen reward function. In the vehicle traffic control problem,
the reward of a vehicle could denote the inverse of the time spent waiting at
the intersection before being allowed to pass. Regenerative renewal processes
can be used to model the fault-tolerance control problem since the system
effectively “restarts” from within the certified safety bound after the
modulation control component corrects for the destabilizing pattern. Moreover,
practical reasons for modeling systems using delayed renewal processes may be
due to the system needing some additional time to warm up at the start.

Now, we introduce an important unifying limiting theorem for the mean process
of a renewal process over time, known as Blackwell’s theorem, for different
types of renewal processes. We can view Blackwell’s theorem as a further
development to the basic result described in Theorem 1. Several versions of
Blackwell’s theorem have been described in [40], [41], as well as in [42].
Section 4.4 of [10] and Chapter 9 of [11] further generalizes Blackwell’s
theorem and discusses some properties of renewal processes by invoking Laplace
transforms. However, we emphasize that the version of Blackwell’s theorem in
this paper is specialized to make it easier to apply to the proposed
controller synthesis framework, and also to the case studies that are
addressed in Section 4. For an extensive treatment of Blackwell’s theorem and
the properties of renewal processes with the additional random processes
background needed to facilitate their discussion, we refer to our textbook
preprint [18].

######  Definition 4 (Lattice).

A nonnegative random variable $S$ with cdf $F$ is lattice if there exists a
$c\geq 0$ such that $S$ only takes on values which are integer multiples of
$c$.

$\displaystyle\sum\limits_{n=0}^{\infty}\mathbb{P}(S=nc)=1$

The largest such $c$ in which this property holds is referred to as the period
of $S$.

We overload the terminology of “lattice” to describe both the random variable
$S$ and its distribution function $F$.

######  Definition 5 (Ladder Variables).

An ascending variable of ladder height $S_{n}$ occurs at time $n$ if
$S_{n}>\max\\{0,S_{1},\cdots,S_{n-1}\\}$. Similarly, a descending variable of
ladder height $S_{n}$ occurs at time $n$ if
$S_{n}<\max\\{0,S_{1},\cdots,S_{n-1}\\}$.

######  Theorem 2 (Blackwell’s Theorem).

Let $\\{A_{i}\\}_{i=1}^{\infty}$ be iid sequence such that
$\mathbb{E}[A_{i}]:=\mathbb{E}[A]=\mu<\infty$ for all $i$, and let $F$ be the
distribution function of $A_{i}$. Let $N(t)$ be the corresponding renewal
process, with $m(t):=\mathbb{E}[N(t)]$.

  1. 1.

If $F$ is not lattice, then

$\displaystyle m(t+a)-m(t)\to\frac{a}{\mu}\ \text{ as }\ t\to\infty$ (13)

for all $a\geq 0$.

  2. 2.

If $F$ is lattice with period $c\geq 0$, then

$\displaystyle\mathbb{E}[N(nc)]\to\frac{c}{\mu}\ \text{ as }\ n\to\infty$ (14)

Note that $N(nc)$ denotes the number of renewals which have occurred by time
$nc$.

###### Proof of Theorem 2.

We will only prove the nonlattice case of Blackwell’s theorem statement, since
the lattice case follows from a similar argument. For easier notation, let us
denote $g(a):=\lim_{t\to\infty}(m(t+a)-m(t))$. Then note that

$\displaystyle
g(a+b)=\lim_{t\to\infty}(m(t+a+b)-m(t+a))+\lim_{t\to\infty}(m(t+a)-m(t))=g(b)+g(a)$

The form of $g$ which satisfies this equation is given by $g(a)=c\cdot a$, for
some constant $c$. Now we want to show that $c=1/\mu$. Consider the following
successive increments of $a=1$:

$\displaystyle\Delta m_{1}$ $\displaystyle:=m(1)-m(0)$ $\displaystyle\Delta
m_{2}$ $\displaystyle:=m(2)-m(1)$ $\displaystyle\vdots$ $\displaystyle\Delta
m_{n}$ $\displaystyle:=m(n)-m(n-1)$

Note that $\lim_{n\to\infty}\Delta m(n)=c$.

On one hand, by the law of large numbers:

$\displaystyle\lim_{n\to\infty}\frac{1}{n}\sum\limits_{k=1}^{n}\Delta m(k)=c$
(15)

On the other hand, by Theorem 1:

$\displaystyle\frac{1}{n}\sum\limits_{k=1}^{n}\Delta
m(k)=\frac{m(n)}{n}\to\frac{1}{\mu}\qquad\text{ as }n\to\infty$ (16)

Combining (15) together with (16), we have that $c=1/\mu$. This concludes the
proof of the first part of the theorem. ∎

######  Corollary 1 (Extensions to Blackwell’s Theorem).

There are also two straightforward extensions to Blackwell’s theorem. The
first is in the context of renewal reward processes. Suppose the renewal
process $\\{N(t),t\geq 0\\}$ has iid rewards $\\{R_{i}\\}_{i=1}^{\infty}$.
Assuming the distribution of the cycle of a renewal reward process is not
lattice, then

$\displaystyle\mathbb{E}[R(t,t+a)]\to\frac{a\mathbb{E}[R]}{\mathbb{E}[T]}$
(17)

where $T$ is the length of a cycle of the renewal reward process.

The second extension is with respect to random walks, which are set up as
follows. Let $X_{1},X_{2},\cdots$ be iid with mean
$\mu:=\mathbb{E}[X]<\infty$, and let $S_{n}:=\sum_{i=1}^{\infty}X_{i}$.
Typically, the random walk $S_{n}$ is started at $X_{0}=S_{0}=0$, and we
assume this implicitly throughout unless stated otherwise. Denote

$\displaystyle U(t):=\sum\limits_{n=1}^{\infty}I_{n}\ \text{ where }\
I_{n}=\begin{cases}1&\text{ if }S_{n}\leq t\\\ 0&\text{ else}\end{cases}$

If $\mu>0$ and $X_{i}$ are nonlattice, then

$\displaystyle\frac{u(t+a)-u(t)}{t}\to\frac{a}{\mu}\ \text{ as }\ t\to\infty\
\forall a>0$ (18)

###### Proof of Corollary 1.

Next, for the extension of Blackwell’s theorem pertaining to renewal reward
processes, note that

$\displaystyle\mathbb{E}[R(t,t+a)]$
$\displaystyle:=\mathbb{E}\left[\sum\limits_{n=0}^{N(t+a)}R_{n}-\sum\limits_{n=0}^{N(t)}R_{n}\right]$
$\displaystyle=\left(\mathbb{E}[N(t+a)]-\mathbb{E}[N(t)]\right)\mathbb{E}[R]\
\text{ by Wald's equation}$ $\displaystyle=(m(t+a)-m(t))\mathbb{E}[R]\ \text{
by }m(t)\text{ definition}$
$\displaystyle\to\frac{a}{\mathbb{E}[T]}\cdot\mathbb{E}[R]\ \text{ as
}t\to\infty$

where the limit follows from (13).

Finally, to prove Blackwell’s result pertaining to random walks, we define a
renewal process using successive ascending ladder heights as the renewals, and
denote $Y(t)$ to be the excess height of the renewal process past height
$t>0$. Then $S_{n}=Y(t)+t$ is the first value of the random walk that exceeds
$t$. See Figure 1 for visualization. Hence, the primary difference between
Blackwell’s Theorem for Random Walks and the original Blackwell’s Theorem or
Theorem 1 is that the renewal process has renewals which are dependent upon
the previous renewals.

Figure 1: The ascending ladder height renewal process with the excess at
height $c=3$. The excess $Y(t)$ is the length of the thick red line.

The proof of this theorem adheres very closely to the technique of the proof
for the original Blackwell’s theorem (13). Define

$\displaystyle h(a)$
$\displaystyle:=\lim_{t\to\infty}\left(u(t+a)-u(a)\right)$

Then we can show that $h(a+b)=h(a)+h(b)$ using the same logic as in the proof
of (13). The solution to such an equation is then given by $h(a)=\theta a$ for
some constant $\theta$ to be determined.

Let $\tau(t):=\min\\{n|S_{n}>t\\}$. We look at two cases of $X_{i}$, just as
in the proof of (13).

First, if there exists $M>0$ such that $X_{i}\leq M$ for all $i$, then

$\displaystyle t<\sum\limits_{i=1}^{\tau(t)}X_{i}<t+M\ \ \Longrightarrow\ \
\frac{1}{\mu}<\frac{\mathbb{E}[\tau(t)]}{t}<\frac{1}{\mu}\left(1+\frac{M}{t}\right)$

which implies that

$\displaystyle\lim_{t\to\infty}\frac{\mathbb{E}[\tau(t)]}{t}=\frac{1}{\mu}$
(19)

On the other hand, if $X_{i}$ are unbounded, denote

$\displaystyle N^{*}(t):=|\\{n>\tau(t)|S_{n}\in(-\infty,t]\\}|$

to be the number of times after exceeding $c$ once $S_{n}$ lands in
$(-\infty,t]$.

Then note that

$\displaystyle U(t)=|\\{n|S_{n}\leq t\\}|=(\tau(t)-1)+N^{*}(t)$ (20)

where the $-1$ comes from excluding the time $S_{n}$ exceeded $t$.

Note that given the value of $Y(t)=y$, the distribution of $U(t+a)-U(t)$ is
independent of $t$. If the first point of the random walk past $c$ occurs at
$y+t$, then the number of points in $(t,t+a)$ has the same distribution as the
number of points in $(0,a)$ given the first positive value of the random walk
occurs at $y$.

Thus,

$\displaystyle\mathbb{E}[N^{*}(t)]\leq\mathbb{E}\left[|\\{n>\tau(0)|S_{n}<0\\}|\right]$

Since $\mu>0$, $\mathbb{E}[\tau(0)]<\infty$. At time $\tau(0)$, there is
probability $1-p_{-}>0$ such that $S_{n}>S_{\tau(0)}$ for all $n>\tau(0)$.
Otherwise, if there is such an $n$ where $S_{n}<S_{\tau(0)}$, then the
expected additional time $m>0$ such that $S_{n+m}>0$ is finite since $\mu>0$.
From time $n+m$, there is again a probability of $1-p_{-}$
$S_{n+k}>S_{\tau(0)}$ for all $k>m$. Thus:

$\displaystyle(1-p_{-})\mathbb{E}\left[|\\{n>\tau(0)|S_{n}<0\\}|\right]\leq\mathbb{E}[\tau(0)|X_{1}<0]$
$\displaystyle\Longrightarrow\ \ $
$\displaystyle\mathbb{E}\left[|\\{n>\tau(0)|S_{n}<0\\}|\right]\leq\frac{\mathbb{E}[\tau(0)|X_{1}<0]}{1-p_{-}}<\infty$

This shows that $\mathbb{E}[N^{*}(t)]<\infty$, and combined with (20), yields

$\displaystyle\lim_{t\to\infty}\frac{\mathbb{E}[\tau(t)]}{t}=\lim_{t\to\infty}\frac{u(t)}{t}$
(21)

Finally, to conclude the result from both (19) and (21), note that
$u(1+a)-u(a)\to\theta$ as $a\to\infty$. This implies

$\displaystyle\frac{u(n+1)-u(1)}{n}=\frac{1}{n}\sum\limits_{a=1}^{n}u(1+a)-u(a)\to\theta\
\text{ as }\ n\to\infty$

Indeed, $\theta=1/\mu$ and this concludes the proof. ∎

Now that we have discussed Theorem 1 and Blackwell’s theorem, we are ready to
consider some other important properties of reward, delayed, and regenerative
renewal processes, i.e. the arrival time of the last renewal before a certain
time, or the mean number of renewals that have arrived by a certain time. This
requires a result related to taking the integral with respect to the mean
process of the renewal process. Before we present the result, we define
Riemann-integrable functions within the context of renewal theory.

######  Definition 6 (Riemann-Integrable).

Let $f:\mathbb{R}^{+}\to\mathbb{R}$ such that

$\displaystyle\underline{f}_{n}(a)\leq f(t)\leq\overline{f}_{n}(a)\ \text{ for
}\ t\in[(n-1)a,na]$

where $\underline{f}_{n}$ is the lower Riemann sum and $\overline{f}_{n}$ is
the upper Riemann sum. We say that $f$ is Riemann-integrable if

  * •

$\sum\limits_{n=1}^{\infty}\underline{f}_{n}(a)$ and
$\sum\limits_{n=1}^{\infty}\overline{f}_{n}(a)$ are finite for all $a>0$

  * •

$\lim_{a\to 0}a\sum\limits_{n=1}^{\infty}\underline{f}_{n}(a)=\lim_{a\to
0}a\sum\limits_{n=1}^{\infty}\overline{f}_{n}(a)$

Furthermore, a sufficient condition for $f$ to be Riemann integrable is that
1) $f(t)\geq 0$ for all $t\geq 0$, 2) $f(t)$ is nonincreasing, 3)
$\int_{0}^{\infty}f(t)dt<\infty$.

######  Theorem 3.

Let $\\{N(t),t\geq 0\\}$ be a renewal process with interarrival times
$\\{A_{i}\\}_{i=1}^{\infty}$ being an iid sequence with distribution function
$F$ (i.e., $F(t):=\mathbb{P}(A_{i}=t)$) such that
$\mathbb{E}[A_{i}]:=\mathbb{E}[A]=\mu<\infty$ for all $i$. In addition, let
$f:\mathbb{R}^{+}\to\mathbb{R}$ be a Riemann-integrable function. Then the
following equality holds:

$\displaystyle\lim_{t\to\infty}\int_{0}^{t}f(t-s)dm(s)=\frac{1}{\mu}\int_{0}^{\infty}f(s)ds$

where

$\displaystyle
m(x):=\mathbb{E}[N(t)]=\sum\limits_{n=1}^{\infty}F_{n}(x),\qquad\mu:=\int_{0}^{\infty}\overline{F}(t)dt$

where $F_{n}$ is the distribution of arrival time $T_{n}$ (which is the
$n$-fold convolution of interarrival distribution $F$), and
$\overline{F}(t):=\mathbb{P}(A_{i}>t)$ for all $i$.

The importance of Theorem 3 arises in computing the limiting value of some
probability or expectation-like function $g(t)$ related to the renewal
process. This yields an equation of the form

$\displaystyle g(t)=h(t)+\int_{0}^{t}h(t-s)dm(s)$

for some Riemann-integrable function $h$. One specific function is the
distribution of $T_{N(t)}$, the arrival time of the last renewal before time
$t$.

$\displaystyle\mathbb{P}(T_{N(t)}\leq s)$
$\displaystyle=\sum\limits_{n=0}^{\infty}\mathbb{P}(T_{n}\leq s,N(t)\leq n)$
$\displaystyle=\mathbb{P}(T_{0}\leq
s,T_{1}>t)+\sum\limits_{n=1}^{\infty}\mathbb{P}(T_{n}\leq s,T_{n+1}>t)\ \text{
since }\\{N(t)\leq n\\}\Longleftrightarrow\\{T_{n+1}>t\\}$
$\displaystyle=\mathbb{P}(T_{1}>t)+\sum\limits_{n=1}^{\infty}\mathbb{P}(T_{n}\leq
s,T_{n+1}>t)\ \text{ since }T_{0}:=0\leq s\text{ always}$
$\displaystyle=\overline{F}(t)+\sum\limits_{n=1}^{\infty}\int_{0}^{\infty}\mathbb{P}(T_{n}\leq
s,T_{n+1}>t|T_{n}\leq r)dF_{n}(r)$
$\displaystyle=\overline{F}(t)+\sum\limits_{n=1}^{\infty}\int_{0}^{s}\mathbb{P}(T_{n+1}-T_{n}>t-r)dF_{n}(r)$
$\displaystyle=\overline{F}(t)+\int_{0}^{s}\overline{F}(t-r)d\left(\sum\limits_{n=1}^{\infty}F_{n}(r)\right)$
$\displaystyle=\overline{F}(t)+\int_{0}^{s}\overline{F}(t-r)dm(r)$

Hence:

$\displaystyle\mathbb{P}(T_{N(t)}\leq s)$
$\displaystyle=\overline{F}(t)+\int_{0}^{s}\overline{F}(t-r)dm(r)$ (22)

Now we are ready to describe the properties of reward, delayed, and
regenerative renewal processes, respectively.

######  Lemma 2 (Property of a Renewal Reward Process).

Let $N(t)$ be a renewal reward process with interarrival times
$\\{A_{n}\\}_{n=1}^{\infty}$ and rewards $\\{R_{n}\\}_{n=1}^{\infty}$.
Moreover, let $R(t)$ represent the total reward earned by time $t$:

$\displaystyle R(t):=\sum\limits_{n=1}^{N(t)}R_{n}$

and denote $\nu:=\mathbb{E}[R_{n}],\mu:=\mathbb{E}[A_{n}]$ for all $n\geq 1$.
Further suppose $\nu,\mu<\infty$. Then the following hold:

$\displaystyle\lim_{t\to\infty}\frac{R(t)}{t}$ $\displaystyle=\frac{\nu}{\mu}\
\text{ w.p. }1$ (23a)
$\displaystyle\lim_{t\to\infty}\frac{\mathbb{E}[R(t)]}{t}$
$\displaystyle=\frac{\nu}{\mu}$ (23b)

###### Proof of Lemma 2.

Since the proof of (23b) follows similarly to the proof of (23a), we will only
prove (23a). Write:

$\displaystyle\frac{R(t)}{t}:=\frac{1}{t}\sum_{n=1}^{N(t)}R_{n}=\left(\frac{1}{N(t)}\sum_{n=1}^{N(t)}R_{n}\right)\left(\frac{N(t)}{t}\right)$

By the strong law of large numbers, $(\sum_{n=1}^{N(t)}R_{n})/N(t)\to\nu$ as
$t\to\infty$, while $N(t)/t\to 1/\mu$ as $t\to\infty$ follows from (7). The
combination yields (23a). ∎

######  Lemma 3 (Properties of a Delayed Renewal Process).

Consider a delayed renewal process $\\{N_{D}(t),t\geq 0\\}$, with first
interarrival time distribution $A_{1}\sim G$ with finite mean, i.e.
$G(t):=\mathbb{P}(T_{1}<t)$, and successive interarrival time distribution
$A_{2},A_{3},\cdots\sim F$, where $F$ is nonlattice with $\int
s^{2}dF(s)<\infty$. Then the following properties hold:

  * •

Denoting $m_{D}(t):=\mathbb{E}[N_{D}(t)]$ to be the mean number of renewals by
time $t$:

$\displaystyle m_{D}(t)$
$\displaystyle=G(t)+\int_{0}^{t}\sum\limits_{n=1}^{\infty}F_{n}(t-s)dG(s)$
(24)

  * •

Denoting $H_{D}(t):=t-T_{N_{D}(t)}$ to be the age of the process by time $t$,
we have $t\overline{G}(t)\to 0$ as $t\to\infty$ and

$\displaystyle\mathbb{E}[H_{D}(t)]\to\left(\int_{0}^{\infty}s^{2}dF(s)\right)\left(2\int_{0}^{\infty}sdF(s)\right)^{-1}\
\text{ as }t\to\infty$ (25)

###### Proof.

First, by definition of expectation and utilizing the equivalence in (5):

$\displaystyle m_{D}(t):=\mathbb{E}[N_{D}(t)]$
$\displaystyle=\sum\limits_{n=0}^{\infty}\mathbb{P}(N_{D}(t)>n)$
$\displaystyle=\mathbb{P}(N_{D}(t)>0)+\sum\limits_{n=1}^{\infty}\mathbb{P}(N_{D}(t)>n)$
$\displaystyle=G(t)+\sum\limits_{n=1}^{\infty}\int_{0}^{t}\mathbb{P}(N_{D}(t)>n|T_{1}\leq
s)dG(s)$
$\displaystyle=G(t)+\int_{0}^{t}\sum\limits_{n=1}^{\infty}F_{n}(t-s)dG(s)$

This proves (24).

Second, we first have by the dominated convergence theorem

$\displaystyle\lim_{t\to\infty}t\overline{G}(t)=\lim_{t\to\infty}t\int_{t}^{\infty}G(s)ds\leq\lim_{t\to\infty}\int_{t}^{\infty}sG(s)ds$
(26)

Note that because the mean of $G$ is assumed to be finite, the integrand of
(26) is finite. Hence, when taking $t\to\infty$, the value of the overall
integral tends to 0 since the upper and lower limits converge to the same
value.

Now we can consider the age of the delayed renewal process. By conditioning on
the value of $T_{N_{D}(t)}$ and substituting in (22) (and taking care to
ensure that the distribution of the first interarrival time is given by $G$,
not $F$), we get

$\displaystyle\mathbb{E}[H_{D}(t)]$
$\displaystyle=\mathbb{E}[H_{D}(t)|T_{N_{D}(t)}=0]\mathbb{P}(T_{N_{D}(t)}=0)+\int_{0}^{t}\mathbb{E}[H_{D}(t)|T_{N_{D}(t)}=s]\mathbb{P}(T_{N_{D}(t)}=s)ds$
$\displaystyle=\mathbb{E}[H_{D}(t)|T_{N_{D}(t)}=0]\overline{G}(t)+\int_{0}^{t}\mathbb{E}[H_{D}(t)|T_{N_{D}(t)}=s]\overline{F}(t-s)dm_{D}(s)$
$\displaystyle=\mathbb{E}[H_{D}(t)|A_{1}>t]\overline{G}(t)+\int_{0}^{t}\mathbb{E}[H_{D}(t)|T_{N_{D}(t)}=s]\overline{F}(t-s)dm_{D}(s),\
\text{ for }n\geq 2$
$\displaystyle=t\overline{G}(t)+\int_{0}^{t}(t-s)\overline{F}(t-s)dm_{D}(s)$
(27)

since note that the age is simply the time elapsed since the last renewal.
Now, note that under the assumption that $G$ is finite, we showed above that
$t\overline{G}(t)\to 0$ as $t\to\infty$, which implies that the first term of
(2.1) tends to $0$. We will thus ignore the first term in our analysis and
focus primarily on the second term. Using Theorem 3, we get:

$\displaystyle\int_{0}^{t}(t-s)\overline{F}(t-s)dm_{D}(s)\to\frac{1}{\mu}\int_{0}^{\infty}s\overline{F}(s)ds$
(28)

Note the relationship

$\displaystyle\overline{F}(s)=\mathbb{P}(Y>s)=\int_{0}^{\infty}\mathbb{P}(Y=u)du$

Substituting, we get:

$\displaystyle(\ref{eq:mean_delay_renewal_2})$
$\displaystyle=\frac{1}{\mu}\int_{0}^{\infty}s\left(\int_{s}^{\infty}dF(u)\right)ds$
$\displaystyle=\frac{1}{\mu}\int_{0}^{\infty}\left(\int_{0}^{u}sds\right)dF(u)\
\text{ via change of variables}$
$\displaystyle=\frac{1}{2\mu}\int_{0}^{\infty}u^{2}dF(u)=\left(\int_{0}^{\infty}s^{2}dF(s)\right)\left(2\int_{0}^{\infty}sdF(s)\right)^{-1}$

This proves (25). ∎

######  Lemma 4 (Property of a Regenerative Process).

Denote $A^{(0)}$ to be the time length of a cycle for regenerative process
$\\{N(t),t\geq 0\\}$, i.e. the duration of time between two consecutive time
points at which the state of the renewal process is $0$. Denote $A_{i}^{(0)}$
to be the total amount of time spent in state $i$ in between two consecutive
times at which the renewal process is in state $0$. Further suppose the
distribution $F$ of a cycle has a density over some interval of time and
$\mathbb{E}[A_{i}^{(0)}]<\infty$ for all $i$. Then the following property
holds:

$\displaystyle
P_{i}:=\lim_{t\to\infty}P(t):=\lim_{t\to\infty}\mathbb{P}(N(t)=i)=\frac{\mathbb{E}[A_{i}^{(0)}]}{\mathbb{E}[A^{(0)}]}$
(29)

###### Proof.

Conditioning on the time of the last cycle before time $t$, and using (22)
yields:

$\displaystyle
P(t)=\mathbb{P}(N(t)=i|T_{N(t)}=0)\overline{F}(t)+\int_{0}^{t}\mathbb{P}(N(t)=i|T_{N(t)}=s)\overline{F}(t-s)dm(s)$
(30)

where $m(t):=\mathbb{E}[N(t)]$. We’ve seen before that

$\displaystyle\mathbb{P}(N(t)=i|T_{N(t)}=0)$
$\displaystyle=\mathbb{P}(N(t)=i|A_{1}^{(0)}>t)$
$\displaystyle\mathbb{P}(N(t)=i|T_{N(t)}=s)$
$\displaystyle=\mathbb{P}(N(t)=i|A_{1}^{(0)}>t-s)$

and hence:

$\displaystyle(\ref{eq:regenerative_proof_1})$
$\displaystyle=\mathbb{P}(N(t)=i|A_{1}^{(0)}>t)\overline{F}(t)+\int_{0}^{t}\mathbb{P}(N(t)=i|A_{1}^{(0)}>t-s)\overline{F}(t-s)dm(s)$
$\displaystyle\to\frac{1}{\mathbb{E}[A_{1}^{(0)}]}\int_{0}^{\infty}\mathbb{P}(N(t)=i|A_{1}^{(0)}>s)\overline{F}(s)ds\
\text{ by~{}Theorem~{}\ref{thm:key_renewal}}$ (31)

and this proves the result since the integral denotes exactly the amount of
time within a cycle $A^{(0)}$ the system spends in state $i$. ∎

###  2.2 The Pattern Occurrence Problem

With the renewal theory background established, we now consider the general
problem of pattern occurrence. We first discuss a couple motivational examples
before describing a more general result.

######  Example 1 (Motivating Example: Expected Time).

Suppose that we are observing a sequence of iid binary random variables
$X_{1},X_{2},\cdots$, each with distribution

$\displaystyle X_{i}=\begin{cases}1&\text{ with probability }\ p\\\ 0&\text{
with probability }\ q:=1-p\end{cases}$

Suppose we designate two strings $A_{1}$ and $A_{2}$ composed of $0$’s and
$1$’s. One common problem of interest is the expected number of trials it
takes to observe two consecutive instances of $A_{1}$ in the sequence
$\\{X_{i}\\}_{i=1}^{\infty}$; likewise, for $A_{2}$. Denote $T_{i}$ to be the
time in between two consecutive instances of $A_{i}$, where $i=1,2$.

We choose for concreteness $A_{1}:=(1,0,1,0,\cdots,1,0)$ to be the length-$2n$
alternating sequence of $1$ and $0$, and $A_{2}:=(1,\cdots,1,0,\cdots,0)$ to
be the length-$m$ string of all $1$’s followed by the length-$m$ string of all
$0$’s.

We first compute $\mathbb{E}[T_{1}]$. Note that if we were to treat each pair
of $(1,0)$ as a single symbol, then we can view $A_{1}$ as a length-$n$ string
composed entirely of $(1,0)$ pairs. Clearly, the probability of observing
exactly $(1,0)$ is $pq$. Hence, the number of trials required to observe
$(1,0)$ for the first time after the last occurrence of $A_{1}$ is distributed
according to a Geometric random variable with parameter $pq$. We can now
iteratively derive the expression for the expected time it takes to obtain a
new string of $n$ pairs of $(1,0)$ after the last occurrence.

$\displaystyle\mathbb{E}[T_{1}]=\sum\limits_{j=1}^{n}\frac{1}{(pq)^{j}}$ (32)

The expression (32) can also be directly derived using a system of linear
equations. Denote $E_{n,j}$ to be the expected number of trials needed to
observe $n$ consecutive $(1,0)$’s given $j$ consecutive $(1,0)$’s, where
$0\leq j\leq n$, have already been observed. Further denote $E_{n,j}^{(1)}$ to
be the expected number of trials needed to observe $n$ consecutive $(1,0)$’s
given $j$ consecutive $(1,0)$’s and an additional trial with outcome $1$ have
been observed. We now have $n$ equations with these variables set up as
follows:

$\displaystyle E_{n,n-k}$ $\displaystyle=1+pE_{n,n-k}^{(1)}+qE_{n,0}$
$\displaystyle E_{n,n-k}^{(1)}$ $\displaystyle=1+pE_{n,0}^{(1)}+qE_{n,n-k+1},\
\ \forall 2\leq k\leq n$ $\displaystyle E_{n,n}$ $\displaystyle=1$

Solving this system and setting $\mathbb{E}[T_{1}]=E_{n,0}$ yields the same
expression as in (32).

We compute $\mathbb{E}[T_{2}]$ using a similar approach. We must first observe
the $m$ consecutive $1$’s before considering the $m$ consecutive $0$’s. Note
that the probability of observing exactly $m$ consecutive $1$’s is $p^{m}$;
hence, the time it takes to observe $m$ consecutive $1$’s is Geometrically
distributed with parameter $p^{m}$. Once $m$ $1$’s have been observed, the
time it takes to observe $m$ consecutive $0$’s is also Geometrically
distributed. Put together, the time to observe $A_{2}$ is Geometrically
distributed with parameter $p^{m}q^{m}$.

$\displaystyle\mathbb{E}[T_{2}]=\frac{1}{(pq)^{m}}$ (33)

The expression (33) can also be derived by solving a system of equations.
Denote $E_{k,i}$ for $0\leq k\leq m$ and $i=0,1$ to be the expected number of
trials needed to observe the full $A_{2}$ given we have observed the
subsequence of $A_{2}$ up to the $k$th outcome of $i$. Then:

$\displaystyle E_{k,1}$ $\displaystyle=1+pE_{k+1,1}+qE_{0,1},\ \ \forall\
0\leq k\leq m-1$ $\displaystyle E_{m,1}$ $\displaystyle=1+pE_{m,1}+qE_{1,0},$
$\displaystyle E_{k,0}$ $\displaystyle=1+pE_{1,1}+qE_{k+1,0},\ \ \forall\
1\leq k\leq m$ $\displaystyle E_{m,0}$ $\displaystyle=1$

Solving this system and setting $\mathbb{E}[T_{2}]=E_{0,1}$ yields the same
expression as in (32). For further details on the derivation for both
$\mathbb{E}[T_{1}]$ and $\mathbb{E}[T_{2}]$, see [18].

######  Example 2 (Motivating Example: Probability).

Given a sequence of binary random variables $X_{1},X_{2},\cdots$, another
problem of interest is the probability of observing one subsequence before
another. Let $A_{1}$ be a string of $n$ $1$’s, $A_{2}$ be a string of $m$
$0$’s, and $A_{3}$ be a string of $r$ $2$’s, where $n,m,r\in\mathbb{N}^{+}$.
Suppose the values of $\\{X_{i}\\}_{i=1}^{\infty}$ are generated in the
following way. Until one of the two sequences $A_{1}$ or $A_{2}$ have been
observed:

$\displaystyle X_{i}=\begin{cases}1&\text{ with probability }\ p_{1}\\\
0&\text{ with probability }\ q_{1}:=1-p_{1}\end{cases}$

If $A_{1}$ is observed first, the $X_{i}$ take the following distribution
until either $A_{2}$ or $A_{3}$ is observed:

$\displaystyle X_{i}=\begin{cases}2&\text{ with probability }\ p_{2}\\\
0&\text{ with probability }\ q_{2}:=1-p_{2}\end{cases}$

Otherwise, if $A_{2}$ is observed first, the $X_{i}$ take the following
distribution until either $A_{1}$ or $A_{3}$ is observed:

$\displaystyle X_{i}=\begin{cases}1&\text{ with probability }\ p_{3}\\\
2&\text{ with probability }\ q_{3}:=1-p_{3}\end{cases}$

Given this setup, we are interested in the probability $P_{1,3}$ that $A_{1}$
is observed before $A_{2}$, and then $A_{3}$ is observed before $A_{2}$.
Denote $\mathcal{E}_{1}$ to be the event that $A_{1}$ is observed before
$A_{2}$, and let $P_{1}:=\mathbb{P}(\mathcal{E}_{1})$. Further denote
$\mathcal{E}_{3}$ to be the event that $A_{3}$ is observed before $A_{2}$
given $A_{1}$ has been observed first, and let
$P_{3}:=\mathbb{P}(\mathcal{E}_{3})$. Then by conditional probability, we can
decompose the probability into two parts:

$\displaystyle P_{1,3}=P_{1}P_{3}$

Now $P_{1}$ and $P_{3}$ can then be computed independently. We first compute
$P_{1}$ by conditioning on the outcome of the first trial $X_{1}$. To that
end, we denote $\mathcal{S}_{1}$ to be the event that $X_{2}=\cdots=X_{n}=1$
and $\mathcal{S}_{0}$ to be the event that $X_{2}=\cdots=X_{m}=0$. Thus:

$\displaystyle P_{1}:=\mathbb{P}(\mathcal{E})$
$\displaystyle=p_{1}\left(p_{1}^{n-1}\mathbb{P}(\mathcal{E}|X_{1}=1,\mathcal{S}_{1})+(1-p_{1}^{n-1})\mathbb{P}(\mathcal{E}|X_{1}=1,\mathcal{S}_{1}^{c})\right)$
$\displaystyle\hskip
28.45274pt+q_{1}\left(q_{1}^{m-1}\mathbb{P}(\mathcal{E}|X_{1}=0,\mathcal{S}_{0})+(1-q_{1}^{m-1})\mathbb{P}(\mathcal{E}|X_{1}=0,\mathcal{S}_{0}^{c})\right)$
(34)

Note that $\mathbb{P}(\mathcal{E}|X_{1}=1,\mathcal{S}_{1})=1$ and
$\mathbb{P}(\mathcal{E}|X_{1}=0,\mathcal{S}_{0})=0$. Furthermore,
$\mathbb{P}(\mathcal{E}|X_{1}=1,\mathcal{S}_{1}^{c})=\mathbb{P}(\mathcal{E}|X_{1}=0)$
because $\mathcal{S}_{1}^{c}$ means that the outcome is $0$ for one of the
trials among $X_{2},\cdots,X_{n}$, after which we need to restart the count;
the probability then becomes equivalent to $\mathbb{P}(\mathcal{E}|X_{1}=0)$.
Likewise,
$\mathbb{P}(\mathcal{E}|X_{1}=0,\mathcal{S}_{0}^{c})=\mathbb{P}(\mathcal{E}|X_{1}=1)$.
We then arrive at a system of two equations and two unknowns
$\mathbb{P}(\mathcal{E}|X_{1}=0)$ and $\mathbb{P}(\mathcal{E}|X_{1}=1)$, which
we can solve and substitute back into (2). We obtain an equivalent expression
for $P_{3}$ via similar calculations. Hence:

$\displaystyle
P_{1,3}=\left(\frac{p_{1}^{n-1}(1-q_{1}^{m})}{q_{1}^{m-1}+p_{1}^{n-1}-q_{1}^{m-1}p_{1}^{n-1}}\right)\left(\frac{p_{2}^{r-1}(1-q_{2}^{m})}{q_{2}^{m-1}+p_{2}^{r-1}-q_{2}^{m-1}p_{2}^{r-1}}\right)$
(35)

Now return back to the case from Example 1 where $A_{1}=(1,0,1,0,\cdots,1,0)$
with length $2n$ and $A_{2}=(1,\cdots,1,0,\cdots,0)$ with length $2m$. For the
sake of simplicity, we will take the symmetric case of $p=q=1/2$. Again define
$\mathcal{E}$ to be the event where $A_{1}$ is observed before $A_{2}$, and
let $P_{1}:=\mathbb{P}(\mathcal{E})$. We can again compute $P_{1}$ by
conditioning on the outcomes of trials, but in this case, both $A_{1}$ and
$A_{2}$ start with $1$. Thus, we instead condition on the outcome of the first
two trials $X_{1}$ and $X_{2}$. To that end, we denote $\mathcal{S}_{1}$ to be
the event that $X_{3}=1,X_{4}=0,\cdots=X_{2n-1}=1,X_{2n}=0$ and
$\mathcal{S}_{2}$ to be the event that
$X_{3}=\cdots=X_{m}=1,X_{m+1}=\cdots=X_{2m}=0$. Thus:

$\displaystyle P_{1}:=\mathbb{P}(\mathcal{E})$
$\displaystyle=p\mathbb{P}(\mathcal{E}|X_{1}=1)+q\mathbb{P}(\mathcal{E}|X_{1}=0)$
$\displaystyle=p\left(p\mathbb{P}(\mathcal{E}|X_{1}=1,X_{2}=1)+q\mathbb{P}(\mathcal{E}|X_{1}=1,X_{2}=0)\right)+q\mathbb{P}(\mathcal{E})$

where $\mathbb{P}(\mathcal{E}|X_{1}=0)=\mathbb{P}(\mathcal{E})$ because
neither $A_{1}$ nor $A_{2}$ start with $0$.

Moreover, conditioning on $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$, we get the
following respective equations:

$\displaystyle\mathbb{P}(\mathcal{E}|X_{1}=1,X_{2}=0)$
$\displaystyle=p^{n-1}q^{n-1}+(1-p^{n-1}q^{n-1})\left[\frac{1}{2}\mathbb{P}(\mathcal{E})+\frac{1}{2}\mathbb{P}(\mathcal{E}|X_{1}=1,X_{2}=1)\right]$
$\displaystyle\mathbb{P}(\mathcal{E}|X_{1}=1,X_{2}=1)$
$\displaystyle=(1-p^{m-2}q^{m})\left[\frac{m-2}{2m-2}\mathbb{P}(\mathcal{E}|X_{1}=1,X_{2}=0)+\frac{m}{2m-2}\mathbb{P}(\mathcal{E}|X_{1}=1)\right]$

Altogether, we obtain a system of three equations with three unknowns.
Substituting $p=q=1/2$ and solving the linear system of equations for
$n=5,m=6$ yields $P_{1,10}=0.7895$, $P_{1,11}=0.7884$, and $P_{1}=0.7889$. For
further details, see [18].

The discussion of the simpler Example 1 and Example 2 segways naturally to
more complicated pattern sequences and broader probability distributions of
$X_{i}$, i.e. those that take more than two values. The next theorem provides
a result for when there is dependence among the values of $X_{i}$.

######  Definition 7 (Pattern Overlap).

For a renewal process $X_{1},X_{2},\cdots$ taking values $x_{1},x_{2},\cdots$
from a certain probability distribution, we say that a pattern
$(x_{(1)},x_{(2)},\cdots,x_{(m)})$ has an overlap of size $k<m$ if

$\displaystyle
k:=\max\\{\ell<m|(x_{1},\cdots,x_{\ell})=(x_{m-\ell+1},\cdots,x_{m})\\}$

That is, $k$ is the largest value such that the first $k$ elements are
identical to the last $k$ elements.

######  Theorem 4 (Pattern Occurrence for Discrete-State Markov Chain).

Let $X_{1},X_{2},\cdots$ denote a sequence of random variables taking values
from a discrete-state Markov Chain with transition probability matrix
$P:=\\{P_{ij}\\}$ and stationary distribution $\\{\pi_{k}\\}$. Let $T$ denote
the next time the pattern $(x_{1},\cdots,x_{m})$ occurs after its first
occurrence. Then:

  * •

When the pattern $(x_{1},\cdots,x_{m})$ does not contain any overlaps. then
the expected time $T$ in between consecutive observations of the pattern is
given by

$\displaystyle\mathbb{E}[T|X_{0}=x_{0}]=\frac{1}{\pi_{x_{1}}\prod\limits_{i=1}^{m-1}P_{x_{i},x_{i+1}}}+\mu(x_{0},x_{1})-\mu(x_{m},x_{1})$
(36)

where $\mu(x,y)$ denotes the mean time it takes to reach state $y$ in the
Markov chain from state $x$.

  * •

When the pattern $(x_{1},\cdots,x_{m})$ has an overlap $(x_{1},\cdots,x_{k})$
of size $k$, and $(x_{1},\cdots,x_{k})$ itself does not contain any overlaps,
then the expected time $T$ in between consecutive observations is given by

$\displaystyle\mathbb{E}[T|X_{0}=x_{0}]=\frac{1}{\pi_{x_{1}}\prod\limits_{i=1}^{m-1}P_{x_{i},x_{i+1}}}+\frac{1}{\pi_{x_{1}}\prod\limits_{i=1}^{k-1}P_{x_{i},x_{i+1}}}+\mu(x_{0},x_{1})-\mu(x_{m},x_{1})$
(37)

######  Example 3 (Theorem 4 for iid Sequence).

We can specialize the results of Theorem 4 to the case where the random
variables $X_{i}$ are iid. Let $X_{1},X_{2},\cdots$ denote a sequence of iid
random variables taking on values from a discrete, finite set $\mathcal{X}$.
Denote $p_{k}:=\mathbb{P}(X_{i}=k)$ for all $i$, and let $T$ denote the next
time the pattern $(x_{1},\cdots,x_{m})$ occurs after its first occurrence.
Then:

  * •

When the pattern $(x_{1},\cdots,x_{m})$ does not contain any overlaps. then
the expected time $T$ in between consecutive observations of the pattern is
given by

$\displaystyle\mathbb{E}[T]=\frac{1}{\prod\limits_{i=1}^{m}p_{x_{i}}}$ (38)

  * •

When the pattern $(x_{1},\cdots,x_{m})$ has an overlap $(x_{1},\cdots,x_{k})$
of size $k$, and $(x_{1},\cdots,x_{k})$ itself does not contain any overlaps,
then the expected time $T$ in between consecutive observations is given by

$\displaystyle\mathbb{E}[T]=\frac{1}{\prod\limits_{i=1}^{m}p_{i}}+\frac{1}{\prod\limits_{i=1}^{k}p_{i}}$
(39)

Note that computing the expected times to between consecutive instances of,
respectively, the $A_{1}$ and $A_{2}$ used in Example 1, we obtain the exact
same formulas (32) and (33) Specifically, $A_{2}$ does not have any overlaps,
which is why $\mathbb{E}[T_{2}]$ can be derived using the formula (38);
$A_{1}$ has overlapping patterns in the form of all length-$2j$ subsequences
of alternating $(1,0)$, for $1\leq j\leq n-1$, and so $\mathbb{E}[T_{1}]$ can
be derived using the formula (39).

######  Remark 1.

Some of the standard references in renewal theory [40, 41, 42] also provide
some discussion on the pattern-occurrence problem from renewal theory, but
often only present the iid case of Example 3. In Theorem 4, we extended this
result to include a possible dependence structure for its relevance to the
specific fault-tolerance and congestion control case studies we investigate
later in Section 4. While a rough sketch of the proof for the iid case Example
3 can be found in [40], we provide a more detailed derivation of the formulas
in our work [18]. The proof to Theorem 4 can also be found in [18].

Furthermore, we can address the question of comparing multiple different
patterns at once. Let $\\{A_{1},\cdots,A_{M}\\}$ for $M\in\mathbb{N}^{+}$ be
$M$ different patterns of interest, and let $T_{A_{i}}$ denote the time it
takes to observe pattern $A_{i}$. Denote
$T_{\text{min}}:=\min\\{T_{A_{1}},\cdots,T_{A_{M}}\\}$ and denote $P_{i}$ to
be the probability of observing pattern $A_{i}$ first at time
$T_{\text{min}}$. We further denote $T_{A_{i}|A_{j}}$ to be the additional
time it takes to observe the pattern $A_{i}$ after $A_{j}$ has been observed.
We are interested in computing the $P_{i}$ and $\mathbb{E}[T_{\text{min}}]$.

We further denote $T_{A_{i}|A_{j}}$ to be the additional time it takes to
observe sequence $A_{i}$ given that we’ve already observed $A_{j}$, for all
$i\neq j$. Since all the patterns $\\{A_{1},\cdots,A_{M}\\}$ are known, both
$\mathbb{E}[T_{A_{i}}]$ and $\mathbb{E}[T_{A_{i}|A_{j}}]$ can be computed
using either Theorem 4 or Example 3. We can then derive a system of equations
with these variables as follows:

$\displaystyle\mathbb{E}[T_{A_{k}}]$
$\displaystyle=\mathbb{E}[T_{\text{min}}]+\mathbb{E}[T_{A_{k}}-T_{\text{min}}]=\mathbb{E}[T_{\text{min}}]+\sum\limits_{j\neq
k}\mathbb{E}[T_{A_{k}|A_{j}}]P_{j}+0\cdot P_{k}$

which, combined with the constraint that $P_{M}:=1-\sum_{i<M}P_{i}$ yields $M$
linear equations with $M$ unknowns
$P_{1},\cdots,P_{M-1},\mathbb{E}[T_{\text{min}}]$. For the case where $M=2$,
we obtain the explicit formula:

$\displaystyle P_{1}$
$\displaystyle=\frac{\mathbb{E}[T_{A_{2}}]+\mathbb{E}[T_{A_{1}|A_{2}}]-\mathbb{E}[T_{A_{1}}]}{\mathbb{E}[T_{A_{2}|A_{1}}]+\mathbb{E}[T_{A_{1}|A_{2}}]},\qquad\mathbb{E}[T_{\text{min}}]=\mathbb{E}[T_{A_{2}}]-\mathbb{E}[T_{A_{2}|A_{1}}]P_{1}$
(40)

In relation to Example 2, applying (40) to the case where $A_{1}$ is $n$
consecutive $1$’s and $A_{2}$ is $m$ consecutive $0$’s yields the desired
result (35). Likewise, applying (40) to the case where
$A_{1}:=(1,0,\cdots,1,0)$ and $A_{2}:=(1,\cdots,1,0,\cdots,0)$ with $n=5,m=6$
implies that $\mathbb{E}[T_{A_{1}|A_{2}}]=\mathbb{E}[T_{A_{1}}]$ and
$\mathbb{E}[T_{A_{2}|A_{1}}]=\mathbb{E}[T_{A_{2}}]$. With $p=q=1/2$, we obtain
the numerical values derived at the end of Example 2.

######  Remark 2 (Alternative Pattern-Occurrence Problem with Random Walks).

If we are interested in keeping track of longer pattern sequences of impulsive
disturbances, the pattern-occurrence problem can also be solved using an
alternative approach with random walks. Borrowing influence from common
motivational problems such as the Gambler’s Ruin problem, the theory of random
walks can be used to determine the expected time it takes the system to reach
certain boundaries imposed on the system state, upon which the modulation
control mechanism takes over. For the sake of keeping this paper focused, we
defer discussion of the connections between the pattern-occurrence problem and
the theory of random walks to [18]. A comprehensive treatment of random walk
theory background needed to understand these connections can also be found in
[18].

##  3 The Modulation Control Component

In this section, we describe the second part of the controller synthesis
procedure: the development of the actual control action to be taken when a
specific state is first recognized by the first part learning component,
especially during the event where a recognized pattern sequence of impulsive
jumps causes the system to grow more and more unstable. This requires explicit
formulation of the problem as an optimal control problem with corresponding
performance objectives, and there is a wide diversity of modulation-type
controllers that can be used in place of this second part depending on the
kind of application considered. For the purposes of the specific fault-
tolerance and congestion control applications that we investigate in the next
Section 4, we introduce the impulse control method, which is a Hamilton-
Jacobi-Bellman-based control for jump-diffusion processes that has been
described in several references such as [33, 13] and used for financial
applications. Roughly speaking, the impulse control methodology forces the
state of the system down to some safer, lower-energy state once it exceeds a
prespecified limit determined by the first part of the hierarchical
controller. This section adapts the general theory of the impulse control
framework from [33, 13] so that we can directly use it to the specific case
examples to be studied in Section 4.

###  3.1 Stochastic Processes Review

The general Poisson random measure, typically denoted $N(dt,dy)$ over the
space $[0,t]\times E$ with “jump space” $E$, is characterized by the intensity
measure Leb$\times\nu$, where Leb denotes the standard Lebesgue measure in
time and $\nu(dy)$ is the probability measure on $E$ describing the
distribution of jumps. The formal definition of the Poisson random measure can
be found in Theorem 2.3.5 in [1] or Definition 3.1 in [50], and other standard
texts pertaining to Poisson processes.

A process $L(t)$ is said to be a Lévy process if 1) all paths of $L$ are
right-continuous and left-limit (rcll), 2) $\mathbb{P}(L(0)=0)=1$, and 3) $L$
has stationary and independent increments [50, 20]. This implies that both
Gaussian white noise processes and compound Poisson processes are Lévy
processes, and that the affine combination of the two, such as the process
described in (4), is also a Lévy process. In fact, a well-known result called
the Lévy-Khintchine Theorem, stated formally in Theorem 1.6 of [50], Theorem
2.7 of [4], or Theorem 1.2.14 of [2], says that Lévy measures can be
represented as weak limits of the convolution of Brownian motion processes and
Poisson random measures. This even includes the Lévy process whose intensity
measure has unbounded jumps; one common example is a Gamma process, which has
intensity measure on $\mathbb{R}^{+}$ given by $\nu(dy)=ay^{-1}e^{-by}dy$ such
that on any finite interval of time, the number of jumps which lies in the
interval $(0,1)$ is infinite. We do not consider such types of Lévy processes
in this paper, since they rarely occur in the practical control and
engineering applications of our target scope. Throughout this paper, we
henceforth use the phrase “Lévy noise processes” specifically to refer only to
the class of bounded-measure Lévy processes of the linear combination form in
(4).

######  Lemma 5 (Itô’s Formula for 1D Jump-Diffusion Processes).

Consider the SDE

$\displaystyle dX(t)=f(t)dt+\sigma(t)dW(t)+\int_{\mathbb{R}}\xi(t,z)N(dt,dz)$
(41)

where $X(t)\in\mathbb{R}$. Then for functions $F\in\mathcal{C}^{(1,2)}$, the
derivative is given by

$\displaystyle dF(t,X(t))$
$\displaystyle=\partial_{t}F(t,X(t))dt+\partial_{x}F(t,X(t))dX(t)+\frac{1}{2}\partial_{x}^{2}F(t,X(t))d[X,X](t)$
$\displaystyle=\partial_{t}F(t,X(t))dt+\partial_{x}F(t,X(t))dX^{c}(t)+\frac{1}{2}\partial_{x}^{2}F(t,X(t))d[X,X]^{c}(t)$
$\displaystyle\hskip
28.45274pt+\int_{\mathbb{R}}\left[F(t,X(t)+z)-F(t,X(t))\right]N(dt,dz)$ (42)

where $dX^{c}(t)$ represents the continuous part of the SDE, and
$d[X,X]^{c}(t)$ represents the continuous part of the quadratic variation.

###### Proof.

We provide a proof of Itô’s formula which is simpler than the version
presented in [37]. Note that by integration-by-parts,

$\displaystyle d(X(t)Y(t))=X(t-)dY(t)+Y(t-)dX(t)+d[X,Y](t)$
$\displaystyle\Longrightarrow\ $
$\displaystyle[X,Y](t)=X(t)Y(t)-\int_{0}^{t}X(s-)dY(s)+Y(s-)dX(s)$

where $X(t)$ and $Y(t)$ are two separate stochastic processes and
subsequently,

$\displaystyle[X,X](t)=X^{2}(t)+2\int_{0}^{t}X(s-)dX(s)$

Hence

$\displaystyle\Delta[X,X](t)$ $\displaystyle=\Delta(X^{2}(t))+2X(t-)\Delta
X(t)$ $\displaystyle=X^{2}(t)-X^{2}(t-)+2X(t-)(X(t)-X(t-))=\left(\Delta
X(t)\right)^{2}$

Recall the second-order Taylor expansion for $F\in\mathcal{C}^{2}$. We further
assume $x\leq y$:

$\displaystyle F(y)-F(x)$
$\displaystyle=\partial_{x}F(x)(y-x)+\frac{1}{2}\partial_{x}^{2}F(x)(y-x)^{2}+R(y,x)$

where the remainder term $R(y,x)$ can be written as

$\displaystyle R(y,x)=\frac{\partial_{x}^{3}(z)}{3!}(y-x)^{3}\text{ for some
}z\in(x,y)$

Now let $\mathcal{P}_{n}:=\\{0=:T_{0}^{n}\leq T_{1}^{n}\leq\cdots\leq
T_{m_{n}}^{n}:=t\\}$ be a partition of the time interval $[0,t]$. We can then
write the difference as the sum

$\displaystyle
F(X(t))-F(x_{0})=\sum\limits_{i=0}^{m_{n}-1}\left[F(X(T_{i+1}^{n}))-F(X(T_{i}^{n}))\right]$
(43)

We split the analysis into two cases

  * •

Continuous Case: When $X(t)$ is the state of a SDE which only has continuous
terms, we can use Taylor’s formula to expand every term in the sum (43):

$\displaystyle(\ref{eq:riemann_sum_ito_proof})$
$\displaystyle=\sum\limits_{i=0}^{m_{n}-1}\partial_{x}F(X(T_{i}^{n}))(X(T_{i+1}^{n})-X(T_{i}^{n}))$
$\displaystyle\hskip
28.45274pt+\frac{1}{2}\sum\limits_{i=0}^{m_{n}-1}\partial_{x}^{2}F(X(T_{i}^{n}))\left(X(T_{i+1}^{n})-X(T_{i}^{n})\right)^{2}$
$\displaystyle\hskip
28.45274pt+\sum\limits_{i=0}^{m_{n}-1}R(X(T_{i+1}^{n}),X(T_{i}^{n}))$

and as $n\to\infty$, i.e., as the interval size between partitions decreases
to $0$,

$\displaystyle\sum\limits_{i=0}^{m_{n}-1}\partial_{x}F(X(T_{i}^{n}))(X(T_{i+1}^{n})-X(T_{i}^{n}))$
$\displaystyle\to\int_{0}^{t}\partial_{x}F(X(s-))dX(s)$
$\displaystyle\frac{1}{2}\sum\limits_{i=0}^{m_{n}-1}\partial_{x}^{2}F(X(T_{i}^{n}))\left(X(T_{i+1}^{n})-X(T_{i}^{n})\right)^{2}$
$\displaystyle\to\frac{1}{2}\int_{0}^{t}\partial_{x}^{2}F(X(s-))d[X,X](s)$

and $R(X(T_{i+1}^{n}),X(T_{i}^{n}))\to 0$ since

$\displaystyle
R(X(T_{i+1}^{n}),X(T_{i}^{n}))\propto(X(T_{i+1}^{n})-X(T_{i}^{n}))^{3}\text{
and }X(T_{i+1}^{n})-X(T_{i}^{n})\to 0\text{ as }n\to\infty$

With the terms all combined altogether

$\displaystyle
F(X(t))-F(x_{0})=\int_{0}^{t}\partial_{x}F(X(s-))dX(s)+\frac{1}{2}\int_{0}^{t}\partial_{x}^{2}F(X(s-))d[X,X](s)$
(44)

which is indeed the Itô formula when the SDE contains only continuous terms.

  * •

General Semimartingale Case: We split the intervals of the partition into two
pieces: $\mathcal{P}_{n}^{+}$ is the subset of the subintervals over which the
trajectory $X(t)$ contains a jump of size at least $0<\varepsilon<<1$ and
$\mathcal{P}_{n}^{-}:=\mathcal{P}_{n}/\mathcal{P}_{n}^{+}$ is the subset of
subintervals over which the trajectory $X(t)$ is completely continuous.

$\displaystyle\mathcal{P}_{n}^{+}:=\\{T_{i}^{n}\ |\ \exists
s\in(T_{i}^{n},T_{i+1}^{n}]\ \text{ s.t. }\ \lvert
X(s)-X(s-)\rvert>\varepsilon\\}$

Then we split the sum (43) into two parts:

$\displaystyle(\ref{eq:riemann_sum_ito_proof})$
$\displaystyle=\sum\limits_{i\in\mathcal{P}_{n}^{+}}^{m_{n}-1}\left[F(X(T_{i+1}^{n}))-F(X(T_{i}^{n}))\right]+\sum\limits_{i\in\mathcal{P}_{n}^{-}}^{m_{n}-1}\left[F(X(T_{i+1}^{n}))-F(X(T_{i}^{n}))\right]$

Note that as $n\to\infty$, the second collective summation term can be reduced
to the Continuous Case analyzed previously, with a superscript of $c$ appended
to the $dX$ and $d[X,X]$ terms to distinguish the continuous part from the
discontinuous part. Furthermore, as $n\to\infty$, the first collective sum
converges as follows

$\displaystyle\sum\limits_{i\in\mathcal{P}_{n}^{+}}^{m_{n}-1}\left[F(X(T_{i+1}^{n}))-F(X(T_{i}^{n}))\right]\to\sum_{0\leq
s\leq t}\left[F(X(s))-F(X(s-))\right]$

With all the terms combined together, we obtain the Itô formula described in
(5). This concludes the proof. ∎

We further define the compensated Poisson random measure as
$\tilde{N}(dt,dz):=N(dt,dz)-\nu(dz)dt$, where
$\nu(dz)dt:=\mathbb{E}\left[N(dt,dz)\right]$. We often care about the
compensated Poisson random measure more than the original measure $N$ because
it is mean zero. For jump-diffusions of the form

$\displaystyle dX(t)$
$\displaystyle=f(t)dt+\sigma(t)dW(t)+\int_{\mathbb{R}}\xi(t,z)\tilde{N}(dt,dz)$
$\displaystyle=\left(f(t)-\int_{\mathbb{R}}\xi(t,z)\nu(dz)\right)dt+\sigma(t)dW(t)+\int_{\mathbb{R}}\xi(t,z)N(dt,dz)$
(45)

the Itô formula is written as follows

$\displaystyle dF(t,X(t))$
$\displaystyle=\left(\partial_{t}F(t,X(t))+\partial_{x}F(t,X(t))f(t)+\frac{1}{2}\partial_{x}^{2}F(t,X(t))\sigma^{2}(t)\right)dt$
$\displaystyle\hskip
28.45274pt+\int_{\mathbb{R}}\left[F(t,X(t)+z)-F(t,X(t))-\partial_{x}F(t,X(t))\xi(t,z)\right]\nu(dz)dt$
$\displaystyle\hskip
28.45274pt+\partial_{x}F(t,X(t))\sigma(t)dW(t)+\int_{\mathbb{R}}\left[F(t,X(t)+z)-F(t,X(t))\right]N(dt,dz)$

######  Definition 8 (Infinitesimal Generator).

For $F\in\mathcal{C}^{(1,2)}$, the infinitesimal generator is defined to be

$\displaystyle\mathcal{L}F(x)=\lim_{t\to
0}\frac{\mathbb{E}_{x}\left[F(X(t))\right]-F(x)}{t}$

where $\mathbb{E}_{x}[F(X(t))]$ denotes the expected value of $F(X(t))$
evaluated with initial condition $X(0)=x$.

From Itô’s formula, we can determine the form of the infinitesimal generator
for the SDE (41). Note that because the integral with respect to the white
noise process $W(t)$ and the integral with respect to the compensated Poisson
process $\tilde{N}$ are martingales

$\displaystyle\mathcal{L}F(x)=\partial_{t}F(t,X(t))+\partial_{x}F(t,X(t))f(t)+\frac{1}{2}\partial_{x}^{2}F(t,X(t))\sigma^{2}(t)$

######  Theorem 5 (Dynkin’s Formula).

For $X(t)$ a trajectory of (41) and $\varphi\in\mathcal{C}^{2}$, the following
equality holds:

$\displaystyle\mathbb{E}_{x}\left[\varphi(X(t))\right]=\varphi(x)+\mathbb{E}_{x}\left[\int_{0}^{\tau_{S}}\mathcal{L}\varphi(X(s))ds\right]$

###  3.2 The Impulse Control Method

Consider the following Lévy noise system, assuming the control input enters
into the system additively

$\displaystyle d{\bf x}(t)=f({\bf x}(t))dt+\sigma({\bf
x}(t))dW(t)+\int_{\mathbb{R}^{\ell}}\xi({\bf x}(t-),z)\tilde{N}(dt,dz)+u(t)dt$

An impulse control law is defined to be a sequence of intervention times and
corresponding impulse heights
$u:=(\tau_{1},\tau_{2},\cdots;z_{1},z_{2},\cdots)$ such that the closed-loop
system state ${\bf x}_{u}(t)$ abides by the following dynamics:

$\displaystyle{\bf x}_{u}(0-)$ $\displaystyle=y$ $\displaystyle d{\bf
x}_{u}(t)$ $\displaystyle=f({\bf x}_{u}(t))dt+\sigma({\bf
x}_{u}(t))dW(t)+\int_{\mathbb{R}^{\ell}}\xi({\bf
x}_{u}(t-),z)\tilde{N}(dt,dz)+\sum\limits_{j}\mathds{1}\\{t-\tau_{j}\\}z_{j}$

As with many standard optimal control problems, we seek to find an optimal
impulse control law which minimizes a certain cost. To this end, we denote the
augmented state ${\bf y}(t):=(t,{\bf x}(t))^{T}$. Define the cost-to-go
function $\ell({\bf y})$ and the terminal cost $g({\bf y}(t))$. Further denote
the cost of making an intervention with impulse $z$ and state $y$ as $K({\bf
y},z)$. Then the overall performance objective to minimize is as follows:

$\displaystyle J_{u}(y)=\mathbb{E}_{y}\left[\int_{0}^{\tau_{S}}\ell({\bf
y}_{u}(t))dt+g({\bf
y}_{u}(\tau_{S}))\mathds{1}\\{\tau_{S}<\infty\\}+\sum\limits_{\tau_{j}\leq\tau_{S}}K({\bf
y}_{u}(\tau_{j}),z_{j})\right]$

where $\tau_{S}$ is the (possibly infinite) stopping time of the system and
$y$ is the initial state.

As is standard in many Hamilton-Jacobi optimal control approaches, the problem
is posed as the following minimization scheme: we want to find $\Phi(y)$ and
$u^{*}\in\mathcal{U}$ such that

$\displaystyle\Phi(y):=\inf_{u\in\mathcal{U}}J_{u}(y)=J_{u^{*}}(y)$

A verification theorem provides for a tractable way to iteratively design such
a $u^{*}$ with guaranteed optimality. A more general version of the
verification theorem with certain continuity, differentiability, and
convergence conditions imposed on any candidate value function
$\varphi:\mathbb{R}^{+}\times\mathbb{R}^{n}\to\mathbb{R}^{\geq 0}$ such that
$\varphi(y)\geq\Phi(y)$ for all $y$ is presented in [33, 13], but it is too
complex for the purposes of our controller synthesis procedure. Theorem 6
introduces a simplified version of the verification theorem. For the case
studies we investigate in Section 4, any candidate value function that we
consider immediately satisfies the continuity, differentiability, and
convergence conditions imposed in the general statement from [33, 13]; we thus
remove explicit mention of these conditions. More importantly, Theorem 6
yields a variational inequality that is easier to solve. For simplicity of
notation, the verification theorem is presented with the state space taken to
be the real line ($\ell=1$) with the notation $Y(t):={\bf y}(t)$ and
$Y_{u}(t):={\bf y}_{u}(t)$, but extension to multiple dimensions is
straightforward.

######  Theorem 6 (Verification Theorem).

Define

$\displaystyle\mathcal{M}\varphi(y):=\inf_{z\in\mathbb{R}}\left\\{\varphi(y+z)+K(y,z)\right\\}$

for Borel-measurable, twice continuously-differentiable function $\varphi$.

  1. A.

Suppose

    1. (a)

$\mathcal{L}\varphi(y)+\ell(y)\leq 0$ for all $y\in D$ where
$D:=\\{y\in\mathbb{R}|\varphi(y)\geq\mathcal{M}\varphi(y)\\}$

    2. (b)

$\varphi(Y(t))\to g(Y(\tau_{S}))\mathds{1}\\{\tau_{S}<\infty\\}$ as
$t\to\tau_{S}$

Then $\varphi(y)\geq\Phi(y)$ for all $y\in\mathbb{R}$.

  2. B.

Put $\tau_{0}=0$ and construct $\hat{u}$ inductively by

$\displaystyle\hat{\tau}_{j+1}$
$\displaystyle=\min\\{\tau_{S},\inf\\{t>\hat{\tau}_{j}|Y_{\hat{u}_{j}}(t)\not\in
D\\}\\}$ $\displaystyle\hat{z}_{j+1}$
$\displaystyle=\hat{\zeta}(Y_{\hat{u}_{j}}(\hat{\tau}_{j+1}-))$

where $\hat{\zeta}(y)\in\text{argmin}_{z}\mathcal{M}\varphi(y)$ and
$Y_{\hat{u}_{j}}$ is the result of applying
$\hat{u}_{j}:=(\tau_{1},\cdots,\tau_{j};z_{1},\cdots,z_{j})$ to $Y$.

Suppose that in addition to A, we have

    1. (a)

$\mathcal{L}\varphi(y)+\ell(y)=0$ for all $y\in D$

    2. (b)

$\hat{u}\in\mathcal{U}$ and $\\{\varphi(Y_{\hat{u}}(t))\\}$ is uniformly
integrable.

Then $\varphi(y)=\Phi(y)$ for all $y\in\mathbb{R}$.

###### Proof.

To prove part A, we recall Dynkin’s formula from Theorem 5. Applying this
formula to consecutive intervals $[\tau_{j},\tau_{j+1})$ which each contain a
single impulse jump yields:

$\displaystyle\mathbb{E}_{y}\left[\varphi(Y_{u}(\tau_{j+1}-))\right]-\mathbb{E}_{y}\left[\varphi(Y_{u}(\tau_{j}))\right]=\mathbb{E}_{y}\left[\int_{\tau_{j}}^{\tau_{j+1}}\mathcal{L}\varphi(Y_{u}(s))ds\right]$

Fix a specific $m\in\mathbb{N}^{+}$. Then summing all equations of the above
form from $j=0$ to $m$ gives

$\displaystyle-\varphi(y)-\sum\limits_{j=1}^{m}\mathbb{E}_{y}\left[\varphi(Y_{u}(\tau_{j}))-\varphi(Y_{u}(\tau_{j}-))\right]+\mathbb{E}_{y}\left[\varphi(Y_{u}(\tau_{m+1}-))\right]=\mathbb{E}_{y}\left[\int_{0}^{\tau_{m+1}}\mathcal{L}\varphi(Y_{u}(s))ds\right]$
(46)

By definition of $\mathcal{M}$, we have

$\displaystyle\mathcal{M}\varphi(Y_{u}(\tau_{j}-))\leq\varphi(Y_{u}(\tau_{j}))+K(Y_{u}(\tau_{j}-),z_{j})$

and subtracting both sides by $\varphi(Y_{u}(\tau_{j}-))$:

$\displaystyle\mathcal{M}\varphi(Y_{u}(\tau_{j}-))-\varphi(Y_{u}(\tau_{j}-))\leq\varphi(Y_{u}(\tau_{j}))-\varphi(Y_{u}(\tau_{j}-))+K(Y_{u}(\tau_{j}-),z_{j})$
(47)

Substituting the left side of (47) into (46) and multiplying the inequality
throughout by $-1$:

$\displaystyle\varphi(y)+\sum\limits_{j=1}^{m}\mathbb{E}_{y}\left[\mathcal{M}\varphi(Y_{u}(\tau_{j}-))-\varphi(Y_{u}(\tau_{j}-))-K(Y_{u}(\tau_{j}-),z_{j})\right]$
$\displaystyle\hskip
28.45274pt-\mathbb{E}_{y}\left[\varphi(Y_{u}(\tau_{m+1}-))\right]\geq-\mathbb{E}_{y}\left[\int_{0}^{\tau_{m+1}}\mathcal{L}\varphi(Y_{u}(s))ds\right]$
(48)

Using the first condition, we have

$\displaystyle\sum\limits_{j=1}^{m}\mathbb{E}_{y}\left[\mathcal{M}\varphi(Y_{u}(\tau_{j}-))-\varphi(Y_{u}(\tau_{j}-))\right]\leq
0$
$\displaystyle-\mathbb{E}_{y}\left[\int_{0}^{\tau_{m+1}}\mathcal{L}\varphi(Y_{u}(s))ds\right]\geq\mathbb{E}_{y}\left[\int_{0}^{\tau_{m+1}}\ell(Y_{u}(s))ds\right]$

which transforms (3.2) to

$\displaystyle\varphi(y)\geq\mathbb{E}_{y}\left[\int_{0}^{\tau_{m+1}}\ell(Y_{u}(s))ds\right]+\mathbb{E}_{y}\left[\varphi(Y_{u}(\tau_{m+1}-))\right]+\sum\limits_{j=1}^{m}\mathbb{E}_{y}\left[K(Y_{u}(\tau_{j}-),z_{j})\right]$
(49)

Taking $m\to\infty$, i.e. $t\to\tau_{S}$, and applying it to (49) gives

$\displaystyle\varphi(y)\geq\mathbb{E}_{y}\left[\int_{0}^{\tau_{S}}\ell(Y_{u}(s))ds+g(\tau_{S})\mathds{1}\\{\tau_{S}<\infty\\}+\sum\limits_{\tau_{j}<\tau_{S}}K(Y_{u}(\tau_{j}-),z_{j})\right]=:\Phi(y)$

and this proves part A of the theorem. To prove part B, we can simply repeat
the proof of part A while replacing every inequality with an equality, which
comes from the conditions of part B in the theorem’s hypothesis. ∎

Overall, the optimal value function $\Phi(y)$ should satisfy the following
variational inequality for all $y\in\mathbb{R}$.

$\displaystyle\max\\{\mathcal{L}\varphi(y)+\ell(y),\varphi(y)-\mathcal{M}\varphi(y)\\}=0$

Further illustrative examples demonstrating how to apply the impulse control
method for certain jump-diffusion systems is presented in our textbook
preprint [18]. For additional background on the connection between the impulse
control approach and other standard Hamilton-Jacobi-Bellman optimal control
methods, we refer the interested reader to [18].

##  4 Application Case Studies

###  4.1 Incremental Stability for Jump-Linear System

Now that we have established the relevant theory for the proposed two-part
controller, we demonstrate its usage using shot-noise-modified extensions of
two simple scalar systems which are commonly studied in the field of
stochastic processes. In both examples, stability bounds are explicitly
computed using the framework discussed in our first part of this paper [19],
then used as the certified safety bound which determines the threshold at
which the system transitions between two independent controllers. This
hierarchical layering of controllers is motivated by spacecraft control
applications [16, 49, 27], which manipulates the thrusters by switching
between different flight control systems depending on factors such as how far
away the system is from a desired trajecory or how close the system is to an
impending meteorite strike. When the system remains within the safety region,
a lower-level controller (e.g., a reference-tracking controller) drives the
trajectory. Moreover, previous incremental stability results for deterministic
[29] and Gaussian white noise-perturbed systems [12] show that such systems
are guaranteed to remain within the safety region. Hence, for our systems of
consideration, (3) and (4), the shot noise component of the noise process is
arguably the main cause of destabilization in the system. Thus, when the
system no longer remains within the safety region, the two-part controller is
used to first identify the sequence of impulsive disturbances which caused the
destabilization, then steer the trajectory back to within the safety region.

The first scalar system of our study is as follows. We assume the control
input enters into the system additively. It can be viewed as the Ornstein-
Uhlenbeck process [32] augmented with shot noise instead of the usual white
noise:

$\displaystyle dx(t)=ax(t)dt+u(t)dt+\xi\int_{\mathbb{R}}zN(dt,dz)$ (50)

where $a\neq 0$, $\xi>0$ are constants, and $N(dt,dz)$ is a 1D Poisson random
measure with rate $\lambda>0$ and jump height distribution as a Bernoulli
random variable which takes value $\eta>0$ with probability $p$, and $-\eta$
with probability $q:=1-p$. As motivated above, we distinguish the control law
into two parts

$\displaystyle
u(t):=\mathds{1}\\{x(t)\in\mathcal{S}\\}u_{\ell}(t)+\mathds{1}\\{x(t)\not\in\mathcal{S}\\}u_{tp}(t)$

where $\mathcal{S}\subset\mathbb{R}$ defines the safety region computed from
the bound of [19], $u_{\ell}(t)$ describes the lower-level controller, and
$u_{tp}(t)$ describes the two-part controller. For the purposes of keeping the
discussion relevant to the paper, we focus on the degisn and impact of
$u_{tp}(t)$ on the system and assume that $u_{\ell}(t)$ is already given. One
possible choice is a reference-tracking controller designed to track some
reference trajectory $x_{r}(t)$:

$\displaystyle u_{\ell,r}(t)=\dot{x}_{r}(t)-ax_{r}(t),\qquad
u_{\ell}(t)=u_{\ell,r}(t)-k(x(t)-x_{r}(t))$ (51)

and gain $k>\lvert a\rvert$.

We now explicitly compute the form of the safety region $\mathcal{S}$. The
contraction metric $M(t,x)$ is chosen to be the identity $1$, meaning
$\overline{m}=\underline{m}=1$, and we have contraction rate $\alpha:=\lvert
a\rvert$. We substitute only the lower-level controller $u_{\ell}(t)$ into
(50) for the computation of the stability bound, with the interpretation being
that we want to determine the local extent of which the lower-level controller
is able to handle the system.

$\displaystyle x(t)$
$\displaystyle=x_{0}e^{(a-k)t}+\int_{0}^{t}\left(u_{r}(t)+kx_{r}(t)\right)e^{(a-k)(t-s)}ds+\int_{0}^{t}\int_{\mathbb{R}}\xi
ze^{(a-k)(t-s)}N(ds,dz)$

A trajectory of the noiseless system is given by

$\displaystyle y(t)$
$\displaystyle=y_{0}e^{(a-k)t}+\int_{0}^{t}\left(u_{r}(t)+kx_{r}(t)\right)e^{(a-k)(t-s)}ds$

Taking the mean-squared difference between $x(t)$ and $y(t)$ yields:

$\displaystyle\mathbb{E}\left[\lvert
y(t)-x(t)\rvert^{2}\right]\leq\mathbb{E}\left[\lvert
y_{0}-x_{0}\rvert^{2}\right]e^{2(a-k)t}+\kappa_{s}(2(a-k),t)$ (52)

with steady-state error bound

$\displaystyle\kappa_{s}(2(a-k),t)$
$\displaystyle=2e^{(a-k)t}\mathbb{E}\left[\lvert
y_{0}-x_{0}\rvert\right]\mathbb{E}\left[\left\lvert\int_{0}^{t}\int_{\mathbb{R}}\xi
ze^{(a-k)(t-s)}N(ds,dz)\right\rvert\right]$ $\displaystyle\hskip
28.45274pt+\mathbb{E}\left[\left\lvert\int_{0}^{t}\int_{\mathbb{R}}\xi
ze^{(a-k)(t-s)}N(ds,dz)\right\rvert^{2}\right]$ $\displaystyle\leq 2\xi
e^{(a-k)t}c_{0}\mathbb{E}\left[\int_{0}^{t}\int_{\mathbb{R}}\left\lvert
ze^{(a-k)(t-s)}\right\rvert N(ds,dz)\right]$ $\displaystyle\hskip
28.45274pt+\xi^{2}\mathbb{E}\left[\int_{0}^{t}\int_{\mathbb{R}}\left\lvert
ze^{(a-k)(t-s)}\right\rvert^{2}N(ds,dz)\right]$ (53)

where $c_{0}>0$ is the length of the compact support of the probability
distribution where the initial conditions $x_{0},y_{0}$ are drawn from, and
the second inequality follows from the Cauchy-Schwarz Inequality. Note that
the Poisson integrals in the two terms can be evaluated using Campbell’s
formula (presented in Section 3.2 of [26] and Proposition 2.7 of [28]) and the
definition of the Poisson integral from Section 2.3.2 of [1]:

$\displaystyle\mathbb{E}\left[\int_{0}^{t}\int_{\mathbb{R}}\left\lvert
ze^{(a-k)(t-s)}\right\rvert N(ds,dz)\right]$
$\displaystyle=\int_{0}^{t}e^{(a-k)(t-s)}\int_{\mathbb{R}}\lvert
z\rvert\nu(dz)ds=\frac{\eta}{a-k}(e^{(a-k)t}-1)$
$\displaystyle\mathbb{E}\left[\int_{0}^{t}\int_{\mathbb{R}}\left\lvert
ze^{(a-k)(t-s)}\right\rvert^{2}N(ds,dz)\right]$
$\displaystyle=\int_{0}^{t}e^{(a-k)(t-s)}\int_{\mathbb{R}}z^{2}\nu(dz)ds=\frac{\eta^{2}}{2(a-k)}(e^{2(a-k)t}-1)$

and substituting back into (4.1) yields:

$\displaystyle(\ref{eq:1Dlqr_kappa_unsimp})$ $\displaystyle\leq\frac{2\xi\eta
c_{0}}{a-k}(e^{2(a-k)t}-e^{(a-k)t})+\frac{\xi^{2}\eta^{2}}{2(a-k)}(e^{2(a-k)t}-1)$
(54)

We simulate (50) using the state-feedback lower-level controller to track the
zero reference line (i.e., perform disturbance rejection), and visualize our
results in Figure 2 for three values of $\lambda\in\\{2,1,0.5\\}$. For each
$\lambda$ value, we simulate three sample trajectories (in three different
shades of gray) representing the mean-squared-difference $\lvert
y(t)-x(t)\rvert^{2}$. The initial conditions $x_{0}$ and $y_{0}$ are sampled
uniformly in the range $[0,2]$. For each subfigure, plotted in black-dashed
line with their respective colors is the upper-bound of the envelope captured
by the theoretical bound of $\kappa_{s}(-2(a-k),t)$ provided by (54). Notice
that it is entirely feasible for the shot noise perturbations to bring each
trajectory outside of the safety envelope, upon which we allow the two-part
controller to take over and steer the system back to within the envelope. Note
that we achieve global exponential convergence for the system because of its
simplified linear nature, so the lower-level controller manages to stabilize
the system even while it is outside of the safety envelope by itself. However,
we can still demonstrate the procedure of using the learning component of the
two-part controller for determining re-ocurring jump patterns on this system;
in our second example, we add Gaussian white noise to the dynamics so that the
necessity of the two-part controller is more apparent.

Figure 2: Three sample absolute MSE differences (in varying shades of gray)
between the trajectory of a stable linear system and the trajectory of the
system with additive shot noise for varying values of $\lambda$. For each
subplot corresponding to $\lambda$, the black-dashed line shows the outline of
the envelope captured by the theoretical error bound derived as in (52).

We assume that a given specific pattern sequence of jump sizes leads to
instability in the system. In this simple setup, the learning component
approximates variations in the interarrival time between consecutive jumps
using various zero paddings. What is the number of jumps $T$ after which the
exact pattern sequence of jumps will occur again? For concreteness, we focus
on the specific pattern of $(1,2,1)$ with $M=9$. Then

$\displaystyle\mathbb{E}[T]=\frac{1}{p_{1}^{2}p_{2}}+\frac{1}{p_{1}}$ (55)

By symmetry of the problem, negative valued jumps should also be considered,
i.e. $(-1,-2,-1)$. In this case, we compute $\mathbb{E}[T]$ by conditioning
using the same methodology described in Section 2.2. Denote $A:=(1,2,1)$ and
$B:=(-1,-2,-1)$ and use the notation $T[(*)]:=\mathbb{E}[T(*)]$ and
$T[\text{min}]:=\mathbb{E}[T_{\text{min}}]$ for simplicity. Similar to (55),
we get:

$\displaystyle T[A]=\frac{1}{p_{1}^{2}p_{2}}+\frac{1}{p_{1}},\ \
T[B]=\frac{1}{p_{-1}^{2}p_{-2}}+\frac{1}{p_{-1}}$

and because there is no overlap between $A$ and $B$, the conditional
quantities are exactly the same as the original quantities: $T[B|A]=T[B]$ and
$T[A|B]=T[A]$.

Denote $P_{A}$ to be the probability that the string sequence $A$ occurs
before $B$. Then the renewal time in between consecutive unstable jump
sequences is given by $T_{\text{min}}:=\min\\{T_{A},T_{B}\\}$, which can be
obtained according to Section 2.2.

Now, further note that the order of the jump sizes also does not matter, since
it is the cumulative sum of the jump sizes which impacts the system trajectory
(again, assuming the interarrival times between consecutive jumps are not
accounted for). Hence, all three combinations for $(1,2,1)$ and $(-1,-2,-1)$
should be taken into consideration. For the moment, we will only consider the
permutations of $(1,2,1)$. Define $A:=(1,2,1)$, $B:=(1,1,2)$, and
$C:=(2,1,1)$. $T_{\text{min}}:=\min\\{T(A),T(B),T(C)\\}$. Computing the
expected renewal time $T[\text{min}]$ only requires a slight extension to the
procedure of Section 2.2, but the idea is the same.

Note that

$\displaystyle T[A]=\frac{1}{p_{1}^{2}p_{2}}+\frac{1}{p_{1}},\qquad
T[B]=T[C]=\frac{1}{p_{1}^{2}p_{2}}$

and

$\displaystyle T[A|B]=T[A],$ $\displaystyle\qquad
T[A|C]=T[A]-T[(1)]=\frac{1}{p_{1}^{2}p_{2}}$ $\displaystyle
T[B|A]=T[B]-T[(1)]=\frac{1}{p_{1}^{2}p_{2}}-\frac{1}{p_{1}},$
$\displaystyle\qquad
T[B|C]=T[B]-T[(1,1)]=\frac{1}{p_{1}^{2}p_{2}}-\frac{1}{p_{1}^{2}}-\frac{1}{p_{1}}$
$\displaystyle T[C|A]=T[C],$ $\displaystyle\qquad
T[C|B]=T[C]-T[(2)]=-\frac{1}{p_{1}^{2}p_{2}}-\frac{1}{p_{2}}$

Now denote $P_{A}$ to be the probability that $A$ is the first to occur among
all three patterns. Likewise, define $P_{B}$ and $P_{C}=1-P_{A}-P_{B}$. We can
write a system of three equations with three unknowns

$\displaystyle
T[\text{min}]=T[A]+T[\text{min}]-T[A]=T[A]+T[A|B]P_{B}+T[A|C]P_{C}$
$\displaystyle
T[\text{min}]=T[B]+T[\text{min}]-T[B]=T[B]+T[B|A]P_{A}+T[B|C]P_{C}$
$\displaystyle
T[\text{min}]=T[C]+T[\text{min}]-T[C]=T[C]+T[C|A]P_{A}+T[C|B]P_{B}$

Now we consider the following Lévy noise system, which can be viewed as a Lévy
noise extension to the well-known Geometric SDE [32]. We demonstrate how to
design the control action synthesis part of the two-part controller.

$\displaystyle dx(t)=ax(t)dt+u(t)dt+\sigma x(t)dW(t)+\xi
x(t)\int_{\mathbb{R}}zN(dt,dz)$ (56)

where $a\neq 0,\sigma>0,\xi>0$ are constants, and the jump size $z$ is
distributed uniformly over the interval $[-2,-1]\cup[1,2]$. We invoke the
impulse control methodology described in Section 3.2 to determine how to steer
the trajectory of the system back towards the bounded error ball after the
instability pattern has occurred. Suppose that we seek to minimize the
performance objective designed with the cost-to-go and impulse cost functions
chosen as

$\displaystyle K(y,z)=e^{-t}5\lvert z\rvert,\qquad\ell(y)=e^{-t}x^{2}$

We have $y:=(t,x)$ to be the state of the augmented system. Consider a value
function of the form $\varphi(s,x)=e^{-s}\psi(x)$. Due to the symmetry of the
problem, we choose region

$\displaystyle D:=\\{x\in\mathbb{R}|\psi(x)<\mathcal{M}\psi(x)\\}=(-b,b)$

for some $b>0$ to be determined.

The first condition of Theorem 6 states that the following expression needs to
be zero for $x\in[-b,b]$ in order for $\varphi$ to be optimal:

$\displaystyle\mathcal{L}\varphi(t,x)+\ell(t,x)=e^{-t}\left(-\psi(x)+ax\psi^{\prime}(x)+\frac{1}{2}\sigma^{2}x^{2}\psi^{\prime\prime}(x)+\int_{\mathbb{R}}\left[\psi(x+z)-\psi(x)\right]\nu(dz)+x^{2}\right)$

where $\mathcal{L}\varphi$, i.e. $d\psi$, was computed using Itô’s formula.
$\psi$ must then satisfy the following differential equation:

$\displaystyle-\psi(x)+ax\psi^{\prime}(x)+\frac{1}{2}\sigma^{2}x^{2}\psi^{\prime\prime}(x)+\int_{\mathbb{R}}\left[\psi(x+z)-\psi(x)\right]\nu(dz)=-x^{2}$

Again, we can solve this nonhomogeneous ordinary differential equation as a
sum of homogeneous and nonhomogeneous parts. We guess the exponent of the
homogeneous solution $\psi^{h}(x):=x^{r}$ through the following auxiliary
equation:

$\displaystyle-1+ar+\frac{1}{2}\sigma^{2}r(r-1)+\int_{\mathbb{R}}\left[(1+z)^{r}-1\right]\nu(dz)=0$
(57)

Note that

$\displaystyle\int_{\mathbb{R}}\left[(1+z)^{r}-1\right]\nu(dz)$
$\displaystyle=\frac{1}{2}\left[\int_{-2}^{-1}\left[(1+z)^{r}-1\right]dz+\int_{1}^{2}\left[(1+z)^{r}-1\right]dz\right]=\frac{1}{r+1}\left((-1)^{r}+3^{r+1}-2^{r+1}\right)-2$

and so (57) reduces to

$\displaystyle-3+ar+\frac{1}{2}\sigma^{2}r(r-1)+\frac{1}{r+1}\left((-1)^{r}+3^{r+1}-2^{r+1}\right)=0$

Solving this auxiliary equation yields one positive root $r_{+}$ and one
negative root $r_{-}$. Furthermore, the partial solution $\psi^{p}(x)$
corresponding to the nonhomogeneous part of the equation can be assumed to
take on a form of a second-order polynomial $A_{2}x^{2}+A_{1}x+A_{0}$.
Substitute $\psi(x)=\psi^{h}(x)+\psi^{p}(x)$ into the original equation, then
match the coefficients to determine the $A_{i}$. Overall, when $\lvert
x\rvert\leq b$, the complete solution turns out to be

$\displaystyle\psi(x)=\psi_{1}(x):=C_{+}e^{r_{+}x}+C_{-}e^{r_{-}x}+x^{2}+1$
(58)

Since we have symmetry of the problem in the sense that we desire to push the
trajectory within an equidistant tube surrounding the zero line, we choose
specifically $C_{+}=C_{-}=-C$, where $C>0$, so that

$\displaystyle\psi_{1}(x)=C(e^{r_{+}x}+e^{r_{-}x})+x^{2}+1$

When $\lvert x\rvert>b$, we look at the second condition from Theorem 6.
First, the intervention operator is written as:

$\displaystyle\mathcal{M}\psi(x)=\inf_{z\in\mathbb{R}}\\{\psi(x+z)+5\lvert
z\rvert\\}$ (59)

which implies that the minimizing value of $z$ satisfies

$\displaystyle\begin{cases}\psi^{\prime}(x+z)=-5&\text{ if }z>0\\\
\psi^{\prime}(x+z)=5&\text{ if }z<0\end{cases}$

and so we want to find $a>0$ such that $-b<-a<0<a<b$. Essentially, the impulse
control law is designed to push the trajectory up ($z>0$) to $-a$ if it goes
beneath level $-b$ and push the trajectory down ($z<0$) to $a$ if it goes
above level $+b$. This corresponds to the first-order conditions
$\psi^{\prime}(a)=-5$ and $\psi^{\prime}(-a)=5$.

With level $a$ assigned, we explicitly choose the form of

$\displaystyle\psi_{2}(x):=\begin{cases}\psi_{1}(a)+5(x-a),&\text{ if }x>b\\\
\psi_{1}(-a)-5(x+a),&\text{ if }x<-b\end{cases}$ (60)

Thus, in combination, the form of $\psi$ can be written as follows:

$\displaystyle\psi(x)=\begin{cases}C(e^{r_{+}x}+e^{r_{-}x})+x^{2}+1&\text{ if
}\lvert x\rvert\leq b\\\ \psi_{1}(a)+5(x-a),&\text{ if }x>b\\\
\psi_{1}(-a)-5(x+a),&\text{ if }x<-b\end{cases}$ (61)

Figure 3: A sample closed-loop trajectory of the Lévy noise system with the
designed impulse control applied.

Now, we can use the first-order conditions and the continuity and
differentiability conditions to solve for $a$ and $C$.

  1. 1.

Continuity at $x=b$ implies we need $\psi(b-)=\psi(b+)$:

$\displaystyle\psi_{1}(b)=\psi_{1}(a)+5(b-a)$ $\displaystyle\Longrightarrow\ $
$\displaystyle
C(e^{r_{+}b}+e^{r_{-}b})+b^{2}+1=C(e^{r_{+}a}+e^{r_{-}a})+a^{2}+1+5(b-a)$

  2. 2.

Differentiability condition at $x=b$ implies we need
$\psi_{1}^{\prime}(b)=\psi_{2}^{\prime}(b+)$:

$\displaystyle Cr_{+}e^{r_{+}b}+Cr_{-}e^{r_{-}b}+2b=5$

  3. 3.

We also have the required condition that
$\psi^{\prime}(a)=\psi_{1}^{\prime}(a)=-5$ (and the opposite condition does
not need to be mentioned due to symmetry):

$\displaystyle Cr_{+}e^{r_{+}a}+Cr_{-}e^{r_{-}a}+2a=-5$

See Figure 3 for a visualization of a sample trajectory for the system (56)
with the impulse control law applied. Intuitively, it is easy to see that the
impulse control method is optimal because it instantaneously pushes the state
of the system down to a safer, lower-energy state. Furthermore, the nature of
the control law is that this only happens once the trajectory exceeds a
prespecified limit. We remark that the behavior of the trajectory illustrated
in Figure 3 shows the ideal system response under no physical constraints on
the system’s components, e.g. its actuators. This is similar to the well-known
bang-bang control action for spacecraft applications; while theoretically
optimal, they are not always practical to implement. Similarly, in this
setting, it may be difficult or most practical systems to perform a maneuver
as sharp as an impulse control. However, we emphasize that the impulse control
mechanism can be replaced with a synthesis procedure that incorporates
physical constraints. The hierarchical nature of the two-part controller still
remains the same, hence, the benefits arising from storing in memory control
laws for future occurrences of destabilizing patterns which have been observed
before are still present.

###  4.2 Controlling Vehicle Traffic at an Intersection

In this section, we demonstrate application of the two-part controller
synthesis procedure on congestion control problems for discrete-valued
quantities, such as the number of vehicles present in each lane of a stretch
of road, or the number of packets in each flow that is queued up at an
internet router. Particularly for congestion control problems, the discrete
value of the state allows the learning component of the two-part procedure to
identify recurring patterns much more accurately. For that reason, the
pattern-occurrence problem is arguably better suited to congestion-type
applications moreso than the scalar fault-tolerance control problem presented
in the previous section. Another key distinction for how the two-part
procedure treats congestion control-type problems is that the control action
is applied as soon as possible in an effort to drive the level of congestion
close to zero as quickly as possible, as opposed to the fault-tolerance
control problems considered previously, which waits until an appropriate
accumulation of impulsive disturbances has driven the trajectory beyond a
nonzero bound.

For concreteness, we demonstrate this application to the specific congestion-
type problem of controlling vehicle traffic across a single intersection by
adjusting light signal patterns, and we look into two specific types of
intersection scenarios: 1) the four-way intersection with one lane per road,
and 2) the four-way intersection with one lane per road assuming the lanes on
the opposite side of the intersection can be congested, and 3) the four-way
intersection with two lanes per road, one for forward and right-turning
traffic and one for left-turning traffic. For each of the scenarios, we look
into how the learning component is designed by using the pattern-occurrence
problem to compute the expected time that elapses between two consecutive
instances of the same intersection state. First, we establish the general
setting and the relevant simplifying assumptions for the problem.

Consider a single four-way intersection for oncoming vehicles. The four ways
of each intersection are $E$ for East, $N$ for North, $W$ for West, and $S$
for South. New platoons of vehicles can enter the intersection from any of the
four directions according to compound Poisson processes of possibly different
intensities, where the jump sizes indicate the number of vehicles entering the
lane. For the dynamics, the state we keep track of is the queue length (i.e.,
number of vehicles) at each of the lanes, represented by the vector ${\bf
x}\in\mathbb{R}^{n}$. Furthermore, each component
$x_{\ell}\in[0,x_{\text{max}}]$, where $\ell\in\mathbb{N}^{+}$ denotes the ID
of the lane in the intersection, and $x_{\text{max}}\in\mathbb{Z}^{+}$ denotes
the maximum number of cars allowed to enter a single lane within one timestep.
For concreteness, we take $x_{\text{max}}=5$. One simplification we make is
the discretization of time and the consequent representation of vehicle
interarrival times as Geometric random variables instead of Exponential ones.
This allows us to model the dynamics of the number of vehicles per lane of the
intersection as a Markov chain. We denote $p_{k}$ to be the probability that
$k\in[1,x_{\text{max}}]$ vehicles enter into lane $i$ within one timestep.

The intersection is locally controlled by traffic lights, one per lane, and
each take on binary values depending on whether the light is green $(1)$ or
not $(0)$. Suppose that the control law signal is such that the probability of
the light being green at a certain time instance can be represented by a
probability $0<p_{G}<1$ and let $p_{R}:=1-p_{G}$ be the probability that the
light is red. This probability is what the second part of the two-part
controller adjusts in order to optimize traffic flow, and we discuss this
aspect in more detail later on. For simplicity, we assume that all vehicles
travel at the same speed, and thus at a single timestep when the light is
green, a constant number $M<x_{\text{max}}$ of vehicles can pass.

The learning component seeks to solve the following problem. Suppose that at
time $t$, the state of the intersection is given by ${\bf
x}_{0}\in\mathbb{R}^{n}$. We are interested in computing the expected number
of timesteps after $t$ in which the state ${\bf x}_{0}$ occurs again. This is
precisely the pattern-occurrence problem that we’ve studied in Section 2.2; in
this setup, the renewals denote the event that the state of the intersection
is ${\bf x}_{0}$. We are interested in this quantity for two complementary
reasons. On one hand, it saves computational resources to have the system
memorize the optimal traffic signal patterns for the first occurrence of ${\bf
x}_{0}$, then apply it for every future occurrence of ${\bf x}_{0}$. On the
other hand, if the system has limited memory storage and the time between
consecutive occurrences of ${\bf x}_{0}$ is too long, then the optimal control
sequence may no longer be retained in memory, prompting recomputation from
scratch anyway. We now address the pattern-occurrence problem for each of hte
three cases described above.

One Lane per Road: Suppose there is one lane per direction, and vehicles in
each lane are only allowed to pass the intersection by going straight forward.
Then the dimension of the state is $n=4$ and ${\bf
x}:=(x_{1},\cdots,x_{4})^{T}\in\mathbb{R}^{4}$. We order the counts of the
lanes in the intersection as a vector according to $(E,N,W,S)$. We further
suppose that thhere is one designated traffic light assigned to each lane in
each direction for a total of four lights, i.e. ${\bf
u}:=(u_{1},\cdots,u_{4})^{T}\in\\{0,1\\}^{4}$. However, certain constraints
can be imposed on the four lights for basic efficiency, e.g. $E$ and $W$
traffic can pass simultaneously, and likewise for $N$ and $S$ traffic.

If we modeled the number of vehicles in each lane $x_{\ell}$,
$\ell=1,\cdots,4$, as a Markov chain then we take the transition probabilities
to be given by

$\displaystyle p_{ij}=\begin{cases}p_{R}p_{0}+p_{G}p_{M}&\text{ if }j=i\\\
p_{R}p_{j-i}+p_{G}p_{j-i+M}&\text{ if }j\in\\{i+1,\cdots,i+M+1\\}\\\
p_{R}p_{j-i}&\text{ if }j\in\\{i+M+2,i+x_{\text{max}}\\}\\\ p_{G}p_{0}&\text{
if }j=\max\\{0,i-M\\}\end{cases}$

for all $i\in\mathbb{Z}^{\geq 0}$. Now suppose for concreteness, $M=2$,
$x_{\text{max}}=5$, and $p_{G}=0.6$, and suppose we are interested in the
intersection snapshot ${\bf x}_{0}:=(5,1,5,1)^{T}$. Enumerating all possible
one-timestep previous states ${\bf x}_{0}$ could have come from yields:

  1. 1.

$(y_{1},x_{1},y_{2},x_{2})^{T}$ where $y_{1},y_{2}\in\\{2,3,4,5,6,7\\}$ and
$x_{1},x_{2}\in\\{0,1\\}$, which reach ${\bf x}_{0}$ in one step if the East
and West lanes were given the green light at the same time some number of
vehicles between five and zero entered the corresponding lanes, and if traffic
in the North and South lanes were stopped at the same time one or no vehicles
entered the correpsonding lanes.

  2. 2.

$(y_{1},x_{1},y_{2},x_{2})^{T}$ where $y_{1},y_{2}\in\\{0,1,2,3,4,5\\}$ and
$x_{1},x_{2}\in\\{0,1,2,3\\}$, which reach ${\bf x}_{0}$ in one step if the
East and West lanes were stopped at the same time some number of vehicles
between five and zero entered the corresponding lanes, and if if traffic in
the North and South lanes were given the green light at the same time three,
two, one, or no vehicles entered the corresponding lanes.

Then the expected time in between consecutive instances of ${\bf x}_{0}$ is
given by

$\displaystyle\mathbb{E}[T]:=\left(\sum\limits_{\begin{subarray}{c}x_{1},x_{2}\in\\{0,1\\}\\\
y_{1},y_{2}\in\\{2,3,4,5,6,7\\}\end{subarray}}\pi_{(y_{1},x_{1},y_{2},x_{2})}p_{y_{1,5}}p_{x_{1,1}}p_{y_{2,5}}p_{x_{2,1}}+\sum\limits_{\begin{subarray}{c}x_{1},x_{2}\in\\{0,1,2,3\\}\\\
y_{1},y_{2}\in\\{0,1,2,3,4,5\\}\end{subarray}}\pi_{(y_{1},x_{1},y_{2},x_{2})}p_{y_{1,5}}p_{x_{1,1}}p_{y_{2,5}}p_{x_{2,1}}\right)^{-1}$
(62)

Now we set ${\bf x}_{0}^{(1)}:={\bf x}_{0}$ and consider an alternative
snapshot of the intersection ${\bf x}_{0}^{(2)}:=(3,3,3,3)^{T}$. We are
interested in the probability $P_{1}$ of observing ${\bf x}_{0}^{(1)}$ before
${\bf x}_{0}^{(2)}$ and the minimum time $T_{\text{min}}$ it takes to observe
one of the two patterns. Denote $\mathbb{E}[T_{1}]:=\mathbb{E}[T]$ from (62).
This is analogous to the coin tossing example of Section 2.2.

Again enumerating all possible one-timestep previous states ${\bf
x}_{0}^{(2)}$ could have come from yields:

  1. 1.

$(y_{1},x_{1},y_{2},x_{2})^{T}$ where $y_{1},y_{2}\in\\{2,3,4,5\\}$ and
$x_{1},x_{2}\in\\{0,1,2,3\\}$, which reach ${\bf x}_{0}$ in one step if the
East and West lanes were given the green light at the same time three, two,
one, or no vehicles entered the corresponding lanes, and if traffic in the
North and South lanes were stopped at the same time one or no vehicles entered
the correpsonding lanes.

  2. 2.

$(y_{1},x_{1},y_{2},x_{2})^{T}$ where $y_{1},y_{2}\in\\{0,1,2,3\\}$ and
$x_{1},x_{2}\in\\{2,3,4,5\\}$, which reach ${\bf x}_{0}$ in one step if the
East and West lanes were stopped at the same time one or no vehicles entered
the correpsonding lanes, and if if traffic in the North and South lanes were
given the green light at the same time three, two, one, or no vehicles entered
the corresponding lanes.

Then the expected time in between consecutive instances of ${\bf x}_{0}^{(2)}$
is given by

$\displaystyle\mathbb{E}[T]:=\left(\sum\limits_{\begin{subarray}{c}x_{1},x_{2}\in\\{0,1,2,3\\}\\\
y_{1},y_{2}\in\\{2,3,4,5\\}\end{subarray}}\pi_{(y_{1},x_{1},y_{2},x_{2})}p_{y_{1,3}}p_{x_{1,3}}p_{y_{2,3}}p_{x_{2,3}}+\sum\limits_{\begin{subarray}{c}x_{1},x_{2}\in\\{2,3,4,5\\}\\\
y_{1},y_{2}\in\\{0,1,2,3\\}\end{subarray}}\pi_{(y_{1},x_{1},y_{2},x_{2})}p_{y_{1,3}}p_{x_{1,3}}p_{y_{2,3}}p_{x_{2,3}}\right)^{-1}$
(63)

As in the coin tossing example of Section 2.2, we can set up the equations as
follows. Note that there is no overlap between the two patterns, which implies
$T_{1|2}=T_{1}$ and $T_{2|1}=T_{2}$.

$\displaystyle\mathbb{E}[T_{1}]$
$\displaystyle=\mathbb{E}[T_{\text{min}}]+(\mathbb{E}[T_{1}]-\mathbb{E}[T_{\text{min}}])=\mathbb{E}[T_{\text{min}}]+(1-P_{1})\mathbb{E}[T_{1|2}]=\mathbb{E}[T_{\text{min}}]+(1-P_{1})\mathbb{E}[T_{1}]$
$\displaystyle\mathbb{E}[T_{2}]$
$\displaystyle=\mathbb{E}[T_{\text{min}}]+(\mathbb{E}[T_{2}]-\mathbb{E}[T_{\text{min}}])=\mathbb{E}[T_{\text{min}}]+P_{1}\mathbb{E}[T_{2|1}]=\mathbb{E}[T_{\text{min}}]+P_{1}\mathbb{E}[T_{2}]$

Hence,

$\displaystyle
P_{1}=\frac{\mathbb{E}[T_{2}]}{\mathbb{E}[T_{2}]+\mathbb{E}[T_{1}]}$

where $T_{1}$ is from (62) and $T_{2}$ is from (63).

One Lane per Road with Possible Jamming: Suppose now there is the possibility
of a traffic jam on the opposite side of the intersection, which might prevent
vehicles from being able to pass the intersection even on a green light. Note
that if the rate of cars clearing the intersection on a green light without
jams is given by $M$, the rate of cars leaving from the opposite side of the
intersection and clearing space should also be $M$. Furthermore, since jams
are most likely caused by adjacent intersections, we let $p_{G}$ be the
probability that the vehicles in the jammed lanes begin to move, and $p_{R}$
is the probability that they remain in place, preventing cars on the incident
side of the intersection from being able to cross.

The sole difference between including and excluding lane jams is the
transition probability matrix. Essentially, vehicles can only cross an
intersection when both lights are green, and can be stopped at an intersection
if the opposite lane is blocked with other cars.

$\displaystyle
p_{ij}=\begin{cases}(p_{R}+p_{G}p_{R})p_{0}+p_{G}^{2}p_{M}&\text{ if }j=i\\\
(p_{R}+p_{G}p_{R})p_{j-i}+p_{G}^{2}p_{j-i+M}&\text{ if
}j\in\\{i+1,\cdots,i+M+1\\}\\\ (p_{R}+p_{G}p_{R})p_{j-i}&\text{ if
}j\in\\{i+M+2,i+x_{\text{max}}\\}\\\ p_{G}^{2}p_{0}&\text{ if
}j=\max\\{0,i-M\\}\end{cases}$

for all $i\in\mathbb{Z}^{\geq 0}$. We can then repeat the compuation shown in
the previous scenario without lane jamming, with the appropriate Markov chain
probabilities replaced.

Two Lanes per Road: Now suppose there are two lanes per road: one for forward
and right-turning traffic, and one for left-turning traffic. The dimension of
the state is now $n=8$, ${\bf x}:=(x_{1},\cdots,x_{8})^{T}\in\mathbb{R}^{8}$,
and we order of the components in the vector is ‘forward/right’ first, ‘left’
second with the directions ordered counterclockwise from East to South. We
again assume that there is one designated traffic light per lane ${\bf
u}:=(u_{1},\cdots,u_{8})^{T}\in\\{0,1\\}^{8}$, but impose certain common-sense
constraints as in the previous one-lane case, i.e., vehicle streams passing in
opposite directions ($E$ and $W$, or $N$ and $S$) can pass simultaneously. We
also assume that the roads of the intersection are wide enough so that left-
turning vehicles from opposite directions can also pass at the same time. For
a visualization of the intersection, we refer to Figure 4.

Figure 4: A single four-way intersection with two lanes per direction. Red
bars indicate that the corresponding lane is given the red light and stopped,
while green bars indicate that vehicles in that lane are allowed to pass. In
this particular configuration, the North and South left-turning lanes are
given the green light.

A vehicle can either choose to turn left, right, or go straight forward with
the following probabilities:

  1. 1.

$p_{L}$ denotes the probability of vehicles which enter the left-turn lane
among all the vehicles which enter the intersection from a neighboring
intersection, and denote $p_{FR}:=1-p_{L}$.

  2. 2.

$q_{F}$ denotes the probability that vehicles in the forward/right-turning
lane of an intersection go forwards, and $q_{R}:=1-q_{F}$ denotes the
probability that a vehicle turns right.

For each of the four directions, we let $p_{G,L}$ be the probability that
vehicles in left-turning lane are given the green light, $p_{G,FR}$ be the
probability that vehicles in forward and right-turning lane are given the
green light, and $p_{R,L}:=1-p_{G,L}$, $p_{R,FR}:=1-p_{G,FR}$. Additionally,
since there are different distances that need to be crossed depending on
whether a vehicle is turning left, right, or going forward, constant speed
vehicles still take different amounts of time to cross the intersection. Thus,
we also distinguish the constants $M_{L}<x_{\text{max}}$ and
$M_{FR}<x_{\text{max}}$.

Then the Markov chain probabilities for all four forward and right-turning
lanes are different from the probabilities for all four left-turning lanes.
Namely, for the number of vehicles in each forward and right-turning lane
$x_{\ell}$, $\ell=1,3,5,7$, the corresponding Markov chain transition
probabilities are as follows:

$\displaystyle p_{ij}=\begin{cases}p_{R,FR}p_{0}+p_{G,FR}p_{M,FR}&\text{ if
}j=i\\\ p_{R,FR}p_{j-i}+p_{G,FR}p_{j-i+M_{FR}}&\text{ if
}j\in\\{i+1,\cdots,i+M_{FR}+1\\}\\\ p_{R,FR}p_{j-i}&\text{ if
}j\in\\{i+M_{FR}+2,i+x_{\text{max}}\\}\\\ p_{G,FR}p_{0}&\text{ if
}j=\max\\{0,i-M_{FR}\\}\end{cases}$

for all $i\in\mathbb{Z}^{\geq 0}$ and for the number of vehicles in each left-
turning lane $x_{\ell}$, $\ell=2,4,6,8$, the corresponding transition
probabilities are:

$\displaystyle p_{ij}=\begin{cases}p_{R,L}p_{0}+p_{G,L}p_{M,L}&\text{ if
}j=i\\\ p_{R,L}p_{j-i}+p_{G,L}p_{j-i+M_{L}}&\text{ if
}j\in\\{i+1,\cdots,i+M_{L}+1\\}\\\ p_{R,L}p_{j-i}&\text{ if
}j\in\\{i+M_{L}+2,i+x_{\text{max}}\\}\\\ p_{G,L}p_{0}&\text{ if
}j=\max\\{0,i-M_{L}\\}\end{cases}$

##  5 Conclusion

In this paper, we extended the study of stochastic control theory to include
the class of Poisson shot noise by designing a two-part hierarchical control
policy for systems of the form (3) and (4). The first part of the control
policy invokes renewal theory to construct a learning component which
recognizes previously-occurred states and their corresponding optimal control
responses. Namely, we utilize the “pattern-occurrence” problem to determine
the expected time between consecutive instances of the same state. Even
incorporating this simple learning component into the system has the potential
to save time and computational energy because there is no need to devote
resources towards recomputing a control action for a state that has been
observed before. The second part of the control policy invokes an impulse
control approach which computes the actual control action which is optimal for
each of the specific states kept track of by the first learning component
part.

We then presented two simplified specific applications for control design: 1)
a 1D fault-tolerance system and 2) a control problem for moderating vehicle
traffic at an intersection. For the 1D fault-tolerance problem, we explicitly
computed steady-state error bound $\kappa_{s}(\beta_{s},t)$ and showed that
larger jump norm bounds $\eta$ and 2) shorter interarrival times between jumps
correspond to a larger error ball. We then used renewal theory to address the
converse problem of determining the largest possible values of the shot noise
characteristics, i.e. intensity and maximum absolute jump norm, such that the
steady state error bound remains bounded by a desired tolerance. In this
context, the renewals referred to the event where the trajectory exceeds the
stability bound by an amount which makes the system unstable. The impulse
control method is then applied at these points to navigate the trajectory back
within the desired error bound.

For the vehicle traffic control problem, we used renewal theory to compute the
expected time between consecutive renewals, which referred to certain
snapshots of the intersection. The reason for saving these snapshots and their
corresponding optimal control actions is to save resources. One might observe
10 cars in the East lane and five cars in the North lane, and the optimal
control action might be to let the first five East cars pass, then the five
North cars, and finally the last five East cars. If the system observes the
exact same scenario in a future time, we simply recycle the same optimal
control action used previously. We showed that renewal theory is also useful
for choosing which states are worth saving in memory. For snapshots which do
not have a high probability of occurring (e.g., ten vehicles occupying all
four directions of the intersections simultaneouly), there is not much
computational benefit to saving the corresponding optimal control action,
especially when the system has limited storage. The performance objective for
the impulse control method refers to the level of congestion in the
intersection, and we desire to compute an action of traffic light sequences
which minimizes the level of congestion as quickly as possible. Unlike the 1D
reference-tracking problem, a necessary addition to the standard impulse
control method is a time-varying performance criteria which assigns varying
priorities to the lanes depending on the number of vehicles that are present
at each lane.

We argue that the simplified examples investigated in this paper are
sufficient enough to develop the theoretical framework for the controller
synthesis procedure. To make the controller more applicable to more complex
real-life instances, certain factors also need to be considered. One extension
is towards the direction of continuous-valued jumps, which may be addressed by
first discretizing the space of jumps:

$\displaystyle\mathcal{S}:=\\{\xi(t,{\bf x},{\bf z})|\left\lVert\xi(t,{\bf
x},{\bf z})\right\rVert\leq\eta\\}\ \Longrightarrow\
\mathcal{S}_{i}:=\\{\xi(t,{\bf x},{\bf z})|\left\lVert\xi(t,{\bf x},{\bf
z})\right\rVert\leq\eta_{i}\\}$

for chosen threshold values $0<\eta_{1}<\eta_{2}<\cdots\leq\eta_{k}:=\eta$,
where $\eta$ is the upper bound on the norm of the jumps, and some
$k\in\mathbb{N}$. Then any two jumps $\xi_{a}(t,{\bf x},{\bf
z}),\xi_{b}(t,{\bf x},{\bf z})$ which belong in the same set $\mathcal{S}_{i}$
can be controlled using the same law. Another possible extension to the
pattern occurrence problem is when we care about what specific order a certain
number of patterns $A_{1},\cdots,A_{M}$ occurs in. For example, for the case
of $M=3$, define $T^{*}$ to be the expected time until we see $A_{3}$ after we
have already observed occurrences of $A_{1},A_{2}$ in any order. Then, with
the notation $P_{i}$ being the probability of observing pattern $A_{i}$ first
among all $M$ patterns, we have

$\displaystyle\mathbb{E}[T^{*}]=P_{A_{1}}(\mathbb{E}[T_{A_{1}}]+\mathbb{E}[T_{A_{2}|A_{1}}])+P_{A_{2}}(\mathbb{E}[T_{A_{2}}]+\mathbb{E}[T_{A_{1}|A_{2}}])$

The interest for looking into these types of pattern arrangements arises from
applications in fault tolerance such as the turbulence of ocean waves
affecting a drifting boat, or the collapse of the Tacoma Narrows Bridge in
1940. While these systems may have been designed to withstand strong
perturbations, it may fail in events resulting from a steady accumulation of
consecutive smaller perturbations. An extension for the modulation control
component is the replacement of the impulse controller with an alternative
controller, especially in applications where a sharp decay in the state is not
physically feasible. The hierarchical structure of the two-part controller
remains the same regardless: the learning component facilitates the
recognition of destabilizing patterns, and the modulation controller is
applied only then. One could also derive first-order conditions to impose
additional limits on the extent of being able to control the system using
impulsive jumps of large magnitude.

## Acknowledgments

The authors would like to thank John C. Doyle for the discussion of ideas
which provided motivation for this work.

## References

  * Applebaum [2009] Applebaum, D. (2009).  Lévy Processes and Stochastic Calculus.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition.
  * Applebaum and Siakalli [2009] Applebaum, D. and Siakalli, M. (2009).  Asymptotic stability of stochastic differential equations driven by Lévy noise.  Journal of Applied Probability, 46:1116–1129.
  * Baccelli and Blaszczyszyn [2009] Baccelli, F. and Blaszczyszyn, B. (2009).  Stochastic Geometry and Wireless Networks, Part I: Theory.  Now Publishers Inc., Hanover, MA, USA.
  * Bass [2014] Bass, R. F. (2014).  Jump processes.  http://bass.math.uconn.edu/jump-processes.pdf.
  * Beenakker [1992] Beenakker, C. W. J. (1992).  Quantum transport in semiconductor-superconductor microjunctions.  Phys. Rev. B, 46:12841–12844.
  * Bernstein and Haddad [1988] Bernstein, D. S. and Haddad, W. M. (1988).  LQG control with an $h_{\infty}$ performance bound: a Riccati equation approach.  In 1988 American Control Conference, pages 796–802.
  * Capuano et al. [2019] Capuano, V., Harvard, A., Lin, Y., and Chung, S.-J. (2019).  DGNSS-vision integration for robust and accurate relative spacecraft navigation.  In Proceedings of the 32nd International Technical Meeting of the Satellite Division of The Institute of Navigation (ION GNSS+ 2019), pages 2923–2939.
  * Collaboration [2011] Collaboration, T. L. S. (2011).  A gravitational wave observatory operating beyond the quantum shot-noise limit.  Nature Phys, 46:962–965.
  * Cont and Tankov [2004] Cont, R. and Tankov, P. (2004).  Financial Modelling With Jump Processes.  CRC Press UK, London, UK.
  * Cox [1962] Cox, D. R. (1962).  Renewal Theory.  John Wiley & Sons Inc., London.
  * Cox and Miller [1965] Cox, D. R. and Miller, H. D. (1965).  The Theory of Stochastic Processes.  Taylor & Francis Group.
  * Dani et al. [2015] Dani, A. P., Chung, S.-J., and Hutchinson, S. (2015).  Observer design for stochastic nonlinear systems via contraction-based incremental stability.  IEEE Transactions on Automatic Control, 60(3):700–714.
  * Davis et al. [2010] Davis, M. H. A., Guo, X., and Wu, G. (2010).  Impulse control of multidimensional jump diffusions.  SIAM J. Control Optim., 48(8):5276–5293.
  * Deisenroth et al. [2015] Deisenroth, M. P., Fox, D., and Rasmussen, C. E. (2015).  Gaussian processes for data-efficient learning in robotics and control.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 37(2):408–423.
  * Doyle [1978] Doyle, J. (1978).  Guaranteed margins for LQG regulators.  IEEE Transactions on Automatic Control, 23(4):756–757.
  * Franchi et al. [2018] Franchi, L., Feruglio, L., Mozzillo, R., and Corpino, S. (2018).  Model predictive and reallocation problem for CubeSat fault recovery and attitude control.  Mechanical Systems and Signal Processing, 98:1034–1055.
  * Han and Weinan [2016] Han, J. and Weinan, E. (2016).  Deep learning approximation for stochastic control problems.  ArXiv preprint, arxiv:1611.07422.
  * Han [2021] Han, S. (2021).  Stochastic Differential Equations and Random Processes for Control Engineers.  Book preprint.
  * Han and Chung [tted] Han, S. and Chung, S.-J. (2021, to be submitted).  Incremental nonlinear stability analysis for stochastic systems perturbed by Lévy noise.  Systems and Control Letters.
  * Jeanblanc [2007] Jeanblanc, M. (2007).  Jump processes.  https://www.maths.univ-evry.fr/pages_perso/jeanblanc/conferences/Cimpa-sauts.pdf.
  * Kalakrishnan et al. [2011] Kalakrishnan, M., Chitta, S., Theodorou, E., Pastor, P., and Schaal, S. (2011).  STOMP: Stochastic trajectory optimization for motion planning.  In 2011 IEEE International Conference on Robotics and Automation, pages 4569–4574.
  * Kalman [1960] Kalman, R. E. (1960).  A new approach to linear filtering and prediction problems.  Journal of basic Engineering, 82(1):35–45.
  * Karlin [1976] Karlin, S. (1976).  A First Course in Stochastic Processes.  Academic Press.
  * Karlin and Taylor [1981] Karlin, S. and Taylor, H. (1981).  A Second Course in Stochastic Processes.  Academic Press.
  * Khalil [2002] Khalil, H. K. (2002).  Nonlinear Systems; 3rd ed. Prentice-Hall, Upper Saddle River, NJ, USA.
  * Kingman [1993] Kingman, J. F. C. (1993).  Poisson processes, volume 3.  Oxford University Press, NY, USA.
  * Kolcio and Fesq [2016] Kolcio, K. and Fesq, L. (2016).  Model-based off-nominal state isolation and detection system for autonomous fault management.  In 2016 IEEE Aerospace Conference, pages 1–13.
  * Last and Penrose [2017] Last, G. and Penrose, M. (2017).  Lectures on the Poisson process.  Cambridge University Press, NY, USA.  https://www.math.kit.edu/stoch/~last/seite/lectures_on_the_poisson_process/media/lastpenrose2017.pdf.
  * Lohmiller and Slotine [1998] Lohmiller, W. and Slotine, J.-J. E. (1998).  On contraction analysis for non-linear systems.  Automatica, 34(6):683–696.
  * Munos and Bourgine [1998] Munos, R. and Bourgine, P. (1998).  Reinforcement learning for continuous stochastic control problems.  In Advances in Neural Information Processing Systems 10, pages 1029–1035. MIT Press.
  * Nakka and Chung [pear] Nakka, Y. and Chung, S.-J. (2019, to appear).  Trajectory optimization for chance-constrained nonlinear stochastic systems.  In 58th IEEE Conference on Decision and Control.
  * Øksendal [2010] Øksendal, B. (2010).  Stochastic Differential Equations: An Introduction with Applications.  Universitext. Springer Berlin, Berlin, Germany.
  * Øksendal and Sulem-Bialobroda [2007] Øksendal, B. and Sulem-Bialobroda, A. (2007).  Applied Stochastic Control of Jump Diffusions.  Universitext. Springer-Verlag, Berlin, Germany.
  * Olsman et al. [2019] Olsman, N., Xiao, F., and Doyle, J. C. (2019).  Architectural principles for characterizing the performance of antithetic integral feedback networks.  iScience, 14:277–291.
  * Patel and Kosko [2009] Patel, A. and Kosko, B. (2009).  Stochastic resonance in continuous and spiking neuron models with Lévy noise.  IEEE Transactions on Neural Networks, 19:1993–2008.
  * Pinsky and Karlin [2011] Pinsky, M. and Karlin, S. (2011).  An Introduction to Stochastic Modeling.  Academic Press.
  * Protter [1992] Protter, P. (1992).  Stochastic Integration and Differential Equation.  Springer-Verlag, Berlin, Heidelberg, second edition.
  * Rawlik et al. [2013] Rawlik, K., Toussaint, M., and Vijayakumar, S. (2013).  On stochastic optimal control and reinforcement learning by approximate inference.  In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence, pages 3052–3056.
  * Reif et al. [1999] Reif, K., Gunther, S., Yaz, E., and Unbehauen, R. (1999).  Stochastic stability of the discrete-time extended Kalman filter.  IEEE Transactions on Automatic Control, 44(4):714–728.
  * Ross [1996] Ross, S. (1996).  Stochastic Processes.  John Wiley & Sons Inc., New York, USA, second edition.
  * Ross [2006] Ross, S. (2006).  A First Course in Probability.  Pearson Prentice Hall, Upper Saddle River, NJ, USA, seventh edition.
  * Ross [2010] Ross, S. (2010).  Introduction to Probability Models.  Academic Press, San Diego, CA, USA, tenth edition.
  * Sastry [1999] Sastry, S. (1999).  Nonlinear Systems: Analysis, Stability, and Control.  Springer-Verlag New York, Inc., Secaucus, NJ, USA.
  * Shi et al. [2020] Shi, G., Hönig, W., Yue, Y., and Chung, S.-J. (2020).  Neural-swarm: Decentralized close-proximity multirotor control using learned interactions.  In IEEE Int. Conf. Robot. Autom.
  * Slotine and Li [1991] Slotine, J. and Li, W. (1991).  Applied Nonlinear Control.  Prentice Hall, Eaglewood Cliffs, NJ, USA.
  * Theodorou et al. [2010] Theodorou, E., Buchli, J., and Schaal, S. (2010).  A generalized path integral control approach to reinforcement learning.  Journal of Machine Learning Research, 11:3137–3181.
  * Tsukamoto and Chung [2021] Tsukamoto, H. and Chung, S.-J. (2021).  Neural contraction metrics for robust estimation and control: A convex optimization approach.  IEEE Control Syst. Lett., 5(1):211–216.
  * Wan and Van Der Merwe [2000] Wan, E. A. and Van Der Merwe, R. (2000).  The unscented Kalman filter for nonlinear estimation.  In Proceedings of the IEEE 2000 Adaptive Systems for Signal Processing, Communications, and Control Symposium, pages 153–158.
  * Wander and Förstner [2013] Wander, A. and Förstner, R. (2013).  Innovative fault detection, isolation and recovery on-board spacecraft: Study and implementation using cognitive automation.  In 2013 Conference on Control and Fault-Tolerant Systems (SysTol), pages 336–341.
  * Watson [2016] Watson, A. (2016).  Introduction to Lévy processes.  https://personalpages.manchester.ac.uk/staff/alex.watson/lectures/intro-levy.pdf.
  * Yang et al. [2017] Yang, J., Dani, A., Chung, S.-J., and Hutchinson, S. (2017).  Vision-based localization and robot-centric mapping in riverine environments.  J. Field Robot, 34(3):429–450.
  * Zhou et al. [1996] Zhou, K., Doyle, J. C., and Glover, K. (1996).  Robust and Optimal Control.  Prentice-Hall, Inc., Upper Saddle River, NJ, USA.