Help with understanding a normal distribution/probability question

Question

Could someone please help me translate what this is saying on page P15, section 4.2:

http://www.ntuzov.com/Nik_Site/Niks_files/Research/papers/stat_arb/Ahmed_2009.pdf

Specifically:

When the order rates are time-varying probabilities must be computed via Monte Carlo. A simple algorithm is as follows. There are six types of orders; buy/sell and market/limit/cancel. For each type of order there are multiple rates depending on the distance to the bid/ask, i.e. if the bid is at the tenth highest tick level then there are ten limit buy orders.

Let $\lambda_i$, $i \in \mathcal{I}$ be the collection of all order rates and $\boldsymbol{x}_t = (x_1, \ldots, x_n)$ be the current state of the order book, as specified in [1]. Then there are a fixed and finite number of possible states $x_t+1$ can take on. The next state of the order book is completely determined by which order arrives first. It is known that if $X_i \sim \exp(\lambda_i)$ then

Therefore to determine the next state of the order book we just sample $u \sim U(0,1)$ then partition the interval $(0, 1)$ according to the above probabilities to determine which order arrived first. After the next state of the order book is computed we recompute the $\lambda_i$'s since they depend on the order book, i.e. $x_t$ is an inhomogeneous Markov chain, and repeat to generate an entire sample path.

Let $A$ be the set of $\omega$ where the midprice increases, to compute its probability we simulate sample paths until there is a change in the midprice and compute $I_A(\omega)$ then estimate the probability as

EDIT:

Ok, I have made some progress:

As the comment below says, X is exponentially distributed. However, I do not get what calculating the "distribution of the minimum exponential random variable" is for?

Also, once we have done this we then (seem to) plot the uniform distribution between 0 and 1 and then plot the probabilities on the x-axis, and, I think, look for the probability with the greatest area?

I really don't understand why this tells us the next state?? What exactly is finding the minimum exponential random variable telling us?

Why do we need to use the uniform distribution?

Answer 1

My understanding is the following. They want to determine the next state of the order book. So, they need to know which order comes first.

One way to find which order arrives first could be to generate a new $X_i$ for all $i \in \mathcal{I}$, and to identify the smallest. This would not be efficient. The alternative that they mention relies on $$ p_k := {\rm Pr}[\min (X_i : i \in \mathcal{I}) = X_k] = \frac{\lambda_k}{\sum_{i \in \mathcal{I}} \lambda_i}, $$ which provides the probability that the $k$th is the smallest. Obviously, these probabilities sum to one. The idea is to partition the interval $[0, 1]$ into disjoint segments of size $p_k$, one for each order $k$. To determine which order comes first, one just needs to sample a uniform random variable on $[0,1]$, and determine in which segment it belongs.

Edit: example of determination of the first order
Suppose that $\mathcal{I} = \{1, 2, 3\}$, and $\lambda_1 = 2, \lambda_2 = 5, \lambda_3 = 3$. So, $p_1 = 0.2, p_2 = 0.5, p_3 = 0.3$, and the segments are [0, 0.2], (0.2, 0.7] and (0.7, 1].
Let $u$ denote the value sampled from the uniform distribution. If $u \in [0, 0.2]$ then $k = 1$, if $u \in (0.2, 0.7]$ then $k = 2$, and if $u \in (0.7, 1]$ then $k = 3$.