Simulation of Markov Chains with Continuous State Space by Using Simple Stratified and Sudoku Latin Square Sampling

Rami El Haddad (), Joseph El Maalouf (), Rana Fakhereddine () and Christian Lécot ()
Additional contact information
Rami El Haddad: Laboratoire de Mathématiques et Applications, U.R. Mathématiques et modélisation, Faculté des sciences, Université Saint-Joseph
Joseph El Maalouf: American University of the Middle East, College of Engineering and Technology
Rana Fakhereddine: Laboratoire de Mathématiques et Applications, U.R. Mathématiques et modélisation, Faculté des sciences, Université Saint-Joseph
Christian Lécot: Université Savoie Mont Blanc, Laboratoire de Mathématiques, UMR 5127 CNRS

A chapter in Advances in Modeling and Simulation, 2022, pp 239-260 from Springer

Abstract: Abstract Monte Carlo (MC) is widely used for simulating discrete time Markov chains. Here, N copies of the chain are simulated in parallel, using pseudorandom numbers. We restrict ourselves to a one-dimensional continuous state space. We analyze the effect of replacing pseudorandom numbers on $$I := [0,1)$$ I : = [ 0 , 1 ) with stratified random points over $$I^2$$ I 2 : for each point, the first component is used to select a state and the second component is used to advance the chain by one step. Two stratified sampling techniques are compared: simple stratified sampling (SSS) and Sudoku Latin square sampling (SLSS). For both methods and for $$N=p^2$$ N = p 2 samples, the unit square is dissected into $$p^2$$ p 2 subsquares and there is one sample in each subsquare. For SLSS, each side of the unit square is divided into N subintervals and the projections of the samples on the side are distributed with one projection in each subinterval. Stratified strategies outperform classical MC if the N copies are reordered by increasing states at each step. We prove that the variance of SSS and SLSS estimators is bounded by $$\mathcal {O}(N^{-3/2})$$ O ( N - 3 / 2 ) , while it is bounded by $$\mathcal {O}(N^{-1})$$ O ( N - 1 ) for MC. The results of numerical experiments indicate that these upper bounds match the observed rates. They also show that SLSS gives a smaller variance than SSS.

Keywords: Monte Carlo methods; Markov chains; Simulation; Stratified sampling (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-031-10193-9_12

Ordering information: This item can be ordered from
http://www.springer.com/9783031101939

DOI: 10.1007/978-3-031-10193-9_12

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().