Lower bounds for the discrepancy of inversive congruential pseudorandom numbers with power of two modulus

Abstract:

The inversive congruential method with modulus $m = {2^\omega }$ for the generation of uniform pseudorandom numbers has recently been introduced. The discrepancy $D_{m/2}^{(k)}$ of k-tuples of consecutive pseudorandom numbers generated by such a generator with maximal period length $m/2$ is the crucial quantity for the analysis of the statistical independence properties of these pseudorandom numbers by means of the serial test. It is proved that for a positive proportion of the inversive congruential generators with maximal period length, the discrepancy $D_{m/2}^{(k)}$ is at least of the order of magnitude ${m^{ - 1/2}}$ for all $k \geq 2$. This shows that the bound $D_{m/2}^{(2)} = O({m^{ - 1/2}}{(\log m)^2})$ established by the second author is essentially best possible.