# A time-dependent Markovian model of a limit order book

Jonathan A. Chávez-Casillas<EMAIL_ADDRESS>ORCiD: 0000-0002-8494-7538
Department of Mathematics and Applied Mathematical Sciences,
University of Rhode Island

(February 18th, 2022)

###### Abstract

This paper considers a Markovian model of a limit order book where time-
dependent rates are allowed. With the objective of understanding the
mechanisms through which a microscopic model of an orderbook can converge to
more general diffusion than a Brownian motion with constant coefficient, a
simple time-dependent model is proposed. The model considered here starts by
describing the processes that govern the arrival of the different orders such
as limit orders, market orders and cancellations. In this sense, this is a
microscopic model rather than a “mesoscopic” model where the starting point is
usually the point processes describing the times at which the price changes
occur and aggregate in these all the information pertaining to the arrival of
individual orders. Furthermore, several empirical studies are performed to
shed some light into the validity of the modeling assumptions and to verify
whether certain stocks satisfy the conditions for their price process to
converge to a more complex diffusion.

keywords: Limit order book, Price process, Diffusion approximation, Time-
dependency

##  1 Introduction

The evolution of trading markets has progressed considerably in the last few
decades. One of the main drivers of such evolution has been the creation and
usage of fast-paced technological developments. In the past, liquidity was
provided by the so-called market makers, which collected buy and sell orders
from all market participants to set bid and ask quotes. While this traditional
method was generally accepted, mainly, because of the lack of alternatives, it
was also criticized due to the bias and questionable conflict of interest from
the market maker. Nowadays, most exchanges use completely automated platforms
called Electronic Communication Networks (ECN). These ECN enables a continuous
double auction trading mechanism, which eliminates the need of a market maker
or an intermediary that matches the opposite parties in a trade. The auction
that the ECN manages is called “continuous double” since traders can submit
orders in form of bids (i.e., buy orders) as well as asks (i.e., sell orders)
at any point in time. ECNs increase significantly the speed of trading, taking
only a few milliseconds from sending an order to its execution.

A bid limit order (resp. ask limit order) specifies the quantity and the price
at which a trader wants to buy (resp. sell) certain asset. The limit order
book consists of all the collection of limit orders from every trader.
Outstanding limit orders are stored in different queues inside the order book.
These queues are ordered by the price and type (bid or ask). The difference in
price between the lowest ask price and the highest bid price is called the
spread.

The counterpart of limit orders are market orders, which allow traders to buy
and sell at the best available price. While limit orders will not trigger an
immediate transaction, market orders are immediately executed. In this sense,
limit orders accumulate, create, and extend the size of queues at both sides
of the LOB, while market orders remove limit orders from the best available
price. Sometimes informed traders are associated with traders that place
market orders, while uninformed traders are associated to the ones that place
limit orders, but this goes against the fact that many of the most successful
hedge funds make extensive use of limit orders (see Bouchaud et al., (2009)).

In addition to limit orders and market orders, cancellation of limit orders is
another common operation. The basic idea of a cancellation is that a trader is
no longer willing to buy or sell at the specified price. Cancellations account
for a large fraction of the operations on an order book, partly due to the
introduction and evolution of high frequency trading (see Harris, (2003)), in
which the inter-arrival times of limit orders and cancellations, occur at a
millisecond time scale (see Cont and de Larrard, (2013)).

An important feature of a LOB is that traders can choose between submitting
limit and market orders. The biggest advantage of limit orders is the
possibility of matching better prices than the ones they can obtain with
market orders, but as drawback, there is a risk of never being executed.
Conversely, market orders never match at prices better than the best bid or
the best ask, but the execution is certain and immediate. Usually, the bid-ask
spread can be considered as a measure of how expensive is the certainty and
immediacy of buying or selling the underlying asset.

From a modeling perspective, sometimes it is important to identify the
different types of traders that are able to participate in the market. As
stated in Foucault et al., (2003), LOBs allowed traders to immediately obtain
liquidity, but at the same time, they also allow other traders to supply
liquidity to those who require it later. On the exchanges, most traders
combine limit orders and market orders to create a trading strategy according
to their needs and the current state of the order book. However, broadly, as
detailed in Foucault et al., (2003), traders with short-horizon strategies, as
arbitrageurs, technical traders, and indexers, prefer to post market orders,
while, traders with long-horizon strategies, as portfolio managers, place
limit orders.

As pointed out in Gould et al., (2013), there are many practical advantages in
understanding LOB dynamics. Examples of these are: gaining clearer insight
into how best to act in a given market situation (cf. Harris and Hasbrouck,
(1996)), devising optimal order execution strategies (Obizhaeva and Wang,
(2013), Law, (2015), Cartea and Jaimungal, (2015)), minimizing the market
impact (Eisler et al., (2012)); designing better electronic trading algorithms
(Engle et al., (2006)), and assessing market stability (Kirilenko et al.,
(2011)).

Due to the complexity of a LOB, when interpreted as a dynamical system, any
attempt to model a LOB requires considerable assumptions. One of the most
important assumptions is how the order flow evolves in time. One of the
seminal works in modeling a complete LOB in continuous time is the one
proposed by Cont et al., (2010). This is a zero-intelligence model, in which
the order flows follow independent Poisson processes whose rate parameters
depend on the type of order, distance to the bid-ask spread, and state of the
order book. With this model, the authors try to understand how the frequency
at which certain events occur depends on the state of the order book. Another
important trait of this model is the use of a power-law distribution for the
arrival of limit orders depending on their relative price, which fits well
with empirical observations.

In an attempt to simplify the dynamics of the order book and provide estimates
for the volatility in terms of the parameters governing the order flow, Cont
and de Larrard, (2013) propose a model that keeps track of the first level of
the order book instead of the whole LOB. When there was a depletion in either
side of this simplified I-level order book, the amounts of orders available at
the next best prices were assumed to be drawn from a distribution $f$ on
$\mathbb{N}^{2}$, and the spread was always kept constant at 1 tick. The
authors’ justification for this simplified framework was that many traders can
only view the depths available at the best prices and, also, that the
percentage of time, in liquid markets, that the spread is 1 is typically
larger than $97\%$. In this model, arrival of limit, market and cancellation
orders are modeled as independent Poisson processes. One of the advantages of
this approach is the ability to estimate analytically, depending just on the
Poisson processes’ parameters and the depth distribution $f$, quantities of
interest such as the volatility, the distribution of time until the next price
change, the distribution and auto-correlation of price changes, and the
conditional probability that the price moved in a specified direction given
the current state of the order book.

As noted in Chávez-Casillas et al., (2019), one of main drawbacks of the model
presented in Cont and de Larrard, (2013) is the assumption that the limit
orders, market orders and cancellations arrive as homogeneous Poisson
processes. In an attempt to improve this assumption, in Chávez-Casillas et
al., (2019), the authors assume that all the orders arrive as Non-homogeneous
Poisson processes but in contrast to the model presented in Cont and de
Larrard, (2013), the random clock driving the arrivals of these orders is not
reset after a price change. In fact, this random clock signaling the arrival
of new orders is never reset and instead of a reset, an assumption of
periodicity is used. That is, it is assumed that every week, every day, or
every given period of time, the intensities of the processes signaling the
arrival of orders is the same. While this approach is suitable to analyze the
behaviour of the orderbook at a mesoscopic time scale, the distributional
properties of the inter arrival times between price changes and their
consequences on the heavy-traffic approximation of the price process are not
discussed, which is the the aim of the present study with some corresponding
empirical data analysis.

By analyzing the distributional properties of the inter-arrival times and
allowing the intensity of the point process dictating their occurrence to be
time-dependent, it can be shown that the volatility in the long-run dynamics
of the price process possess, on certain cases, a time dependent component.
This is a new improvement in an attempt to reconcile the macro-price dynamics,
as a more general process than merely a Brownian motion with constant
volatility, of the orderbook when doing the modeling from the microscopic
price formation time scale. Indeed, in the existing literature, most of the
models that start from the modeling of how orders arrive to the macro-price
formation conclude that the price process is a Brownian motion with constant
volatility. The aim of the present paper is to shed some light into how it can
be possible to extend such models in such a way that the limiting price
process converges to a more general diffusion.

One of the aims of this paper is to analyze the different cases under which
the price process when modeled from a microscopic scale, referring to a model
that starts from considering the arrival of individual orders, rather than
from a mesoscopic scale, referring to a model that considers as a baseline the
arrival of changes in the price and aggregating all the information provided
in the arrival of individual orders all the way up to the arrival of a price
change. This entails more complex dynamics and there are few models in the
literature that consider creating bottom-up estimates and models; and while
one of the aims of the present work is to expand in the existing literature
and to study empirically whether the assumptions of the model might be
validated, it also wants to serve as a first step in creating more complex
models that start at a microscopic scale and can provide conditions under
which the long-run dynamics of the price process possess a more complex
structure than a simple Brownian motion with constant volatility.

This paper is organized as follows. In section 2 a precise description of the
Limit Order Book model is presented with its corresponding assumptions. In
Section 3 the distributional properties of the model and the long-run dynamics
of the price process are analyzed depending on the tail behaviour of the time
span between price changes. In section 4 the six study cases from this paper
are introduced and analyzed. Finally, in section 5 some conclusions are
presented along with further research directions in an attempt to generalize
the price process when modeling from the micro-price dynamics.

##  2 Description of the model

In this paper, a Level-1 Limit Order Book model is discussed using as a
framework the model proposed in Cont and de Larrard, (2013). However, in
contrast to such model, the point processes describing the arrivals of Limit
orders are described by a time-dependent periodic rate proportional to the
rate describing the arrival of Market orders plus Cancellations.

The next paragraphs will describe the modeling assumptions of the orderbook
model as well as some of its basic dynamics. First, as it was mentioned
before, only the best level at each side will be considered, together with
their corresponding sizes. . This assumption is justified by the fact that
most of the operations inside an orderbook are performed at the level-I, as
pointed out in Cont and de Larrard, (2013). Also, in this sense, the orderbook
is assumed to have a unitary tick size since for the stocks considered in
section 4, the spread spend more than $90\%$ within 1 tick.

A more controversial assumption which is meant to be relaxed in further
research is a classical assumption in these models that the order volume is
also unitary. Since the model presented is inspired by the original model
presented in Cont and de Larrard, (2013), the same assumption is kept, but it
is the author’s interest to relax this assumption. However, contrasting to the
original model and creating a much more realistic assumption, limit orders at
the bid and ask sides of the book arrive independently according to
inhomogeneous Poisson processes $L_{t}^{b}$ and $L_{t}^{a}$, with intensities
$\lambda^{b}_{t}$ and $\lambda_{t}^{a}$ respectively. Similarly, market orders
plus cancellations at the bid and ask sides of the book arrive independently
according to inhomogeneous Poisson processes $M_{t}^{b}$ and $M_{t}^{a}$, with
intensities $\mu^{b}_{t}$ and $\mu^{a}_{t}$ respectively. Notice that, since
in this model limit orders increase the queue size and both market orders and
cancellations decrease the queue size the latter are merged int one process,
which is natural by our assumption of a unitary volume in all orders. Further,
it is assumed that the processes $L_{t}^{a},L_{t}^{b},M_{t}^{a}$ and
$M_{t}^{b}$ are all pairwise independent.

Finally, it will be described what happens every time there is a price change.
Indeed, whenever the bid queue or the ask queue gets depleted, a price change
occurs. If the bid side is depleted, the price decreases and if the ask queue
is depleted, the price increases. After a price change occurs, the depth of
the orderbook will be considered via the distribution of two new queue sizes.
That is, after a price change, both the bid and the ask prices increase by one
tick, and the size of both queues gets redrawn from some distribution
$f\in\mathbb{N}^{2}$.

##  3 Distributional Properties of the Inter-arrival times and the Price
Process

For this model it will be assumed that after each price change, the clock
signaling the arrivals of new orders or cancellation in the orderbook will be
reset between the arrivals of these processes, so that if $\tau_{n}$, $n\geq
1$ represents inter-arrival time between the $(n-1)-$th and $n-$th price
change, then, the sequence $\\{\tau_{n}\\}_{n\geq 1}$ becomes an independent
sample.

In order to accurately describe the distribution of the inter-arrival time in
between price changes, some general notation that will be used throughout will
be introduced. Let $\\{(a_{n},b_{n})\\}_{n\geq 1}$ be a sequence of
independent random variables generated from the distribution
$f\in\mathbb{N}^{2}$. These will represent the initial amount of orders at the
bid and ask side of the order book, respectively, after the $n-$th price
change. For $t\geq 0$, let also, $\\{X_{x_{n-1}}^{(n)}(t)\\}_{n\geq 1}$ and
$\\{Y_{y_{n-1}}^{(n)}(t)\\}_{n\geq 1}$ be two families of mutually independent
one-dimensional time continuous random walks in the positive axis parametrized
by their starting point, i.e. for any $n\in\mathbb{N}$,
$X_{x_{n-1}}^{(n)}(0)=x_{n-1}$ and $Y_{y_{n-1}}^{(n)}(0)=y_{n-1}$, whose
generators $\mathscr{L}_{t}^{(X,n)}$ and $\mathscr{L}_{t}^{(Y,n)}$ are given
by

