Practical Applications of Randomness
at Hiroshima University, 2007 March 26
| Date: | 2007 March 26 (Mon.) |
| Place: | Hiroshima University, Faculty of Science Building B, B707 |
| 1-3-1, Kagamiyama, Higashi Hiroshima, JAPAN | |
Pierre L'Ecuyer 教授
（Departement d'Informatique et de Recherche Operationnelle, Universite de Montreal, Montreal, CANADA)
Quasi-Monte Carlo (QMC) methods are numerical techniques for
estimating large-dimensional integrals, usually over the unit
hypercube. They can be applied, at least in principle, to any
stochastic simulation whose aim is to estimate a mathematical
expectation. This covers a wide range of applications. Practical
error bounds are hard to obtain with QMC but randomized quasi-
Monte Carlo (RQMC) permits one to compute an unbiased estimator
of the integral, together with a confidence interval. RQMC can
in fact be viewed as a variance-reduction technique.
In this talk, we review some key ideas of RQMC methods and provide concrete examples of their application to simulate systems modeled as Markov chains. We also present a new RQMC method, called array-RQMC, recently introduced to simulate Markov chains over a large number of steps. The array-RQMC method is joint work with Christian Universite de Savoie) and Bruno Tuffin (IRISA).
伏見正則 教授 （南山大学数理情報学部）
Parallel computations are often used for large scale Monte Carlo simulations, in which we want to have independent (or at least uncorrelated) streams of (pseudo-)random numbers. Several algorithms for generating independent streams of random numbers have been proposed so far. We briefly review some of them in the first part of this talk.
Independent streams of random numbers are also necessary to test VLSI chips for malfunctions. Since the number of gates of a VLSI chip is more than a million, it is impossible to test a chip by exhaustively checking all the states that the chip can assume, and some mechanism of random sampling of the states is necessary. It is natural to include a testing mechanism into a chip to shorten the time required for test procedures. When we include a random number generator into a VLSI chip, it is desirable to make the area that the generator assumes as compact as possible. Cellular automata are preferable to linear feedback shift registers in this respect. We discuss a method of designing good celullar automata for generating independent substreams of pseudo-random test patterns. Some computational results will be reported.
共催：
日本オペレーションズ・リサーチ学会中国・四国支部
The Operations Research Society of Japan - Chugoku-Shikoku Chapter
広島大学ミニワークショップ実行委員会
Hiroshima University Mini Workshop Comittee (Hiroshima Univ.- Dept. of Math: Makoto Matsumoto)
（広島大学大学院理学研究科 松本 眞）
協賛：
JSPS (Japan Society for Promotion of Science)
Core-to-Core Program 18005; Grant-in-Aid for Scientific Research 18654021