×

Deterministic sampling from uniform distributions with Sierpiński space-filling curves. (English) Zbl 1505.62013

Summary: In this paper the problem of sampling from uniform probability distributions is approached by means of space-filling curves, a topological concept that has found a number of important applications in recent years. Departing from the theoretical fact that they are surjective but not necessarily injective, the investigation focused upon the structure of the distributions obtained when their domains are swept in a uniform and discrete manner, and the corresponding values used to build histograms, that are approximations of their true PDFs. This work concentrates on the real interval \([0,1]\) and the Sierpiński space-filling curve was chosen because of its favorable computational properties. In order to validate the results, the Kullback-Leibler and other divergence measures are used when comparing the obtained distributions in several levels of granularity with other already established sampling methods. In truth, the generation of uniform random numbers is a deterministic simulation of randomness using numerical operations. In this fashion, sequences resulting from this sort of process are not truly random. Despite this, and to be coherent with the literature, the expression “random number” will be used along the text to mean “pseudo-random number”.

MSC:

62-08 Computational methods for problems pertaining to statistics
65C10 Random number generation in numerical analysis
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization

Software:

Ziggurat; rnorrexp
PDFBibTeX XMLCite
Full Text: DOI DOI

References:

[1] Basu, A.; Shioya, H.; Park, C., Statistical inference: the minimum distance approach (2011), Boca Raton: CRC Press, Boca Raton · Zbl 1281.62016 · doi:10.1201/b10956
[2] Boyarsky A, Góra P (1997) Laws of Chaos. Invariant measures and dynamical systems in one dimension. Birkhäuser, Boston · Zbl 0893.28013
[3] Burkardt J (2021) RANDLC method implementation, https://people.sc.fsu.edu/ jburkardt/cpp_src/randlc/randlc.html. Accessed Apr 21
[4] Burkardt J (2021) RNGLIB method implementation, https://people.sc.fsu.edu/ jburkardt/cpp_src/rnglib/rnglib.html. Accessed Apr 21
[5] Burkardt J (2021) Ziggurat method implementation, https://people.sc.fsu.edu/ jburkardt/cpp_src/ziggurat/ziggurat.html. Accessed Apr 21
[6] Choe, GH, Computational Ergodic Theory (2005), Berlin: Springer, Berlin · Zbl 1064.37004
[7] Cover, TM; Thomas, JA, Elements of information theory (1991), Hoboken: Wiley, Hoboken · Zbl 0762.94001 · doi:10.1002/0471200611
[8] Dajani, K.; Kraaikamp, C., Ergodic theory of numbers (2002), Washington DC: The Mathematical Association of America, Washington DC · Zbl 1033.11040 · doi:10.5948/UPO9781614440277
[9] Edgar, G., Measure, topology, and fractal geometry (2008), Berlin: Springer, Berlin · Zbl 1152.28008 · doi:10.1007/978-0-387-74749-1
[10] Fog A (2021) Mersenne twister implementation of Randomc library, www.agner.org/random/. Accessed in Apr 21
[11] Goertzel, B., Global optimization with space-filling curves, Appl Math Lett, 12, 133-135 (1999) · Zbl 1052.90612 · doi:10.1016/S0893-9659(99)00134-2
[12] LEcuyer, P., Serge cote, implementing a random number package with splitting facilities, ACM Trans Math Softw, 17, 1, 98-111 (1991) · Zbl 0900.65008 · doi:10.1145/103147.103158
[13] Lera, D.; Sergeyev, YD, Lipschitz and Hölder global optimization using space-filling curves, Appl Numer Math, 60, 115-129 (2010) · Zbl 1201.65101 · doi:10.1016/j.apnum.2009.10.004
[14] Marsaglia, G., Remarks on choosing and implementing random number generators, Commun ACM, 36, 105-108 (1993) · doi:10.1145/159544.376068
[15] Marsaglia, G.; Tsang, WW, The ziggurat method for generating random variables, J Stat Softw, 5, 8 (2000) · doi:10.18637/jss.v005.i08
[16] Oliveira HA Jr (2016) Evolutionary global optimization. Springer-Verlag, Cham Heidelberg New York Dordrecht London, Manifolds and applications · Zbl 1336.90002
[17] Oliveira, HA Jr; Petraglia, A.; Gaspar-Cunha, A., Global optimization using space-filling curves and measure-preserving transformations, Soft computing in industrial applications, 121-130 (2011), Berlin, Heidelberg: Springer, Berlin, Heidelberg · doi:10.1007/978-3-642-20505-7_10
[18] Oliveira, HA Jr; Ingber, L.; Petraglia, A.; Petraglia, MR; Machado, MAS, Stochastic global optimization and its applications with fuzzy adaptive simulated annealing (2012), Berlin-Heidelberg: Springer, Berlin-Heidelberg · Zbl 1236.90003
[19] Sagan, H., Space-filling curves (1994), New York: Springer, New York · Zbl 0806.01019 · doi:10.1007/978-1-4612-0871-6
[20] Sergeyev, YD; Strongin, RG; Lera, D., Introduction to global optimization exploiting space-filling curves (2013), Heidelberg, New York, Dordrecht, London: Springer, Heidelberg, New York, Dordrecht, London · Zbl 1278.90005 · doi:10.1007/978-1-4614-8042-6
[21] von Neumann J (1963) Various techniques used in connection with random digits. Collected Works, 5. Pergamon Press, Oxford, pp 768-770
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.