$\mathscr{L}^{(X,n)}_{t}(i,j)=\mathscr{L}_{t}^{(Y,n)}(i,j):=\left\\{\begin{array}[]{ccl}0&\text{if}&i=0,\
j\geq 0,\\\ \mu_{t}&\text{if}&1\leq i,\ j=i-1,\\\ \lambda_{t}&\text{if}&1\leq
i,\ j=i+1,\\\ -(\lambda_{t}+\mu_{t})&\text{if}&1\leq i,\ j=i,\\\
0&\text{if}&|i-j|>1\end{array}\right.$ (1)

Note that $0$ is an absorbing state for any Markov chain with generator
$\mathscr{L}^{(X,\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
)}_{t}$ or
$\mathscr{L}^{(Y,\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
)}_{t}$. When a chain reaches the absorbing point $0$, one calls it
extinction.

Let $\sigma_{x_{n-1}}^{(X,n)}$ and $\sigma_{y_{n-1}}^{(Y,n)}$ be the
extinction times the independent Markov chains $X_{x_{n-1}}^{(n)}(t)$ and
$Y_{{y_{n-1}}}^{(n)}(t)$. Further, set $\tau_{0}:=0$ and
$\tau_{n}:=\min\left(\sigma_{x_{n-1}}^{(n)},\sigma_{y_{n-1}}^{(n)}\right)$.

The dynamics of the orderbook can be described as follows. Let
$q_{t}=(q_{t}^{b},q_{t}^{a})$ be the amount of bid and ask orders at time $t$,
with $(x_{0},y_{0})$ the initial amount of orders at each side of the book,
that is, $q_{0}=(x_{0},y_{0})$. For $0\leq t<\tau_{1}$, define
$q_{t}:=(X_{x_{0}}^{(1)}(t),Y_{y_{0}}^{(1)}(t))$, so that, $\tau_{1}$ is the
time at which the first price change occurs. At time $\tau_{1}$, both queues
move one tick (to the right if the ask queue is depleted or to the left if the
bid queue is depleted). The size of the ask and bid queue are then set to be
$(x_{2},y_{2})$ (which are drawn from the distribution $f\in\mathbb{N}^{2}$),
and $q_{\tau_{1}}$ is defined as $(x_{1},y_{1})$. Furthermore, for
$\tau_{1}\leq t<\tau_{2}$, $q_{t}$ is defined as
$(X_{x_{1}}^{(2)}(t),Y_{y_{1}}^{(2)}(t))$ and the process continues. To
simplify notation, we denote by $\sigma_{a}^{n}$ and $\sigma_{b}^{n}$ the
random variables $\sigma_{x_{n-1}}^{(X,n)}$ and $\sigma_{y_{n-1}}^{(Y,n)}$,
respectively.

###  3.1 Distribution of the inter-arrival time between price changes

Because of the independence between the ask and the bid side of the book
before the first price change, to analyze the distribution of $\tau_{1}$, it
is enough to study one side of the orderbook, say the ask. In this case, an
explicit formula for $\mathbb{P}[\sigma_{a}^{1}>t]$ is given by the following
result whose proof is defered to Appendix A.

######  Proposition 3.1.

Let $q_{t}^{a}$ be the process defined above starting at $x$, that is, the
Markov process with generator given by Equation 1 such that $q_{0}^{a}=x$. Fix
any $T>0$ and let
$\bar{u}(t,z):\mathbb{R}_{+}\times(\mathbb{N}\cup\\{0\\})\to\mathbb{R}$ be a
bounded function such that $t\mapsto\bar{u}(t,x)$ is $C_{1}(\mathbb{R})$ for
all $x$ and $(t,x)\mapsto\partial\bar{u}(t,z)/\partial t$ is bounded and
satisfies the conditions:

$\left\\{\begin{array}[]{rcl}\left(\frac{\partial}{\partial
r}+\mathscr{L}_{r}\right)\bar{u}(T-r,z)=0&\text{for}&0<r<T,\;z\in\mathbb{N}.\\\
\bar{u}(T-r,0)=0&\text{for}&0\leq r<T.\\\
\bar{u}(0,z)=1&\text{for}&z\in\mathbb{N}.\end{array}\right.$ (2)

Then,

$\bar{u}(T,x)=\mathbb{P}[\sigma_{a}^{1}(x)>T],$

where $\sigma_{a}^{1}=\inf\\{t>0\;|\;q_{t}^{a}=0\\}$.

As a first approach some assumptions on the behaviour of the rates
$\lambda_{t}$ and $\mu_{t}$ will be made.

Assumption 1: There exists a function
$\alpha_{t}:\mathbb{R}_{+}\rightarrow\mathbb{R}_{+}$ such that for some
positive constants $\lambda$ and $\mu$,

$\lambda_{t}=\lambda\alpha_{t}\qquad\qquad\text{and}\qquad\qquad\mu_{t}=\lambda\alpha_{t}$
(3)

Let $\mathcal{H}_{t}$ denote the generator of the Markov process describing
the dynamics of the queues’ size under Assumption 1, that is,

$\mathcal{H}_{t}(i,j)=\left\\{\begin{array}[]{ccl}0&\text{if}&i=0,\ j\geq
0,\\\ \mu\alpha_{t}&\text{if}&1\leq i,\ j=i-1,\\\
\lambda\alpha_{t}&\text{if}&1\leq i,\ j=i+1,\\\
-(\lambda\alpha_{t}+\mu\alpha_{t})&\text{if}&1\leq i,\ j=i,\\\
0&\text{if}&|i-j|>1.\end{array}\right.$ (4)

In the case when the rates are constant, that is when in Assumption 1 above,
$\alpha_{t}\equiv 1$, the generator $\mathscr{A}_{t}$ given in Equation 1
reduces to

$\mathcal{Q}(i,j)=\left\\{\begin{array}[]{ccl}0&\text{if}&i=0,\ j\geq 0,\\\
\mu&\text{if}&1\leq i,\ j=i-1,\\\ \lambda&\text{if}&1\leq i,\ j=i+1,\\\
-(\lambda+\mu)&\text{if}&1\leq i,\ j=i,\\\
0&\text{if}&|i-j|>1.\end{array}\right.$ (5)

Before proceeding, we will define the inter-arrival times between price
changes as follows. For
$\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
\in\\{a,b\\}$, let
$\sigma_{\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
,\mathcal{Q}}^{1}$ be the extinction times of the Markov processes as
described in Section 3 where
$\mathscr{L}^{(X,n)}_{t}(i,j)=\mathscr{L}_{t}^{(Y,n)}(i,j)=\mathcal{Q}(i,j)$.
Define in the same way the sequence $\\{\tau_{\mathcal{Q}}^{n}\\}_{n\geq 0}$
of inter-arrival times and the queue process
$q_{t,\mathcal{Q}}:=(q_{0,\mathcal{Q}}^{a},q_{0,\mathcal{Q}}^{b})$.

Analogously, for
$\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
\in\\{a,b\\}$, let
$\sigma_{\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
,\mathcal{H}}^{1}$ be the extinction times of the Markov processes as
described in Section when
$\mathscr{L}^{(X,n)}_{t}(i,j)=\mathscr{L}_{t}^{(Y,n)}(i,j)=\mathcal{H}_{t}(i,j)$.
Define in the same way the sequence $\\{\tau_{\mathcal{H}}^{n}\\}_{n\geq 0}$
of inter-arrival times and the queue process
$q_{t,\mathcal{H}}:=(q_{0,\mathcal{H}}^{a},q_{0,\mathcal{H}}^{b})$.

The following lemma gives the distribution of $\sigma_{a,\mathcal{Q}}^{1}$.

######  Lemma 3.2.

For the difference operator $\mathcal{Q}$ given by (5), a solution to the
initial value problem

$\left\\{\begin{array}[]{rcl}\left(\frac{\partial}{\partial
r}+\mathcal{Q}\right)\bar{u}(T-r,z)=0&\text{for}&0<r<T,\;z\in\mathbb{N}.\\\
\bar{u}(T-r,0)=0&\text{for}&0\leq r<T.\\\
\bar{u}(0,z)=1&\text{for}&z\in\mathbb{N}.\end{array}\right.$ (6)

is given by the function

$\bar{u}_{\mathcal{Q}}(T,x)=\left(\frac{\mu}{\lambda}\right)^{x/2}\int_{T}^{\infty}\frac{x}{s}I_{x}\left(2s\sqrt{\lambda\mu}\right)e^{-s(\lambda+\mu)}ds,$
(7)

where $I_{\nu}(\cdot)$ is the modified Bessel function of the first kind.
Consequently,
$\mathbb{P}[\sigma_{a,\mathcal{Q}}^{1}>T]=\bar{u}_{\mathcal{Q}}(T,x)$.

###### Proof.

When $\mathscr{L}_{t}\equiv\mathcal{Q}$, the model reduces to the case
consider in Cont and de Larrard, (2013). Therefore, the result follows from
Proposition 1 therein. ∎

It is important to analyze the tail behaviour of the survival distribution for
$\sigma_{a,\mathcal{Q}}^{1}$. The following lemma, whose proof is deferred to
Appendix A, establishes such behaviour.

######  Lemma 3.3.

Let $\mathcal{C}=(\sqrt{\mu}-\sqrt{\lambda})^{2}$. Then, for a sufficiently
large $T$,

$\mathbb{P}[\sigma_{a,\mathcal{Q}}^{1}>T\;|\;q_{0}^{a}=x]\sim\left\\{\begin{array}[]{rrl}\left(\frac{\mu}{\lambda}\right)^{x/2}\frac{x}{\mathcal{C}\sqrt{\pi\sqrt{\lambda\mu}}}\frac{e^{-T}}{T^{1/2}}&\text{if}&\lambda<\mu\\\
\frac{x}{\lambda\sqrt{\pi}}\frac{1}{\sqrt{T}}&\text{if}&\lambda=\mu\end{array}\right.$

Consequently, as expected, if $\lambda=\mu$,
$\mathbb{E}[\sigma_{a,\mathcal{Q}}^{1}]=\infty$, whereas if $\lambda<\mu$, for
every $k\in\mathbb{N}$,

$\mathbb{E}\left[\left(\sigma_{a,\mathcal{Q}}^{1}\right)^{k}\right]<\infty.$

######  Remark 3.4.

Notice that if $\lambda=\mu$, the results in Lemma 3.3 agree with the results
obtained in Eq. (6) in Cont and de Larrard, (2013). However, if $\lambda<\mu$,
Eq. (5) in Cont and de Larrard, (2013) says that

$\mathbb{P}[\sigma_{a,\mathcal{Q}}^{1}>T\;|\;q_{0}^{a}=x]\sim\frac{x(\lambda+\mu)}{2\lambda(\mu-\lambda)}\frac{1}{T},$

which is not correct, due to the well known fact that a Birth and death
process with a death rate larger than its birth rate, its extinction time,
$\sigma_{a,\mathcal{Q}}^{1}$, has moments of all orders (an easy way to see
this is to use the Moment Generating Function (MGF) computed on Proposition 1
in Cont and de Larrard, (2013) and observe that if $\lambda<\mu$, then the MGF
is defined on an open interval around 0 (c.f. Billingsley, (1995)[Section
21]).

Lemma 3.2 allows a closed formula to be obtained for the distribution of
$\sigma_{a,\;\mathcal{H}}^{1}$, when the rates are proportional to each other,
as in Assumption 1. Such a formula is described in the following proposition,
whose proof is deferred to Appendix A.

######  Proposition 3.5.

Under Assumption 1, for $A_{t}=\int_{0}^{t}\alpha_{s}ds$, the distribution of
$\sigma_{a,\mathcal{H}}^{1}$ is given by

$\mathbb{P}[\sigma_{a,\mathcal{H}}^{1}>T|\;q_{0}^{a}=x]=\left(\frac{\mu}{\lambda}\right)^{x/2}\int_{A_{T}}^{\infty}\frac{x}{s}I_{x}\left(2s\sqrt{\lambda\mu}\right)e^{-s(\lambda+\mu)}ds,$

where $I_{\nu}(\cdot)$ is the modified Bessel function of the first kind.

######  Remark 3.6.

Lemma 3.2 and Proposition 3.5 imply that

$\mathbb{P}[\sigma_{a,\mathcal{H}}^{1}>T|\;q_{0}^{a}=x]=\mathbb{P}[\sigma_{a,\mathcal{Q}}>A_{T}|\;q_{0}^{a}=x].$

This implies that the distribution of the time between price changes in the
present model is comparable to the distribution of the inter-arrival time
between price changes for the model presented in Cont and de Larrard, (2013)

Finally, we present the distribution of the time for the first price change.

######  Corollary 3.7.

Under Assumption 1, for $A_{t}=\int_{0}^{t}\alpha_{s}ds$, the distribution of
$\tau_{\mathcal{H}}^{1}$ is given by

$\mathbb{P}[\tau_{\mathcal{H}}^{1}>T\;|\;q_{0}^{a}=x,q_{0}^{b}=y]=\mathbb{P}[\sigma_{a,\mathcal{H}}^{1}>T|\;q_{0}^{a}=x]\mathbb{P}[\sigma_{a,\mathcal{H}}^{1}>T|\;q_{0}^{a}=y],$

where using the formula in proposition 3.5.

###### Proof.

The result follows from the fact that
$\tau_{\mathcal{H}}^{n}=\sigma_{a,\mathcal{H}}^{n}\wedge\sigma_{\mathcal{H},b}^{n}$,
Lemma 3.5 and the independence between $\sigma_{a,\mathcal{H}}^{n}$ and
$\sigma_{b,\mathcal{H}}^{n}$. ∎

Now, the asymptotic behaviour of the survival distribution function of
$\tau_{\mathcal{H}}^{1}$ is presented and its proof is deferred to Appendix A.

######  Lemma 3.8.

Let $\mathcal{C}=(\sqrt{\mu}-\sqrt{\lambda})^{2}$. Then,

$\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>T\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]\sim\left\\{\begin{array}[]{rrl}\left(\frac{\mu}{\lambda}\right)^{(x+y)/2}\frac{xy}{\pi\mathcal{C}^{2}\sqrt{\lambda\mu}}\frac{\exp(-2A_{T}\mathcal{C})}{A_{T}}&\text{if}&\lambda<\mu\\\\[11.38092pt]
\dfrac{xy}{\lambda^{2}\pi}\dfrac{1}{A_{T}}&\text{if}&\lambda=\mu\end{array}\right.$

Moreover, if

  * •

$\alpha_{t}\sim t^{s}\log^{m}(t)$ as $t\to\infty$ for some $s\neq-1$, $m\geq
0$, and $n\in\mathbb{N}$,

$\mathbb{E}\left[\left(\tau_{\mathcal{H}}^{1}\right)^{n}\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]\left\\{\begin{array}[]{rrl}<\infty&\text{if}&\lambda<\mu\\\
<\infty&\text{if}&\lambda=\mu\text{ and }n<s+1\\\
=\infty&\text{if}&\lambda=\mu\text{ and }n\geq s+1\end{array}\right.$

  * •

$\alpha_{t}\sim k/t$ as $t\to\infty$ for some $k>0$,

$\mathbb{E}\left[\left(\tau_{\mathcal{H}}^{1}\right)^{n}\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]\left\\{\begin{array}[]{rrl}<\infty&\text{if}&n<2k\mathcal{C}\text{
and }\lambda<\mu\\\ =\infty&\text{if}&n\geq 2k\mathcal{C}\text{ and
}\lambda<\mu\\\ =\infty&\text{if}&\lambda=\mu\end{array}\right.$

###  3.2 Long-run dynamics of the price process

We are interested in analyzing the asymptotic behaviour of the number of price
changes up to time $t$. That is, in describing

$N_{t}^{\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
}:=\max\\{n>0\;|\;\tau_{\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
}^{1}+\tau_{\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
}^{2}+\ldots+\tau_{\,\begin{picture}(-1.0,1.0)(-1.0,-2.0)\circle*{2.0}\end{picture}\
}^{n}\leq t\\},$ (8)

where, $\tau_{\mathcal{Q}}^{n}$ and $\tau_{\mathcal{H}}^{n}$ are defined
above.

The next proposition, whose proof is deferred to Appendix A, provides an
expression which relates the distribution of the partial sums for the waiting
times between price changes for the models with the generators
$\mathcal{H}_{t}$ and $\mathcal{Q}$.

######  Proposition 3.9.

Let
$S_{\mathcal{H}}^{n}:=\tau_{\mathcal{H}}^{1}+\tau_{\mathcal{H}}^{2}+\ldots+\tau_{u\mathcal{H}}^{n}$
and
$S_{\mathcal{Q}}^{n}:=\tau_{\mathcal{Q}}^{1}+\tau_{\mathcal{Q}}^{2}+\ldots+\tau_{\mathcal{Q}}^{n}$.
Then,

$\mathbb{P}[S^{n}_{\mathcal{H}}\leq t]=\mathbb{P}[S^{n}_{\mathcal{Q}}\leq
A_{t}],$

where $A_{t}=\int_{0}^{t}\alpha_{s}ds$ in accordance with Assumption 1.

The following results provide the convergence of the price process. For
presentation purposes we separate them into the case when $\lambda<\mu$ and
when $\lambda=\mu$.

######  Theorem 3.10.

Assume $\lambda<\mu$ and let $\mathcal{C}=(\sqrt{\mu}-\sqrt{\lambda})^{2}$.
Then, under Assumption 1, for $A_{t}=\int_{0}^{t}\alpha_{s}ds$,

  * •

If $\dfrac{\alpha_{t}}{t^{s}}\to\widetilde{K}$ with $s\neq-1$ or if
$\dfrac{\alpha_{t}}{t^{-1}}\to K$ as $t\to\infty$, with $2\mathcal{C}K>1$, the
rescaled price process converges and for the sequence $t_{n}=nt$ and a
constant $\sigma$, in distribution,

$\frac{s_{t_{n}}}{\sqrt{n}}\Rightarrow\sigma W_{t}$

  * •

If $\dfrac{\alpha_{t}}{t^{-1}}\sim K$ with $2\mathcal{C}K\leq 1$ as
$t\to\infty$, the rescaled price process converges and for the sequence
$t_{n}=tn^{1/2k\mathcal{C}}$ and a constant $\sigma$, in distribution,

$\frac{s_{t_{n}}}{\sqrt{n}}\Rightarrow\sigma\int_{0}^{t}\sqrt{\frac{1}{u^{1-2\mathcal{C}K}}}dW_{u}$

######  Theorem 3.11.

Assume $\lambda=\mu$. Then, under Assumption 1, for
$A_{t}=\int_{0}^{t}\alpha_{s}ds$,

  * •

If $\alpha_{t}\sim t^{-1+s}$ as $t\to\infty$, for any $s>1$, the rescaled
price process converges and for the sequence $t_{n}=nt$ and a constant
$\sigma$, in distribution,

$\frac{s_{t_{n}}}{\sqrt{n}}\Rightarrow\sigma W_{t}$

  * •

If $\alpha_{t}\sim t^{-1+s}$ as $t\to\infty$ for any $s\in(0,1]$, the rescaled
price process converges and for the sequence $t_{n}=t(n)^{1/s}\log(n)$ and a
constant $\sigma$, in distribution,

$\frac{s_{t_{n}}}{\sqrt{n}}\Rightarrow\sigma\int_{0}^{t}\sqrt{\frac{1}{u^{s}}}dW_{u}$

  * •

If $\alpha_{t}=o(t^{-1+s})$, for some $s>0$, the price process converges
cannot be rescaled to ensure convergence.

######  Remark 3.12.

It is important to notice that we recover the model proposed by Cont and de
Larrard, (2013) in our current setting. Indeed, for recovering their model,
$\alpha_{t}$ should be chosen such that $\alpha_{t}\equiv 1=x^{0}$. In such
case,

  * •

If $\lambda<\mu$ and $\alpha_{t}=1$, then $\alpha_{t}/t^{-1}\to\infty$ and the
result in Cont and de Larrard, (2013) follows immediately from Theorem 3.10.

  * •

If $\lambda=\mu$ and $\alpha_{t}=t^{-1+1}$, it becomes the borderline case in
Theorem 3.11. In such case, we can see from the proof of the aforementioned
theorem that we need to choose the rescaling sequence $t_{n}=tn\log(n)$, but
we get convergence to a Brownian motion with constant volatility.

##  4 Empirical Results

In this paper six different stocks will be analyzed. These stocks vary on the
type of sector they belong to and in their frequency of trading as well as
other properties. The main goal is to see the different quantities being fit
to the model and to contrast them to the model in Cont and de Larrard, (2013).
The selected stocks were CSCO, FB, INTC, MSFT, LBTYK and VOD and all were
analyzed on the week of Nov 3rd to Nov 7th of 2014.

The first quantity that will be analyzed in this paper will be the
distribution of the time between price changes. From Lemma 3.8, it follows
that

$\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>T\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]\sim\left\\{\begin{array}[]{rrl}\left(\frac{\mu}{\lambda}\right)^{(x+y)/2}\frac{xy}{\pi\mathcal{C}^{2}\sqrt{\lambda\mu}}\frac{\exp(-2A_{T}\mathcal{C})}{A_{T}}&\text{if}&\lambda<\mu\\\\[11.38092pt]
\dfrac{xy}{\lambda^{2}\pi}\dfrac{1}{A_{T}}&\text{if}&\lambda=\mu\end{array}\right.$

Then, by adding over all possible initial positions of the queues and
multiplying by the prbability that such position occurs, we have that

$\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>T\right]\sim\left\\{\begin{array}[]{rrl}\sum\limits_{x=1}^{\infty}\sum\limits_{y=1}^{\infty}\left(\frac{\mu}{\lambda}\right)^{(x+y)/2}\frac{xyf(x,y)}{\pi\mathcal{C}^{2}\sqrt{\lambda\mu}}\frac{\exp(-2A_{T}\mathcal{C})}{A_{T}}&\text{if}&\lambda<\mu\\\\[11.38092pt]
\sum\limits_{x=1}^{\infty}\sum\limits_{y=1}^{\infty}\dfrac{xyf(x,y)}{\lambda^{2}\pi}\dfrac{1}{A_{T}}&\text{if}&\lambda=\mu\end{array}\right.$

By taking derivatives and using L’Hopital rule, we have that if
$f_{\tau_{\mathcal{H}}^{1}}(t)$ is the density of $\tau_{\mathcal{H}}^{1}$
then,

$f_{\tau_{\mathcal{H}}^{1}}(t)\sim\left\\{\begin{array}[]{rrl}\sum\limits_{x=1}^{\infty}\sum\limits_{y=1}^{\infty}\left(\frac{\mu}{\lambda}\right)^{(x+y)/2}\frac{xyf(x,y)}{\pi\mathcal{C}^{2}\sqrt{\lambda\mu}}\frac{(2\mathcal{C}A_{T}+1)\alpha_{T}\exp(-2A_{T}\mathcal{C})}{A_{T}^{2}}&\text{if}&\lambda<\mu\\\\[11.38092pt]
\sum\limits_{x=1}^{\infty}\sum\limits_{y=1}^{\infty}\dfrac{xyf(x,y)}{\lambda^{2}\pi}\dfrac{\alpha_{T}}{A_{T}^{2}}&\text{if}&\lambda=\mu\end{array}\right.$
(9)

The next figure show the empirical densities of
$f_{\tau_{\mathcal{H}}^{1}}(t)$ for the six picked stocks. As it will be shown
in Table 3, in all six cases it happens that,in average, $\mu<\lambda$ but in
almost all cases $\mu/\lambda>0.9$.

Figure 1: Densities of the inter-arrival time between price changes on the six
stocks for the week of Nov 3rd to Nov 7th of 2014.

Next, the intensities of Limit orders at the ask side, $\lambda_{t}^{a}$, and
Market orders plus Cancellations, $\mu_{t}^{a}$, are plotted for each stock.
In each plot the intensity $\lambda_{t}^{a}$ or $\mu_{t}^{a}$ is computed for
each day of the week and a power-law fit is found using regression. The
results of the regression are summarized in Table 1 after the corresponding
figure.

Figure 2: Daily intensities of Limit Orders at the Ask side for the six stocks
considered on the week of Nov 3rd to Nov 7th of 2014 and their corresponding
power law fit.

Figure 3: Daily intensities of Marker Orders plus Cancellations on the Ask
side for the six stocks considered on the week of Nov 3rd to Nov 7th of 2014
and their corresponding power law fit.

In order to approximate the the long-run dynamics of the price process as
stated in Theorems (3.10)-(3.11), a power law fit to the intensity of Limit
Orders $\lambda_{t}^{a}$ at the ask side was fit in each of the six stocks
analyzed. That is, a regression is performed to fit
$\lambda_{t}^{a}\approx\frac{K_{\lambda,a}}{t^{s}}$. Similarly, a power law
fit to the intensity of Market Orders plus Cancellations $\mu_{t}^{a}$ at the
ask side was fit in each of the six stocks analyzed. In this case, a
regression is performed to fit $\mu_{t}^{a}\approx\frac{K_{\mu,a}}{t^{r}}$.
The following table summarizes the power law fit to the intensities of the
analyzed stocks.

Stock | Fit for $\lambda_{t}^{a}\approx K_{\lambda,a}t^{-s}$ | Fit for $\mu_{t}^{a}\approx K_{\mu,a}t^{-r}$
---|---|---
Coefficient $K_{\lambda,a}$ |  Exponent $s$ |  Coefficient $K_{\mu,a}$ | Exponent $r$
CSCO | 0.1703 | 0.4560 | 0.1790 | 0.4412
FB | 0.4664 | 1.0045 | 0.5429 | 1.0073
INTC | 0.2604 | 0.6127 | 0.3582 | 0.6515
MSFT | 0.4002 | 0.6153 | 0.4671 | 0.6363
LBTYK | 0.0146 | 0.7438 | 0.0211 | 0.8640
VOD | 0.1199 | 0.5536 | 0.1927 | 0.6116
Table 1: Regression fit for $\lambda_{t}^{a}\approx Ct^{-s}$ and
$\mu_{t}^{a}\approx Dt^{-r}$ for all six stocks analyzed.

Now, the intensities of Limit orders at the bid side, $\lambda_{t}^{b}$, and
Market orders plus Cancellations, $\mu_{t}^{b}$, are now plotted for each
stock. Similarly as before, in each plot the intensity $\lambda_{t}^{b}$ or
$\mu_{t}^{b}$ is computed for each day of the week and a power-law fit is
found using regression. The results of the regression are summarized in Table
2 after the corresponding figure.

Figure 4: Daily intensities of Limit Orders at the Bid side for the six stocks
considered on the week of Nov 3rd to Nov 7th of 2014 and their corresponding
power law fit.

Figure 5: Daily intensities of Marker Orders plus Cancellations on the Bid
side for the six stocks considered on the week of Nov 3rd to Nov 7th of 2014
and their corresponding power law fit.

In the same fashion as before, a power law fit to the intensity of Limit
Orders $\lambda_{t}^{b}$ at the bid side was fit in each of the six stocks
analyzed. That is, a regression is performed to fit
$\lambda_{t}^{b}\approx\frac{K_{\lambda,b}}{t^{s}}$. Similarly, a power law
fit to the intensity of Market Orders plus Cancellations $\mu_{t}^{b}$ at the
bid side was fit in each of the six stocks analyzed. In this case, a
regression is performed to fit $\mu_{t}^{b}\approx\frac{K_{\mu,b}}{t^{r}}$.
The following table summarizes the power law fit to the intensities of the
analyzed stocks.

Stock |  Fit for $\lambda_{t}^{b}\approx K_{\lambda,b}t^{-s}$ |  Fit for $\mu_{t}^{b}\approx K_{\mu,b}t^{-r}$
---|---|---
Coefficient $K_{\lambda,b}$ |  Exponent $s$ |  Coefficient $K_{\mu,b}$ |  Exponent $r$
CSCO | 0.1264 | 0.4149 | 0.1775 | 0.4509
FB | 0.4584 | 1.0039 | 0.5359 | 1.0064
INTC | 0.2041 | 0.5872 | 0.3525 | 0.6649
MSFT | 0.3887 | 0.6163 | 0.5014 | 0.6522
LBTYK | 0.0127 | 0.7466 | 0.0196 | 0.8352
VOD | 0.1223 | 0.5806 | 0.2143 | 0.6566
Table 2: Regression fit for $\lambda_{t}^{b}\approx Ct^{-s}$ and
$\mu_{t}^{a}bapproxDt^{-r}$ for all six stocks analyzed.

Finally, in order to assess how close the quotients
$\lambda_{t}^{a}/\mu_{t}^{a}$ and $\lambda_{t}^{b}/\mu_{t}^{b}$ behave like
constants, a plot of this quotients is presented along with their average.
First the quotients at the ask side are presented and then the quotients at
the bid. As it can be observed, in all cases, the quotient is less than 1
indicating that the queues are in a stationary case.

Figure 6: Plot of the quotient $\lambda_{t}^{a}/\mu_{t}^{a}$ versus the time
$t$. The assumption of a constant quotient is contrasted here.

Next, the quotient on the bid side is displayed.

Figure 7: Plot of the quotient $\lambda_{t}^{b}/\mu_{t}^{b}$ versus the time
$t$. The assumption of a constant quotient is contrasted here.

The last component of this section is a table that compares the mean of the
quotient $\lambda_{t}^{a}/\mu_{t}^{a}$ for the ask side of all six stocks with
the same quotient $\lambda_{t}^{b}/\mu_{t}^{b}$ for the bid side for all six
stocks.

Stock |  Mean of the quotient $\lambda_{t}^{a}/\mu_{t}^{a}$ |  Mean of the quotient $\lambda_{t}^{b}/\mu_{t}^{b}$
---|---|---
CSCO | 0.9598 | 0.9392
FB | 0.9927 | 0.9993
INTC | 0.9441 | 0.9544
MSFT | 0.9901 | 0.9912
LBTYK | 0.9998 | 0.9498
VOD | 0.8919 | 0.9255
Table 3: Comparison of the mean quotient of the intensities for limit orders
vs market orders plus cancellations at the ask side and the bid side for all
six stocks analyzed.

##  5 Conclusions and Further Research

For this paper, a simple limit order book model was proposed with the
intention to further study the empirical features of these complicated
systems. In particular, this paper tries to focus and understand the empirical
features of the inter-arrival times between order submissions and how do these
empirical features may affect the fluid dynamics of the price process. Indeed,
as shown in section 3, depending on the speed at which the density of the
times between arrivals of orders decays, the long-run dynamics of the price
process might have a time-dependent volatility. This is an important feature
because it will be interesting to find conditions under which the long-run
dynamics of the price process possess converges to a more general Ito
diffusion than a simple Brownian motion with constant volatility, say a
geometric Brownian motion, which is one of the most used models for stock
prices. Further, many of the existing models, to the knowledge of the author,
that try to achieve these convergence define a point process that counts the
arrivals of the price changes but not of the orders. That is, many work at a
mesoscopic level but not at the microscopic level generated by accounting for
the individual orders.

In this intent to create simple models that generalize the long-run dynamics
of the price process, this paper has shown that different cases might arise.
For example, while CSCO, INTC and VOD exhibit a quotient
$\lambda_{t}/\mu_{t}<1$, implying that they will fall under the case covered
in Theorem 3.10 and since all of them have a tail that decays as a power law
with exponent different from $-1$, they will converge to a simple Brownian
motion with constant volatility. However, for the other three stocks (FB, MSFT
and LBTYK), it can be seen that their quotient $\lambda_{t}/\mu_{t}<1$ is
significantly close to 1, implying that they will fall under the case covered
in Theorem 3.11, and in here, two cases arise: while MSFT and LBTYK have a
tail that decays slower than $t^{-1}$ and thus will converge to a Brownian
motion with a time-dependent volatility, FB exhibits a tail that is barely
heavier that $t^{-1}$, implying that it will converge to a normal Brownian
motion with constant volatility.

As it can be seen with this small sample of stocks, many different scenarios
have arose, implying that these conditions imposed in the model are
attainable. Of course, the model has some limitations and many simplifications
took place, but the author believes that this is the first step towards
working in obtaining more realistic models such as a GBM. A good example of
how these models have been found but where the taken scale is a mesoscopic one
is provided on Jaisson and Rosenbaum, (2015), where the authors use almost
unstable Hawkes processes to achieve convergence to a GBM starting from
modeling the times of arrivals of the price changes. An interesting model
would then become to consider how to use similar results to achieve
convergence to such processes starting from the arrival of individual orders
and no from the aggregated data. The difficult part in all of these models is
to understand the tail behaviour of the stopping time that signals a price
change, such as the one provided in Lemma 3.8. While the author believes that
many more interesting features can be achieved by substituting the
inhomogeneous Poisson process by a more general point process such as a Hawkes
process, or even better, a state-dependent Hawkes process (one where the
intensity depends on the state of the process) the complicated part is to
unravel the behavior of the aforementioned stopping time and this will become
an interesting research direction for the near future.

## References

  * Billingsley, (1995) Billingsley, P. (1995).  Probability and measure.  Wiley Series in Probability and Mathematical Statistics. John Wiley & Sons Inc., New York, third edition.  A Wiley-Interscience Publication.
  * Bouchaud et al., (2009) Bouchaud, J., Farmer, J., and Lillo, F. (2009).  How markets slowly digest changes in supply and demand.  Proceedings of the Handbook of Financial Markets: Dynamics and Evolution, 9(70):57–160.
  * Cartea and Jaimungal, (2015) Cartea, A. and Jaimungal, S. (2015).  Optimal execution with limit and market orders.  Quantitative Finance, 0(0):1–13.
  * Chávez-Casillas et al., (2019) Chávez-Casillas, J. A., Elliott, R. J., Rémillard, B., and Swishchuk, A. V. (2019).  A level-1 limit order book with time dependent arrival rates.  Methodology and Computing in Applied Probability, 21(3):699–719.
  * Cont and de Larrard, (2013) Cont, R. and de Larrard, A. (2013).  Price dynamics in a markovian limit order market.  SIAM Journal on Financial Mathematics, 4(1):1–25.
  * Cont et al., (2010) Cont, R., Stoikov, S., and Talreja, R. (2010).  A stochastic model for order book dynamics.  Operations Research, 58(3):549–563.
  * Eisler et al., (2012) Eisler, Z., Bouchaud, J.-P., and Kockelkoren, J. (2012).  The price impact of order book events: market orders, limit orders and cancellations.  Quantitative Finance, 12:1395–1419.
  * Engle et al., (2006) Engle, R. F., Ferstenberg, R., and Russell, J. R. (2006).  Measuring and Modeling Execution Cost and Risk.  NYU Working Paper.
  * Foucault et al., (2003) Foucault, T., Kadan, O., and Kandel, E. (2003).  Limit Order Book as a Market for Liquidity.  Discussion paper series, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
  * Gould et al., (2013) Gould, M. D., Porter, M. A., Williams, S., McDonald, M., Fenn, D. J., and Howison, S. D. (2013).  Limit order books.  Quantitative Finance, 13(11):1709–1742.
  * Gut, (2013) Gut, A. (2013).  Probability: a graduate course, volume 75.  Springer Science & Business Media.
  * Harris, (2003) Harris, L. (2003).  Trading and exchanges: market microstructure for practitioners.  Oxford University Press.
  * Harris and Hasbrouck, (1996) Harris, L. and Hasbrouck, J. (1996).  Market vs. limit orders: The superdot evidence on order submission strategy.  Journal of Financial and Quantitative Analysis, 31:213–231.
  * Jaisson and Rosenbaum, (2015) Jaisson, T. and Rosenbaum, M. (2015).  Limit theorems for nearly unstable hawkes processes.  The Annals of Applied Probability, 25(2):600–631.
  * Kirilenko et al., (2011) Kirilenko, A., Kyle, A. S., Samadi, M., and Tuzun, T. (2011).  The flash crash: The impact of high frequency trading on an electronic market.
  * Law, (2015) Law, B. (2015).  A pure-jump market-making model for high-frequency trading.  PhD thesis, Purdue University.
  * Obizhaeva and Wang, (2013) Obizhaeva, A. A. and Wang, J. (2013).  Optimal trading strategy and supply/demand dynamics.  Journal of Financial Markets, 16(1):1 – 32.
  * Olver et al., (2010) Olver, F. W., Lozier, D. W., Boisvert, R. F., and Clark, C. W. (2010).  NIST Handbook of Mathematical Functions.  Cambridge University Press, New York, NY, USA, 1st edition.

##  Appendix A Proofs of Section 3

###### Proof of Proposition 3.1.

. The arrival processes $L_{t}$ and $M_{t}$ are Markov processes. Moreover,
the queue process, describing the amount of orders at the ask, $q_{t}^{a}$ is
also a Markov process with its generator given by Equation 1. That is, for any
function $u\in\text{Dom}(\mathscr{L}_{t})$, $t\in\mathbb{R}^{+}$ and
$z\in\mathbb{N}$,

$\mathscr{L}_{t}u(t,z)=\lambda_{t}u(t,z+1)+\mu_{t}u(t,z-1)-(\lambda_{t}+\mu_{t})u(t,z).$
(10)

Let $\bar{u}(t,x)$ be an arbitrary bounded function such that
$t\mapsto\bar{u}(t,x)$ is $C_{1}$ for all $x$ and
$(t,x)\mapsto\partial\bar{u}(t,x)/\partial t$ is bounded. Fix $T>0$ and let
$f(t,x)=\bar{u}(T-t,x)$. Under the stated conditions, $\bar{u}$ belongs to the
domain of the generator $\mathscr{L}_{t}$ and, thus, the process

$f(t,q_{t}^{a})-f(0,q_{0}^{a})-\int_{0}^{t}\left(\frac{\partial}{\partial
r}+\mathscr{L}_{r}\right)f(r,q_{r}^{a})dr,\quad t\in[0,T]$

is a local martingale. Therefore,

$M_{t}:=\bar{u}(T-t,q_{t})-\bar{u}(T,q_{0})-\int_{0}^{t}\left(\frac{\partial}{\partial{r}}+\mathscr{L}_{r}\right)\bar{u}(T-r,q_{r})dr,\quad{t\in[0,T]},$

is a martingale with $M_{0}=0$. Let $\varsigma:=T\wedge\sigma_{a}^{1}$. By the
Optional Sampling Theorem,

$\bar{u}(T,x)=\mathbb{E}_{x}[\bar{u}(T-\varsigma,{q_{\varsigma}})]-\mathbb{E}_{x}\left[\int_{0}^{\varsigma}\left(\frac{\partial}{\partial{r}}+\mathscr{L}_{r}\right)\bar{u}(T-r,q_{r})dr\right],$
(11)

where $\mathbb{E}_{x}[\cdot]:=\mathbb{E}[\;\cdot\;|\;q_{0}=x]$.

On the other hand, suppose that $\bar{u}(t,x)$ solves the initial value
problem 2. That is, $\bar{u}(t,x)$ satisfies

$\left\\{\begin{array}[]{rcl}\left(\frac{\partial}{\partial
r}+\mathscr{L}_{r}\right)\bar{u}(T-r,z)=0&\text{for}&0<r<T,\;z\in\mathbb{N}.\\\
\bar{u}(T-r,0)=0&\text{for}&0\leq r<T.\\\
\bar{u}(0,z)=1&\text{for}&z\in\mathbb{N}.\end{array}\right.$

In that case, by (11),

$\displaystyle\bar{u}(T,x)$ $\displaystyle=$
$\displaystyle\mathbb{E}[\bar{u}(T-\varsigma,q_{\varsigma})]$ $\displaystyle=$
$\displaystyle\mathbb{E}[\bar{u}(T-\varsigma,q_{\varsigma})\mathbb{I}\\{\sigma_{a}^{1}\leq
T\\}+\bar{u}(T-\varsigma,q_{\varsigma})\mathbb{I}\\{\sigma_{a}^{1}>T\\}]$
$\displaystyle=$
$\displaystyle\mathbb{E}[\bar{u}(T-\sigma_{a}^{1},0)\mathbb{I}\\{\sigma_{a}^{1}\leq
T\\}+\bar{u}(0,q_{T})\mathbb{I}\\{\sigma_{a}^{1}>T\\}]$ $\displaystyle=$
$\displaystyle\mathbb{P}[\sigma_{a}^{1}(x)>T].$

This implies that $\bar{u}(T,x)=\mathbb{P}[\sigma_{a}^{1}(x)>T]$.

∎

###### Proof of Lemma 3.3.

According to Olver et al., (2010)[Formula 10.30.4], for fixed $\nu$,

$I_{\nu}(x)\sim\frac{e^{x}}{\sqrt{2\pi x}}\qquad\qquad\text{as}x\to\infty.$

Thus, as $T\to\infty$,

$\displaystyle\mathbb{P}[\sigma_{a,\mathcal{Q}}^{1}>T\;|\;q_{0}^{a}=x]$
$\displaystyle=$
$\displaystyle\left(\frac{\mu}{\lambda}\right)^{x/2}\int_{T}^{\infty}\frac{x}{s}I_{x}\left(2s\sqrt{\lambda\mu}\right)e^{-s(\lambda+\mu)}ds$
$\displaystyle\sim$
$\displaystyle\left(\frac{\mu}{\lambda}\right)^{x/2}\int_{T}^{\infty}\frac{x}{s}\frac{e^{2s\sqrt{\lambda\mu}}}{\sqrt{4s\pi\sqrt{\lambda\mu}}}e^{-s(\lambda+\mu)}ds$
$\displaystyle\sim$
$\displaystyle\left(\frac{\mu}{\lambda}\right)^{x/2}\int_{T}^{\infty}\frac{x}{2\sqrt{\pi\sqrt{\lambda\mu}}}s^{-3/2}e^{-s(\sqrt{\mu}-\sqrt{\lambda})^{2}}ds$

Consequently, if $\lambda=\mu$,

$\displaystyle\mathbb{P}[\sigma_{a,\mathcal{Q}}^{1}>T\;|\;q_{0}^{a}=x]$
$\displaystyle\sim\int_{T}^{\infty}\frac{x}{2\lambda\sqrt{\pi}}s^{-3/2}ds$
$\displaystyle\sim\frac{x}{2\lambda\sqrt{\pi}}\frac{2}{\sqrt{T}}$
$\displaystyle\sim\frac{x}{\lambda\sqrt{\pi}}\frac{1}{\sqrt{T}}.$

This agrees with the result proved in Cont and de Larrard, (2013). However, if
$\lambda<\mu$,

$\displaystyle\mathbb{P}[\sigma_{a,\mathcal{Q}}^{1}>T\;|\;q_{0}^{a}=x]$
$\displaystyle\sim\left(\frac{\mu}{\lambda}\right)^{x/2}\int_{T(\sqrt{\mu}-\sqrt{\lambda})^{2}}^{\infty}\frac{x}{2\sqrt{\pi\sqrt{\lambda\mu}}}\frac{(\sqrt{\mu}-\sqrt{\lambda})^{3}}{u^{3/2}}e^{-u}\frac{du}{(\sqrt{\mu}-\sqrt{\lambda})^{2}}$
$\displaystyle\sim\left(\frac{\mu}{\lambda}\right)^{x/2}\frac{x(\sqrt{\mu}-\sqrt{\lambda})}{2\sqrt{\pi\sqrt{\lambda\mu}}}\int_{T(\sqrt{\mu}-\sqrt{\lambda})^{2}}^{\infty}u^{-3/2}e^{-u}du$
$\displaystyle=\left(\frac{\mu}{\lambda}\right)^{x/2}\frac{x(\sqrt{\mu}-\sqrt{\lambda})}{\sqrt{\pi\sqrt{\lambda\mu}}}\left[\frac{e^{-T(\sqrt{\mu}-\sqrt{\lambda})^{2}}}{(\sqrt{\mu}-\sqrt{\lambda})\sqrt{T}}-\Gamma\left(\frac{1}{2},T(\sqrt{\mu}-\sqrt{\lambda})^{2}\right)\right]$
$\displaystyle\sim\left(\frac{\mu}{\lambda}\right)^{x/2}\frac{x(\sqrt{\mu}-\sqrt{\lambda})}{\sqrt{\pi\sqrt{\lambda\mu}}}\left[\frac{e^{-T(\sqrt{\mu}-\sqrt{\lambda})^{2}}}{(\sqrt{\mu}-\sqrt{\lambda})\sqrt{T}}-T^{-3/2}e^{-T}+O(T^{-1})\right]$
$\displaystyle=\left(\frac{\mu}{\lambda}\right)^{x/2}\frac{x(\sqrt{\mu}-\sqrt{\lambda})}{\sqrt{\pi\sqrt{\lambda\mu}}}\left[\frac{e^{-T(\sqrt{\mu}-\sqrt{\lambda})^{2}}}{(\sqrt{\mu}-\sqrt{\lambda})\sqrt{T}}+o(T^{-1/2})\right]$
$\displaystyle\sim\left(\frac{\mu}{\lambda}\right)^{x/2}\frac{x(\sqrt{\mu}-\sqrt{\lambda})}{\sqrt{\pi\sqrt{\lambda\mu}}}\frac{e^{-T\mathcal{C}}}{(T\mathcal{C})^{1/2}},$

where in the second to last asymptotic expansion we used Formula 8.11.2 in
Olver et al., (2010)

Let $\mathcal{C}=(\sqrt{\mu}-\sqrt{\lambda})^{2}$. To compute the expectation
in the case where $\lambda=\mu$, notice that, for large enough $T$,

$\mathbb{E}\left[\sigma_{a,\mathcal{Q}}^{1};|\;q_{0}^{a}=x\right]=\int_{0}^{\infty}\mathbb{P}[\sigma_{a,\mathcal{Q}}^{1}>t;|\;q_{0}^{a}=x]dt\geq\frac{x}{\lambda\sqrt{\pi}}\int_{0}^{\infty}\frac{1}{\sqrt{t}}dt=\infty,$

whereas if $\lambda<\mu$, for a sufficiently large $T$, there are finite
constants $\widehat{C_{1}}$ and $\widehat{C_{2}}$ such that for any $n\geq 1$,

$\displaystyle\mathbb{E}\left[\left(\sigma_{a,\mathcal{Q}}^{1}\right)^{k};|\;q_{0}^{a}=x\right]$
$\displaystyle=n\int_{0}^{\infty}t^{n-1}\mathbb{P}[\sigma_{a,\mathcal{Q}}^{1}>t]dt$
$\displaystyle\leq\widehat{C_{1}}+\widehat{C_{2}}\int_{T}^{\infty}t^{n-1}\Big{(}(t\mathcal{C})^{-1/2}e^{-t\mathcal{C}}\Big{)}dt$
$\displaystyle\leq\widehat{C_{1}}+\widehat{C_{2}}\int_{T}^{\infty}t^{n-1-1/2}e^{-t\mathcal{C}}dt$
$\displaystyle=\widehat{C_{1}}+\widehat{C_{2}}\Gamma(n-1/2,T\mathcal{C})<\infty$

∎

###### Proof of Proposition 3.5.

For $0\leq t\leq A_{T}$, let $\bar{w}(t,x)$ be the function defined in
Equation 7. For $0\leq t\leq T$, set $\bar{v}(t,x)=\bar{w}(A_{t},x)$. Then,
$\bar{v}(t,x)$ belongs to the Domain of $\mathscr{L}_{t}$ and

$\frac{\partial}{\partial r}\bar{v}(T-r,x)=\frac{\partial}{\partial
r}\Bigg{[}\bar{w}(A_{T-r},x)\Bigg{]}=\frac{\partial}{\partial
r}\bar{w}(A_{T-r},x)\cdot(-a_{r})=-Q\bar{w}(A_{T-r},x)a_{r},$

for all $r\in(0,T)$ and $x\in\mathbb{N}$. However, since
$\mathscr{L}_{r}=Qa_{r}$,

$\frac{\partial}{\partial t}\bar{v}(t,x)+\mathscr{L}_{r}\bar{v}(t,x)=0$

for all $x\in\mathbb{N}$, $t\in(0,T)$. Moreover, since $\bar{w}(t,x)$
satisfies the IVP 6, for $0\leq r<T$, $\bar{v}(T-r,0)=\bar{w}(A_{T-r},0)=0$
and for any $z\in\mathbb{N}$, $\bar{v}(0,z)=\bar{w}(A_{0},z)=\bar{w}(0,z)=1$.
Thus, by Proposition 3.1, the result follows. ∎

###### Proof of Lemma 3.8.

By Remark 3.6 and Lemma 3.3, the first part is straightforward. If

  * •

$\alpha_{t}\sim t^{s}\log^{m}(t)$ as $t\to\infty$ for some $s\neq-1$,
$m\in\mathbb{N}\cup\\{0\\}$. Then, for sufficiently large $t$,
$A_{t}\geq\hat{c}t^{s+1}$. Therefore,

    * –

If $\lambda<\mu$, (by the Proof of Lemma ), there are finite constants
$\mathcal{C}$, $C_{1}$, $C_{2}$ and $C_{3}$ such that,

$\displaystyle\mathbb{E}\left[\left(\tau_{\mathcal{H}}^{1}\right)^{n}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]$
$\displaystyle=$ $\displaystyle
n\int_{0}^{\infty}t^{n-1}\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>t\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]dt$
$\displaystyle=$ $\displaystyle
n\int_{0}^{\infty}t^{n-1}\mathbb{P}\left[\tau_{\mathcal{Q}}^{1}>A_{t}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]dt$
$\displaystyle\leq$ $\displaystyle
T^{n}+n\int_{T}^{\infty}t^{n-1}\mathbb{P}\left[\tau_{\mathcal{Q}}^{1}>A_{t}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]dt$
$\displaystyle\leq$ $\displaystyle
T^{n}+C_{1}\int_{T}^{\infty}t^{n-1}\left[\left(\mathcal{C}A_{t}\right)^{-1/2}e^{-\mathcal{C}A_{t}}\right]^{2}dt$
$\displaystyle\leq$ $\displaystyle
T^{n}+C_{1}\int_{T}^{\infty}t^{n-1}\left[\left(\mathcal{C}t^{s+1}\right)^{-1/2}e^{-\mathcal{C}t^{s+1}}\right]^{2}dt$
$\displaystyle\leq$ $\displaystyle
T^{n}+C_{2}\int_{T}^{\infty}t^{n-s-2}e^{-2\mathcal{C}t^{s+1}}dt$
$\displaystyle=$ $\displaystyle
T^{n}+C_{3}\int_{T}^{\infty}u^{(n-2(s+1))/(s+1)}(u/2\mathcal{C})e^{-u}du$
$\displaystyle=$ $\displaystyle
T^{n}+C_{4}\int_{T}^{\infty}u^{n/(s+1)-2}e^{-u}du<\infty.$

    * –

If $\lambda=\mu$, there are finite constants $C_{1}$, $C_{2}$ and $C_{3}$ such
that,

$\displaystyle\mathbb{E}\left[\left(\tau_{\mathcal{H}}^{1}\right)^{n}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]$
$\displaystyle=$ $\displaystyle
n\int_{0}^{\infty}t^{n-1}\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>t\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]dt$
$\displaystyle=$ $\displaystyle
n\int_{0}^{\infty}t^{n-1}\mathbb{P}\left[\tau_{\mathcal{Q}}^{1}>A_{t}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]dt$
$\displaystyle=$ $\displaystyle
C_{1}+n\int_{T}^{\infty}t^{n-1}\mathbb{P}\left[\tau_{\mathcal{Q}}^{1}>A_{t}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]dt$
$\displaystyle=$ $\displaystyle
C_{1}+C_{2}\int_{T}^{\infty}\dfrac{xy}{\lambda^{2}\pi}t^{n-1}\dfrac{1}{A_{T}}dt$
$\displaystyle=$ $\displaystyle
C_{1}+C_{2}\int_{T}^{\infty}\frac{xy}{\lambda^{2}\pi}t^{n-s-2}dt$
$\displaystyle=$ $\displaystyle
C_{3}\mathbbm{1}_{\left\\{{n<s+1}\right\\}}+\infty\mathbbm{1}_{\left\\{{n\geq
s+1}\right\\}}.$

  * •

$\alpha_{t}\sim k/t$ for some $k>0$. Then $A_{t}\sim k\log(t)$.

    * –

If $\lambda<\mu$, for sufficiently large $T$, there are finite constants
$\mathcal{C}$, $C_{1}$, $C_{2}$ and $C_{3}$ such that,

$\displaystyle\mathbb{E}\left[\left(\tau_{\mathcal{H}}^{1}\right)^{n}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]$
$\displaystyle=$ $\displaystyle
n\int_{0}^{\infty}t^{n-1}\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>t\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]dt$
$\displaystyle=$ $\displaystyle
n\int_{0}^{\infty}t^{n-1}\mathbb{P}\left[\tau_{\mathcal{Q}}^{1}>A_{t}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]dt$
$\displaystyle=$ $\displaystyle
C_{1}+n\int_{T}^{\infty}t^{n-1}\left[A_{t}^{-1/2}e^{-\mathcal{C}A_{t}}\right]^{2}dt$
$\displaystyle=$ $\displaystyle
C_{1}+n\int_{T}^{\infty}t^{n-1}\left[(k\log(t))^{-1/2}e^{-k\mathcal{C}\log(t)}\right]^{2}dt$
$\displaystyle=$ $\displaystyle
C_{1}+C_{2}\int_{T}^{\infty}kt^{n-1-2k\mathcal{C}}\log(t)dt$ $\displaystyle=$
$\displaystyle C_{3}(\mathbb{I}\\{n<2\mathcal{C}k\\}+\infty(\mathbb{I}\\{n\geq
2\mathcal{C}k\\}).$

    * –

If $\lambda=\mu$, there are finite constants $C_{1}$, $C_{2}$ and $C_{3}$ such
that,

$\displaystyle\mathbb{E}\left[\left(\tau_{\mathcal{H}}^{1}\right)^{n}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]$
$\displaystyle=n\int_{0}^{\infty}t^{n-1}\mathbb{P}\left[\tau_{\mathcal{Q}}^{1}>A_{t}\;|\;q_{0}^{a}=x,q_{0}^{b}=y\right]dt$
$\displaystyle=C_{1}+C_{2}\int_{T}^{\infty}\dfrac{xy}{\lambda^{2}\pi}t^{n-1}\dfrac{1}{A_{T}}dt$
$\displaystyle=C_{1}+C_{2}\int_{T}^{\infty}\dfrac{xy}{\lambda^{2}\pi}t^{n-1}\dfrac{1}{k\log(t)}dt$
$\displaystyle=C_{1}+C_{3}\int_{T}^{\infty}\frac{t^{n-1}}{\log(t)}dt=\infty.$

∎

###### Proof of Proposition 3.9.

Let $F_{n,\mathcal{Q}}(t)$ and $F_{n,\mathcal{H}}(t)$ denote the cdf of
$S^{n}_{\mathcal{Q}}$ and $S^{n}_{\mathcal{H}}$, respectively. Moreover, let
$f_{n,\mathcal{Q}}(t)$ and $f_{n,\mathcal{H}}(t)$ denote their corresponding
densities. The result will be proven by induction. The base case, $n=1$ is
given in Corollary 3.7. Assume the result is true for any $m\leq
n\in\mathbb{N}$. Then by Corollary 3.7 and the induction hypothesis,

$F_{\mathcal{H}}(t)=F_{\mathcal{Q}}(A_{t})\qquad\qquad\text{and}\qquad\qquad
f_{n,\mathcal{H}}(t)=f_{n,\mathcal{Q}}(A_{t})\alpha_{t}$ (12)

Furthermore, by the definition of $\tau^{n}$ and $S^{n}$

$\displaystyle\mathbb{P}_{x,y}[S^{n+1}_{\mathcal{H}}\leq t]$
$\displaystyle=\mathbb{P}_{x,y}[S^{n}_{\mathcal{H}}\leq
t,\tau^{n+1}_{\mathcal{H}}\leq t-S^{n}_{\mathcal{Q}}]$
$\displaystyle=\int_{0}^{t}\mathbb{P}_{x,y}[S^{n}_{\mathcal{H}}\leq
t,\tau^{n+1}_{\mathcal{H}}\leq
t-S^{n}_{\mathcal{H}}\;|\;S^{n}_{\mathcal{H}}=u]\mathbb{P}_{x,y}[S^{n}_{\mathcal{H}}=u]du$
$\displaystyle=\int_{0}^{t}\mathbb{P}[\tau^{n+1}_{\mathcal{H}}\leq
t-S^{n}_{\mathcal{H}}\;|\;S^{n}_{\mathcal{H}}=u]\mathbb{P}_{x,y}[S^{n}_{\mathcal{H}}=u]du$
(13) $\displaystyle=\int_{0}^{t}\mathbb{P}[\tau^{n+1}_{\mathcal{H}}\leq
t-u]f_{n,\mathcal{H}}(u)du$ (14)
$\displaystyle=\int_{0}^{t}\mathbb{P}[\tau^{n+1}_{\mathcal{Q}}\leq
A_{t-u}]f_{n,\mathcal{Q}}(A_{u})\alpha_{u}du$
$\displaystyle=\int_{0}^{t}F_{1,\mathcal{Q}}(A_{t}-A_{u})f_{n,\mathcal{Q}}(A_{u})\alpha_{u}du$
$\displaystyle=\int_{0}^{A_{t}}F_{1,\mathcal{Q}}(A_{t}-u)f_{n,\mathcal{Q}}(u)du$
$\displaystyle=\int_{0}^{A_{t}}F_{1,\mathcal{Q}}(A_{t}-u)dF_{n,\mathcal{Q}}(u)$
$\displaystyle=\mathbb{P}_{x,y}[S^{n+1}_{\mathcal{Q}}\leq A_{t}],$

In the last equality we used the facts that $S_{n+1}=S_{n}+\tau_{n+1}$ and
that for $X$ and $Y$, non-negative independent random variables,

$F_{X+Y}(t)=\mathbb{P}[X+Y\leq
t]=F_{X}*F_{Y}(t)=\int_{0}^{t}F_{X}(t-x)dF_{Y}(x),$

with $F_{X}$ and $F_{Y}$ denoting the cdfs of $X$ and $Y$. ∎

###### Proof of Theorem 3.10.

By the dynamics of the order book described in Section 3, the sequence of
random price changes $X_{i}\in\\{-1,1\\}$ is independent. Then, if
$\lambda<\mu$ and,

  * •

If $\alpha_{t}\sim t^{s}\log^{m}(t)$ for $s\neq-1,m\geq 0$ or if
$\dfrac{\alpha_{t}}{t^{-1}}\to K$ as $t\to\infty$, with $2\mathcal{C}K>1$, by
Lemma 3.8, for every $x,y\in\mathbb{N}$,

$\mathbb{E}\left[\left(\tau_{\mathcal{H}}^{1}\right)^{n}\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]<\infty.$

Since $N_{t}=\max\\{n\geq 0\;|\;\tau_{1}+\tau_{2}+\ldots+\tau_{n}\leq t\\}$
then,

$\tau_{1}+\tau_{2}+\ldots+\tau_{N_{t}}\leq
t\leq\tau_{1}+\tau_{2}+\ldots+\tau_{N_{t}+1}.$

Dividing the previous inequality by $N_{t}$, since $N_{t}\to\infty$ as
$t\to\infty$, by using the Strong Law of Large Numbers we obtain that a.s.

$\mathbb{E}[\tau]:=\sum\limits_{x,y\in\mathbb{N}}\mathbb{E}\left[\left(\tau_{\mathcal{H}}^{1}\right)^{n}\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]f(x,y)\to\frac{t}{N_{t}}\qquad\qquad\text{
as }t\to\infty.$

Therefore, by using the sequence $t_{n}=tn$, we decompose the process
$s_{t_{n}}:=\sum\limits_{j=1}^{N_{t_{n}}}X_{i}$ as:

$s_{t_{n}}=\underbrace{\frac{s_{0}}{\sqrt{n}}}_{\hbox{I}_{n}}+\underbrace{\frac{1}{\sqrt{n}}\sum\limits_{j=1}^{[tn/\mathbb{E}[\tau_{1}]]}\left(X_{j}\right)}_{\hbox{II}_{n}}+\underbrace{\left(\frac{1}{\sqrt{n}}\sum\limits_{j=1}^{N_{t_{n}}}X_{j}-\frac{1}{\sqrt{n}}\sum\limits_{j=1}^{[tn/\mathbb{E}_{\pi}(\tau_{1})]}X_{j}\right)}_{\hbox{III}_{n}}$

As $n\rightarrow\infty$, clearly, I${}_{n}\Rightarrow 0$. Also, by Donsker’s
Invariance principle,

$\displaystyle\hbox{II}_{n}$ $\displaystyle\Rightarrow\sigma W_{t},$

where $\sigma$ is a constant. Now, since $X_{j}\in\left\\{1,-1\right\\}$, for
any $\epsilon>0$,

$\displaystyle\mathbb{P}\left(\left|\sum\limits_{j=1}^{N_{t_{n}}}X_{j}-\sum\limits_{j=1}^{[tn/\mathbb{E}[\tau_{1}]]}\Pi_{j}\right|\geq\epsilon\sqrt{n}\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\sum\limits_{j=N_{t_{n}}\wedge[tn/\mathbb{E}[\tau_{1}]]}^{N_{t_{n}}\vee[tn/\mathbb{E}[\tau_{1}]]}X_{j}\right|\geq\epsilon\sqrt{n}\right)$
$\displaystyle\leq\mathbb{P}\left(\frac{1}{2}\left|N_{t_{n}}-[tn/\mathbb{E}[\tau_{1}]]\right|\geq\epsilon\sqrt{n}\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\frac{N_{t_{n}}}{[tn/\mathbb{E}[\tau_{1}]]}-1\right|\geq\frac{2\epsilon\sqrt{n}}{[tn/\mathbb{E}[\tau_{1}]]}\right),$

which converges to 0 as $n\rightarrow\infty$. Thus, IIIn converges to 0 in
probability and we conclude the proof.

  * •

If $\dfrac{\alpha_{t}}{t^{-1}}\sim K$ with $2\mathcal{C}K\leq 1$ as
$t\to\infty$, then $A_{T}\sim k\log(T)$. By Lemma 3.8

$\displaystyle\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>T\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]$
$\displaystyle\sim\left(\frac{\mu}{\lambda}\right)^{(x+y)/2}\frac{xy}{\pi\mathcal{C}^{2}\sqrt{\lambda\mu}}\frac{\exp(-2\mathcal{C}k\log(T))}{k\log(T)}$
$\displaystyle\sim\left(\frac{\mu}{\lambda}\right)^{(x+y)/2}\frac{xy}{\pi\mathcal{C}^{2}\sqrt{\lambda\mu}}\frac{T^{-2\mathcal{C}k}}{k\log(T)}$
$\displaystyle\sim\left(\frac{\mu}{\lambda}\right)^{(x+y)/2}\frac{xy}{\pi\mathcal{C}^{2}\sqrt{\lambda\mu}}\frac{1}{kT^{2\mathcal{C}k}\log(T)}$

Therefore,

$\displaystyle
n\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>n^{1/2k\mathcal{C}}\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]$
$\displaystyle\sim
n\left[\left(\frac{\mu}{\lambda}\right)^{(x+y)/2}\frac{xy}{\pi\mathcal{C}^{2}\sqrt{\lambda\mu}}\frac{1}{kn\log(n^{1/2k\mathcal{C}})}\right]$
$\displaystyle\sim\left(\frac{\mu}{\lambda}\right)^{(x+y)/2}\frac{xy}{\pi\mathcal{C}^{2}\sqrt{\lambda\mu}}\frac{1}{k\log(n^{1/2k\mathcal{C}})}.$

Thus,

$n\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>n^{1/2k\mathcal{C}}\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]\to
0\qquad\qquad\text{ as }n\to\infty.$

and by Theorem 6.4.2 in Gut, (2013), in probability,

$\frac{S_{n}-n\mathbb{E}\left[\tau_{\mathcal{H}}^{1}\mathbbm{1}_{\left\\{{\tau_{\mathcal{H}}^{1}<n^{1/2k\mathcal{C}}}\right\\}}\right]}{n^{1/2k\mathcal{C}}}\to
0\qquad\qquad\text{ as }n\to\infty.$

By Proposition B.1,
$\hat{\mathcal{A}}:=\lim_{n\to\infty}\frac{n\mathbb{E}[\tau\mathbb{I}\\{\tau<n^{1/2k\mathcal{C}}]}{n^{1/2k\mathcal{C}}}$
is a constant. Thus, by a similar argument as in the previous bullet, in
probability,

$\frac{t}{N_{t}^{1/2k\mathcal{C}}}\to\hat{\mathcal{A}}\qquad\qquad\text{ as
}t\to\infty,$

or equivalently,

$N_{t}\to\left(\frac{t}{\hat{\mathcal{A}}}\right)^{2k\mathcal{C}}\qquad\qquad\text{
as }t\to\infty.$

As before, by using the sequence $t_{n}=tn^{1/2k\mathcal{C}}$, we decompose
the process $s_{t_{n}}:=\sum\limits_{j=1}^{N_{t_{n}}}X_{i}$ as:

$s_{t_{n}}=\underbrace{\frac{s_{0}}{\sqrt{n}}}_{\hbox{I}_{n}}+\underbrace{\frac{1}{\sqrt{n}}\sum\limits_{j=1}^{[n(t/\hat{\mathcal{A}})^{{2k\mathcal{C}}}]}\left(X_{j}\right)}_{\hbox{II}_{n}}+\underbrace{\left(\frac{1}{\sqrt{n}}\sum\limits_{j=1}^{N_{t_{n}}}X_{j}-\frac{1}{\sqrt{n}}\sum\limits_{j=1}^{[n(t/\hat{\mathcal{A}})^{{2k\mathcal{C}}}]}X_{j}\right)}_{\hbox{III}_{n}}$

By similar arguments as above, as $n\rightarrow\infty$,

$\displaystyle\hbox{I}_{n}$ $\displaystyle\Rightarrow 0$
$\displaystyle\hbox{III}_{n}$ $\displaystyle\Rightarrow 0$
$\displaystyle\hbox{II}_{n}$ $\displaystyle\Rightarrow
W_{(t/\hat{\mathcal{A}})^{{2k\mathcal{C}}}}=W_{\hat{\mathcal{A}}^{-{2k\mathcal{C}}}\int_{0}^{t}\frac{1}{u^{1-2k\mathcal{C}}}du}.$

Moreover, in distribution,

$W_{(t/\hat{\mathcal{A}})^{{2k\mathcal{C}}}}=\hat{\mathcal{A}}^{-k\mathcal{C}}\int_{0}^{t}\sqrt{\frac{1}{u^{1-2\mathcal{C}k}}}dW_{u},$

which concludes the proof.

∎

###### Proof of Theorem 3.11.

By the dynamics of the order book described in Section 3, the sequence of
random price changes $X_{i}\in\\{-1,1\\}$ is independent. Then, if
$\lambda=\mu$,

  * •

If $\alpha_{t}\sim t^{s}\log^{m}(t)$ as $t\to\infty$, for any $s>0,m\geq 0$,
by Lemma 3.8, for every $x,y\in\mathbb{N}$,

$\mathbb{E}\left[\left(\tau_{\mathcal{H}}^{1}\right)^{n}\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]<\infty.$

and the proof follows in the same way as in the proof of Theorem 3.10.

  * •

If $\alpha_{t}\sim t^{-1+s}$ as $t\to\infty$ for any $s\in(0,1]$, then
$A_{t}\sim t^{s}/s$ and by Lemma 3.8

$\displaystyle\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>T\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]$
$\displaystyle\sim\dfrac{xy}{\lambda^{2}\pi}\dfrac{s}{T^{s}}$

Therefore,

$\displaystyle
n\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>n^{1/s}\log(n)\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]$
$\displaystyle\sim
n\left[\dfrac{xy}{\lambda^{2}\pi}\dfrac{s}{n\log^{s}(n)}\right]$
$\displaystyle\sim\dfrac{xy}{\lambda^{2}\pi}\dfrac{s}{\log^{s}(n)}.$

Thus, since $s>0$,

$n\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>n^{1/s}\log(s)\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]\to
0\qquad\qquad\text{ as }n\to\infty.$

and by Theorem 6.4.2 in Gut, (2013), in probability,

$\frac{S_{n}-n\mathbb{E}\left[\tau_{\mathcal{H}}^{1}\mathbb{I}\\{\tau_{\mathcal{H}}^{1}<n^{1/s}\log(n)\right]}{n^{1/s}\log(n)}\to
0\qquad\qquad\text{ as }n\to\infty,$

where by Proposition (B.2)
$\hat{\mathcal{B}}:=\lim_{n\to\infty}\frac{n\mathbb{E}[\tau\mathbb{I}\\{\tau<n^{s}\log(n)]}{n^{s}\log(n)}$
is a constant. Thus, by a similar argument as in the proof of Theorem 3.10, in
probability,

$\frac{t}{N_{t}^{s}\ln(N_{t})}\sim\hat{\mathcal{B}}\qquad\qquad\text{ as
}t\to\infty,$

or what is the same,

$N_{t}^{s}\log(N_{t})\sim\frac{t}{\hat{\mathcal{B}}}\qquad\qquad\text{ as
}t\to\infty.$ (15)

Let $\psi(t)$ be the inverse function of $f(t):=t^{s}\log(t)$. Notice that
$\psi$ is well defined since $f$ is strictly increasing. By definition,
$\psi(t)=u$ implies that $f(u)=t$ or, what is the same, $u^{s}\log(u)=t$, or
$\psi(t)^{s}\log(\psi(t))=t$.Thus,

$\displaystyle\psi(t)$ $\displaystyle\sim\frac{t^{1/s}}{\log(\psi(t))}$
$\displaystyle\sim\frac{t^{1/s}}{(1/s)\log(\psi(t)^{s})}$
$\displaystyle\sim\frac{st^{1/s}}{\log(\psi(t)^{s}\log(\psi(t)))}$
$\displaystyle\sim\frac{st^{1/s}}{\log(t)}$

Therefore, by Eq. 15,

$f(N_{t})\sim\frac{t}{\hat{\mathcal{B}}}$

and since $\psi$ is the inverse of $f$, then

$N_{t}\sim\psi\left(\frac{t}{\hat{\mathcal{B}}}\right)\sim\frac{s\left(\frac{t}{\hat{\mathcal{B}}}\right)^{1/s}}{\log\left(\frac{t}{\hat{\mathcal{B}}}\right)}\sim\frac{s}{\hat{\mathcal{B}}^{1/s}}\frac{t^{1/s}}{\log\left(t\right)-\log(\hat{\mathcal{B}})}$

Using the sequence $t_{n}=t(n\log(n))^{s}$, we have that,

$\displaystyle N_{t_{n}}$
$\displaystyle\sim\frac{s}{\hat{\mathcal{B}}^{1/s}}\frac{(tn^{s}\log^{s}(n))^{1/s}}{\log\left(tn^{s}\log^{s}(n)\right)-\log(\hat{\mathcal{B}})}$
$\displaystyle\sim\frac{s}{\hat{\mathcal{B}}^{1/s}}\frac{t^{1/s}n\log(n)}{\log\left(tn^{s}\log^{s}(n)\right)-\log(\hat{\mathcal{B}})}$
$\displaystyle\sim\frac{s}{\hat{\mathcal{B}}^{1/s}}\frac{t^{1/s}n}{\frac{\log\left(tn^{s}\log^{s}(n)\right)}{\log(n)}-\frac{\log(\hat{\mathcal{B}})}{\log(n)}}$
$\displaystyle\sim\frac{s}{\hat{\mathcal{B}}^{1/s}}\frac{t^{1/s}n}{s}\sim\frac{t^{1/s}n}{\hat{\mathcal{B}}^{1/s}}$

To conclude, we decompose the process
$s_{t_{n}}:=\sum\limits_{j=1}^{N_{t_{n}}}X_{i}$ as in the proof of Theorem
3.10 and use the same arguments therein.

  * •

If $\alpha_{t}\sim t^{s}\log^{m}(t)$ for every $s<0$ or if $\alpha_{t}\sim
k/t$, then for any regularly varying sequence at infinity with exponent
$1/\rho$ for some $\rho\in(0,1]$,

$n\mathbb{P}\left[\tau_{\mathcal{H}}^{1}>b_{n}\;\Big{|}\;q_{0}^{a}=x,q_{0}^{b}=y\right]\to\infty\qquad\qquad\text{
as }n\to\infty.$

Thus, $N_{t}$ cannot be rescaled to ensure a Law of Large Numbers and the
price process does not converge.

∎

##  Appendix B Auxiliary Results

######  Proposition B.1.

Let $\tau$ be positive random variable such that
$\mathbb{P}[\tau>t]\sim\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}$ with
$2k\mathcal{C}\leq 1$, $\Theta$ a constant and define the sequence

$X_{n}=\frac{n}{n^{1/2k\mathcal{C}}}\tau\mathbbm{1}_{\left\\{{\tau<n^{1/2k\mathcal{C}}}\right\\}}.$

Then, $\Psi_{n}:=\mathbb{E}[X_{n}]$ converges as $n\to\infty$.

###### Proof.

Let $F_{\tau}(t)$ denote the CDF of $\tau$. Then, since $\tau$ is a positive
random variable,

$\mathbb{E}[g(\tau)]=\int_{0}^{\infty}g(x)dF_{\tau}(x),$

where the last integral should be understood as a Riemann-Stieltjes integral.
Letting
$g(x)=\frac{n}{n^{1/2k\mathcal{C}}}x\mathbbm{1}_{\left\\{{x<n^{1/2k\mathcal{C}}}\right\\}}$
and substituting in the above formula,

$\displaystyle\mathbb{E}\left[\frac{n}{n^{1/2k\mathcal{C}}}\tau\mathbbm{1}_{\left\\{{\tau<n^{1/2k\mathcal{C}}}\right\\}}\right]$
$\displaystyle=\frac{n}{n^{1/2k\mathcal{C}}}\int_{0}^{n^{1/2k\mathcal{C}}}xdF_{\tau}(x)$
$\displaystyle=-\frac{n}{n^{1/2k\mathcal{C}}}\int_{0}^{n^{1/2k\mathcal{C}}}xd(1-F_{\tau}(x))$

Noting that the Left Hand Side is $\Psi_{n}$ and integrating by parts,

$\displaystyle\Psi_{n}$ $\displaystyle=-\frac{n}{n^{1/2k\mathcal{C}}}\cdot
x\mathbb{P}[\tau>x]\Big{|}_{x=0}^{n^{1/2k\mathcal{C}}}+\frac{n}{n^{1/2k\mathcal{C}}}\int_{0}^{n^{1/2k\mathcal{C}}}\mathbb{P}[\tau>t]dt$
$\displaystyle=-n\mathbb{P}\left[\tau>n^{1/2k\mathcal{C}}\right]+n^{1-1/2k\mathcal{C}}\int_{0}^{n^{1/2k\mathcal{C}}}\mathbb{P}[\tau>t]dt$
$\displaystyle\sim-\left.n\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}\right|_{t=n^{1/2k\mathcal{C}}}+n^{1-1/2k\mathcal{C}}\int_{0}^{n^{1/2k\mathcal{C}}}\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}dt$
$\displaystyle\sim-\frac{\Theta}{2k\mathcal{C}\log(n)}+n^{1-1/2k\mathcal{C}}\int_{0}^{n^{1/2k\mathcal{C}}}\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}dt$
(16)

Then, by using L’Hopital rule and considering $\Psi_{n}$ as a (differentiable)
function of $n$ and setting $\widehat{\Theta}=\Theta/2k\mathcal{C}$,

$\frac{d}{dn}\Psi_{n}\sim\frac{\widehat{\Theta}}{n\log^{2}(n)}+n^{-1/2k\mathcal{C}}\int_{0}^{n^{1/2k\mathcal{C}}}\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}dt+n^{1-1/2k\mathcal{C}}\frac{\widehat{\Theta}}{n\log(n)}$

which is clearly positive and thus $\Psi_{n}$ is an increasing sequence.
Furthermore, by (B), there exist constants $\epsilon$ and $T_{\epsilon}$ such
that if $n^{1/2k\mathcal{C}}>T_{\epsilon}$,

$\Psi_{n}\leq-\frac{\Theta}{2k\mathcal{C}\log(n)}+n^{1-1/2k\mathcal{C}}\int_{0}^{T_{\epsilon}}\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}dt+n^{1-1/2k\mathcal{C}}\int_{T_{\epsilon}}^{n^{1/2k\mathcal{C}}}\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}dt$

