Limit order books and queueing models

Definition A limit order book is the record, at a given time, of the resting limit orders for one instrument on one trading venue, grouped by side and price level, with prices in currency units. A buy limit order names the highest price it accepts and a sell limit order the lowest. The best bid is the highest price with resting buy orders and the best ask is the lowest price with resting sell orders. In a continuous book, orders that cross execute at once, so the best bid stays below the best ask. A marketable order, such as a market order or a limit order priced to cross, executes against resting orders on the opposite side, starting at the best price. Queue priority is the rule that decides which resting units at a price level execute first. Under price-time priority better prices execute first, and at one price level orders execute first-in-first-out (FIFO), in order of arrival. The queue position of an order is the number of eligible units ahead of it under the venue’s rule, which need not equal the displayed depth at its level. Other allocation rules such as pro-rata matching, hidden orders, amendments that lose priority and cancellations all change which units are effectively ahead. Under FIFO a new limit order at the same price joins the back of the queue, and a cancellation behind an order leaves its position unchanged.

Definition Let $N_t$ count a specified class of book events up to time $t$, for example the units removed from the front of our queue, and let $\mathcal{F}_t$ be the information available at time $t$, such as the past of the book. An arrival intensity of $N$ is a nonnegative process $\lambda_t$, known just before $t$, such that $N_t - \int_0^t \lambda_s \, ds$ is a local martingale with respect to $\mathcal{F}_t$, and a martingale when $\lambda$ is bounded. It is measured in events per unit of time. Under mild regularity, for example when $\lambda$ is bounded with continuous paths,

so the intensity is the conditional expected number of events per unit time, and $\lambda_t \Delta$ is the expected count over a short window. A counting process with jumps of size one and a constant intensity is a Poisson process, the subject of the next card. A state-dependent intensity is a function $\lambda(x)$ of the current book state $x$, such as the sizes of the best queues, as in queue-reactive models. The class of events has to be fixed before its rate means anything. For an order waiting in a queue, executions at its level and cancellations ahead of it move it forward, cancellations behind it and new orders at its price do not, and a cancellation of the order itself ends its chance to fill and is not an execution.

Definition A Poisson process with rate $\mu > 0$ is a counting process $(N_t)_{t \ge 0}$ with $N_0 = 0$ and independent increments such that, for all $t \ge 0$ and $h > 0$, the count $N_{t+h} - N_t$ has the Poisson distribution with mean $\mu h$,

for every integer $k \ge 0$. Equivalently, the times between consecutive events are independent and exponentially distributed with rate $\mu$, so each has mean $1/\mu$. The intensity of a Poisson process with respect to its own history is the constant $\mu$, all its jumps have size one, and $\mu h$ is the dimensionless expected count over a window of length $h$. The sum of two independent Poisson processes with rates $\mu_1$ and $\mu_2$ is a Poisson process with rate $\mu_1 + \mu_2$. A single event that removes several units at once is not a jump of size one, so it needs a different counting model.

Definition The fill probability of a resting order over a horizon $h$ is the probability $\mathbb{P}(T_{\text{fill}} \le h)$, under the model’s probability measure $\mathbb{P}$, that the order is completely executed within time $h$, where $T_{\text{fill}}$ is its fill time and $T_{\text{fill}} = \infty$ if it never fills. The pure queue-depletion model makes these assumptions. The order is one unit with $a \in \{0, 1, 2, \dots\}$ eligible units ahead of it under FIFO priority. Each counted service event removes exactly one unit from the front of the queue, first the units ahead and then ours. The service events form a Poisson process $N$ with rate $\mu > 0$. No unit ever enters ahead of ours, the price level stays available, and we do not cancel. The order then fills at the $(a+1)$-th service event, so $\{T_{\text{fill}} \le h\} = \{N_h \ge a + 1\}$, and the complement collects the counts $0$ through $a$,

The probability depends on $\mu$ and $h$ only through $m = \mu h$. Writing it as $g(m)$, the sum telescopes when differentiated, and

which is positive for $m > 0$. So the fill probability is $0$ at $h = 0$, strictly increases with the rate and the horizon, and tends to $1$ as $h \to \infty$. For $h > 0$ it strictly decreases with the number of units ahead, because one more unit ahead subtracts $\mathbb{P}(N_h = a + 1) > 0$. A fill probability says nothing about the quality of the fill. A passive buy order is more likely to fill when sellers are active, and sellers may be trading on information that the price will fall. Expected profit given a fill therefore depends on the joint law of fills and later prices, together with fees and inventory, and simulating fills independently of adverse price moves can overstate the value of a strategy even when the average fill rate is right.

Definition For an integer $n \ge 1$ and a rate $\mu > 0$, the Erlang distribution with shape $n$ and rate $\mu$ is the law of the sum of $n$ independent exponential random variables with rate $\mu$. It is the gamma distribution with integer shape $n$, with density

mean $n/\mu$ and variance $n/\mu^2$. In a Poisson process with rate $\mu$, the time $T_n$ of the $n$-th event is the sum of $n$ interarrival times, so it has this law. The events $\{T_n \le h\}$ and $\{N_h \ge n\}$ coincide, which gives the distribution function

In the pure queue-depletion model the fill time is $T_{\text{fill}} = T_{a+1}$, which is Erlang with shape $a + 1$ and rate $\mu$, so

The count threshold and the sum of waiting times describe the same restricted queue. If a price change can end the queue, if the service rate changes over time or with the state, or if one event can remove several units, the fill time is in general no longer Erlang.

Definition A birth-death process is a continuous-time Markov chain on the nonnegative integers whose jumps are $+1$, called births, or $-1$, called deaths. In a fill model with births, let $n_t$ be the number of units still to be served including ours, so $n_0 = a + 1$. In every state $n \ge 1$, a unit is placed ahead of ours at rate $\alpha \ge 0$, which raises $n$ by one, and a service event at rate $\mu > 0$ lowers $n$ by one. State $0$ means that our order has filled, and it is absorbing, because no unit can be placed ahead of an order that has already traded. The probabilities $p_n(t) = \mathbb{P}(n_t = n)$ solve the Kolmogorov forward equations

with $p_{a+1}(0) = 1$ and $p_n(0) = 0$ for $n \ne a + 1$, and the fill probability by time $h$ is $p_0(h)$. Each equation adds the probability flow into state $n$, at the rates of the states it comes from, and subtracts the flow out of $n$. State $1$ receives no births, because state $0$ produces none. With rates $\alpha_n$ and $\mu_n$ that depend on the state, the interior equation becomes

Setting $\alpha = 0$ recovers the pure queue-depletion model. Births ahead need a stated mechanism, such as a loss of priority or a rule for hidden liquidity, because under FIFO a new order at our price joins behind us. Trades that remove several units at once, cancellations ahead whose rate depends on how many units are ahead, and price changes that end the queue before a fill call for a different generator and possibly a larger state space, for example a second absorbing state for an order that can no longer fill. None of them is captured by refitting a constant $\mu$.