Florida web design - 136 RANDOM NUMBERS 3.4.1 25. [AL%] Let XI,
136 RANDOM NUMBERS 3.4.1 25. [AL%] Let XI, X2, . . . , X5 be binary words each of whose bits is independ- ently 0 or 1 with probability f. What is the probability that a given bit position of Xl V (X2 A (Xs V (X4 A X5))) contains a l? Generalize. 26. [MI81 Let Nl and NZ be independent Poisson deviates with respective means ~1 and ~2, where PI > ~2 2 0. Prove or disprove: (a) NI + NZ has the Poisson distribution with mean ~1 + ~2. (b) NI -NZ has the Poisson distribution with mean /h–pz. 27. [ZZ] (J. H. Ahrens.) On most binary computers there is an efficient way to count the number of l s in a binary word (cf. Section 7.1). Hence there is a nice way to obtain the binomial distribution (t,p) when p = f, simply by generating t random bits and counting the number of 1 s. Design an algorithm that produces the binomial distribution (t, p) for arbitrary p, using only a subroutine for the special case p = 3 as a source of random data. [Hint: Simulate a process that first looks at the most significant bits of t uniform deviates, then at the second bit of those deviates whose leading bit is not sufficient to determine whether or not their value is < p, etc.] 28. [HAL%] (R. P. Brent.) Develop a method to generate a random point on the surface of the ellipsoid defined by c ak$ = 1, where al 2 e . . 2 a, > 0. 29. [M20] (J. L. Bentley and J. D. Saxe.) Fint a simple way to generate n numbers Xl,…, X, that are uniform between 0 and 1 except for the fact that they are sorted: Xl 5 ..* 5 X,. Your algorithm should take only O(n) steps. 3.4.2. Random Sampling and Shuffling Many data processing applications call for an unbiased choice of n records at random from a file containing N records. This problem arises, for example, in quality control or other statistical calculations where sampling is needed. Usually N is very large, so that it is impossible to contain all the data in memory at once; and the individual records themselves are often very large, so that we can t even hold n records in memory. Therefore we seek an efficient procedure for selecting n records by deciding either to accept or to reject each record as it comes along, writing the accepted records onto an output file. Several methods have been devised for this problem. The most obvious approach is to select each record with probability n/N; this may sometimes be appropriate, but it gives only an average of n records in the sample. The standard deviation is n(1 - n/N), and it is possible that the sample will be either too large for the desired application, or too small to give the necessary results. A simple modification of the obvious procedure gives what we want: The (t + 1)st record should be selected with probability (n - m)/(N -t), if m items have already been selected. This is the appropriate probability, since of all the possible ways to choose n things from N such that m values occur in the first t, exactly (1)