MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

520 ANSWERS TO EXERCISES 3.1 The desired average value can now be computed; it is (cf. exercise 12) E,,, = ;(HI + 2H$$ + 3H3 - +f~~+…. =1+j m This latter formula was obtained by quite different means by Martin D. Kruskal, AMM 61 (1954), 392-397. Using the integral representation he proved the asymptotic relation lim,,, (Em -$ lnm) = i(r + ln2). For further results and references, see John Riordan, Annals Math. Stat. 33 (1962), 178-185. 15. The probability that f(s) # z for all x is (m-l) /m, which is approximately l/e. The existence of a self-repeating value in an algorithm like Algorithm K is therefore not colossal at all-it occurs with probability 1 - l/e M .63212. The only colossal thing was that the author happened to hit such a value when X0 was chosen at random (see exercise 11). 16. The sequence will repeat when a pair of successive elements occurs for the second time. The maximum period is m2. (Cf. next exercise.) 17. After selecting Xc,. . . , Xk-1 arbitrarily, let Xn+l = f(Xn, , Xn-kfr), where 0 0. 2. Let X, be the first repeated value in the sequence. If X, were equal to Xk for some k where 0 < k < r, we could prove that X,-i = X&r, since X, uniquely determines X,-i when a is prime to m. Hence Ic = 0. 3. If d is the greatest common divisor of a and m, the quantity ax,, can take on at most m/d values. The situation can be even worse; e.g., if m = 2e and if a is even, Eq. (6) shows that the sequence is eventually constant. 4. Induction on k. 5. If a is relatively prime to m, there is a number a for which aa = 1 (modulo m). Then X,-r = (a/X% -a c) mod m, and in general, xn-k = ((a )kXn -c(a + . . . + (a )k)) mod m = (a )kXn -c(a cT:r ) modm when k > 0, n-k 2 0. If a is not relatively prime to m, it is not possible to determine XnP1 when X, is given; multiples of m/gcd(a,m) may be added to X,-i without changing the value of X,. (See also exercise 3.2.1.3-7.)

This entry was posted on Tuesday, September 11th, 2007 at 3:14 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.