An efficient algorithm for sequential random sampling

ABSTRACT

We examine several methods for drawing a sequential random sample of n records from a file containing N records. Method D is recommended for general use. The algorithm is on-line (so that CPU time can be overlapped with I/O), has a small constant memory requirement, and is easy to program. An improved implementation is detailed in the Appendix.

REFERENCES

• 1: J. H. Ahrens , U. Dieter, Computer methods for sampling from the exponential and normal distributions, Communications of the ACM, v.15 n.10, p.873-882, Oct. 1972 [doi>10.1145/355604.361593]
• 2: J. H. Ahrens , U. Dieter, Sequential random sampling, ACM Transactions on Mathematical Software (TOMS), v.11 n.2, p.157-169, June 1985 [doi>10.1145/214392.214402]
• 3: ERNVALL, J., AND NEVALAINEN, O. An algorithm for unbiased random sampling. Comput. J. 25, 1 (Jan. 1982) 45-47.
• 4: FAN, C. T., MULLER, M. E., AND REZUCHA, I. Development of sampling plans by using sequential (item by item) selection techniques and digital computers. Am. Star. Assn. J. 57 (June 1962) 387-402.
• 5: GEHRKE, H. Einfache sequentielle Stichprobenentnahme. Diplomarbeit, Universit/it Kiel, Kiel, West Germany (Aug. 1984).
• 6: T. G. Jones, A note on sampling a tape-file, Communications of the ACM, v.5 n.6, p.343, June 1962 [doi>10.1145/367766.368159]
• 7: KAWARASAKI, J., AND SIBUYA, M. Random numbers for simple random sampling without replacement. Keio Math. Sere. Rep. 7 (1982) 1-9.
• 8: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 9: Jeffrey Scott Vitter, Faster methods for random sampling, Communications of the ACM, v.27 n.7, p.703-718, July 1984 [doi>10.1145/358105.893]

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical software

General Terms:
Algorithms, Design, Performance