and since $2k\mathcal{C}<1$, then $1-1/2\mathcal{C}\leq 0$ and thus

$\displaystyle\Psi_{n}$
$\displaystyle\leq-\frac{\Theta}{2k\mathcal{C}}+\int_{0}^{T_{\epsilon}}\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}dt+n^{1-1/2k\mathcal{C}}\int_{T_{\epsilon}}^{n^{1/2k\mathcal{C}}}\frac{\Theta}{t^{2k\mathcal{C}}}dt$
$\displaystyle=-\frac{\Theta}{2k\mathcal{C}}+\int_{0}^{T_{\epsilon}}\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}dt+n^{1-1/2k\mathcal{C}}\frac{n^{-1+1/2k\mathcal{C}}+C(T_{\epsilon})}{-2k\mathcal{C}+1}$
$\displaystyle\leq-\frac{\Theta}{2k\mathcal{C}}+\int_{0}^{T_{\epsilon}}\frac{\Theta}{t^{2k\mathcal{C}}\log(t)}dt+\frac{1}{1-2k\mathcal{C}}+\frac{C(T_{\epsilon})}{1-2k\mathcal{C}}$
$\displaystyle<\infty$

Therefore, $\Psi_{n}$ is also bounded and by the monotone convergence theorem
for sequences it converges to a constant limit.

