Help with understanding a normal distribution/probability question

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?

• I'm having a hard time trying to understand what you want. What do you mean by "the probability $X_i$ is normally distributed"? The claims that $X_i$ is exponentially distributed. – QuantIbex Jul 13 '13 at 15:15
• Please see edit – user997112 Jul 13 '13 at 15:28

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$.

• I don't get it. If one $\lambda_k$ changes, then $\sum \lambda_k$ will change. For the simulation, if you pick the $k$ having the largest $\lambda_k$, say $\tilde{k}$, then you pick $\tilde{k}$ with probability one, which is not equal to $p_{\tilde{k}}$. – QuantIbex Jul 13 '13 at 17:08
• From the article: "After the next state of the order book is computed we recompute the $\lambda_i$ ’s since they depend on the order book". – QuantIbex Jul 13 '13 at 17:16
• Yes, within one iteration $\sum \lambda_k$ is constant, and the $k$ with the largest $\lambda_k$ will also have the largest $p_k$. But what do you infer from that? – QuantIbex Jul 13 '13 at 17:54
• I don't see were they say to plot the uniform distribution. The "according to the above probabilities to determine which order arrived first" is what I explained in the last two sentences of my answer. See edit for an example. – QuantIbex Jul 14 '13 at 7:52
• That is exactly what is explained in the answer. I can't explain it in more basic terms. It seems that I won't be able to help you further on this. – QuantIbex Jul 14 '13 at 17:40