Performance Analysis of the Interval Algorithm for Random Number Generation Based on Number Systems
In this paper we analyze the interval algorithm for random number generation proposed by Han and Hoshi using the expression of real numbers on the interval [0, 1). We first establish an explicit representation of the interval algorithm with the representation of real numbers on the interval [0, 1) based on number systems. Next, using the expression of the interval algorithm, we give a rigorous analysis of the interval algorithm. We discuss the difference between the expected number of the coin tosses in the interval algorithm and their upper bound derived by Han and Hoshi and show that it can be characterized explicitly with the established expression of the interval algorithm.
performance analysis interval algorithm random number generation number systems generating tree