∎

######  Proposition B.2.

Let $\tau$ be positive random variable such that
$\mathbb{P}[\tau>t]\sim\frac{\Theta}{t^{s}}$ with $0<s\leq 1$ with $\Theta$ a
constant. Define the sequence

$X_{n}=\frac{n}{n^{1/s}\log(n)}\tau\mathbbm{1}_{\left\\{{\tau<n^{1/s}\log(n)}\right\\}}.$

Then, $\Phi_{n}:=\mathbb{E}[X_{n}]$ converges as $n\to\infty$.

###### Proof.

As in the previous result, let $F_{\tau}(t)$ denote the CDF of $\tau$. Then,
again, since $\tau$ is a positive random variable,

$\mathbb{E}[g(\tau)]=\int_{0}^{\infty}g(x)dF_{\tau}(x).$

Substituting
$g(x)=\frac{n}{n^{1/s}\log(n)}x\mathbbm{1}_{\left\\{{x<n^{1/s}\log(n)}\right\\}}$
in the above formula,

$\displaystyle\mathbb{E}\left[\frac{n}{n^{1/s}\log(n)}\tau\mathbbm{1}_{\left\\{{\tau<n^{1/s}\log(n)}\right\\}}\right]$
$\displaystyle=\frac{n}{n^{1/s}\log(n)}\int_{0}^{n^{1/s}\log(n)}xdF_{\tau}(x)$
$\displaystyle=-\frac{n}{n^{1/s}\log(n)}\int_{0}^{n^{1/s}\log(n)}xd(1-F_{\tau}(x))$

