3.3.3 ANSWERS TO EXERCISES 541 Fig. A-l. Permutation regions for Fibonacci generator. Fig. A-2. Run-length regions for Fibonacci generator. 24. Proceed as in the previous exercise; the sum of the interval lengths is 5 c at- (a -1) = at&)(a+:-2). ol k>l The value for a truly random sequence would be e -1; and our value is e -1 + (e/2 -1)/a + 0(1/a ). [Note: The same result holds for an ascending run, since we have U,, > Un+I if and only if 1 -U,, < 1 -Un+I. This would lead us to suspect that runs in linear congruential sequences might be slightly longer than normal, so the run test should be applied to such generators.] 25. z must be in the interval [(k + a -Q/a, (k + p -0)/a) for some k, and also in the interval [a, p). Let ko = [aa: + 0 -p l, ICI = lab + 0 -/3 l. With due regard to boundary conditions, we get the probability (kl -ko)(P -a/)/a -I- max(0, P -(kl + a -0)/a) -max(O, cx-(k. + a -.9)/a). This is (/3 -cu)(p -CY ) + E, where 1~1 < 2(p -&)/a. 26. See Fig. A-l; the orderings U1 < Us < Uz and Uz < U3 < UI are impossible; the other four each have probability f . 27. U, = {F,-~UO $ F,Ul}. We need to have both F~--~UO + Fkul < 1 and FkUo + Fk+l VI > 1. The half-unit-square in which UO > UI is broken up as shown in Fig. A-2, with various values of k indicated. The probability for a run of length k is 3, if k = 1; l/Fk-l Fk+l -l/Fk Fk+2, if k > 1. The corresponding probabilities for a random sequence are 2k/(k + l)! -2(k + l)/(k + 2)!; the following table compares the first few values. k: 1234 5 Probability in Fibonacci case: f 4 & & & Probability in random case: B s2 ti3%i&
This entry was posted
on Sunday, September 30th, 2007 at 1:09 am and is filed under MySQL.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.