A one-dimensional sequence $u_0, u_1, u_2, \ldots \in [0, 1)$ is said to be completely uniformly distributed (CUD) if overlapping $s$-blocks $(u_i, u_{i+1}, \ldots , u_{i+s-1})$, $i = 0, 1, 2, \ldots$, are uniformly distributed for every dimension $s \geq 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 (2021) focused 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 \geq 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.
翻译:一维序列$u_0, u_1, u_2,...\in [0,1)$称为完全均匀分布(CUD)序列,如果重叠的$s$个$(u_i, u_{i+1},\ldots,u_{i+s-1})$块,在每个维度$s\geq1$上都是均匀分布的。这个概念在马尔科夫链准蒙特卡罗(QMC)中自然产生。然而,CUD序列的定义并不是构造性的,因此如何在实践中实现马尔科夫链QMC算法仍然存在问题。Harase (2021)关注了在QMC研究中广泛使用的均匀性度量$t$值,并实现了短周期Tausworthe生成器(即,线性反馈移位寄存器生成器),通过运行整个周期来近似CUD序列。在本文中,我们将搜索算法从二元域$\mathbb{F}_2$推广到任意有限域$\mathbb{F}_b$($b$个元素),并在$\mathbb{F}_b$上进行Tausworthe生成器的搜索,使得维度$s=3$时$t$值为零(即最优),当$s\geq4$时$t$值较小,特别是当$b=3,4$和$5$时。我们提供了$\mathbb{F}_4$上Tausworthe生成器的参数表,并在使用马尔科夫链QMC的数值例子中,报告了我们在$\mathbb{F}_4$上的新生成器与现有的$\mathbb{F}_2$生成器的比较结果。