Randomness and random numbers are needed in a wide range of areas; they are of basic importance in computational statistics, in the implementation of probabilistic algorithms and in related problems of statistical computing that have a stochastic ingredient for e.g., Computational Chemistry, Risk and Uncertainty Analysis, Process Design under Uncertainty, Scheduling and Planning, Process Control, Financial Modeling, Artificial Intelligence, Design of Experiments[1]. In most applications, the actual relationship between successive points in a sample has no physical significance; hence, randomness of the sample for approximating a uniform distribution is not critical. The Quasi Random (low discrepancy) sequences are designed to have better uniformity. These Quasi Monte Carlo sequences are shown to be more efficient than Pseudo Random Number based Monte Carlo Sequences for various applications [3]. For higher dimensional stochastic processes, however, as the number of dimensions increases, the quality of the Quasi Random sequences rapidly deteriorates [2]. The long term focus of this research is to come up with optimal strategies for random number generations that will perform better in higher dimensions as well. In order to determine an optimal random number generator, a universal performance index across different dimensions, functionalities, probability distributions and applications is needed. Although discrepancy provides a measure of uniformity, it does not provide estimation of accuracy for a given application. Further, it is difficult to visualize discrepancy for higher dimensions.

Approach

We propose here a novel approach for characterizing the error in Monte Carlo and Quasi Monte Carlo sampling which can also serve as a performance index for the purpose of evaluating various random number sequences. The approach is based on the concepts of fractal geometry. A fractal is a geometrical figure that consists of an identical motif repeating itself on an ever-reduced scale. The striking feature of fractals is their property of self-similarity i.e. subsets of a fractal object have primarily the same form as the whole object. Also they are described by a non-integral dimension called the fractal dimension. Most practical applications of random numbers require the estimation of probabilistic functions which are quantified in terms of moments like mean, variance and fractiles. The plots of relative error in prediction of the value of these moments for a probabilistic function against the number of samples are observed. It is found that these curves are of a fractal nature. A scaling relationship can be established between the error and the sample size as error ~ Nd ( ~ interpreted as “scales as”).

Results and Conclusions

By systematic experiments, we verified that “d” is indeed the dimension of the fractal represented by the curve. These experiments were carried out for the Monte Carlo sequence and some Quasi Monte Carlo sequences like Sobol sequence, Hammersley sequence and the Halton sequence for different dimensions, probability distributions and function forms. These experiments proved that the fractal dimension model is universally applicable, in the sense that it is independent of the functional form of the probabilistic function, number of dimensions of the problem and the probability distribution used. Also, this model applies to both Pseudo and Quasi Random number sequences alike. Another interesting observation is that for Quasi Random Number sequences in higher dimensions, as the uniformity breaks down, the scaling relationship no longer holds true. In essence this model can also capture the breakdown of uniformity. In summary, the fractal dimension model can be used as an effective performance index for finding the optimal random number generator for various applications.

References [1] Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods, Society for Industrial and Applied Mathematics, Philadelphia, Pennsylvania, 1992. [2] Ladislav Kocis and William J. Whiten. 1997. Computational Investigations of Low-Discrepancy Sequences. ACM Transactions on Mathematical Software, Vol.23 , 266-294 [3] Urmila Diwekar, Renyou Wang, Catherine Gregoire Padro, Efficient Sampling Techniques for Uncertainties in Risk Analysis. Environmental Progress, Vol.23, No.2, Jul 2004.