Frontpage web hosting - 554 ANSWERS TO EXERCISES 3.4.1 29. Let Xn+l
554 ANSWERS TO EXERCISES 3.4.1 29. Let Xn+l = 1, then set Xk + Xk+lUi k or Xk + Xk+tlePYklk for k = n, n-l, . . . . 1, where uk is uniform or Yk is exponential. [ACM Trans. Math. Software, to appear.] SECTION 3.4.2 1. There are (rr$) ways to pick n -m records from the last N -t; (:!,I:) ways to pick n -m -1 from N -t -1 after selecting the (t + 1)st item. 2. Step S3 will never go to step S5 when the number of records left to be examined is equal to n -m. 3. We should not confuse conditional and unconditional probabilities. The quantity m depends randomly on the selections that took place among the first t elements; if we take the average over all possible choices that could have occurred among these elements, we will find that (n -m)/(N -t) is exactly n/N on the average. For example, consider the second element; if the first element was selected in the sample (this happens with probability n/N), the second element is selected with probability (n -l)/(N -1); if the first element was not selected, the second is selected with probability n/(N -1). The overall probability of selecting the second element is (nlN)((n -l)l(N -1)) i- (1 -nlN)(nlW -1)) = n/N. 4. From the algorithm, p(m,t + 1) = (1 - E) p(m, t) + n -i , ) dm - 1, t), The desired formula can be proved by induction on t. In particular, p(n, N) = 1. 5. In the notation of exercise 4, the probability that t = k at termination is qk = p(n, k) -p(n, k -1) = (:I:)/(:). The average is ~,,,,, kqk = (N $- l)n/(n f 1). 6. Similarly, co,,,, k(k + l)qk = (N + 2)(N $-l)n/(n + 2); the variance is therefore (N + l)(N -n)n/(n + 2)(n + 1) . 7. Suppose the choice is 1 5 ~1 < 22 < ... < zn 2 N. Let 20 = 0, zn+l = N+l. The choice is obtained with probability p = n,,,,N--pt, where p = N-((t-1)-n+m t for xm < t < xm+l; N -(t -1) n-m pt = N-@-l) for t = zm+l. The denominator of the product p is N!; the numerator contains the terms N -n, N-n -1, , 1 for those t s that are not z s, and the terms n, n -1, . . , 1 for those t s that are z s. Hence p = (N -n)!n!/N!. Example: n = 3, N = 8, (~1~22,~s) = (2,3,7); p = i$$$$$++. 9. The reservoir gets seven records: 1, 2, 3, 5, 9, 13, 16. The final sample consists of records 2, 5, 16. 10. Delete step R6 and the variable m. Replace the I table by a table of records, initialized to the first n records in step Rl, and with the new record replacing the Mth table entry in step R4.
Note: If you are looking for cheap and reliable webhost to host and run your mysql application check mysql web server services.