Why Sorting Uniform Samples Works
A Poisson process gives both a random number of events and random event times. Sometimes the count on a fixed interval is already specified or simulated, and the remaining task is to place those events in time. For a homogeneous Poisson process, the conditional placement has a simple exact rule: draw independent uniform times on the interval and sort them. The sorting is essential because arrival times are recorded chronologically.
Let \((\Omega,\mathcal{F},\mathbb{P})\) be a probability space, and let \((N_t)_{t\ge0}\) be a homogeneous Poisson process with rate \(\lambda>0\), starting with \(N_0=0\). Its count \(N_t\) is the number of arrivals in \((0,t]\); counts on disjoint intervals are independent, and \(N_t-N_s\) has the Poisson distribution with mean \(\lambda(t-s)\) for \(0\le s<t\). Let \(T>0\) be fixed, and let \(\mathcal{F}_t=\sigma(N_s:0\le s\le t)\) be the natural filtration. Write \(S_1<S_2<\cdots\) for the arrival times. We condition on \(N_T=n\), an event of positive probability \(e^{-\lambda T}(\lambda T)^n/n!\) for every integer \(n\ge0\).
Proof. Fix \(n\ge1\). The interarrival times of a homogeneous Poisson process are independent exponential random variables with rate \(\lambda\). Consequently, for \(0<s_1<\cdots<s_n<T\), the density that the first \(n\) arrivals occur at those ordered times and that there is no further arrival by \(T\) is the product of the \(n\) interarrival densities and the probability that the next waiting time exceeds \(T-s_n\). The interarrival lengths are \(s_1,s_2-s_1,\ldots,s_n-s_{n-1}\); their sum is \(s_n\). Thus this density is $$ \lambda^n e^{-\lambda s_n}e^{-\lambda(T-s_n)} =\lambda^n e^{-\lambda T}. $$ The event described is exactly \(N_T=n\) together with arrival times in the stated infinitesimal region. Dividing this joint density by \(\mathbb{P}(N_T=n)=e^{-\lambda T}(\lambda T)^n/n!\) gives the conditional density \(n!/T^n\) on the ordered region.
Now let \(U_1,\ldots,U_n\) be independent Uniform\((0,1)\) random variables, and sort them as \(U_{(1)}<\cdots<U_{(n)}\). Before sorting, their joint density is \(1\) on the unit cube. For any strictly ordered point in the cube, there are \(n!\) permutations of its coordinates, each with the same density. Therefore the density of the sorted vector is \(n!\) on \(0<u_{(1)}<\cdots<u_{(n)}<1\). Scaling each coordinate by \(T\) gives density \(n!/T^n\) on the corresponding ordered region in \((0,T)\). This matches the conditional density just derived, proving the equivalence. The case \(n=0\) is the empty list of arrivals by definition. \(\square\)
The Simulation Procedure
Once the count \(n\) is given, the parameter \(\lambda\) does not appear in the conditional placement rule. It affects how likely the count is, but not where the arrivals fall after conditioning on that count. For \(n\ge1\), generate \(n\) independent Uniform\((0,1)\) values, multiply each by \(T\), and sort the results in increasing order. The sorted values are the simulated arrival times. If the count is \(0\), return an empty list.
Use the specified integer \(n\ge0\) and interval length \(T>0\). If the count is being simulated first, this procedure is conditional on its realized value.
For \(n\ge1\), draw independent \(U_1,\ldots,U_n\), each Uniform\((0,1)\). For \(n=0\), generate no values.
Set \(S_k=T U_{(k)}\) for \(k=1,\ldots,n\), where \(U_{(1)}<\cdots<U_{(n)}\) are the sorted values.
The result is a chronologically ordered list in \((0,T)\), except for endpoint cases of probability zero under the ideal continuous uniform distribution.
The process is usually defined to count arrivals in \((0,T]\), so \(0\) and \(T\) are not interior times. Under a continuous uniform distribution, a sample equals either endpoint with probability zero. For a finite number \(n\) of samples, the probability that any sample is an endpoint is also zero: the probability of the union of the \(2n\) endpoint events is at most the sum of their zero probabilities. The probability of a tie between any two samples is zero as well. Thus, with probability one, the sorted times satisfy \(0<S_1<\cdots<S_n<T\). A computer’s finite-precision random-number routine may have a different endpoint convention; use a routine that returns values strictly between \(0\) and \(1\), or handle endpoint outputs explicitly rather than treating them as ordinary continuous draws.
Worked Example: Two Arrivals on a Three-Unit Interval
Suppose a rate-\(2\) Poisson process is observed to have \(n=2\) arrivals by \(T=3\). The event being conditioned on has probability $$ \mathbb{P}(N_3=2)=e^{-2\cdot3}\frac{(2\cdot3)^2}{2!} =e^{-6}\frac{36}{2}=18e^{-6}>0. $$ The conditional joint density of the ordered times is \(2!/3^2=2/9\) on \(0<s_1<s_2<3\).
Take uniform values \(U_1=\tfrac14\) and \(U_2=\tfrac56\). Scaling by \(T=3\) gives \(3(\tfrac14)=\tfrac34\) and \(3(\tfrac56)=\tfrac{15}{6}=\tfrac52\). They are already ordered, so the simulated arrival times are \(S_1=\tfrac34\) and \(S_2=\tfrac52\). Both are strictly inside the interval, and \(\tfrac34<\tfrac52\).
Check: The joint density at this ordered pair is \(2/9\), as required. Also, the values arose from exactly two uniform draws and scaling by \(3\); sorting did not change their values. The conditional density integrates to one because the ordered triangle has area \(3^2/2=9/2\), and \((2/9)(9/2)=1\).
Worked Example: Counts in Subintervals
Suppose there are \(n=3\) arrivals conditional on \(N_4=3\), and divide \((0,4]\) into \((0,1]\), \((1,3]\), and \((3,4]\). Draw \(U_1=\tfrac18\), \(U_2=\tfrac12\), and \(U_3=\tfrac78\). Scaling by \(T=4\) gives $$ 4\left(\tfrac18,\tfrac12,\tfrac78\right) =\left(\tfrac12,2,\tfrac72\right). $$ These are strictly ordered. The first lies in \((0,1]\), the second in \((1,3]\), and the third in \((3,4]\), so the three interval counts are \(1,1,1\).
The interval lengths are \(1,2,1\), so a single uniform time falls in the three intervals with probabilities \(\tfrac14,\tfrac24,\tfrac14\). Conditional on three independent uniform times, the probability of exactly one in each interval is $$ \frac{3!}{1!1!1!}\left(\frac14\right)\left(\frac24\right)\left(\frac14\right) =6\cdot\frac{2}{64}=\frac{3}{16}. $$ The factor \(3!\) counts the assignments of the three independent samples to the three intervals.
Check: The simulated times \(\tfrac12,2,\tfrac72\) give one point in each interval under the stated endpoint convention. The conditional probability calculation is also the multinomial probability for counts \((1,1,1)\), and its three probabilities sum to \(\tfrac14+\tfrac24+\tfrac14=1\).
The interval-count calculation follows generally from the same conditional representation. If \((0,T]\) is divided into \(r\) disjoint intervals of lengths \(\ell_1,\ldots,\ell_r\), where each \(\ell_a\ge0\) and \(\sum_{a=1}^r\ell_a=T\), then each independent uniform sample falls in interval \(a\) with probability \(\ell_a/T\). For nonnegative integers \(c_1,\ldots,c_r\) summing to \(n\), the probability of those counts is $$ \frac{n!}{c_1!\cdots c_r!}\prod_{a=1}^r\left(\frac{\ell_a}{T}\right)^{c_a}. $$ Indeed, each particular assignment of the \(n\) labelled samples to intervals with these counts has probability \(\prod_a(\ell_a/T)^{c_a}\); there are \(n!/(c_1!\cdots c_r!)\) such assignments. This proves the conditional multinomial rule. If an interval has length zero, its count must be zero; the displayed formula is interpreted with that constraint, avoiding an ambiguous \(0^0\).
Worked Example: The Zero-Arrival Case
Let the rate be \(\lambda=3\) and the interval length be \(T=2\), and condition on \(N_2=0\). The conditioning event has probability $$ \mathbb{P}(N_2=0)=e^{-3\cdot2}\frac{(3\cdot2)^0}{0!}=e^{-6}>0. $$ Since the count is fixed at zero, the algorithm draws no uniform values and returns the empty list.
Check: The returned list contains zero times, so its number of arrivals is \(0\), as required by the conditioning event. In particular, there is no first arrival time to set equal to \(0\) or \(T\); an empty list is different from a list containing an endpoint.
Why the Conditional Distribution Has This Form
Conditioning removes the randomness in the number of arrivals but leaves their locations exchangeable: before sorting, no one of the \(n\) points is distinguished as the first, second, or last. The uniform distribution expresses the fact that, given the total count, subintervals receive points in proportion to their lengths. Sorting then converts an unordered sample into the chronological order required for a path.
This is a conditional statement, not a replacement for simulating the count. If a complete homogeneous Poisson process on \((0,T]\) is needed, first generate \(N_T\) from the Poisson distribution with mean \(\lambda T\), then apply the sorting procedure using that count. The resulting count has the required Poisson law, and conditional on each possible count the times have the required conditional distribution. Alternatively, if a count is supplied by a model or data condition, use it directly and do not generate another count.
The method also gives a useful check on simulated paths. For any fixed partition of the interval, the conditional counts should follow the multinomial probabilities above. This checks placement conditional on the count; it does not by itself check that the count-generation step has the correct Poisson distribution.
Common Mistake: Forgetting to Sort
A common error is to scale the uniform values and report them in the order generated. For example, with \(T=3\), take \(U_1=\tfrac34\) and \(U_2=\tfrac14\). Scaling gives \(3U_1=\tfrac94\) and \(3U_2=\tfrac34\). Reporting \((\tfrac94,\tfrac34)\) as the arrival sequence gives a decreasing sequence, which cannot be the chronological list \((S_1,S_2)\). The correction is to sort: the arrival times are \((\tfrac34,\tfrac94)\), and they satisfy \(0<\tfrac34<\tfrac94<3\).
Sorting does not claim that the original independent uniform draws are themselves the successive interarrival times. They are event locations on the full interval. If interarrival times are needed, they can be recovered from the sorted locations as \(S_1,S_2-S_1,\ldots,S_n-S_{n-1}\); the final gap to the right endpoint is \(T-S_n\). The conditional-location method and the exponential-waiting-time construction describe the same Poisson process in different ways, but the uniform samples must be sorted to represent event times.
Check Your Understanding
Use the conditional distribution and the endpoint conventions to answer these questions.
- Given \(N_5=2\), what is the joint density of \((S_1,S_2)\) on its ordered region?
- For \(T=6\), scale and sort the uniform values \(\tfrac23\) and \(\tfrac16\). What are the two arrival times?
- If an interval of length \(2\) is divided into lengths \(1\) and \(1\), what is the conditional probability that exactly two arrivals, given \(N_2=2\), both fall in the first half?
- Why does conditioning on \(N_T=n\) make \(\lambda\) disappear from the conditional distribution of the arrival times?
- What output should the algorithm return when the specified count is \(n=0\), and why is that not an arrival at time \(0\)?