# 1 Quasi-Monte Carlo Approaches to Option Pricing

Quasi-Monte Carlo Approaches to Option Pricing John R. Birge* Department of Industrial and Operations Engineering University of Michigan Ann Arbor, MI 48109 (313)764-9422 Abstract: Complications such as varying interest rates and complex contingencies can prohibit analytical computation of option and other derivative prices. A typical approach is to rely on Monte Carlo simulation in these cases and to use statistical properties of assumed random sequences. This approach has two drawbacks. First, the validity of a pseudo-random sequence for statistical randomness is somewhat questionable. Second, even assuming randomness, the error from central limit arguments decreases slowly, inversely proportional to the square root of the number of observations. Quasi-Monte Carlo sequences, on the other hand, do not rely on a randomness assumption and have order of magnitude better asymptotic error rates. We show how quasi-Monte Carlo sequences can be used in option pricing, give some analytical just?cation for their preference over crude or pseudo-Monte Carlo methods, and present some empirical evidence based on simple call option models.

Keywords: simulation, option pricing, quasi-random 1. Introduction The landmark paper of Black and Scholes [1973] spawned many other approaches to option pricing and to the evaluation of general contingent claims (see, e.g., Jarrow and Rudd [1983]). Many of these approaches try to ?nd simple analytical calculations as in the Black-Scholes formula. When the contingencies become complex, interest rates vary, or other simplifying assumptions are invalid, analytical formulas may either contain excessive errors or may not be available. In these cases, Monte Carlo simulation can be used to represent many random phenomena that can in?uence the option price (see, e.g., Boyle [1977]). * Based on work supported by the National Science Foundation under Grant ECS 8815101 and 92-15921. The author thanks Sanjeev Acharya and Jim Wartinbee for assistance in the computational implementations. 1

