Performance Analysis of the Interval Algorithm for Random Number Generation Based on Number Systems

Author

Oohama, Yasutada

Author_Institution

Dept. of Inf. Sci. & Intell. Syst., Univ. of Tokushima, Tokushima, Japan

Volume

57

Issue

3

fYear

2011

fDate

3/1/2011 12:00:00 AM

Firstpage

1177

Lastpage

1185

Abstract

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 . We first establish an explicit representation of the interval algorithm with the representation of real numbers on the interval 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.

Keywords

information theory; number theory; random number generation; random sequences; explicit representation; interval algorithm; number systems; random number generation; rigorous analysis; Algorithm design and analysis; Encoding; Performance analysis; Random number generation; Random sequences; Random variables; Generating tree; interval algorithm; number systems; performance analysis; random number generation;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2010.2103730

Filename

5714259