4 Presentations

• 
  10:45 AM - 11:10 AM

  Array-RQMC for option pricing under stochastic volatility models

  • Amal Ben Abdellah, presenter, Diro, Université de Montréal, Canada
  • Pierre L'Ecuyer, Diro, Université de Montréal, Canada
  • Florian Puchhammer, Diro, Université de Montréal, Canada

  Problems from mathematical finance often consist in evaluating the expected value of some payoff function depending on quantities, such as stock prices, which satisfy stochastic differential equations driven by an underlying Brownian motion. The expectation can be expressed as a high-dimensional integral, with the dimension being the product of the number of Brownian motions and the number of time steps in the discretization.
  In this talk, we explore a different approach for RQMC simulation of Markov chains on a large number of steps, called Array-RQMC, which can help to improve the convergence rate, and significantly reduce the variance for a given computation budget. This method simulates $ n $ copies of the chain in parallel using a set of randomized RQMC point independently at each step, and sorts these copies using a specific sorting function after each step. We illustrate the large efficiency improvements on numerical examples for pricing option under a variance gamma process, and with Heston and Ornstein volatility model.
• 
  11:10 AM - 11:35 AM

  Variance reduction for chemical reaction networks with Array-RQMC

  • Florian Puchhammer, presenter, Diro, Université de Montréal, Canada
  • Amal Ben Abdellah, Diro, Université de Montréal, Canada
  • Pierre L'Ecuyer, Université de Montréal

  Mathematical processes in molecular biology frequently rely on path simulation algorithms for discrete time Markov chains. For instance, the fixed step tau-leap method by Gillespie (2001), a modification of the Stochastic Simulation Algorithm or Gillespie Algorithm, can be used to study well-mixed chemically reacting systems. For the simulation of the sample paths, crude Monte Carlo (MC) is commonly seen as a viable approach, however, one might expect a smaller variance for more refined techniques. Very recently in 2018, Beentjes and Baker used randomized quasi-Monte Carlo (RQMC) for simulating chemical reaction networks with tau-leaping but the gain in terms of variance was limited. We examine the application of a different path simulation algorithm, Array-RQMC, to this problem, which has already proven to significantly outperform MC in many other applications. In the Array-RQMC algorithm, many chains are efficiently simulated in parallel, however, the states need to be sorted after each step. Even though standard sorting procedures exist, they sometimes lack efficiency when the states are high-dimensional. In this talk we show empirically that combining Array-RQMC with tau-leaping for well-mixed chemical reaction networks can lead to a significantly faster convergence of the variance than MC. Moreover, we demonstrate that sorting with respect to a specific importance function of the states, which assigns to each state a real value, can outperform standard sorting procedures in this setting in terms of both efficiency and variance.

  Keywords: chemical reaction networks, Array-RQMC, quasi-Monte Carlo, Markov chains
• 
  11:35 AM - 12:00 PM

  Problem-driven scenario generation in multistage stochastic optimization

  • Julien Keutchayan, presenter, Polytechnique Montréal
  • Michel Gendreau, Polytechnique Montréal
  • Fabian Bastin, Université de Montréal

  Multistage stochastic programming problems are characterized by a stochastic process (modeling the random parameters), an objective function (modeling the expected costs or rewards accumulated through time), and some feasible sets (constraining the decision variables). Due to their high complexity, they generally require an approximation step, done through scenario generation, that reduces their large dimension to a manageable size. Unlike most scenario generation methods, which focus exclusively on approximating the stochastic process, problem-driven ones aim at approximating the problem as a whole, i.e., by considering relevant features of the objective function and the constraints as well. In this presentation, we will develop a new problem-driven approach that extends the concept of worst-case error (initially developed for numerical integration methods like quasi-Monte Carlo) to a multistage stochastic programming setting. This leads to a new multistage measure, called the "figure of demerit", which can be used to generate scenario approximations better suited to problems, as the numerical experiments will demonstrate.
• 
  12:00 PM - 12:25 PM

  Monte Carlo and randomized Quasi-Monte Carlo density estimation by conditioning

  • Pierre L'Ecuyer, presenter, Université de Montréal
  • Florian Puchhammer, Diro, Université de Montréal, Canada
  • Amal Ben Abdellah, Université de Montréal, Canada

  We are interested in estimating the density of a random variable $X$ that can be sampled exactly by Monte Carlo (MC) simulation. The most standard approaches for this use either a histogram or a kernel density estimator. They give convergence rates for the mean integrated square error (MISE) that are slower than O(1/n), in terms of the same size n. We propose an approach that constructs a smooth estimator of the cumulative distribution function (cdf) and takes its sample derivative to estimate the density. One way to achieve the smoothing is via conditional Monte Carlo. We provide conditions under which the resulting density estimator is unbiased and the MISE converges as O(1/n). Moreover, combining this estimator with randomized quasi-Monte Carlo brings a much larger gain than for the standard density estimators, and makes the MISE convergence rate even faster than O(1/n).

  Keywords: simulation, density estimation, quasi-Monte Carlo