Shortest paths through pseudorandom points in the -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 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 .

**[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)**

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