The Monte Carlo method (see Hammersley and Handscomb [1964]) has its basis in statistical theory, in particular, the central limit theorem that allows the calculation of con?dence intervals about the mean value of a random variable based on a sequence of independent random observations. Practically, the validity of this approach depends on the ability to generate sequences of random numbers. Thus, random number generation is a critical element in using the Monte Carlo method (see De? ak [1990]). The general practice is to use pseudo-random sequences that share properties with random sequences, such as frequency of increasing or decreasing runs of various lengths. These pseudo-random sequences are constructed from a variety of techniques involving simple operations on previous numbers in the sequence. Their use and statistical justi?cation in the Monte Carlo method has, however, been questioned (see, e.g., Zaremba [1968]). Even assuming the statistical basis, the error in Monte Carlo estimates decreases at an asymptotic rate that is inversely proportional to the square root of the number of observations, ). O( √1 N An alternative is to rely on numerical properties of the sequence and on how closely a sequence ?lls in each region in the support of the random variables. This measure, called the discrepancy, can be reduced by constructing sequences that more deliberately ?ll in the random support. These sequences are often called quasi-random numbers or low-discrepancy sequences. Their use in approximating integrals or expectations is called the quasi-Monte Carlo method (see Niederreiter [1978] for a survey and comparison with pseudo-random numbers). The great advantage of quasi-random sequences is that the asymptotic error generally
1 reduces to O( N ). The di?culty is, however, that the constants that can be calculated for

this order represent a worst case and may be quite large. In practice, however, the error may be much less. We give some indication of this below. Calculating the error for any individual example may be di?cult but another recent discovery gives even greater potential for the use of quasi-Monte Carlo sequences. Wo? zniakowski [1991] has shown that the expected error of using particular quasi-Monte
1 Carlo sequences is approximately O( N ) for integrating over a general class of continuous

functions in many dimensions. This observation e?ectively suggests, on average, crude Monte Carlo requires the square of the number of observations required by quasi-Monte Carlo to achieve the same error. This conquering of the curse of dimensionality (at least in 2

expectation) has led to renewed interest in improved numerical integration and simulation (see Yam [1991], Guterl [1994]). We suggest some direct uses of this observation below, although it does not directly apply to simple options which correspond only to a small subset of all functions considered in Wo? zniakowski’s result. The general asymptotic error bounds in quasi-Monte Carlo methods do, however, indicate that they can improve on option pricing with pseudo-Monte Carlo. This paper presents both analytical and empirical evidence for this claim. In Section 2, we present our basic approaches for option pricing, which we interpret as integration over a region with dimension equal to the number of distinct periods of price changes. Section 3 gives some analytical comparisons of quasi- and pseudo-random sequence approaches. Section 4 presents our empirical observations. Section 5 gives conclusions.

2. Monte Carlo Option Pricing The Monte Carlo method generally refers to procedures for approximating the integral, I =
R

f (x)dx, of a function, f , over a region, R, where f :

n

, and R ?

n

. The

basic idea is to choose a sequence of points, {xk }, i = 1, . . . , N , uniformly distributed in R and to estimate I by ?(N ) = 1 I N
N

f ( xk ) .
k=1

(1)

If the sequence {xk } indeed represents independent random observations, then the {f (xk )} values can also be considered observations of independent random variables with mean, I . To distinguish the random variables from their observations we use bold-face notation, e.g., xi . Assuming I and a ?nite second moment, N ? I(N ) can be interpreted as the sum of independent random variables. The central limit theorem can be invoked to determine the asymptotic normal distribution of ? I(N ) and to obtain a con?dence interval on I using an observation of ? I(N ) (for derivations, see, for example, Feller [1971]). The fundamental result is that ? I(N ) is asymptotically normally distributed with mean √ ? N )? I ) 1 I and variance N Vf , where Vf = R f (x) 2 dx?I 2 , the variance of f (x). Thus, N (I(√
Vf

is asymptotically a standard normal with zero mean and unit variance. If Φ denotes the distribution function of the standard normal, then a level α con?dence interval can be 3

α ?(N ) of ? obtained from an observation I I(N ) by noting, α = P [Φ?1 ( 1? 2 ) ≤

N )? I ≤ N I(√ Vf

?

Φ?1 (1 ?

1? α 2 )],

so that with probability α, ?(N ) ? √Vf Φ?1 ( 1 ? α ), I ?(N ) + √Vf Φ?1 ( 1 ? α )]. I ∈ [I 2 2 N N (2)

The two primary di?culties in using this method are that deterministic sequences generally replace the random variables in ? I(N ) and that the interval in (2) only changes proportionally to
1 √ . N

The deterministic sequences are pseudo-random sequences that pass tests for

randomness, but then the applicability of (2) is rather tenuous. A further implementation di?culty is that single pseudo-random streams are frequently used to obtain each component of the n-dimensional variable x. The result may be that a sequence that appears quite uniform in one dimension may be distributed with substantial collinearity (or lattice structure) when applied sequentially for higher dimensions. In these cases, generation of more points simply ?lls in each line (or hyperplane in higher dimensions). The error can never improve beyond the error in integrating along the lines. This error may be especially high if the integrand concerns the sum of the components as in option pricing. To overcome the di?culty of collinearity, pseudo-random vector generation schemes are possible (see, for example, Niederreiter [1991]). Another option is to use quasi-random numbers that explicitly consider the full dimension of the problem. These sequences avoid the randomness assumption and attempt to achieve low errors based purely on numerical (not statistical) analysis. In the next section, we give some of the analytical error properties of these sequences. ?(N ) can be constructed by Assuming streams of pseudo- or quasi-random vectors, I simply evaluating f at each point. We will assume that R is the unit hypercube, [0, 1]n , in
n

, and that f is constructed so the components of x are independently distributed. In

this way, we need only generate uniform points in the unit hypercube and then compute f . To illustrate the approach, we assume a simple model of a call option (without early exercise) and ?nd the appropriate f . We suppose that n is the number of periods into which the time to maturity is divided. In practice, the size of periods might vary and their endpoints might correspond to potential interest rate changes, dividend dates, or possible exercise points in an American option. We could include correlations among periods, but, for our illustrations, we assume independence of price changes across periods. 4

Now, assuming that stock returns have a lognormal distribution, we can simply invert the uniform components of x to obtain n normally distributed random values, sum these values, and exponentiate to obtain the price appreciation after n periods. Using the standard risk neutrality argument (see, e.g., Cox and Ross [1976]), the call price can then be discounted by a riskless bond rate to achieve the call option price. To state this more formally, assume that ST (x) is the random stock price at maturity date, T , Ct is the call price at time t, K is the strike price, and r is a riskless return (assumed constant for this discussion). Making the additional assumptions of frictionless markets and no early exercise, we can write Ct as C t = e ? r (T ? t ) (
[0,1]n

(ST (x) ? K )+ dx).

(3)

Hence, in (1), we have f (x) = e?r(T ?t) (ST (x) ? K )+ . We just need to de?ne ST . In general, we might consider many independent factors that all combine to e?ect the price at time T . In the simplest case, each xi corresponds to the quantile of the proportional price change in period i where price changes, (Sti /Sti?1 ), i = 1, . . . , n, among periods are independent. In this way, we let δi (xi ) = (Sti /Sti?1 ) and then ST (x1 , . . . , xn ) = St Πn i=1 δi (xi ). (4)

We also assume for ease of exposition that the proportional price changes are lognor√ 2 mally distributed with mean return (r ? σ 2 )(ti+1 ? ti ) and standard deviation σ ti+1 ? ti , so that log (δi (xi )) ? (r ? σ 2 )(ti+1 ? ti ) √ = Φ? 1 ( x i ) . σ ti+1 ? ti Combining (3), (4) and (5), we have C t = e ? r (T ? t ) (
[0,1]n Φ (St (Πn i=1 e
?1 2

(5)

(x i )σ

ti+1 ?ti +(r ? σ 2 )(ti+1 ?ti )

2

) ? K )+ dx).

(6)

Now, Monte Carlo or quasi-Monte Carlo approaches to evaluating (6) only require ?nding sequences of points, xk , k = 1, . . . , N , as in (1) and using the error results that accompany these sequences. We could use more complicated integrands than those in (6) but we choose the simple form above because analytical results are so readily available. Since we assume the price changes in each period are independent and lognormally distributed, 5

their product, ST , is also lognormally distributed with mean return, (r ? σ 2 )(T ? t), and √ standard deviation, σ T ? t. This observation leads to the Black-Scholes’ formula for Ct = St Φ( log (St /K ) + (r + σ 2 /2)(T ? t) √ ) σ T ?t (7)

2

?Ke?r(T ?t) Φ((

√ log (St /K ) + (r + σ 2 /2)(T ? t) √ ) ? σ T ? t) . σ T ?t

Of course, we do not need to use Monte Carlo approaches to evaluate (6) if (7) or other analytical representations are available. However, when more complicated types of integrals are included, then such straightforward analytical solutions may not be available. We use the simple form here to allow us to evaluate the accuracy of pseudo- and quasi-random schemes against a known analytical value. In the next section, we present some analytical results about the accuracy of these methods.

3. Analytical Error Analysis of Quasi-Monte Carlo Schemes The main basis for error analysis of pseudo-random schemes is the use of the con?dence interval in (2). In the option pricing case presented here, the error in this estimate is √ proportional to the standard deviation of the integrand divided by N . If this quantity is unknown, a sample variance can be used to estimate it with a t-distribution in place of the normal. The result allows asymptotic error bounds with con?dence level α (assuming true randomness). The
1 √ N

proportionality in the error decrease means, for example, that

achieving a con?dence interval that is 1/10 of a standard deviation requires 100 observations but that achieving an error of 1/100 of a standard deviation requires 10, 000 observations (assuming the asymptotics apply). In contrast to this slow error decrease, quasi-random numbers may provide better asymptotic error bounds that are proportional to
1 N

1 √ . N

We will consider two

such sequences here. The basic motivation for them is to achieve low discrepancy, the di?erence between the fraction of sequence points within any region of the unit hypercube and the volume of that region. The discrepancy should decrease to zero. One example of a quasi-random sequence is constructed from irrationals, such as the roots of the ?rst n primes. We will denote this sequence as {αk }, where component i of the k th sample is α k ( i) = k P ( i) ? k 6 P ( i) , (8)

where P (i) is the ith prime number, i = 1, . . . , n, and k integer less than or equal k

P (i) denotes the greatest

P (i). Hammersley and Handscomb [1968] show the following

(which we present without proof). Theorem 1. If the Fourier series of f is absolutely convergent, then there exists a constant c1 such that: 1 f (x)dx ? ( N n [0,1]
N

k=1

f (αk )) ≤ c1

1 + logN . N

(9)

Thus, there exists a constant c1 for any f with these properties that achieves an error bound with probability one that is proportional to
1+logN . N

In contrast to the straight

Monte Carlo approach, the growth in required iterations to achieve given accuracy is much less than quadratic. For example, to reduce the error bound in (9) to 1/10 of c1 requires 49 points while reducing the error bound to 1/100 of c1 requires 647 points. While these analytical results for the quasi-random sequence appear quite good, they depend on the constant c1 which is not easily estimated. They do, however, indicate that asymptotic results may be much better with quasi-random than pseudo-random sequences. Another sequence we shall use is called the Halton sequence (Halton [1960]) based on representing integers in terms of primes. We suppose that k has a representation in base P (i) as k = a1 P (i)k?1 + a2 P (i)k?2 + · · · + ak , and let φk (i) =
k i=1

ak?i+1 P (i)?i . The

sequence is then φk = (φk (1), . . . , φk (n)). Halton shows that this sequence also has low discrepancy. Using a standard result on functions of bounded variation, we can state this as the following. Theorem 2. If f is of bounded variation over [0, 1]n , then there exists a constant c2 such that: (
[0,1]n

f (x)dx ?

1 N

N

k=1

f (φk )) ≤ c2

(logN )n . N

(10)

Comparisons between Theorems 1 and 2 are di?cult again because of the di?culty in estimating the constants. In general, c2 is much less than c1 . Another advantage of the Halton sequence may be in computation since {αk } constructions require many digits of P (i) when k is high. With these caveats, we can still ?nd the worst-case reductions of 7

error from c2 in (10). For three (n = 3) dimensions, with the Halton sequence, reducing the error bound to 1/10 of c2 requires 6910 points while reducing the error bound to 1/100 of c2 requires 176, 000 points. A somewhat better comparison is that the additional digit of accuracy requires 25 times more samples compared to 13 times as many samples using the {αk } sequence and 100 times with standard Monte Carlo. We use the Halton sequence given above because it does not a priori require the total number of observations N . Knowing N (or ?xing N at certain values) can reduce the error order to
(logN )n?1 N

using, for example, the Hammersley sequence (see Hammersley

and Handscomb [1964]). We use methods for variable N , however, to observe the errors directly as N increases. Another sequence, proposed by Faure [1982], has demonstrated smaller errors for the same number of observations (Fox [1986]) with the same asymptotic error rate as in (10) but with generally additional computation time. In our computational comparison, we use this sequence as well. We also include a sequence due to Sobol [1967] (see also Antonov and Saleev [1979]) with the same asymptotic rate and di?erent practical computational characteristics. The Hammersley points have found further justi?cation in a construction by Wo? zniakowski [1991]. He shows that shifting the Hammersley points leads to a sequence of points that achieves the best average case error for numerical integration over continuous real functions on the unit hypercube equipped with the Wiener sheet measure (the mean over all functions at any point is zero and the covariance between values at two points is the product of minimum coordinate values of the points). Wo? zniakowski shows that to achieve an error of requires, on average for functions in this class, O((log )?(
?2
n ?1 2 )

?1

)

function evaluations. This contrasts with Monte Carlo’s requiring O( grid points which require O(
?n

) observations and

) evaluations.

The average case asymptotic advantage over Monte Carlo and any grid point scheme has generated much speculation about the potential improvements in integration over Monte Carlo methods. The average case result would not extend directly to the simple option example we consider here but, for path determined derivatives (e.g, options on weighted average values of securities over a ?xed time horizon or CMOs (see Paskov and Traub [1995] for an implementation)), the class of functions may ?t quite closely (each component in determining the price over time is a Wiener process). This theoretical basis 8

remains of interest, but the results are only for average cases and, again, asymptotic constants may be large. Our goal in the next section is to show that the error of quasi-Monte Carlo may indeed be much better than these analytical results for functions that arise in option pricing. 4. Empirical Observations The results in Section 3 provide some motivation for the use of quasi-random points over pseudo-random points in evaluating integrals such as the option price in (3). A dif?culty in using the analytical results with this model is, however, the estimation of the constants in the error analyses. Indeed, the function with the inverse normal integrand is not even of bounded variation. Nevertheless, the low discrepancy of the points in {αk } and {φk } leads to low errors in calculating these integrals. All computer runs in this section were performed using the FORTRAN compiler on an IBM RS6000 workstation at the University of Michigan. For a pseudo-random number generator, we used the portable FORTRAN generator by Schrage [1979] because of its general acceptance (see, e.g., Law and Kelton [1991]), ease of use, and e?ciency. For the option pricing model, we tested ten, thirty, and one hundred eighty period models. We used identical distributions in each period to make the analytical calculations easier. The initial price (St ) and strike price (K ) were ?rst both set to 40 and then K was varied to 35 and 45. The annual riskfree interest rate was r = 0.1 with annual volatilities of σ = 0.1, 0.3 and 0.6. The three horizons, T ? t = 10, T ? t = 30 and T ? t = 180 days, were chosen to give some indication of changes from relatively low to high dimensions. The analytical values from (7) range from Ct (T ? t = 10, σ = 0.1) = 0.322 to Ct (T ? t = 180, σ = 0.6) = 7.52. Figures 1-13 give indications of the relative accuracy merit of each sequence scheme. We then discuss the computational burden of each method and its relevance in practice. Figures 1 to 3 give the relative error in percentage for the ten, thirty, and one hundred eighty period models, St = K = 40, and σ = 0.3 for each of the pseudo-random sequence (pseudo), the sequence using prime roots (alpha, {αk }) plus the Halton, Faure and Sobol sequences, as the number of samples, N , increases. In Figure 1 (T ? t=10), Sobol has consistently the lowest error until Faure reaches the same level at around 28,000 iterations. The alpha sequence error is also below 0.5% after 5,000 iterations. Halton shows steady 9

improvement, but pseudo displays signi?cant oscillation. In Figure 2, alpha performs best up to 28,500 iterations, where Faure then becomes consistently the most accurate. Sobol’s error is quite low but shows some oscillation. Halton is again consistent but not very accurate, while pseudo su?ers once more from oscillation particularly at low iteration numbers. In Figure 3, Halton and Faure are not present because their errors never reached 2% or less. The alpha sequence generally has the lowest errors. The pseudo sequence has signi?cant oscillation while Sobol has less pronounced oscillation. Some general observations are that the alpha and Sobol sequences achieve relatively low errors quite quickly. The pseudo-random sequence shows signi?cant oscillation in errors. The Halton and Faure sequences are the most consistent in error improvement but they are not competitive in the higher dimensions in these trials. Figures 4 and 5 give the option values obtained for T ? t = 180, σ = 0.3 under each sequence to illustrate the performance of Halton and Faure. Note that the values from these sequences are converging at relatively slow rates from values far from the actual. Figure 5 shows that pseudo and Sobol are biased somewhat above the true value while alpha obtains values below the true value. (This tendency is not, however, uniformly true but does indicate that other variance reduction techniques, such as antithetic variates, may be useful.) The e?ect of varying volatilities is explored in Figures 6 (σ = 0.1) and 7 (σ = 0.6) for T ? t = 180. In general, the results here are quite similar to those for σ = 0.3 except that errors are higher for greater volatilities. Again, Halton and Faure never achieve low errors in 100,000 iterations, pseudo has signi?cant oscillations, and alpha produces slightly more consistent values than Sobol. Figures 8 and 9 demonstrate the e?ect of varying the strike price at out-of-the-money or in-the-money values with K = 35 and K = 45. The results are again quite similar to the previous examples for T ? t = 180. The Sobol sequence, however, appears slightly more consistent than alpha for K = 45 and greater than 70,000 iterations. The advantage of the quasi-Monte Carlo procedures depends on terminating a simulation with an accurate result earlier than the pseudo-Monte Carlo method. The pseudoMonte Carlo method’s bene?t depends on the extent to which one can apply the con?dence 10

interval as in (2) to set a priori run lengths for given desired errors. As we saw above, it is not clear how (2) is interpreted with this deterministic sequence. In our case, (2) is often violated for the sample chosen. The meaning of the α-level con?dence is not clear with the ?xed sequence. The use of sample variances may also lead to signi?cant errors when variances are large but not well detected in the standard Monte Carlo scheme (see, e.g., Fox [1986])). We consider various measure of termination e?ciency in Figures 10-13. These results give the ratio of the stopping times from the quasi-Monte Carlo procedures to the time for pseudo. Each trial’s result (given as T ? t, σ , K (if not 40)) is displayed. Figure 10 shows this result for one alternative, suggested in Fox [1986], to compare values at 2N with values at N observations and to stop if these values are within some relative tolerance (0.5% in Figure 10) of each other. Note that alpha terminates within half the time of pseudo in all but the 180, 0.6 case. Sobol has somewhat less consistency but terminates earlier than pseudo in all but the K = 45 case. Halton terminates earlier than pseudo for T ? t = 10 and T ? t = 30 but has di?culties for T ? t = 180 as mentioned above. Faure also has di?culties for T ? t = 30 in addition to the 180-day trials in this test. Another approach, similar to statistical tests based on mean and range, is to consider the range of observations over some interval compared to the overall mean value. We consider this measure for an interval of 5000 observations and an error of 0.5% in Figure 11. In this test, alpha and Sobol consistently require fewer observations than pseudo with alpha approaching termination as much as ten times faster than pseudo. Halton and Faure again terminate earlier than pseudo for ten and thirty days but not for 180-day models. To consider other stopping conditions, we consider the last iteration with errors above some tolerance in Figure 12 for an error of 1% and Figure 13 for an error of 0.5%. For the 1% error, alpha achieves this result at least twice as fast as pseudo in every case and is ten times faster in several cases. Sobol terminates in this approach faster than pseudo in each case and is almost 50 times faster in the ten-day models. Halton and Faure again have di?culties for the higher dimensions. For the 0.5% error in Figure 13, alpha again achieves earlier termination than pseudo but is not as consistent as with the larger error. Sobol is, however, more consistent in improvements relative to pseudo in this case. The results for Halton and Faure are as in the other tests. 11

A possible advantage of the pseudo-random scheme is in e?ciency of calculation time. In general, we would anticipate the use of these techniques only in problems which are too complicated for analytical solutions and, in which, each function evaluation is much more costly than the random number generation time. For this simple example, function evaluation was quite fast so the times vary slightly. The results for ratios of sequence generation times to the pseudo generation times appear in Table 1 below.

Method Alpha Halton F aure Sobol

Ratio to Pseudo 1. 2 2. 5 5 ? 10 9 ? 10

Table 1. Ratio of computation times over all trials to pseudo-random generation times. Our results are consistent with Fox [1986] and Bratley and Fox [1988]. In general, they report Halton times approximately twice their pseudo times and Faure and Sobol times approximately 5-6 times the values for pseudo. Bratley and Fox [1988], however, report much improved (by an order of magnitude) timings for Sobol with a nonstandard XOR operator in the compiler. Since many derivative evaluations would generally require much greater computation times than number generation times, the results in Table 1 have less relevance. Overall, the results here indicate that the alpha sequence may have the most consistency for 1% accuracy. Sobol may have greater consistency for smaller error values, but this accuracy should be weighed against computation time. Faure in these trials is quite accurate in low dimensions but not e?ective in higher dimensions. Halton does not appear as e?ective as the other methods. These results are consistent with Paskov [1994] and Paskov and Traub [1995] who applied the Sobol and Halton sequences to CMO evaluations. In their studies, Sobol achieves greater accuracy than pseudo-random schemes as well as the Halton sequence.

5. Conclusions We have presented quasi-Monte Carlo approaches to option pricing. We demonstrated some of their analytical advantages over the use of pseudo-random streams in standard 12

Monte Carlo. We also gave some empirical evidence that quasi-random streams can produce more accurate results in fewer iterations than standard Monte Carlo. Quasi-Monte Carlo also o?ers the advantage of less ?uctuation than standard Monte Carlo and makes on-line error approximations possible. The analyses in this paper concentrated on crude pseudo-Monte Carlo and quasi-Monte Carlo schemes. In practice, variance reduction techniques are used to lower the error in either crude scheme. Additional variance reduction techniques should have roughly equivalent e?ects on pseudo- or quasi-Monte Carlo approaches (see, for example, Fox [1986]). In the quasi-Monte Carlo case, however, the reduction in error is caused by reducing discrepancy rather than variance. These results show that quasi-Monte Carlo may have an advantage in a simple model where analytical results are available. The advantage may be even greater in more complex models (such as the CMO evaluations in Paskov and Traub [1995]) which require substantial computation for each function evaluation. They may also be applicable to evaluating pathbased options due to their excellent average case behavior which is an order of magnitude better than standard Monte Carlo.

13

References Antoneev, I.A. and V.M. Saleev. “An economic method ofc computing LPτ -

sequences.” USSR Computational Mathematics and Mathematical Physics, 19 (1979), 252-256. Black, F., and M. Scholes. “The pricing of options and corporate liabilities.” Journal of Political Economics, 81 (1973), 637-659. Boyle, P. “Options: A Monte Carlo approach.” Journal of Finance, 32 (1977), 323-338. Bratley, P., and B.L. Fox. “Algorithm 659, Implementing Sobol’s quasirandom sequence generator.” ACM Transactions on Mathematical Software, 14 (1988), 88100. Cox, J., and S. Ross. “The valuation of options for altenative stochastic processes.” Journal of Financial Economics, 3 (1976), 145-166. I. De? ak. Random Number Generators and Simulation, Akad? emiai Kiad? o, Budapest (1990). Faure, H. “Discr? epance de suites associ? ees ` a un syst` eme de num? eration (en dimension s).” Acta Arithmetica, XLI (1982), 337-351. Feller, W. An Introduction to Probability Theory and Its Applications, Volume II, New York:Wiley (1971). Fox, B. L. “Implementation and relative e?ciency of quasirandom sequence generators.” ACM Trans. Math. Software, 12 (1986), 362-376. Guterl, F. “Suddenly, number theory makes sense to industry.” Business Week, June 20 (1994), 172-174. Halton, J. H. “On the e?ciency of certain quasi-random sequences of points in evaluating multi-dimensional integrals. ” Numer. Math. , 2 (1960), 84-90. Hammersley, J. M., and D.C. Handscomb. Monte Carlo Methods, London:Methuen (1964). Jarrow, R. A., and A. Rudd. Option Pricing, Homewood, Illinois: Irwin (1983). Law, A. M., and W. D. Kelton. Simulation Modeling and Analysis, New York:McGrayHill (1991). 14

Niederreiter, H. “Quasi-Monte Carlo methods and pseudorandom numbers.” Bull. Amer. Math. Soc., 84 (1978), 957-1041. Niederreiter, H. “Recent trends in random number and random vector generation.” Annals of Operations Research, 30 (1991), 323-346. Paskov, S.H. “New methodologies for valuing derivatives.” Technical Report, Department of Computer Science, Columbia University, New York (October 1994). Paskov, S.H., and J. Traub, “Faster valuation of ?nancial derivatives.” Technical Report, Department of Computer Science, Columbia University, New York (January 1995). Schrage, L. “A more portable random number generator.” ACM Trans. Math. Software, 5 (1979), 132-138. Sobol, I.M. “On the distribution of points in a cube and the approximate evaluation of integrals.”USSR Computational Mathematics and Mathematical Physics, 7 (1967), 236-242. Wo? zniakowski, H. “Average-case complexity of multivariate integration.” Bull. Amer. Math. Soc. (new series), 24 (1991), 185-194. Yam, P. “Math Exorcise.” Scienti?c American, July 1991, 29. Zaremba, S.K. “The mathematical basis of Monte Carlo and quasi-Monte Carlo methods.” SIAM review, 10 (1968), 303-314.

15

Quasi-Monte Carlo methods for Choquet.pdf
d To find a suitable quasi-Monte Carlo method for (1), let {ui }n ...(f ) steadily approaches to a true value as n increases, whereas the ...
vray 中英文对照.doc
(倍增)1 Quasi Monte-Carlo(准蒙特卡罗算法) ■▲ Secondary Engine(二次反弹)...(法线极限值) 0.1 Distance Threshold(距离极限值)0.1 Basic Options(基本...

...of Monte Carloquasi-Monte Carlo methods in Option pricing_....pdf
Applications of Monte Carloquasi-Monte Carlo methods in Option pricing_专业...1. A European call option is a contract such that the owner may (...
Modified Monte Carlo methods using quasi-random sequences_....pdf
1 Introduction Quasi-random sequences are a deterministic alternative to random or pseudo-random sequences for use in Monte Carlo methods. Whereas Monte ...
A Parallel Quasi-Monte Carlo Method for Solving Systems of ....pdf
anet 1 2 Abstract. This paper presents a parallel quasi-Monte Carlo method for solving general sparse systems of linear algebraic equations. In our ...
Asynchronous Quasi-Monte Carlo Methods.pdf
2 Quasi-Monte Carlo methods We consider the problem of approximating a multivariate integral of the form I (f ) = Z D f (x)dx; (1) over the n...
A Hybrid Quasi Monte Carlo Method for Estimating the ....pdf
Network Reliability, Multi-state System (MSS), Multistate-node Acyclic Network (MNAN), Hybrid Quasi Monte Carlo Method, Minimal Tree/Cut 1. INTRODUCTION...
Distributed Quasi-Monte Carlo Methods in a Heterogeneous ....pdf
With this option on, the controller would begin to calculate a ij value ...References [1] R. Ca?isch and W. Morokoff. Quasi-Monte Carlo ...
The Study of Quasi Monte Carlo in the Parallel Computation of....pdf
When n approaches infinity, the following frequency is called the time mean...(1) A (2) (3) B As described in [3], the quasi Monte Carlo is ...
AVERAGE PERFORMANCE OF QUASI MONTE CARLO METHODS FOR GLOBAL ....pdf
AVERAGE PERFORMANCE OF QUASI MONTE CARLO METHODS FOR GLOBAL OPTIMIZATION_专业资料。In this paper we compare the average performance of one class of low-...
A Quasi-Monte Carlo Method for Integration with Improved ....pdf
Quasi-Monte Carlo methods often include standard approaches of variance ...Partition [0,1] into N subintervals: x0 = 0; xN = 1; Di ≡ [xi...

Quasi-Monte Carlo methods in computer graphics, Part I The ....pdf
Quasi-Monte Carlo methods in computer graphics, ...We shall discuss low discrepancy approaches to ...integral of f by Z B f (x) dx X 1 N ?...
Quasi-Monte Carlo methods in computer graphics, Part I The ....pdf
can neither predict, nor compare the e ciency of both approaches so far....First, we 0 1 1 =0 0 3 QUASI-MONTE CARLO INTEGRATION de ne as the ...
LOW-DISCREPANCY SEQUENCES, MULTI DIMENSIONAL INTEGRATION_图文....pdf
apply quasi Monte Carlo methods (QMC) to the basket option pricing problem...if Figure 1: Convergence rate for conventional Monte Carlo and quasi-Monte ...
MonteCarlo_Simulations_english.ppt
? At time T1, one can exercise a put or ...? Demonstration Vanilla option pricing using ...Quasi-Monte Carlo Simulation ? http://www.puc-...
...quasi-geostrophic model using Monte Carlo met.pdf
3页 1下载券 Sequent...quasi-geostrophic model using Monte Carlo methods ...equation and proposed a few approaches for ...
Monte Carlo Extension of Quasi-Monte Carlo.pdf
Monte Carlo Extension of Quasi-Monte Carlo_专业...16x x 1 2 1 2 2 1 2 2.3 E ective ...option pricing, in Monte Carlo and quasi-Monte ...
Quasi-Monte Carlo Integration.pdf
1 integration error from Quasi-Monte Carlo is only slightly larger than 1=2 in high dimensions. 1 Introduction Monte Carlo methods use independent, ...