Noting that the Left Hand Side is $\Phi_{n}$ and integrating by parts,

$\displaystyle\Phi_{n}$ $\displaystyle=-\frac{n}{n^{1/s}\log(n)}\cdot
x\mathbb{P}[\tau>x]\Big{|}_{x=0}^{n^{1/s}\log(n)}+\frac{n}{n^{1/s}\log(n)}\int_{0}^{n^{1/s}\log(n)}\mathbb{P}[\tau>t]dt$
$\displaystyle=-n\mathbb{P}\left[\tau>n^{1/s}\log(n)\right]+\frac{n^{1-1/s}}{\log(n)}\int_{0}^{n^{1/s}\log(n)}\mathbb{P}[\tau>t]dt$
$\displaystyle\sim-\left.n\frac{\Theta}{t^{s}}\right|_{t=n^{1/s}\log(n)}+\frac{n^{1-1/s}}{\log(n)}\int_{0}^{n^{1/s}\log(n)}\frac{\Theta}{t^{s}}dt$
$\displaystyle\sim-\frac{\Theta}{\log^{s}(n)}+\frac{n^{1-1/s}}{\log(n)}\int_{0}^{n^{1/s}\log(n)}\frac{\Theta}{t^{s}}dt$
$\displaystyle\sim-\frac{\Theta}{\log^{s}(n)}+\left.\frac{n^{1-1/s}}{\log(n)}\cdot\frac{\Theta
t^{-s+1}}{-s+1}\right|_{t=0}^{n^{1/s}\log(n)}$
$\displaystyle\sim-\frac{\Theta}{\log^{s}(n)}+\frac{n^{1-1/s}}{\log(n)}\cdot\frac{\Theta
n^{-1+1/s}\log^{-s+1}(n)}{-s+1}$
$\displaystyle\sim-\frac{\Theta}{\log^{s}(n)}+\frac{\Theta}{(-s+1)\log^{s}(n)}$
$\displaystyle\sim\frac{(2-s)\Theta}{(1-s)\log^{s}(n)}$

