140 RANDOM NUMBERS 3.4.2 This algorithm was first (Web hosting isp)
140 RANDOM NUMBERS 3.4.2 This algorithm was first published by L. E. Moses and R. V. Oakford, in Tables of Random Permutations (Stanford University Press, 1963); and by R. Durstenfeld, CACM 7 (1964), 420. It can also be modified to obtain a random permutation of a random combination (see exercise 14). For a discussion of random combinatorial objects of other kinds (e.g., parti- tions), see Section 7.2 and/or the book Combinatorial Algorithms by Nijenhuis and Wilf (New York: Academic Press, 1975). EXERCISES 1. [Mz?] Explain Eq. (1). 2. [.20] Prove that Algorithm S never tries to read more than N records of its input file. b 3. [,% I The (t+l)st item in Algorithm S is selected with probability (n–m)/(N–t), not n/N, yet the text claims that the sample is unbiased-so each item should be selected with the same probability. How can both of these statements be true? 4. [A&B] Let p(m, t) be the probability that exactly m items are selected from among the first t in the selection sampling technique. Show directly from Algorithm S that 5. [M.24] What is the average value of t when Algorithm S terminates? (In other words, how many of the N records have been passed, on the average, before the sample is complete?) 6. [M2 4] What is the standard deviation of the value computed in the previous exercise? b 7. [Mz~] Prove that any given choice of n records from the set of N is obtained by Algorithm S with probability l/(E). Th ere f ore the sample is completely unbiased. 8. [A4461 Algorithm S computes one uniform deviate for each input record it handles. Find a more efficient way to determine the number of input records to skip before the first is selected, assuming that N/n is rather large. (We could iterate this process to select the remaining n -1 records, thus reducing the number of necessary random deviates from order N to order n.) 9. [1,6] Let n = 3. If Algorithm R is applied to a file containing 20 records numbered 1 thru 20, and if the random numbers generated in step R3 are respectively 4,1,6,7,5,3,5,11,11,3,7,9,3,11,4,5,4, which records go into the reservoir? Which are in the final sample? 10. [15] Modify Algorithm R so that the reservoir is eliminated, assuming that the n records of the current sample can be held in memory. b 11. [M%] Let pm be the probability that exactly m elements are put into the reservoir during the first pass of Algorithm R. Determine the generating function G(z) = C,,, pmzm, and find the mean and standard deviation. (Use the ideas of Section 1.2.10.)