17. Order Statistics: Let Xi9 ...,Xn be i.i.d. from a continuous distribution F9 and let X{i) denote the /th smallest of Xx,..., Xn, / = 1 , . . . , n.

Suppose we want to simulate XiX) < X{2) < · · · < X(n). One approach is to simulate ç values from F, and then order these values. However, this ordering, or sorting, can be time-consuming when ç is large (the best computer algorithms for sorting ç values take on the order of ç log ç

comparisons).

(a) Suppose that ë(ß)9 the hazard rate function of F9 is bounded. Show how the hazard rate method can be applied to generate the ç variables in such a manner that no sorting is necessary.

Suppose now that F - 1 is easily computed.

(b) Argue that X{X),..., X{n) can be generated by simulating (7( 1) <

^(2) < · · · < U(n)—the ordered values of ç independent random numbers—and then setting X(i) = F~l(U(i)). Explain why this means that X(i) can be generated from F~*(/?,) where ßt is beta with parameters /,

ç + i + 1.

(c) Argue that U{X)9 Uin) can be generated, without any need for sorting, by simulating i.i.d. exponentials Y l 9Y n + X and then setting

'»· »:., : ; ; > : : , - »

Hint: Given the time of the (n + l)st event of a Poisson process, what can be said about the set of times of the first ç events?

(d) Show that if U{n)=y then ( 7 ( 1 ),Ui n_ x ) has the same joint distribution as the order statistics of a set of ç - 1 uniform (0, y) random variables.

(e) Use

(d) to show that U(n) can be generated as follows:

Step 1: Generate random numbers Ux,..., Un.
Step 2: Set u(n) = u\'\ uin_X) = uin){u2Y/in-l\
^o-i) = õù{õË^+Üé/õ-é\ j = 2 , . . . , ç - 1