Monte Carlo and Quasi Monte Carlo Approach to Ulam's Method for Position Dependent Random Maps

Abstract

We consider position random maps $T=\{\tau_1(x),\tau_2(x),\ldots, \tau_K(x); p_1(x),p_2(x),\ldots,p_K(x)\}$ on $I=[0, 1],$ where $\tau_k, k=1, 2, \dots, K$ is non-singular map on $[0,1]$ into $[0, 1]$ and $\{p_1(x),p_2(x),\ldots,p_K(x)\}$ is a set of position dependent probabilities on $[0, 1]$. We assume that the random map $T$ posses a density function $f^*$ of the unique absolutely continuous invariant measure (acim) $\mu^*$. In this paper, first, we present a general numerical algorithm for the approximation of the density function $f^*.$ Moreover, we show that Ulam's method is a special case of the general method. Finally, we describe a Monte-Carlo and a Quasi Monte Carlo implementations of Ulam's method for the approximation of $f^*$. The main advantage of these methods is that we do not need to find the inverse images of subsets under the transformations of the random map $T$.