Antithetic Power Transformed Random Variables in Computer Simulations: An Error Correction Mechanism ()
1. Introduction
A sequence of random numbers that are serially perfectly uncorrelated in its totality can contain what appear to be subsets of correlated sequences. Indeed, positively and negatively correlated subsets are a necessary part of true randomness. Traces of serial correlation in any subset can create a trend that biases the random numbers to the high or low side of the true value. An opposite trend can develop subsequently. But a very large number of random numbers can occur before the net bias is corrected. Proykova [1] describes random walk simulation experiments in which the walker is temporarily trapped in the vicinity of correlated numbers. Either way, apparent subsets of traces of serial correlation introduce unreliability into the simulation. Serial correlation in random numbers that are used in Monte Carlo computer simulation experiments, are known to cause bias in estimates of the response variable (Ferrenberg, Lanau and Wong [2] ). Where possible, bias and variance reduction methods can be very useful for improving accuracy in some applications. For example, physics experiments can utilize as many as 1019 random numbers. Reducing the length of a simulation for the same level of accuracy will save considerable time. Depending on the application, bias free accuracy is of paramount importance. Therefore, apart from their not repeating, the long run quality of the random numbers is irrelevant, since subsets will be correlated. Perhaps it is better to focus on methods that have the potential to improve the results obtained from random numbers that are deficient for any reason related to departure from randomness. Accordingly, some ideas are explored and discussed. The novelty of this paper is to present a new method of antithetic variables that eliminates bias error in the simulation response variable.
1.1. Background
Monte Carlo computer simulation is a widely used method for the study and analysis of complex systems that are not tractable to analytical mathematical formulae. Several methods of random number generation have been devised for use in computer simulation. Once the most common of these was the multiplicative congruential generator first suggested by Lehmer [3] . Various design issues have been identified by Marsaglia [4] and Park and Miller [5] . Pursuant to these issues and others associated with the mixed linear congruential generator, various more complicated methods have been suggested (Marsaglia [6] [7] ; Marsaglia & Tsang [8] ; Marsaglia & Tsay [9] ). Much attention has also been paid to the speed of generating random numbers (Marsaglia, MacLaren & Bray [10] ; Marsaglia & MacLaren [11] ; Marsaglia, Ananthanarayan & Paul [12] ; Marsaglia & Tsang [13] ; Leva [14] ). Kroese, Taimre & Botev [15] discusses the pros and cons of a wide variety of methods. The disconcerting outcome from the use of so called better random numbers is that the bias found by Ferrenberg, Lanau and Wong [2] is worse than that for the simpler linear congruential generator.
Inversely correlated random numbers were suggested by Hammersley and Morton [16] . They proposed a simple method for use in Monte Carlo computer simulation. In that method two simulations are conducted. One simulation uses uniformly distributed (0, 1) random numbers
,
. The other uses the complementary random numbers
. The output responses from the two simulations are then averaged. The method may produce an average response that has a smaller variance than for the individual simulations. Aljeddani [17] uses Bayesian methodology in Monte Carlo simulation to improve estimates where time and cost constraints are prohibitive. In practice, the variance reduction is not guaranteed and may actually increase (Cheng [18] ; Kleijnen [19] ). Cheng [18] goes on to suggest an improvement. However, reducing variance does not correct bias error. It only makes the response variable more precisely wrong. Our aim in this paper is bias elimination.
Antithetic random variables by power transformation of actual time series data was introduced by Ridley [20] . The Ridley [20] antithetic time series theorem states that “if
,
is a discrete realization of a lognormal stochastic process, such that
, then if the correlation between
and
is ρ, then
.” Serially correlated antithetic random variables can be combined so as to generate a new random variable that is not serially correlated. Ridley [20] provides antithetic fitted function, and antithetic fitted error variance function theorems for lognormally distributed random variables. Ridley [21] [22] [23] , Ridley, Ngnepieba & Duke [24] , Ridley & Ngnepieba [25] [26] demonstrate applications in time series analysis and forecasting. At first thought, it appears that the creation of antithetic random variables by this method might be useful for computer simulation. However, the random numbers used in computer simulation are uniformly distributed, not lognormally distributed.
1.2. Proposed Research
The proposed research is concerned with artificial sequences of antithetic random numbers and variables as opposed to the analysis of antithetic time series obtained from recorded data. We define antithetic variables as follows.
Definition. Two random variables are antithetic if their linear correlation is negative. A bivariate collection of random variables is asymptotically antithetic if its limiting correlation approaches minus one asymptotically.
Definition. r(x,i) is an ensemble of random variables, where x belongs to a sample space and i belongs to an index set representing order, such that
is a discrete realization of a stochastic process from the ensemble,
, and
are serially correlated.
The objective of the proposed research is not to create better random numbers. The objective is to reduce the effect of serial correlation in random numbers on bias in the estimate of the response variable from computer simulations regardless of the particular method of random number generation. Combining antithetic computer simulations is investigated for this purpose. Therefore, the worse the random numbers are, the better is the test of efficacy of combining antithetic computer simulations. So, only the simple linear congruential generator (LCG) was used. If the random numbers, however generated, were ideal in every way, the expectation is that no improvement in the accuracy of the response variable will occur due to antithetic combining. We do not know ahead of time the distribution of the response variable. So, beyond what we know about the lognormal case from Ridley [20] , we begin by exploring the correlation between the sequence of various random variables to establish the inverse correlations that are the basis of antithetic combining. This serves to improve our general understanding of antithetic combining and gain insights for what might work best. Then we apply antithetic combining to a response variable from a computer simulation. After examining the results of the exploration, we hypothesize that the estimates of response variables from computer simulations can be combined with their antithetic counterpart to obtain a new response variable that has negligible bias.
The paper is organized as follows. In section 2 we derive the analytic function for the correlation between a uniform random number and the random variate obtained from its pth exponent. In section 3 we derive the analytic function for the correlation between antithetic exponential random variates obtained by power transformation. In Section 4 we derive the correlation between random variates from inverse and power transformations. In section 5 we present the results of a computer simulation experiment. In section 6 we explore the effect of combining a response variable from a Monte Carlo simulation performed with random variates obtained by inverse transformation and by combining the response variable with its power transformed antithetic variable counterpart. Section 7 contains conclusions and suggestions for future research.
2. Correlation between
and
Antithetic uniform random numbers theorem: If
,
is a discrete realization of a uniform stochastic process, such that
for any interval a, b, then if
is the correlation between
and
, then
See Appendix A for the proof.
This correlation is illustrated in Table 1 and Figure 1 for
and values of p on and between −0.1 and −0.001. The correlations are averages calculated from 1000 samples of 500 numbers each, obtained from Matlab [27] . The correlation between
and
is seen to be negative, approaching −0.8666 recurring, or
.
Unlike the case of the lognormal distribution where the correlation between the random variable and its pth exponent is −1, here the correlation is
. That is,
and
can only offer partial antithetic combining. In order to convert
into the units of r, consider the regression of
on
,
. Since
(see Appendix B),
Table 1. Correlation between
and
vs p.
Figure 1. Correlation between
and
vs p.
that is
and
are perfectly negatively correlated, it follows that
where
. That is,
. Let the fitted values of
be denoted by
, let
and
denote least squares estimates of
and
respectively, and let s denote standard deviation. Then,
. This random variable is negatively correlated with r. However, unlike r, the probability distribution of
is not uniform. For purpose of comparison and uniformity,
can be converted back to the original scale of and distribution of
by computing the inverse transform
. As it turns out, r and
are positively correlated.
3. Antithetic Variates
Antithetic random variates theorem: If
,
is a discrete realization of a uniform stochastic process, such that
, then if
is the correlation between
and
, then
.
See Appendix B for the proof.
This correlation is illustrated in Table 2 and Figure 2 for values of p on and between −0.1 and −0.001. The correlations are calculated from just one sample of 100 random numbers. These correlations converge very rapidly. The correlation between
and
is seen to approach −1.
Histograms for
and
and
based on 300 random numbers are shown in Figure 3. The histograms illustrate that in the limit as
, the distributions of
and
are similar to negative
Table 2. Correlation between
and
vs p.
Figure 2. Correlation between
and
vs p.
Figure 3. Distributional characteristics
.
and positive exponential distributions, respectively.
Consider the possibility of combining response variables obtained from two computer simulations that are based on antithetic exponential random variates. Let the mean and standard deviation be 1/λ. Then, the exponential random variates can be obtained from
by converting the mean and standard deviation. This is accomplished by subtracting its sample average
and dividing by the standard deviation (
), then multiply by the population standard deviation (1/λ) and adding the population mean (1/λ) of interest. This suggests that computer simulations based on the antithetic pair
and
might yield a combined response with improved statistics. However, if the distribution of
matches that of the actual problem variable, the distribution of
will not
match, and will not be a good representation. These random variates are perfectly negatively correlated.
4. Correlation between Random Variates from Inverse and Power Transformations
We established that the random variates
are exponentially distributed. Therefore, we explored the comparison between exponential random variates obtained from the traditional inverse transformation and those obtained from the proposed power transformation.
Consider the exponential random variable x with parameter λ. Its pdf given by
The corresponding cumulative distribution is given by
The exponential random variate is calculated by setting
equal to the cumulative distribution
The exponential random variate obtained by inverse transformation is given by
The exponential random variate obtained by power transformation is given by
Substituting the expected values for
and
from Appendix A,
,
where
has the property of equality of mean and standard deviation.
Antithetic inverse and power transform random variates theorem: If
is a uniformly distributed random number,
,
is a discrete realization of an exponential stochastic process such that
derived from the inverse transformation
with parameter λ, and
derived from
, then if
is the correlation between
and
, then
.
See Appendix C for the proof.
This correlation is illustrated in Table 3 for values of p on and between −0.1 and −0.001 and in Figure 4. The correlations are averages calculated from 2000 samples of 500 numbers each, obtained from Matlab [27] . The correlation between
and
is seen to be negative, approaching −0.6484 recurring. That
Table 3. Correlation between
and
vs p.
is, approximately equal to
. This correlation falls short of the ideal correlation of −1. That is,
and
can offer only partial antithetic combining.
5. Computer Simulation Experiment
Consider a simple M/M/1 queue as depicted in Figure 5. There are many systems that can be modelled by queueing theory. They include waiting lines at a business establishment, library or other institution, jobs waiting to be processed by a computer central processing unit, automobile traffic, telephone calls, statistical particle physics, etc. The test system used in the following experiment is limited to a simple queue for which we know precisely the value of the response variable. The expectation is that if bias reduction is effective in the test system, it will also be effective in more complex systems where the answers are unknown and are to be determined. The schematic shows one queueing system and one Monte Carlo experiment. In both cases, entities arrive at the mean rate of λ per unit time and are served at the mean rate of μ per unit time. The time between arrivals is exponentially distributed with mean 1/λ. The service time is exponentially distributed with mean 1/μ. In the standard traditional experiment, the
Figure 4. Correlation between
and
vs p.
experiment is conducted with an inter arrival time denoted by
derived from
and service time
derived from
. The LCG is
(suggested by Harrell, Ghosh & Bowden [28] .
In the simple queue, the source population for arriving entities is infinite. The queue is un-capacitated. There is a single server. The entity processing rule is first come first served. The first actual simulation is based on a mean inter arrival time of 3 minutes and a mean service rate of 2.4 minutes. That is, λ = 1/3 per minute and μ = 1/2.4 per minute. The response variable chosen is the average time that an entity spends in the system. The average time that entities spend in the system is well known to be precisely
minutes. Based on a 100,000 arrivals simulation, the estimated simulation time in the system T = 11.63 (see Table 4). The bias is 12-11.65 = 0.35 = 2.92%. For most applications this level of accuracy may suffice. However, as the λ/μ ratio increases toward 1 the bias increases and the decline in accuracy is significant. Table 4 shows the results for various of λ/μ ratios. For an example of high bias, consider μ = 1/2.4, 1/λ = 2.474, λ/μ = 0.97, the
minutes. The estimated simulation time in the system is T = 65.3807 (see Figure 6). The bias = 65.3807 − 80.24 = −14.8593 = −18.51%. This bias is unacceptable as are many estimates in Table 4.
To reduce this bias the antithetic time in system is obtained from
where p = −0.0001. Then T is regressed on
to express
in the original units of T. The estimated regression equation is given by
.
Figure 6. Simulation estimates of time in system
when
.
Table 4. Computer simulation results 1/μ = 2.4 minutes and various 1/λ, λ/μ and ω.
The final result is the weighted average
, where ω and
are combining weights. For each combination of μ and λ there is an ω for the corresponding λ/μ ratio that results in negligible bias (estimated TC in bold numbers).
Ferrenberg, Lanau, & Wong [2] tried more advanced random number generators to no avail. So, the LCG simulation experiments here were repeated with the most advanced Mersenne Twister algorithm for random numbers. The results were biased similarly.
6. Optimizing the Combining Weights
A graph of ω for various λ/μ ratios that result in negligible bias (estimated TC in bold numbers) is given in Figure 7. This graph of ω is a smooth monotonically increasing function λ/μ. Optimization of the weight is done by consulting Figure 7 once the λ/μ ratio for the system design is known. A graph of simulation estimates of time in system when 1/λ = 2.474, 1/μ = 2.4 minutes, ω = 1.25 and
converges to 81.48 minutes is given is Figure 8. The graph is created once ω is obtained from Figure 7. The bias is now 80.24 − 81.48 = 1.24 = 1.5%. This is acceptable. We also observe that the shapes of the graphs in
Figure 7. Weight ω for various λ/μ ratios that result in negligible bias.
Figure 8. Simulation estimates of time in system
when
.
Figure 6 and Figure 8 are essentially the same except for one is biased and one is unbiased.
7. Conclusion
The experiments in this paper were Monte Carlo computer simulations. Antithetic random variates were created by inverse transformation. The response variable was observed to be highly biased. This appears to be an artifact of a simulation that cannot be improved by the choice of random numbers. Therefore, antithetic random variables were created from the response variable and its power transformation. The idea for this came from insights that were gained from the derivations of the correlation with antithetic counterparts of known functions. These formed antithetic variables that were combined. The combined variable was demonstrated to contain negligible bias. The combined estimates were closer to their corresponding values that are known to be true from theory. Combining reduced bias in the estimated values. The simulations in this research were applied to a simple queue. Like Ferrenberg, Lanau, & Wong [2] in their study of the Ising model two-dimensional lattice gauge physics problem, we conclude here that there is bias leading to the wrong answer for time in the queueing system. Therefore, we repeat their caution here. This research supports the notion that if the bias is due to pre-simulation traces of serial correlation, then since subsets of correlation are part of overall randomness, bias cannot be avoided by better random numbers. Therefore, it is better to pursue ideas for cancelling bias, post-simulation. This research is limited to the simple queuing system. Future research might be conducted for different system designs and antithetic variables combining strategies. The Ising lattice gauge physics problem can be repeated using the method proposed in this research to see if the bias is eliminated there.
Nomenclature
Antithetic variables—Two variables that are oppositely correlated.
Antithetic power transformation—Uses an infinitesimal negative exponent to produce a new variable that is negatively correlated with the original variable.
LCG—Linear congruential generator of pseudorandom numbers.
Mersenne Twister algorithm—Fast generation of high-quality very long period pseudorandom numbers.
Monte Carlo Simulation—A mathematical method for calculating the odds of multiple possible outcomes occurring in an uncertain process through repeated random sampling.
PDF—Probability Density Function.
Random variate—Uniformly distributed [0, 1] random number sequence.
Random variable—Random number sequence that follows a distribution corresponding to a known variable.
Appendix A: Correlation between
and
Consider
with pdf
(A.1)
(A.2)
Next, consider
. Then
Substituting for
from (A.1)
Assume a = 0, b>0, then
,
and
.
This correlation is invariant with respect to the lower limit of the interval a, b.
Appendix B: Correlation between
and
Consider
. Then from Appendix A,
Similarly,
Therefore,
Likewise,
Appendix C: Correlation between
and
Given
,
The expected value of the original variable
is
Since
, (C.1)
. (C.2)
Also,
and since
,
.
Therefore,
, so that
. (C.3)
The expected value of the antithetic variable
is
and since
,
(C.4)
with variance
.
For an n step computer simulation,
as
.
Therefore,
. (C.5)
Remark.
is consistent with
&
expontially distributed.
To obtain the expected value
, consider,
(C.6)
From (A.1) and (A.2)
Therefore, replacing
with
,
with
and
with
,
(C.7)
where
and
, (C.8)
from which we obtain
. (C.9)
The Taylor expansion at
of
is
.
Substituting for
in (C.8)
from which we obtain
. (C.10)
Substituting (C.9) and (C.10) in (C.7)
. (C.11)
Substituting (C.11) in (C.6)
.
From the Lebesque dominated converge theorem,
.
Therefore,
,
and since
(see Appendix D),
. (C.12)
Finally, the correlation between
and
And substituting from (C.2), (C.3), (C.4), (C.5), (C.12),
.
Appendix D
where ζ is the Reimann zeta function. See Chapman [29] .