COMPUTING CONDITIONAL PROBABILITIES FOR F2-LINEAR PSEUDORANDOM BIT GENERATORS BY SPLITTING MACWILLIAMS IDENTITY
Hiroshi Haramoto, Makoto Matsumoto, Takuji Nishimura · 2007
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. AMS Subject Classification: 65C10, 11K45, 11T21