Tests of randomness by the gambler's ruin algorithm

Chihurn Kim; Geon Ho Choe; Dong Han Kim

doi:10.1016/j.amc.2007.09.060

Tests of randomness by the gambler's ruin algorithm

Chihurn Kim, Geon Ho Choe, Dong Han Kim

Department of Mathematics Education

Korea Advanced Institute of Science and Technology

Research output: Contribution to journal › Article › peer-review

4 Scopus citations

Abstract

In the gambler's ruin algorithm on the cyclic group Z_n = {0, 1, ..., n - 1} we consider arrival time at 0 starting from a fixed point x ≠ 0 and use several versions of arrival time algorithm to test pseudorandom number generators. This kind of test based on the exact probability density for a random walk on a finite group is done for the first time. The test results show hidden defects in some generators such as combined multiple recursive generators and Mersenne Twister generators.

Original language	English
Pages (from-to)	195-210
Number of pages	16
Journal	Applied Mathematics and Computation
Volume	199
Issue number	1
DOIs	https://doi.org/10.1016/j.amc.2007.09.060
State	Published - 15 May 2008

Keywords

Gambler's ruin
Pseudorandom number generator
Random walk

Access to Document

10.1016/j.amc.2007.09.060

Cite this

@article{78954541641b49aaa8b4d8dacc1f7e57,

title = "Tests of randomness by the gambler's ruin algorithm",

abstract = "In the gambler's ruin algorithm on the cyclic group Zn = {0, 1, ..., n - 1} we consider arrival time at 0 starting from a fixed point x ≠ 0 and use several versions of arrival time algorithm to test pseudorandom number generators. This kind of test based on the exact probability density for a random walk on a finite group is done for the first time. The test results show hidden defects in some generators such as combined multiple recursive generators and Mersenne Twister generators.",

keywords = "Gambler's ruin, Pseudorandom number generator, Random walk",

author = "Chihurn Kim and Choe, {Geon Ho} and Kim, {Dong Han}",

year = "2008",

month = may,

day = "15",

doi = "10.1016/j.amc.2007.09.060",

language = "English",

volume = "199",

pages = "195--210",

journal = "Applied Mathematics and Computation",

issn = "0096-3003",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Tests of randomness by the gambler's ruin algorithm

AU - Kim, Chihurn

AU - Choe, Geon Ho

AU - Kim, Dong Han

PY - 2008/5/15

Y1 - 2008/5/15

N2 - In the gambler's ruin algorithm on the cyclic group Zn = {0, 1, ..., n - 1} we consider arrival time at 0 starting from a fixed point x ≠ 0 and use several versions of arrival time algorithm to test pseudorandom number generators. This kind of test based on the exact probability density for a random walk on a finite group is done for the first time. The test results show hidden defects in some generators such as combined multiple recursive generators and Mersenne Twister generators.

AB - In the gambler's ruin algorithm on the cyclic group Zn = {0, 1, ..., n - 1} we consider arrival time at 0 starting from a fixed point x ≠ 0 and use several versions of arrival time algorithm to test pseudorandom number generators. This kind of test based on the exact probability density for a random walk on a finite group is done for the first time. The test results show hidden defects in some generators such as combined multiple recursive generators and Mersenne Twister generators.

KW - Gambler's ruin

KW - Pseudorandom number generator

KW - Random walk

UR - http://www.scopus.com/inward/record.url?scp=41949097477&partnerID=8YFLogxK

U2 - 10.1016/j.amc.2007.09.060

DO - 10.1016/j.amc.2007.09.060

M3 - Article

AN - SCOPUS:41949097477

SN - 0096-3003

VL - 199

SP - 195

EP - 210

JO - Applied Mathematics and Computation

JF - Applied Mathematics and Computation

IS - 1

ER -

Tests of randomness by the gambler's ruin algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this