A search for short-period Tausworthe generators over Fb with application to Markov chain quasi-Monte Carlo

Abstract

A one-dimensional sequence $u_0,u_1,u_2,\dots \in [0,1)$ is said to be completely uniformly distributed (CUD) if overlapping s-blocks $(u_i,u_{i+1},\dots ,u_{i+s-1})$, $i=0,1,2,\dots$, are uniformly distributed for every dimension $s\ge 1$. This concept naturally arises in Markov chain quasi-Monte Carlo (QMC). However, the definition of CUD sequences is not constructive, and thus there remains the problem of how to implement the Markov chain QMC algorithm in practice. Harase [A table of short-period Tausworthe generators for Markov chain quasi-Monte Carlo. J Comput Appl Math. 2021;384:Paper No. 113136, 12.] focussed on the t-value, which is a measure of uniformity widely used in the study of QMC, and implemented short-period Tausworthe generators (i.e. linear feedback shift register generators) over the two-element field ${\mathbb{F}}_2$ that approximate CUD sequences by running for the entire period. In this paper, we generalize a search algorithm over ${\mathbb{F}}_2$ to that over arbitrary finite fields ${\mathbb{F}}_b$ with b elements and conduct a search for Tausworthe generators over ${\mathbb{F}}_b$ with t-values zero (i.e. optimal) for dimension s = 3 and small for $s\ge 4$, especially in the case where b = 3, 4, and 5. We provide a parameter table of Tausworthe generators over ${\mathbb{F}}_4$, and report a comparison between our new generators over ${\mathbb{F}}_4$ and existing generators over ${\mathbb{F}}_2$ in numerical examples using Markov chain QMC.

Keywords:

• Pseudorandom number generation
• Quasi-Monte Carlo
• Markov chain Monte Carlo
• Bayesian inference
• Linear regression

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was supported by JSPS KAKENHI Grant Numbers JP22K11945, JP18K18016.