American Mathematical Monthly, The: Sequential searches: Proofreading, Russian Roulette, and the inc

1. INTRODUCTION. So, you've read your fifty page manuscript a half dozen times and you continue to stumble across annoying typos. Is there any end in sight? Just how many more times do you need to read it before you're satisfied?

For purposes of discussion, let's say that your manuscript originally contained 10 errors and that, because of fatigue and a certain level of impatience, the probability that you notice an error when staring right at it is only 1/10. Then the expected number of errors found is one after the first reading, 1.9 after the second reading, and so on. Several such results rounded to the nearest hundreth are shown in Table 1.

AN ACKNOWLEGEMENT AND CLOSING REMARKS. Donald Knuth deserves special mention. His entertaining and enlightening letters were inspirational. Besides several valuable suggestions, he also deduced (8) and (11) independently using an inclusion-exclusion approach.

Other sequential search schemes have been considered by Benkerouf and Bather [1] and Dunkl [4]. In fact, Dunkl studied a variation of proofreading wherein the reader returns to the beginning of the manuscript each time an error is discovered (so that a maximum of one find is allowed per search).

REFERENCES

1. L. Benkerhouf and J. A. Bather, Oil exploration: sequential decisions in the face of uncertainty, J Appl. Probab. 25 (1988) 529-543.

2. G. Blom, J. E. Englund, and D. Sandell, General Russian roulette, Math. Mag. 69 (1996) 293-297.. 3. L. Carlitz, A combinatorial property of q-Eulerian numbers, Amer. Math. Monthly 82 (1975) 51-54.

4. C. F Dunki, The absorption distribution and the q-binomial theorem, Comm. Statist. Theory Methods 10 (1981) 1915-1920.

5. D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd ed., Addison-Wesley, Reading, MA, 1997. 6. T. Herbranson and D. P. Rawlings, A sequential search distribution: Proofreading, Russian roulette, and the incomplete q-Eulerian polynomials, Discrete Math. Theor. Comput. Sci. to appear.

7. P. A. MacMahon, Combinatory Analysis, Vols. 1, 2, Cambridge University Press, London/New York, 1915; reprinted by Chelsea Publishing Co., New York, 1960.

8. R. H. Moritz and R. C. Williams, A coin-tossing problem and some related combinatorics, Math. Mag. 61 (1988) 24-29.

9. D. P. Rawlings, Absorption processes: Models for q-identities, Adv. in Appl. Math. 18 (1997) 133-148. 10. D. Sandell, Fair Russian roulette, Math. Sci. 22 (1997) 52-57.

DON RAWLINGS received his Ph.D. from University of California at San Diego under the direction of Adriano Garsia and Dominique Foata. He has incredible difficulty in spotting his own typos and absolutely hates to look for lost keys. To relax, Don enjoys playing his guitar and kicking up his heels doing a form of tap dance known as clogging.

California Polytechnic State University, San Luis Obispo, CA 93407 drawling@math.calpoly.edu