which shows that it is asymptotically decreasing to zero and thus $\Phi_{n}$
converges by using similar arguments as in the previous theorem.

∎


# A symmetric $\mathbf{\beta}$-model111MSC Subject Classification: 03F35,
03C62, 03C25, 03D80, 03B30.

Stephen G. Simpson222The research presented here was supported by NSF grant
DMS-0070718. This paper was written in the year 2000 but was not published
until 2018. The only change since 2000 is that the references have been
updated.
Department of Mathematics
Vanderbilt University
http://www.math.psu.edu/simpsonhttp://www.math.psu.edu/simpson
mailto:sgslogic<EMAIL_ADDRESS>
(First draft: April 14, 2000
This draft: )

###### Abstract

We prove that there exists a countable $\beta$-model in which, for all reals
$X$ and $Y$, $X$ is definable from $Y$ if and only $X$ is hyperarithmetical in
$Y$. We also obtain some related results and pose some related questions.

###### Contents

  1. 1 The main results
  2. 2 Conservation results
  3. 3 Recursion-theoretic analogs
  4. 4 Some additional results

##  1 The main results

Our context is the study of $\omega$-models of subsystems of second order
arithmetic [7, Chapter VIII]. As in [7, Chapter VII], a $\beta$_-model_ is an
$\omega$-model $M$ such that, for all $\Sigma^{1}_{1}$ sentences $\varphi$
with parameters from $M$, $\varphi$ is true if and only if $M\models\varphi$.
Theorems 1.1 and 1.3 below are an interesting supplement to the results on
$\beta$-models which have been presented in Simpson [7, §§VII.2 and VIII.6].

