Question 11.EX.16: Suppose n balls having weights w1, w2, . . . , wn are in an ......
Suppose n balls having weights w1, w2, . . . , wn are in an urn. These balls are sequentially removed in the following manner: At each selection, a given ball in the urn is chosen with a probability equal to its weight divided by the sum of the weights of the other balls that are still in the urn. Let I1, I2, . . . , In denote the order in which the balls are removed—thus I1, . . . , In is a random permutation with weights.
(a) Give a method for simulating I1, . . . , In.
(b) Let Xi be independent exponentials with rates wi , i = 1, . . . , n. Explain how Xi can be utilized to simulate I1, . . . , In.
(a) They can be simulated in the same sequential fashion in which they are defined. That is, first generate the value of a random variable I1 such that
P\left\{I_{1}=i\right\}=\frac{w_{i}}{\sum_{j=1}^{n} w_{j}}, \quad i=1, \ldots, nThen, if I1 = k, generate the value of I2 where
P\left\{I_{2}=i\right\}=\frac{w_{i}}{\sum_{j \neq k} w_{j}}, \quad i \neq kand so on. However, the approach given in part (b) is more efficient.
(b) Let Ij denote the index of the j th smallest Xi