IJPAM: Volume 38, No. 1 (2007)

COMPUTING CONDITIONAL PROBABILITIES FOR
$\F2$-LINEAR PSEUDORANDOM BIT GENERATORS
BY SPLITTING MACWILLIAMS IDENTITY

Hiroshi Haramoto$^1$, Makoto Matsumoto$^2$, Takuji Nishimura$^3$
$^{1,2}$Department of Mathematics
Graduate School of Science
Hiroshima University
1-3-1, Kagamiyama, Higashi-Hiroshima, 739-8526, JAPAN
$^1$e-mail: haramoto@hiroshima-u.ac.jp
$^2$e-mail: m-mat@math.sci.hiroshima-u.ac.jp
$^3$Department of Mathematical sciences
Faculty of Science
Yamagata University
Kojirakawa-machi, 1-4-12, Yamagata, 990-8560, JAPAN
e-mail: nisimura@sci.kj.yamagata-u.ac.jp


Abstract.Consider the following fair gamble. Fix a positive integer $f$. The player pays 1 dollar to the dealer. The dealer tosses a coin $f$ times. If all are heads, then the player has paid $2^f$ dollars, else nothing is paid. Suppose that the coin-tossing is simulated by a pseudorandom number generator based on a sparse linear recursion, such as ran_array by Knuth. We show that a simple strategy, based only on the number of heads observed so far, leads the player to a dramatical win. On the other hand, we show that such a strategy will not succeed for some generators with denser recursion formulas. The key for these analyses is a splitting version of MacWilliams identity.

Received: April 24, 2007

AMS Subject Classification: 65C10, 11K45, 11T21

Key Words and Phrases: random number generation, test of randomness, MacWilliams identity

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2007
Volume: 38
Issue: 1