Let $\mathrm{HYP}$ denote the set of hyperarithmetical reals. It is well known
that, for any $\beta$-model $M$, $\mathrm{HYP}$ is properly included in $M$,
and each $X\in\mathrm{HYP}$ is definable in $M$.

######  Theorem 1.1.

There exists a countable $\beta$-model satisfying

$\forall X\,($if $X$ is definable, then $X\in\mathrm{HYP})$.

###### Proof.

Fix a recursive enumeration $S_{e}$, $e\in\omega$, of the $\Sigma^{1}_{1}$
sets of reals. If $p$ is a finite subset of $\omega\times\omega^{<\omega}$,
say that $\langle X_{n}\rangle_{n\in\omega}$ _meets_ $p$ if
$X_{n_{1}}\oplus\cdots\oplus X_{n_{k}}\in S_{e}$ for all $(e,\langle
n_{1},\dots,n_{k}\rangle)\in p$. Let $\mathcal{P}$ be the set of $p$ such that
there exists $\langle X_{n}\rangle_{n\in\omega}$ meeting $p$. Put $p\leq q$ if
and only if $p\supseteq q$. Say that $\mathcal{D}\subseteq\mathcal{P}$ is
_dense_ if for all $p\in\mathcal{P}$ there exists $q\in\mathcal{D}$ such that
$q\leq p$. Say that $\mathcal{D}$ is _definable_ if it is definable over the
$\omega$-model $\mathrm{HYP}$, i.e., arithmetical in the complete
$\Pi^{1}_{1}$ subset of $\omega$. Say that $\langle G_{n}\rangle_{n\in\omega}$
is _generic_ if for every dense definable $\mathcal{D}\subseteq\mathcal{P}$
there exists $p\in\mathcal{D}$ such that $\langle G_{n}\rangle_{n\in\omega}$
meets $p$. We can show that for every $p\in\mathcal{P}$ there exists a generic
$\langle G_{n}\rangle_{n\in\omega}$ meeting $p$. (This is a fusion argument, a
la Gandy forcing.) Clearly $\\{G_{n}:n\in\omega\\}$ is a $\beta$-model. We can
also show that, if $C$ is countable and $C\cap\mathrm{HYP}=\emptyset$, then
there exists a generic $\langle G_{n}\rangle_{n\in\omega}$ such that
$C\cap\\{G_{n}:n\in\omega\\}=\emptyset$.

Let $L_{2}(\langle X_{n}\rangle_{n\in\omega})$ be the language of second order
arithmetic with additional set constants $X_{n}$, $n\in\omega$. Let $\varphi$
be a sentence of $L_{2}(\langle X_{n}\rangle_{n\in\omega})$. We say that $p$
_forces_ $\varphi$, written $p\Vdash\varphi$, if for all generic $\langle
G_{n}\rangle_{n\in\omega}$ meeting $p$, the $\beta$-model
$\\{G_{n}:n\in\omega\\}$ satisfies $\varphi[\langle
X_{n}/G_{n}\rangle_{n\in\omega}]$. It can be shown that, for all generic
$\langle G_{n}\rangle_{n\in\omega}$, the $\beta$-model
$\\{G_{n}:n\in\omega\\}$ satisfies $\varphi[\langle
X_{n}/G_{n}\rangle_{n\in\omega}]$ if and only if $\langle
G_{n}\rangle_{n\in\omega}$ meets some $p$ such that $p\Vdash\varphi$.

If $\pi$ is a permutation of $\omega$, define an action of $\pi$ on
$\mathcal{P}$ and $L_{2}(\langle X_{n}\rangle_{n\in\omega})$ by
$\pi(p)=\\{(e,\langle\pi(n_{1}),\dots,\pi(n_{k})\rangle):(e,\langle
n_{1},\dots,n_{k}\rangle)\in p\\}$ and $\pi(X_{n})=X_{\pi(n)}$. It is
straightforward to show that $p\Vdash\varphi$ if and only if
$\pi(p)\Vdash\pi(\varphi)$. The _support_ of $p\in\mathcal{P}$ is defined by
$\mathrm{supp}(p)=\bigcup\\{\\{n_{1},\dots,n_{k}\\}:(e,\langle
n_{1},\dots,n_{k}\rangle)\in p\\}$. Clearly if $p,q\in\mathcal{P}$ and
$\mathrm{supp}(p)\cap\mathrm{supp}(q)=\emptyset$, then $p\cup
q\in\mathcal{P}$.

We claim that if $\langle G_{n}\rangle_{n\in\omega}$ and $\langle
G^{\prime}_{n}\rangle_{n\in\omega}$ are generic, then the $\beta$-models
$\\{G_{n}:n\in\omega\\}$ and $\\{G^{\prime}_{n}:n\in\omega\\}$ satisfy the
same $L_{2}$-sentences. Suppose not. Then for some $p,q\in\mathcal{P}$ we have
$p\Vdash\varphi$ and $q\Vdash\lnot\,\varphi$, for some $L_{2}$-sentence
$\varphi$. Let $\pi$ be a permutation of $\omega$ such that
$\mathrm{supp}(\pi(p))\cap\mathrm{supp}(q)=\emptyset$. Since
$\pi(\varphi)=\varphi$, we have $\pi(p)\Vdash\varphi$, hence $\pi(p)\cup
q\Vdash\varphi$, a contradiction. This proves our claim.

Finally, let $M=\\{G_{n}:n\in\omega\\}$ where $\langle
G_{n}\rangle_{n\in\omega}$ is generic. Suppose $A\in M$ is definable in $M$.
Let $\langle G^{\prime}_{n}\rangle_{n\in\omega}$ be generic such that
$M^{\prime}=\\{G^{\prime}_{n}:n\in\omega\\}$ has $M\cap
M^{\prime}=\mathrm{HYP}$. Let $\varphi(X)$ be an $L_{2}$-formula with $X$ as
its only free variable, such that $M\models(\exists$ exactly one
$X)\,\varphi(X)$, and $M\models\varphi(A)$. Then $M^{\prime}\models(\exists$
exactly one $X)\,\varphi(X)$. Let $A^{\prime}\in M^{\prime}$ be such that
$M^{\prime}\models\varphi(A^{\prime})$. Then for each $n\in\omega$, we have
that $n\in A$ if and only if $M\models\exists X\,(\varphi(X)$ and $n\in X)$,
if and only if $M^{\prime}\models\exists X\,(\varphi(X)$ and $n\in X)$, if and
only if $n\in A^{\prime}$. Thus $A=A^{\prime}$. Hence $A\in\mathrm{HYP}$. This
completes the proof. ∎

######  Remark 1.2.

Theorem 1.1 has been announced without proof by Friedman [3, Theorem 4.3].
Until now, a proof of Theorem 1.1 has not been available.

We now improve Theorem 1.1 as follows.

Let $\leq_{\mathrm{HYP}}$ denote hyperarithmetical reducibility, i.e.,
$X\leq_{\mathrm{HYP}}Y$ if and only if $X$ is hyperarithmetical in $Y$.

######  Theorem 1.3.

There exists a countable $\beta$-model satisfying

> $(*)\qquad\forall X\,\forall Y\,($if $X$ is definable from $Y$, then
> $X\leq_{\mathrm{HYP}}Y)$.

The $\beta$-model which we shall use to prove Theorem 1.3 is the same as for
Theorem 1.1, namely $M=\\{G_{n}:n\in\omega\\}$ where $\langle
G_{n}\rangle_{n\in\omega}$ is generic. In order to see that $M$ has the
desired property, we first relativize the proof of Theorem 1.1, as follows.
Given $Y$, let $\mathcal{P}^{Y}$ be the set of $p\in\mathcal{P}$ such that
there exists $\langle X_{n}\rangle_{n\in\omega}$ meeting $p$ with $X_{0}=Y$.
(Obviously $0$ plays no special role here.) Say that $\langle
G_{n}\rangle_{n\in\omega}$ is _generic over_ $Y$ if, for every dense
$\mathcal{D}^{Y}\subseteq\mathcal{P}^{Y}$ definable from $Y$ over
$\mathrm{HYP}(Y)=\\{X:X\leq_{\mathrm{HYP}}Y\\}$, there exists
$p\in\mathcal{D}^{Y}$ such that $\langle G_{n}\rangle_{n\in\omega}$ meets $p$.

######  Lemma 1.4.

If $\langle G_{n}\rangle_{n\in\omega}$ is generic over $Y$, then $G_{0}=Y$,
and $\\{G_{n}:n\in\omega\\}$ is a $\beta$-model satisfying $\forall X\,($if
$X$ is definable from $Y$, then $X\leq_{\mathrm{HYP}}Y)$.

###### Proof.

The proof of this lemma is a straightforward relativization to $Y$ of the
proof of Theorem 1.1. ∎

Consequently, in order to prove Theorem 1.3, it suffices to prove the
following lemma.

######  Lemma 1.5.

If $\langle G_{n}\rangle_{n\in\omega}$ is generic, then $\langle
G_{n}\rangle_{n\in\omega}$ is generic over $G_{0}$.

###### Proof.

It suffices to show that, for all $p$ forcing $(\mathcal{D}^{X_{0}}$ is dense
in $\mathcal{P}^{X_{0}})$, there exists $q\leq p$ forcing $\exists
r\,(r\in\mathcal{D}^{X_{0}}$ and $\langle X_{n}\rangle_{n\in\omega}$ meets
$r)$.

Assume $p\Vdash(\mathcal{D}^{X_{0}}$ is dense in $\mathcal{P}^{X_{0}})$. Since
$p\Vdash p\in\mathcal{P}^{X_{0}}$, it follows that $p\Vdash\exists q\,(q\leq
p$ and $q\in\mathcal{D}^{X_{0}})$. Fix $p^{\prime}\leq p$ and $q^{\prime}\leq
p$ such that $p^{\prime}\Vdash q^{\prime}\in\mathcal{D}^{X_{0}}$. Put
$S^{\prime}=\\{X_{0}:\langle X_{n}\rangle_{n\in\omega}$ meets $p^{\prime}\\}$.
Then $S^{\prime}$ is a $\Sigma^{1}_{1}$ set, so let $e\in\omega$ be such that
$S^{\prime}=S_{e}$. Claim 1: $\\{(e,\langle 0\rangle)\\}\Vdash
q^{\prime}\in\mathcal{D}^{X_{0}}$. If not, let
$p^{\prime\prime}\leq\\{(e,\langle 0\rangle)\\}$ be such that
$p^{\prime\prime}\Vdash q^{\prime}\notin\mathcal{D}^{X_{0}}$. Let $\pi$ be a
permutation such that $\pi(0)=0$ and
$\mathrm{supp}(p^{\prime})\cap\mathrm{supp}(\pi(p^{\prime\prime}))=\\{0\\}$.
Then $p^{\prime}\cup\pi(p^{\prime\prime})\in\mathcal{P}$ and
$\pi(p^{\prime\prime})\Vdash q^{\prime}\notin\mathcal{D}^{X_{0}}$, a
contradiction. This proves Claim 1.

Claim 2: $q^{\prime}\cup\\{(e,\langle 0\rangle)\\}\in\mathcal{P}$. To see
this, let $\langle G^{\prime}_{n}\rangle_{n\in\omega}$ be generic meeting
$\\{(e,\langle 0\rangle)\\}$. By Claim 1 we have
$q^{\prime}\in\mathcal{D}^{G^{\prime}_{0}}$. Hence
$q^{\prime}\in\mathcal{P}^{G^{\prime}_{0}}$, i.e., there exists $\langle
X_{n}\rangle_{n\in\omega}$ meeting $q^{\prime}$ with $X_{0}=G^{\prime}_{0}$.
Thus $\langle X_{n}\rangle_{n\in\omega}$ meets $q^{\prime}\cup\\{(e,\langle
0\rangle)\\}$. This proves Claim 2. Finally, put
$q^{\prime\prime}=q^{\prime}\cup\\{(e,\langle 0\rangle)\\}$. Then
$q^{\prime\prime}\leq q^{\prime}\leq p$ and
$q^{\prime\prime}\Vdash(q^{\prime}\in\mathcal{D}^{X_{0}}$ and $\langle
X_{n}\rangle_{n\in\omega}$ meets $q^{\prime})$. This proves our lemma. ∎

The proof of Theorem 1.3 is immediate from Lemmas 1.4 and 1.5.

##  2 Conservation results

In this section we generalize the construction of §1 to a wider setting. We
then use this idea to obtain some conservation results involving the scheme
$(*)$ of Theorem 1.3.

Two important subsystems of second order arithmetic are $\mathsf{ATR}_{0}$
(arithmetical transfinite recursion with restricted induction) and
$\Pi^{1}_{\infty}$-$\mathsf{TI}_{0}$ (the transfinite induction scheme). For
general background, see Simpson [7]. It is known [7, §VII.2] that
$\mathsf{ATR}_{0}\subseteq\Pi^{1}_{\infty}$-$\mathsf{TI}_{0}$, and that every
$\beta$-model is a model of $\Pi^{1}_{\infty}$-$\mathsf{TI}_{0}$.

Let $(N,\mathcal{S})$ be a countable model of $\mathsf{ATR}_{0}$, where
$\mathcal{S}\subseteq P(|N|)$. Define
$\mathcal{P}_{(N,\mathcal{S})}=\\{p:(N,\mathcal{S})\models(p$ is a finite
subset of $\omega\times\omega^{<\omega}$ and there exists $\langle
X_{n}\rangle_{n\in\omega}$ meeting $p)\\}$. The notion of $\langle
G_{n}\rangle_{n\in|N|}$ being _generic over_ $(N,\mathcal{S})$ is defined in
the obvious way. As in §1, the basic forcing lemmas can be proved. Let
$\langle G_{n}\rangle_{n\in|N|}$ be generic over $(N,\mathcal{S})$. Put
$\mathcal{S}^{\prime}=\\{G_{n}:n\in|N|\\}$.

######  Lemma 2.1.

$(N,\mathcal{S}^{\prime})$ satisfies the scheme $(*)$ of Theorem 1.3.

###### Proof.

The proof is a straightforward generalization of the arguments of §1. ∎

######  Lemma 2.2.

Let $\psi$ be a $\Pi^{1}_{2}$ sentence with parameters from $|N|$. If
$(N,\mathcal{S})\models\psi$, then $(N,\mathcal{S}^{\prime})\models\psi$.

###### Proof.

Write $\psi$ as $\forall X\,(X\in S_{e})$ for some fixed $e\in|N|$. If
$(N,\mathcal{S})\models\psi$, then for each $n\in|N|$ we have that
$\\{p\in\mathcal{P}_{(N,\mathcal{S})}:(e,\langle n\rangle)\in p\\}$ is dense
in $\mathcal{P}_{(N,\mathcal{S})}$, hence $\emptyset\Vdash X_{n}\in S_{e}$.
Thus $\emptyset\Vdash\forall X\,(X\in S_{e})$, i.e., $\emptyset\Vdash\psi$, so
$(N,\mathcal{S}^{\prime})\models\psi$. ∎

######  Remark 2.3.

