Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Shortest paths through pseudorandom points in the $ d$-cube


Author: J. Michael Steele
Journal: Proc. Amer. Math. Soc. 80 (1980), 130-134
MSC: Primary 65C99; Secondary 60D05
DOI: https://doi.org/10.1090/S0002-9939-1980-0574522-4
MathSciNet review: 574522
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A lower bound for the length of the shortest path through n points in $ {[0,1]^d}$ is given in terms of the discrepancy function of the n points. This bound is applied to obtain an analogue for several pseudorandom sequences to the known limit behavior of the length of the shortest path through n independent uniformly distributed random observations from $ {[0,1]^d}$.


References [Enhancements On Off] (What's this?)

  • [1] J. Beardwood, J. H. Halton and J. M. Hammersley, The shortest path through many points, Proc. Cambridge Philos. Soc. 55 (1959), 299-327. MR 0109316 (22:202)
  • [2] L. Few, The shortest path and the shortest road through n points, Mathematika 2 (1955), 141-144. MR 0078715 (17:1235f)
  • [3] J. H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math. 2 (1960), 84-90; correction, p. 196. MR 0121961 (22:12688)
  • [4] J. Kiefer, On the large deviation of the empiric d.f. of vector chance variables and a law of the iterated logarithm, Pacific J. Math. 11 (1961), 649-660. MR 0131885 (24:A1732)
  • [5] D. E. Knuth, The art of computer programming, Vol. 2, Seminumerical algorithms, Addison-Wesley, Palo Alto, California, 1969. MR 0286318 (44:3531)
  • [6] L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Wiley, Toronto, 1974. MR 0419394 (54:7415)
  • [7] D. S. Mitrinović, Analytic inequalities, Springer-Verlag, New York, 1970. MR 0274686 (43:448)
  • [8] H. Niederreiter, Application of diophantine approximations to numerical integrations, Diophantine Approximation and its Application (C. F. Osgood, ed.), Academic Press, New York, 1973, pp. 129-199. MR 0357357 (50:9825)
  • [9] -, Statistical independence of linear congruential pseudo-random numbers, Bull. Amer. Math. Soc. 82 (1976), 927-929. MR 0419395 (54:7416)
  • [10] -, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), 99-181. MR 0476679 (57:16238)
  • [11] -, Quasi-monte carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), 957-1041. MR 508447 (80d:65016)
  • [12] W. Schmidt, Metrical theorems on fractional parts of sequences, Trans. Amer. Math. Soc. 110 (1964), 493-518. MR 0159802 (28:3018)
  • [13] -, Simultaneous approximation to algebraic numbers by rationals, Acta Math. 125 (1970), 189-201. MR 0268129 (42:3028)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 65C99, 60D05

Retrieve articles in all journals with MSC: 65C99, 60D05


Additional Information

DOI: https://doi.org/10.1090/S0002-9939-1980-0574522-4
Keywords: Discrepancy, pseudorandom, shortest paths, uniform distribution
Article copyright: © Copyright 1980 American Mathematical Society

American Mathematical Society