Shortest paths through pseudorandom points in the 𝑑-cube

Steele, J. Michael

doi:10.1090/S0002-9939-1980-0574522-4

Shortest paths through pseudorandom points in the $d$-cube
HTML articles powered by AMS MathViewer

by J. Michael Steele PDF

Proc. Amer. Math. Soc. 80 (1980), 130-134 Request permission

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

Jillian Beardwood, J. H. Halton, and J. M. Hammersley, The shortest path through many points, Proc. Cambridge Philos. Soc. 55 (1959), 299–327. MR 109316, DOI 10.1017/s0305004100034095
L. Few, The shortest path and the shortest road through $n$ points, Mathematika 2 (1955), 141–144. MR 78715, DOI 10.1112/S0025579300000784
J. H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math. 2 (1960), 84–90. MR 121961, DOI 10.1007/BF01386213
J. Kiefer, On large deviations of the empiric D. F. of vector chance variables and a law of the iterated logarithm, Pacific J. Math. 11 (1961), 649–660. MR 131885, DOI 10.2140/pjm.1961.11.649
Donald E. Knuth, The art of computer programming. Vol. 2: Seminumerical algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969. MR 0286318
L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
D. S. Mitrinović, Analytic inequalities, Die Grundlehren der mathematischen Wissenschaften, Band 165, Springer-Verlag, New York-Berlin, 1970. In cooperation with P. M. Vasić. MR 0274686, DOI 10.1007/978-3-642-99970-3
H. Niederreiter, Application of Diophantine approximations to numerical integration, Diophantine approximation and its applications (Proc. Conf., Washington, D.C., 1972) Academic Press, New York, 1973, pp. 129–199. MR 0357357
Harald Niederreiter, Statistical independence of linear congruential pseudo-random numbers, Bull. Amer. Math. Soc. 82 (1976), no. 6, 927–929. MR 419395, DOI 10.1090/S0002-9904-1976-14222-X
Harald Niederreiter, Pseudo-random numbers and optimal coefficients, Advances in Math. 26 (1977), no. 2, 99–181. MR 476679, DOI 10.1016/0001-8708(77)90028-7
Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, DOI 10.1090/S0002-9904-1978-14532-7
Wolfgang M. Schmidt, Metrical theorems on fractional parts of sequences, Trans. Amer. Math. Soc. 110 (1964), 493–518. MR 159802, DOI 10.1090/S0002-9947-1964-0159802-4
Wolfgang M. Schmidt, Simultaneous approximation to algebraic numbers by rationals, Acta Math. 125 (1970), 189–201. MR 268129, DOI 10.1007/BF02392334