Since $(N,\mathcal{S})\models\mathsf{ATR}_{0}$ and $\mathsf{ATR}_{0}$ is
axiomatized by a $\Pi^{1}_{2}$ sentence, it follows by Lemma 2.2 that
$(N,\mathcal{S}^{\prime})\models\mathsf{ATR}_{0}$. Lemma 2.2 also implies that
$(N,\mathcal{S})$ and $(N,\mathcal{S}^{\prime})$ satisfy the same
$\Pi^{1}_{1}$ sentences with parameters from $|N|$. From this it follows that
the recursive well orderings of $(N,\mathcal{S})$ and
$(N,\mathcal{S}^{\prime})$ are the same, and that
$\mathrm{HYP}_{(N,\mathcal{S})}=\mathrm{HYP}_{(N,\mathcal{S}^{\prime})}$. It
can also be shown that
$\mathrm{HYP}_{(N,\mathcal{S})}=\mathcal{S}\cap\mathcal{S}^{\prime}$.

We now have:

######  Theorem 2.4.

$\mathsf{ATR}_{0}+(*)$ is conservative over $\mathsf{ATR}_{0}$ for
$\Sigma^{1}_{2}$ sentences.

###### Proof.

Let $\varphi$ be a $\Sigma^{1}_{2}$ sentence. Suppose
$\mathsf{ATR}_{0}\not\vdash\varphi$. Let $(N,\mathcal{S})$ be a countable
model of $\mathsf{ATR}_{0}+\lnot\,\varphi$. Let
$\mathcal{S}^{\prime}=\\{G_{n}:n\in|N|\\}$ as above. Since $\lnot\,\varphi$ is
a $\Pi^{1}_{2}$ sentence, we have by Lemmas 2.1 and 2.2 that
$(N,\mathcal{S}^{\prime})\models\mathsf{ATR}_{0}+(*)+\lnot\,\varphi$. Thus
$\mathsf{ATR}_{0}+(*)\not\vdash\varphi$. ∎

In order to obtain a similar result for $\Pi^{1}_{\infty}$-$\mathsf{TI}_{0}$,
we first prove:

######  Lemma 2.5.

$(N,\mathcal{S}^{\prime})\models$ “all ordinals are recursive”, i.e., “every
well ordering is isomorphic to a recursive well ordering”.

###### Proof.

Recall from [7, §§VIII.3 and VIII.6] that all of the basic results of
hyperarithmetical theory are provable in $\mathsf{ATR}_{0}$. In particular, by
[7, Theorem VIII.6.7], the Gandy/Kreisel/Tait Theorem holds in
$\mathsf{ATR}_{0}$. Thus for all $p\in\mathcal{P}_{(N,\mathcal{S})}$ we have

$(N,\mathcal{S})\models$ there exists $\langle X_{n}\rangle_{n\in\omega}$
meeting $p$ such that $\forall
n\,(\omega_{1}^{X_{n}}=\omega_{1}^{\mathrm{CK}})$.

Now, it is provable in $\mathsf{ATR}_{0}$ that the predicate
$\omega_{1}^{X}=\omega_{1}^{\mathrm{CK}}$ is $\Sigma^{1}_{1}$. Thus we have
$\emptyset\Vdash\forall X\,(\omega_{1}^{X}=\omega_{1}^{\mathrm{CK}})$, i.e.,
$\emptyset\Vdash$ “all ordinals are recursive”. This proves our lemma. ∎

######  Remark 2.6.

An alternative proof of Lemma 2.5 is to note that $\mathsf{ATR}_{0}+(*)\vdash$
“$O$ does not exist”, because $O$ would be definable but not
hyperarithmetical. And “$O$ does not exist” is equivalent over
$\mathsf{ATR}_{0}$ to “all ordinals are recursive”. (Here $O$ denotes the
complete $\Pi^{1}_{1}$ set of integers. See [7, §VIII.3].)

######  Theorem 2.7.

$\Pi^{1}_{\infty}$-$\mathsf{TI}_{0}+(*)$ is conservative over
$\Pi^{1}_{\infty}$-$\mathsf{TI}_{0}$ for $\Sigma^{1}_{2}$ sentences.

###### Proof.

By Lemma 2.5 it suffices to prove: if $(N,\mathcal{S})\models$ transfinite
induction for recursive well orderings, then $(N,\mathcal{S}^{\prime})\models$
transfinite induction for recursive well orderings. Let $e\in|N|$ be such that
$(N,\mathcal{S})\models$ “${<}_{e}$ is a recursive well ordering”. Suppose
$p\Vdash\exists n\,(n\in\mathrm{field}({<}_{e})$ and $\varphi(n))$. Put
$A=\\{n\in\mathrm{field}({<}_{e}):p\not\Vdash\lnot\,\varphi(n)\\}$. Clearly
$A\neq\emptyset$. By definability of forcing, $A$ is definable over
$(N,\mathcal{S})$. Hence there exists $a\in A$ such that
$(N,\mathcal{S})\models$ “$a$ is the ${<}_{e}$-least element of $A$”. For each
$n<_{e}a$ we have $p\Vdash\lnot\,\varphi(n)$, but
$p\not\Vdash\lnot\,\varphi(a)$, so let $q\leq p$ be such that
$q\Vdash\varphi(a)$. Then $q\Vdash$ “$a$ is the ${<}_{e}$-least $n$ such that
$\varphi(n)$”. Thus $(N,\mathcal{S}^{\prime})\models$ transfinite induction
for recursive well orderings. ∎

######  Remark 2.8.

Theorems 2.4 and 2.7 are best possible, in the sense that we cannot replace
$\Sigma^{1}_{2}$ by $\Pi^{1}_{2}$. An example is the $\Pi^{1}_{2}$ sentence
“all ordinals are recursive”, which is provable in $\mathsf{ATR}_{0}+(*)$ but
not in $\Pi^{1}_{\infty}$-$\mathsf{TI}_{0}$.

##  3 Recursion-theoretic analogs

The results of §§1 and 2 are in the realm of hyperarithmetical theory. We now
present the analogous results in the realm of recursion theory, concerning
models of $\mathsf{WKL}_{0}$. For background on this topic, see Simpson [7,
§§VIII.2 and XI.2].

Let $\mathrm{REC}$ denote the set of recursive reals. It is well known that,
for any $\omega$-model $M$ of $\mathsf{WKL}_{0}$, $\mathrm{REC}$ is properly
included in $M$, and each $X\in\mathrm{REC}$ is definable in $M$. The
recursion-theoretic analog of Theorem 1.1 is:

######  Theorem 3.1.

There exists a countable $\omega$-model of $\mathsf{WKL}_{0}$ satisfying

$\forall X\,($if $X$ is definable, then $X\in\mathrm{REC})$.

###### Proof.

Use exactly the same construction and argument as for Theorem 1.1, replacing
$\Sigma^{1}_{1}$ sets by $\Pi^{0}_{1}$ subsets of $2^{\omega}$. ∎

######  Remark 3.2.

Theorem 3.1 is originally due to Friedman [2, Theorem 1.10, unpublished] (see
also [3, Theorem 1.6]). It was later proved again by Simpson [8] (see also
Simpson/Tanaka/Yamazaki [9]). All three proofs of Theorem 3.1 are different
from one another.

Let $\leq_{T}$ denote Turing reducibility, i.e., $X\leq_{T}Y$ if and only if
$X$ is computable using $Y$ as an oracle. The recursion-theoretic analog of
Theorem 1.3 is:

######  Theorem 3.3.

There exists a countable $\omega$-model of $\mathsf{WKL}_{0}$ satisfying

$(**)\qquad\forall X\,\forall Y\,($if $X$ is definable from $Y$, then
$X\leq_{T}Y)$.

###### Proof.

Use exactly the same construction and argument as for Theorem 1.3, replacing
$\Sigma^{1}_{1}$ sets by $\Pi^{0}_{1}$ subsets of $2^{\omega}$. ∎

The recursion-theoretic analog of Theorems 2.4 and 2.7 is:

######  Theorem 3.4.

$\mathsf{WKL}_{0}+(**)$ is conservative over $\mathsf{WKL}_{0}$ for
arithmetical sentences.

###### Proof.

The proof is analogous to the arguments of §2. ∎

######  Remark 3.5.

Theorems 3.3 and 3.4 are originally due to Simpson [8]. The proofs given here
are different from the proofs that were given in [8].

##  4 Some additional results

In this section we present some additional results and open questions.

######  Lemma 4.1.

Let $\varphi(X)$ be a $\Sigma^{1}_{1}$ formula with no free set variables
other than $X$. The following is provable in $\mathsf{ATR}_{0}$. If $\exists
X\,(X\notin\mathrm{HYP}$ and $\varphi(X))$, then $\exists P\,(P$ is a perfect
tree and $\forall X\,($if $X$ is a path through $P$ then $\varphi(X)))$.

###### Proof.

This is a well known consequence of formalizing the Perfect Set Theorem within
$\mathsf{ATR}_{0}$. See Simpson [7, §§V.4 and VIII.3]. See also Sacks [5,
§III.6]. ∎

######  Lemma 4.2.

Let $\varphi(X)$ be a $\Sigma^{1}_{2}$ formula with no free set variables
other than $X$. The following is provable in $\mathsf{ATR}_{0}\,+{}$ “all
ordinals are recursive”. If $\exists X\,(X\notin\mathrm{HYP}$ and
$\varphi(X))$, then $\exists P\,(P$ is a perfect tree and $\forall X\,($if $X$
is a path through $P$ then $\varphi(X)))$.

###### Proof.

Since $\varphi(X)$ is $\Sigma^{1}_{2}$, we can write $\varphi(X)\equiv\exists
Y\,\forall f\,\exists n\,R(X[n],Y[n],f[n])$ where $R$ is a primitive recursive
predicate. Let $T_{X,Y}$ be the tree consisting of all $\tau$ such that
$\lnot\,(\exists n\leq\mathrm{lh}(\tau))\,R(X[n],Y[n],\tau[n])$. For
$\alpha<\omega_{1}^{\mathrm{CK}}$ put

$\varphi_{\alpha}(X)\,\,\equiv\,\,\exists Y\,(T_{X,Y}$ is well founded of
height $\leq\alpha)$.

Note that, for each $\alpha<\omega_{1}^{\mathrm{CK}}$, $\varphi_{\alpha}(X)$
is $\Sigma^{1}_{1}$. Reasoning in $\mathsf{ATR}_{0}\,+{}$ “all ordinals are
recursive”, we have $\forall X\,(\varphi(X)$ if and only if
$(\exists\alpha<\omega_{1}^{\mathrm{CK}})\,\varphi_{\alpha}(X))$. Thus Lemma
4.2 follows easily from Lemma 4.1. ∎

######  Theorem 4.3.

Let $T$ be $\mathsf{ATR}_{0}$ or $\Pi^{1}_{\infty}$-$\mathsf{TI}_{0}$. Let
$\varphi(X)$ be a $\Sigma^{1}_{2}$ formula with no free set variables other
than $X$. If $T\vdash\exists X\,(X\notin\mathrm{HYP}$ and $\varphi(X))$, then
$T\vdash\exists P\,(P$ is a perfect tree and $\forall X\,($if $X$ is a path
through $P$ then $\varphi(X)))$.

###### Proof.

From Friedman [1] or Simpson [7, §VII.2], we have that $T\vdash$ the
disjunction (1) all ordinals are recursive, or (2) there exists a countable
coded $\beta$-model $M$ satisfying $T\,+{}$ “all ordinals are recursive”. In
case (1), the desired conclusion follows from Lemma 4.2. In case (2), we have
$M\models\exists X\,(X\notin\mathrm{HYP}$ and $\varphi(X))$, so the proof of
Lemma 4.2 within $M$ gives $\alpha<\omega_{1}^{\mathrm{CK}}$ such that
$M\models\exists X\,(X\notin\mathrm{HYP}$ and $\varphi_{\alpha}(X))$. It
follows that $\exists X\,(X\notin\mathrm{HYP}$ and $\varphi_{\alpha}(X))$. We
can then apply Lemma 4.1 to $\varphi_{\alpha}(X)$ to obtain the desired
conclusion. ∎

######  Corollary 4.4.

Let $T$ and $\varphi(X)$ be as in Theorem 4.3. If $T\vdash\exists
X\,(X\notin\mathrm{HYP}$ and $\varphi(X))$, then $T\vdash\forall Y\,\exists
X\,(\varphi(X)$ and $\forall n\,(X\neq(Y)_{n}))$.

###### Proof.

This follows easily from Theorem 4.3. ∎

######  Theorem 4.5.

Let $T$ and $\varphi(X)$ be as in Theorem 4.3. If $T\vdash(\exists$ exactly
one $X)\,\varphi(X)$, then $T\vdash\exists X\,(X\in\mathrm{HYP}$ and
$\varphi(X))$.

###### Proof.

Consider cases (1) and (2) as in the proof of Theorem 4.3. In both cases it
suffices to show that, for all $\alpha<\omega_{1}^{\mathrm{CK}}$, if
$(\exists$ exactly one $X)\,\varphi_{\alpha}(X)$ then $\exists
X\,(X\in\mathrm{HYP}$ and $\varphi_{\alpha}(X))$. This follows from Lemma 4.1
applied to $\varphi_{\alpha}(X)$. ∎

######  Remark 4.6.

Theorems 4.3 and 4.5 appear to be new. Corollary 4.4 has been stated without
proof by Friedman [3, Theorems 3.4 and 4.4]. A recursion-theoretic analog of
Corollary 4.4 has been stated without proof by Friedman [3, Theorem 1.7], but
this statement of Friedman is known to be false, in view of Simpson [8]. A
recursion-theoretic analog of Theorem 4.5 has been proved by
Simpson/Tanaka/Yamazaki [9].

######  Question 4.7.

Suppose $\mathsf{WKL}_{0}\vdash\exists X\,(X\notin\mathrm{REC}$ and
$\varphi(X))$ where $\varphi(X)$ is $\Sigma^{1}_{1}$, or even arithmetical,
with no free set variables other than $X$. Does it follow that
$\mathsf{WKL}_{0}\vdash\exists X\,\exists Y\,(X\neq
Y\land\varphi(X)\land\varphi(Y))$? A similar question has been asked by
Friedman [2, unpublished].

######  Question 4.8.

Suppose $\mathsf{WKL}_{0}\vdash(\exists$ exactly one $X)\,\varphi(X)$ where
$\varphi(X)$ is $\Sigma^{1}_{1}$ with no free set variables other than $X$.
Does it follow that $\mathsf{WKL}_{0}\vdash\exists X\,(X\in\mathrm{REC}$ and
$\varphi(X))$? If $\varphi(X)$ is arithmetical or $\Pi^{1}_{1}$ then the
answer is yes, by Simpson/Tanaka/Yamazaki [9].

## References

  * [1] Harvey Friedman.  Bar induction and $\Pi^{1}_{1}$-$\mathsf{CA}$.  Journal of Symbolic Logic, 34:353–362, 1969.
  * [2] Harvey Friedman.  Subsystems of second order arithmetic and their use in the formalization of mathematics.  19 pages, unpublished, March 1974.
  * [3] Harvey Friedman.  Some systems of second order arithmetic and their use.  In [4], pages 235–242, 1975.
  * [4] R. D. James, editor.  Proceedings of the International Congress of Mathematicians, Vancouver 1974, volume 1.  Canadian Mathematical Congress, 1975.  XLIX + 552 pages.
  * [5] Gerald E. Sacks.  Higher Recursion Theory.  Perspectives in Mathematical Logic. Springer-Verlag, 1990.  XV + 344 pages.
  * [6] S. G. Simpson, editor.  Reverse Mathematics 2001.  Number 21 in Lecture Notes in Logic. Association for Symbolic Logic, 2005.  X + 401 pages.
  * [7] Stephen G. Simpson.  Subsystems of Second Order Arithmetic.  Perspectives in Mathematical Logic. Springer-Verlag, 1999.  XIV + 445 pages; Second Edition, Perspectives in Logic, Association for Symbolic Logic, Cambridge University Press, 2009, XVI + 444 pages.
  * [8] Stephen G. Simpson.  $\Pi^{0}_{1}$ sets and models of $\mathsf{WKL}_{0}$.  In [6], pages 352–378, 2005.
  * [9] Stephen G. Simpson, Kazuyuki Tanaka, and Takeshi Yamazaki.  Some conservation results on weak König’s lemma.  Annals of Pure and Applied Logic, 118:87–114, 2002.