Queue-Priority Fill Probability with Poisson Depletion

Worked Solution

How to Think About It: You are sitting in a queue, and you need $U + 1$ depletion events to happen before time $T$ for your order to get filled -- $U$ orders ahead of you need to get picked off, and then one more event actually fills you. Under the Poisson assumption, the number of events in $[0, T]$ is $\text{Pois}(\lambda T)$, so the question reduces to a Poisson tail probability. This is the bread and butter of queue modeling in market microstructure. Before doing any math, think about what drives the answer: the ratio $\lambda T / (U+1)$. If the expected number of depletions $\lambda T$ is much larger than $U+1$, you are very likely to get filled. If it is much smaller, you are unlikely to.

Quick Estimate: Take $\lambda = 5$ events/sec, $T = 10$ sec, $U = 30$. Then $\lambda T = 50$ and you need $U + 1 = 31$ events. The mean of the Poisson is $50$ and the standard deviation is $\sqrt{50} \approx 7.07$. You need at least $31$ events, which is $(50 - 31)/7.07 \approx 2.7$ standard deviations below the mean. So $P(\text{fill}) \approx \Phi(2.7) \approx 0.997$. You are almost certainly getting filled. Now try $U = 55$: you need $56$ events from a Poisson with mean $50$, which is $(56 - 50)/7.07 \approx 0.85$ standard deviations above the mean, giving $P(\text{fill}) \approx 1 - \Phi(0.85) \approx 0.20$. Much less likely.

Approach: We derive the fill probability from the Poisson counting process, then express it using the regularized incomplete gamma function and the CLT.

Formal Solution:

*Part (a):*

Let $N(t)$ denote the Poisson counting process with rate $\lambda$. Your order is filled at the moment the $(U+1)$-th depletion event occurs -- i.e., when $N(t)$ first reaches $U + 1$. The fill time $\tau$ is therefore the $(U+1)$-th arrival time of the Poisson process.

The event $\{\tau \leq T\}$ -- that you are filled before $T$ -- is equivalent to the event that at least $U+1$ events have occurred by time $T$:

$\{\tau \leq T\} = \{N(T) \geq U + 1\}.$

Since $N(T) \sim \text{Pois}(\lambda T)$, we have

$P(\text{filled before } T) = P(N(T) \geq U + 1) = \sum_{k=U+1}^{\infty} \frac{(\lambda T)^k e^{-\lambda T}}{k!}.$

This is the key identity: the CDF of the $(U+1)$-th Poisson arrival equals the tail probability of the Poisson count. It follows directly from the duality between Poisson counts and Gamma (Erlang) waiting times.

*Part (b):*

Exact form via the regularized incomplete gamma function:

The standard identity connecting Poisson CDFs and the regularized upper incomplete gamma function $Q(a,x) = \Gamma(a,x)/\Gamma(a)$ is:

$P(\text{Pois}(\mu) \leq n-1) = \sum_{k=0}^{n-1} \frac{\mu^k e^{-\mu}}{k!} = Q(n, \mu) = \frac{\Gamma(n, \mu)}{\Gamma(n)},$

where $\Gamma(a, x) = \int_x^{\infty} t^{a-1} e^{-t} \, dt$ is the upper incomplete gamma function. Taking the complement with $n = U+1$ and $\mu = \lambda T$:

$P(\text{filled before } T) = P(\text{Pois}(\lambda T) \geq U+1) = 1 - Q(U+1,\, \lambda T) = 1 - \frac{\Gamma(U+1,\, \lambda T)}{U!}.$

Equivalently, in terms of the regularized lower incomplete gamma function $P(a,x) = \gamma(a,x)/\Gamma(a)$:

$P(\text{filled before } T) = P(U+1,\, \lambda T) = \frac{\gamma(U+1,\, \lambda T)}{U!},$

where $\gamma(a, x) = \int_0^x t^{a-1} e^{-t} \, dt$ is the lower incomplete gamma function.

Normal approximation for large $\lambda T$:

When $\lambda T$ is large, $N(T) \sim \text{Pois}(\lambda T)$ is approximately $\mathcal{N}(\lambda T, \lambda T)$ by the CLT. Applying a continuity correction:

$P(N(T) \geq U+1) \approx P\left(Z \geq \frac{U + 0.5 - \lambda T}{\sqrt{\lambda T}}\right) = \Phi\left(\frac{\lambda T - U - 0.5}{\sqrt{\lambda T}}\right),$

where $Z$ is standard normal and $\Phi$ is the standard normal CDF.

Answer:

$P(\text{filled before } T) = P(\text{Pois}(\lambda T) \geq U+1) = 1 - \frac{\Gamma(U+1,\, \lambda T)}{U!} \approx \Phi\!\left(\frac{\lambda T - U - 0.5}{\sqrt{\lambda T}}\right).$