![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
A one-dimensional sequence is said to be completely uniformly distributed (CUD) if overlapping s-blocks
,
, are uniformly distributed for every dimension
. 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
that approximate CUD sequences by running for the entire period. In this paper, we generalize a search algorithm over
to that over arbitrary finite fields
with b elements and conduct a search for Tausworthe generators over
with t-values zero (i.e. optimal) for dimension s = 3 and small for
, especially in the case where b = 3, 4, and 5. We provide a parameter table of Tausworthe generators over
, and report a comparison between our new generators over
and existing generators over
in numerical examples using Markov chain QMC.
1. Introduction
We study the problem of calculating the expectation using Markov chain Monte Carlo (MCMC) methods for a target distribution π on a state space
and some function
, where
is a π-distributed random variable on
. We are interested in improving the accuracy by replacing IID uniform random points with quasi-Monte Carlo (QMC) points. However, traditional QMC points (e.g.Sobol', Niederreiter–Xing, Faure, and Halton) are not straightforwardly applicable. Motivated by a simulation study conducted by Liao [Citation1], Owen and Tribble [Citation2] and Chen et al. [Citation3] theoretically showed that Markov chain QMC remains consistent if the driving sequences are completely uniformly distributed (CUD). A one-dimensional sequence
is said to be CUD if overlapping s-blocks
,
, are uniformly distributed for every dimension
. Levin [Citation4] proposed some constructions of CUD sequences, but they are not suitable to implement. Thus, there remains the problem of how we implement the Markov chain QMC algorithm, in particular, how we construct suitable driving sequences in practice.
Tribble and Owen [Citation5] and Tribble [Citation6] proposed an implementation method to obtain point sets that approximate CUD sequences by using short-period linear congruential and Tausworthe generators (i.e.linear feedback shift register generators over the two-element field ) that run for the entire period. Moreover, Chen et al. [Citation7] implemented short-period Tausworthe generators in terms of the equidistribution property, which is a coarse measure of uniformity in the area of pseudorandom number generation [Citation8].
In a previous study, Harase [Citation9] implemented short-period Tausworthe generators over that approximate CUD sequences in terms of the t-value, which is a central measure in the theory of
-nets and
-sequences. The key technique was to use a polynomial analogue of Fibonacci numbers and their continued fraction expansion, which was originally proposed by Tezuka and Fushimi [Citation10]. More precisely, we can view Tausworthe generators as a polynomial analogue of Korobov lattice rules with a denominator polynomial
and a numerator polynomial
(cf. [Citation11,Citation12]), and hence, the t-value is zero (i.e. optimal) for dimension s = 2 if and only if the partial quotients in the continued fraction of
are all of degree one [Citation10,Citation13]. By enumerating such pairs of polynomials
efficiently, Harase [Citation9] conducted an exhaustive search of Tausworthe generators over
with t-values zero for s = 2 and small (but not zero) for
, and demonstrated the effectiveness in numerical examples using Gibbs sampling.
From the theoretical and practical perspective, the most interesting case is the t-value zero. However, Kajiura et al. [Citation14] proved that there exists no maximal-period Tausworthe generator over with t-value zero for s = 3. In fact, in finite fields
of prime power order
, we can find maximal-period Tausworthe generators with t-value zero for s = 3, for some combinations of b and m.
In this paper, our aim is to conduct an exhaustive search of maximal-period Tausworthe generators over with t-values zero for dimension s = 3, in addition to s = 2, especially in the case where b = 3, 4, and 5. For this purpose, we generalize the search algorithms of Tezuka and Fushimi [Citation10] and Harase [Citation9] over
to those over
. We provide a parameter table of Tausworthe generators over
with t-values zero for s = 3 and small for
to implement the Markov chain QMC algorithm. Accordingly, we report a comparison between our new Tausworthe generators over
and existing generators [Citation7,Citation9] over
in numerical examples using Markov chain QMC.
The rest of this paper is organized as follows: In Section 2, we recall the definitions of CUD sequences, Tausworthe generators, and the t-value, and recall a connection between the t-value and continued fraction expansion. In Section 3, we discuss our main results: In Section 3.1, we investigate the number of polynomials for which the partial quotients of the continued fraction expansion of
all have degree one for a given irreducible polynomial
over
. In Section 3.2, we describe a search algorithm of Tausworthe generators over
. In Section 3.3, we conduct an exhaustive search in the case where b = 3, 4, and 5, and provide tables. In Section 4, we present numerical examples, such as Gibbs sampling and a simulation of a queuing system, in which both Tausworthe generators over
and
optimized in terms of the t-value perform comparable to or better than Tausworthe generators [Citation7] optimized in terms of the equidistribution property. In Section 5, we conclude this paper.
2. Preliminaries
We refer the reader to [Citation8,Citation9,Citation11,Citation13,Citation15] for general information.
2.1. Discrepancy and completely uniformly distributed sequences
Let be an s-dimensional point set of N elements in the sense of a multiset. Let us recall the definition of discrepancy
as a measure of uniformity.
Definition 2.1
Discrepancy
For a point set , the (star) discrepancy is defined as
where the supremum is taken over all intervals J of the form
for
,
denotes the number of i with
for which
, and
denotes the volume of J.
We define the CUD property for a one-dimensional sequence in
, which is known as one of the definitions of random number sequences in [Citation16, Chapter 3.5].
Definition 2.2
CUD sequences
A one-dimensional infinite sequence
is said to be completely uniformly distributed (CUD) if overlapping s-blocks satisfy
for every dimension
; in short, the sequence of s-blocks
, is uniformly distributed in
for every dimension
.
In the study of Markov chain QMC, it is desirable that converges to zero as fast as possible if
(cf. [Citation17,Citation18]). As a necessary and sufficient condition of Definition 2.2, Chentsov [Citation19] proved the following theorem:
Theorem 2.3
[Citation19]
A one-dimensional infinite sequence
is CUD if and only if non-overlapping s-blocks satisfy
(1)
(1) for every dimension
.
We thus use a sequence in
for Markov chain QMC in this order.
2.2. Tausworthe generators over ![](//:0)
![](//:0)
Let be a finite field with b elements, where b is a prime power, and perform addition and multiplication over
. We define Tausworhe generators over
, which are usually defined over
[Citation8,Citation20–22].
Definition 2.4
Tausworthe generators over ![](//:0)
![](//:0)
Let , where
. We consider the linear recurrence over
given by
(2)
(2) whose characteristic polynomial is
. Let σ be a step size and w a digit number. We define the output
at step i as
(3)
(3) where
is a bijection with
. If
is primitive,
,
, and
, then the sequences (Equation2
(2)
(2) ) and (Equation3
(3)
(3) ) are both purely periodic with maximal period
. Throughout this paper, we assume these maximal-period conditions. We call a generator in such a class a Tausworthe generator over
(or a linear feedback shift register generator over
).
Similar to the case of , Tausworthe generators over
can be viewed as a polynomial analogue of linear congruential generators (LCGs):
where
, is a sequence of polynomials,
represent a modulus and multiplier, respectively, and the step size σ satisfies
and
. Then, the output
in (Equation3
(3)
(3) ) is expressed as
, where a map
is given by
, which transforms a formal power series in
into a b-adic expansion with w digits in
.
Moreover, similar to LCGs, Tausworthe generators have a lattice structure. Let . We consider a sequence
(4)
(4) generated by a Tausworthe generator (Equation3
(3)
(3) ) with period length N−1. We set s-dimensional overlapping points
for
, that is,
. We construct a QMC point set
(5)
(5) adding the origin
. Note that the cardinality is
. Then, a point set
in (Equation5
(5)
(5) ) can be viewed as a polynomial analogue of Korobov lattice rules:
(6)
(6) where the map
is applied component-wise and
; see [Citation11,Citation12] for details.
A pair of polynomials is a parameter set of Tausworthe generators. Thus, in accordance with Definition 2.2, we would like to find a pair of polynomials
with small discrepancy
for each
.
2.3. t-value and continued fraction expansion
A point set in (Equation5
(5)
(5) ) and (Equation6
(6)
(6) ) generated by a Tausworthe generator (Equation3
(3)
(3) ) is a digital net. Hence, we can compute the t-value, which is closely related to
for
.
Definition 2.5
![](//:0)
-nets
Let and
denote integers. A point set
of
points in
is said to be a
-net in base b if every interval of the form
in
with integers
and
and of volume
contains exactly
points from
.
For a given dimension s, the smallest value t for which is a
-net is said to be the t-value. For a
-net
in base b, we have an upper bound
, where the constant
only depends on s and b; hence a small t-value is desirable. Therefore, we adopt the t-value as a measure of uniformity instead of the direct calculation of
to obtain low-discrepancy point sets.
Furthermore, in the case s = 2, there is a connection between the t-value of a polynomial Korobov lattice rule (Equation6(6)
(6) ) and the continued fraction expansion of
. Let
be a rational function over
with
and
. Then,
has a unique regular continued fraction expansion
with a polynomial part
and partial quotients
satisfying
for
. Under this condition, we put
. We have the following theorem:
Theorem 2.6
[Citation10,Citation13]
Let with
. Let
with
. Suppose that
. Then, the two-dimensional point set
(7)
(7) is a
-net in base b with
, which is exactly the t-value. In particular,
has the t-value zero if and only if
, so
for all
and v = m.
Using the continued fraction expansion based on the above theorem, Tezuka and Fushimi [Citation10] proposed an algorithm to search for Tausworthe generators over having pairs of polynomials
with t-value zero for s = 2 and small for
. Harase [Citation9] recently indicated that their technique is applicable to QMC points that approximate CUD sequences and conducted an exhaustive search over
removing some conditions.
Remark 2.1
In previous studies, L'Ecuyer and Lemieux [Citation12,Citation23] constructed short-period Tausworthe generators for QMC numerical integration in general-purpose use. To assess the uniformity of QMC points, they took into account the quality of the projections and developed several figures of merit using the equidistribution property, which are often used for selecting pseudorandom number generators with very long period [Citation20,Citation21,Citation24]. These figures of merit are implemented in LatNet Builder [Citation25], a software tool to find good parameters, and are probably useful in our study, but they are not so closely related to the discrepancy as the t-value because the condition of the equidistribution property is sometimes weaker than that of the t-value. The CUD sequences are defined via the discrepancy
in Definition 2.1, so we adopt the t-value as a primary criterion. We also note that our study is aimed at an application to Markov chain QMC, not usual pseudorandom number generation.
3. Main results
In the theory of -nets and
-sequences, the most interesting case is the t-value zero. Kajiura et al. [Citation14] proved that there exists no maximal-period Tausworthe generator over
with t-value zero for dimension s = 3. Thus, we conduct a search of Tausworthe generators over
with t-value zero for s = 3, especially in the case where b = 3, 4, and 5.
3.1. Orthogonal multiplicity
To obtain a pair of polynomials with t-value zero for
, it is necessary to satisfy at least
in Theorem 2.6. Thus, we first investigate how many polynomials
satisfying
exist for each irreducible polynomial
. For a given irreducible
, we define the number
The number
is called the orthogonal multiplicity of
in [Citation26]. Specializing the proof for the case
, Mesirov and Sweet [Citation27] proved that every irreducible polynomial
has exactly
for
, that is, there exist only two polynomials
for which the partial quotients of
have all degree one. Moreover, such polynomials are
and its inverse element
, and hence, they yield exactly the same lattice point set
. This result asserts the existence of
with t-value zero for every irreducible polynomial
in Theorem 2.6 but also asserts that there is no degree of freedom to select such
for each
.
In fact, in the case for
, Blackburn [Citation26] indicated that the situation is different far from the case
. More precisely, the orthogonal multiplicities
are not always the same number but are often much greater than two. Figure shows some histograms of orthogonal multiplicities
for all monic irreducible polynomials
with
. No clear regularity as in
has been observed. Additionally, for arbitrary
with
, it is not even known whether there exist irreducible polynomials
with
in general (see Remark 3.1). Thus, using computer calculations, we checked the existence of
as follows:
Theorem 3.1
Let be a finite field with b elements. Every monic irreducible polynomial
with
has
, at least under the following conditions:
for b = 3;
for b = 4;
for b = 5.
Remark 3.1
Let be an irreducible polynomial over
. Assume that
, that is,
is less than the order b of
. Under this condition, Friesen [Citation28, Theorem 2] proved that every irreducible
has
, that is, every irreducible
has
provided the order b of
is sufficiently large. This result is an improvement of that in the study by Blackburn [Citation26, Theorem 2]. However, the assumption
is significantly restrictive compared with the numerical results, and there has been no progress on the study of orthogonal multiplicities
since Friesen's study. Thus, we numerically checked the existence of
only in the range required for our study.
3.2. A search algorithm using Fibonacci polynomials over ![](//:0)
![](//:0)
Tausworthe generators associated with attain the t-value zero for s = 3 only if
in Theorem 2.6. Our strategy is to choose
with t-value zero for s = 3 among pairs satisfying
. Thus, we generalize the search algorithms of Tezuka and Fushimi [Citation10] and Harase [Citation9] over
to those over arbitrary finite fields
.
Recall that Fibonacci numbers , are defined by the recurrence
, where we choose the starting values
. Then, the continued fraction expansion of the ratio of two successive Fibonacci numbers
is given by
with partial quotients that are all one. As a polynomial analogue, we consider a sequence of polynomials
, defined as
(8)
(8)
(9)
(9)
(10)
(10) where
and
so that
. Similarly, we have the continued fraction expansion
, so
holds. The polynomials
, are called Fibonacci polynomials over
(cf. [Citation29]). Figure shows an example of the initial part of a tree of Fibonacci polynomials over
. Note that there exist
different pairs
of Fibonacci polynomials over
. Among pairs
, we choose a suitable pair of
with t-values zero for s = 3 and small for
satisfying Definition 2.4.
We now generalize the algorithms [Citation9,Citation10] over to those over
. Let
denote the leading coefficient of
and
denote a given maximum dimensionality. Our algorithm proceeds as follows:
Before we begin our algorithm, we create a lookup table of primitive polynomials over in advance to avoid repeated computation in Step 3. In Step 2,
generated by (Equation8
(8)
(8) ) is not always monic over arbitrary finite fields
except for
, so it is necessary to divide
and
by the leading coefficient
. In Steps 5 and 6, we compute the t-values using Gaussian elimination [Citation30]. For some combinations of b and m,
might not exist with t-value zero for s = 3 in Step 5. In this case, we skip Steps 6–9 and terminate the algorithm.
Remark 3.2
Tezuka and Fushimi [Citation10] and Harase [Citation9] dealt with the search algorithms that are similar to Algorithm 1 but restricted to the special case . We now note that there are several differences between the cases
and
for
. With regard to Equation (Equation10
(10)
(10) ), we have only two polynomials
with degree one in the case
, that is,
or x + 1; but we have many polynomials with degree one in general cases
(e.g. see Figure ). Thus, the patterns of continued fraction expansions
drastically increase as opposite to the case
. Moreover, every polynomial over
is always monic, and hence, Step 2 in Algorithm 1 is not appeared in the existing algorithms. Once again, as mentioned in Section 3.1, there are only two polynomials
for which the partial quotients of
have all degree one over
, but many polynomials
with such property exist in the case
. Therefore, our generalization would not be straightforward and simple when we search for parameters in practice.
3.3. Specific parameters
We conduct an exhaustive search of short-period Tausworthe generators over ,
, and
using Algorithm 1. We set
. If b is a prime number (i.e, b = 3 or 5), we identify
with
and set a bijection
as the identity map. If b = 4, we set
with
and
and set a bijection
consisting of
Table summarizes the number of maximal-period Tausworthe generators with t-value zero for dimension s = 3. We observe that a very few pairs of polynomials
exist over
; however, many pairs exist over
and
, at least within the range described in the table. From the viewpoint of applications, we tabulate specific parameters of pairs of polynomials
over
and step sizes σ for
in Table . In Table , each first and second row shows the coefficients of
and
respectively; for example,
means
. Table shows the t-values in the range of
. Throughout our search, we find several parameters with the same t-values, so we choose one from them.
Table 1. Number of pairs of polynomials that attain maximal-period Tausworthe generators with t-value zero for dimension
.
Table 2. Specific parameters of pairs of polynomials over
and step sizes σ.
Table 3. The t-values for good Tausworthe generators over .
For the implementation, we introduce a reasonably fast algorithm to generate the output values (Equation3(3)
(3) ) from Tausworthe generators over
. Assume that
. Let
denote a state vector at step i (
means ‘transposed’). We can define a state-space representation
, where
(11)
(11) is a
state transition matrix in
that consists of m column vectors
and w−m zero column vectors
. We now set b = 4 and decompose
,
, into
with
since a set
is a basis of
over
. Then, we can write
, that is, a linear combination of
column vectors
,
, with coefficients in
. From this, we can calculate
by only adding vectors
if
and
if
for each j. Moreover, the elements
can be represented as column vectors
, respectively, and hence,
can be viewed as column vectors in
. Using this property, we can generate
in (Equation3
(3)
(3) ) with reasonable speed, as if we performed additions over
. The sample code is available at https://github.com/sharase/cud-f4.
Remark 3.3
Kajiura et al. [Citation14] proved that there exists no Tausworthe generator over with both maximal periodicity and t-value zero for s = 3 if
. More precisely, they proved that
-linear generators, which are a general class of linear pseudorandom number generators over
including Tausworthe generators (cf. [Citation8,Citation11]), have the t-value zero for
only if the period length is exactly three. Their proof was specialized for the case
; for example, they used the property
in [Citation14, Proof of Theorem 1], where
denotes the identity matrix of order m, and
and
denote a set of non-singular
lower-triangular and upper-triangular matrices, respectively. This is false in the fields
except for
. Indeed, Harase [Citation9] obtained Tausworthe generators over
with t-value two or three for s = 3, but they were not optimal with respect to the t-value. Thus, we conducted a search over
, whose restrictions are looser than those over
.
Remark 3.4
We consider a reason why there are a very few pairs of polynomials with the t-value zero for s = 3 over
in Table . Assume that
. Let
denote the
-transpose companion matrix of
in
given by
where blank entries in this matrix mean zeros. We set an
-matrix
. According to [Citation8, Section 5.1], we can obtain the state transition matrix
in (Equation11
(11)
(11) ) by expanding
, that is, if m = w, then we put
, and if m<w, for
, we attach
as the jth row vector, where the coefficients
are given by the relation
, and add w−m columns of the zero vector
. Thus, the t-value for dimension s is determined by the the maximum number of linear independence of leading row vectors of s generating matrices (
,
; see [Citation13, Theorem 4.28] or [Citation15, Theorem 4.52] for details. In our construction scheme, one can only change the parameter values
and σ, so that the search space is restricted.
As an alternative, we have conducted a numerical experiment for which we discard the structure of Tausworthe generators and take general -full rank matrices
, not given by
, as described in [Citation14, Equ. (4)]. (Here, we may assume without loss of generality that the row vectors
are arbitrary.) Our goal here is to find a full rank matrix
such that a digital net generated by
has the t-value zero for s = 3 and the multiplicative order of
is
. For this, we generate full rank matrices
at random and check the above conditions. In computer search, we have confirmed the existence of such
in
for
. It might be expected that the existence holds true for every m in arbitrary
except for
. However, this approach seems to be significantly inefficient and time-consuming because it is not so easy to find matrices
that generate the digital nets with the t-value zero even for s = 2 if m is large for small b. Therefore, it would be desirable to design some mathematical structure of
in advance before we conduct a search. In contrast, our algorithm always ensures the t-value zero for s = 2. In this paper, we conduct an exhaustive search, but our algorithm has the advantage that we can easily switch from an exhaustive search to a random search by generating
in (Equation10
(10)
(10) ) randomly.
4. Numerical examples
We provide numerical examples to confirm the performance of Markov chain QMC. In our examples, we estimate the expectation and compare the following driving sequences:
New: our new Tausworthe generators over
;
Harase: Tausworthe generators over
developed by Harase [Citation9];
Chen: Tausworthe generators over
developed by Chen et al. [Citation7]; and
IID: Mersenne Twister [Citation31].
We briefly explain how to use Tausworthe generators over . Recall that
and the period length is N−1. For the output values (Equation3
(3)
(3) ) generated by Tausworthe generators, if
, we simply define s-dimensional non-overlapping points starting from the origin:
(12)
(12) If
, instead of (Equation12
(12)
(12) ), we generate d distinct short loops of s-dimensional points, that is,
(13)
(13) for
, and concatenate them starting from the origin
in this order. For these points, we apply b-adic digital shifts, that is, we add
to each s-dimensional point using the digit-wise addition
(see Remark 4.1), where
are IID samples from
, that is, the continuous uniform distribution over
. We use the resulting points as input for Markov chain QMC; see Remark 4.3 and [Citation2,Citation5,Citation6,Citation32] for more details. We set w = 32 over
and w = 16 over
as a digit number in Definition 2.4.
Remark 4.1
We recall the definition of digital shifts. For and
with
, we define the b-adic digitally shifted point
as
, where
with
for infinitely many j and ‘+’ represents the addition in
. For higher dimensions s>1, let
. For
, we similarly define the b-adic digitally shifted point
as
.
4.1. Gaussian Gibbs sampling
Our first example is a systematic Gibbs sampling scheme to generate the s-dimensional multivariate Gaussian (normal) distribution for a mean vector
and covariance matrix
. This can be implemented as
(14)
(14) for
, which reduces to the iteration of the calculation of the one-dimensional normal distribution. (Here, for simplicity of notation, the indices
and
represent the kth component and the components except for the kth component, respectively; e.g.
and so on.) Thus, we apply the inverse transform method in (Equation14
(14)
(14) ). We set the parameter values s = 3 and
which were used in [Citation6, Chapter 6.1].
First, we estimate , and
with true value 0 by taking the sample mean. Figure shows a summary of the root-mean-square errors (RMSEs) in
scale for sample sizes N from
to
using 300 digital shifts. In all cases, the Tausworthe generators (labeled ‘New’ and ‘Harase’) optimized in terms of the t-value have almost the same accuracy and outperform Chen's generators.
Furthermore, we estimate the second-order moments ,
,
and the third-order moment
using 300 digital shifts, respectively. Figures and show summaries of the RMSEs. In Figure , we observe that Chen's generators are unstable and have several bumps when we estimate
.
4.2. M/M/1 queuing system
Our second example is an M/M/1 queuing model, which has the same setting as that in [Citation32, Chapter 8.3.2]. Consider a single-server queuing model, where the customers arrive as a Poisson process with intensity and the service time is exponentially distributed with intensity
. Assume that
for system stability. Let
denote the waiting time of the jth customer,
denote the service time of the jth customer, and
denote the time interval between the jth customer and the
th customer. Then, we have the Lindley recurrence:
(15)
(15)
(16)
(16) for
, where
denotes the exponential distribution. Under stationarity, the average waiting time is known as
(17)
(17) (cf. [Citation33]). We estimate the average waiting time (Equation17
(17)
(17) ) by taking the sample mean
via Equations (Equation15
(15)
(15) )–(Equation16
(16)
(16) ). Note that we need
random points
for N customers. Note also that the function
is unsmooth at 0.
We set the parameters and
. Figure shows the RMSEs for the average waiting time using 300 digital shifts. The three types of QMC points have almost the same performance, except for Chen's generator at
. The bump of Chen's generator coincides with that in [Citation32, Figure 8.2].
4.3. A linear regression model
In the third example, we consider a linear regression model
where
is the ith observation on the response variable,
is a
vector of 1 and ith observations on the k explanatory variables,
is a
vector of regression coefficients, and the error term
is IID normal with mean zero and common variance
. Let
be an
design matrix (with rank k + 1<n) and
an
vector.
We now consider Bayesian inference as follows: We assume that the parameters and
are independent and have the prior distributions
where
denotes the inverse gamma distribution with shape parameter
and rate parameter
, and
-dimensional mean vector
,
-covariance matrix
,
, and
are hyperparameters. Then, according to [Citation34,Citation35], sampling from the joint posterior distribution of
can be generated through sampling from the full conditional distributions
(18)
(18)
(19)
(19) where
Thus, we calculate
and
by taking the sample mean using the Gibbs sampler based on (Equation18
(18)
(18) ) and (Equation19
(19)
(19) ). We generate
in (Equation18
(18)
(18) ) via
for
, where
is the Cholesky decomposition and
is the cumulative distribution function of the standard normal distribution.
As a numerical example, we use the Boston housing data analysed in [Citation36]. To investigate the demand for clean air, Harrison and Rubinfeld [Citation36] built a linear regression model given by
(20)
(20) where the housing price MEDV is a response variable, and
,
,
,
,
,
,
,
,
,
,
,
, and
are 13 explanatory variables (i.e. k = 13); see [Citation36, Table IV] for more details about the variables. In our experiment, we estimate the same linear regression model as in (Equation20
(20)
(20) ). Note that the state vector
has 15 dimensions (i.e.s = 15).
We set the hyperparameter values ,
,
,
, and run the Gibbs sampler for 5000 iterations using random numbers as a burn-in period. Then, we calculate
and
by running the Gibbs sampler for
,
,
, and
iterations. Table shows a summary of sample variances of posterior mean estimates using 300 digital shifts. In both cases
and
, Tausworthe generators optimized in terms of the t-value provide comparable to or better results than Chen's Tausworthe generators optimized in terms of the equidistribution property, excluding some exceptions (e.g.
for
estimated by Tausworthe generators over
). Furthermore, we plot the histograms of
and
using
IID uniform random points and QMC points generated by our new generator over
in Figure . In the case
, the sampling using our new QMC points tends to converge to the posterior distribution faster than the sampling using IID uniform random points, but in the case
, the difference seems to be unclear. From this, the estimation of
might be more difficult than that of
when we apply QMC. Overall, our experiment implies that the t-value is a good measure of uniformity in the study of Markov chain QMC.
Figure 7. Histograms of and
using
IID uniform random points and QMC points generated by our new generator over
.
![Figure 7. Histograms of β0 and β8 using 214 IID uniform random points and QMC points generated by our new generator over F4.](/cms/asset/b96583d1-2b6f-4fad-8ffb-c7275b8e11e9/gscs_a_2312951_f0007_ob.jpg)
Table 4. Variances of posterior mean estimates for and
.
Remark 4.2
According to some heuristic arguments in [Citation6, Chapter 7.1], it is expected that Markov chain QMC drastically improves the rate of convergence when the dependence of states on the past decays quickly. To investigate such phenomena, we plot the sample paths and autocorrelation functions (ACFs) of , and
in Figure using
IID uniform random points, after a burn-in period with 5000 iterations. The ACF plots imply that the dependence of states on the past decays very quickly (i.e. at one step) and has negligible effect on the current state. Moreover, it is believed that QMC methods in high-dimensional problems are successful especially in the case where the problems are dominated by the first leading variables or well approximated by a sum of functions of at most one or two variables (cf. [Citation37]). Our linear regression example is probably included in such a class of problems, and hence, all the three Tausworthe generators drastically improve the rate of convergence. On the other hand, in more complicated applications in practice, the difference among these generators might not become clear, but we expect that Tausworthe generators optimized in terms of the t-value would be at worst superior to IID uniform random points.
Remark 4.3
The generation scheme in (Equation13(13)
(13) ) was originally used in [Citation2,Citation5]. However, if
, then we have d−1 skips in (Equation13
(13)
(13) ) through the entire period. To avoid such irregular skips, Tribble [Citation6] and Chen [Citation32] suggested a strategy in which the skips are the same between every pair of non-overlapping s-blocks: Let r be the smallest integer
such that
. Then, instead of (Equation13
(13)
(13) ), we can consider s-dimensional non-overlapping points starting from the origin:
(21)
(21) which maintain balance (i.e. every r steps) in each coordinate by discarding r−s points between each block. We also implemented the strategy (Equation21
(21)
(21) ) and conducted the same experiments as in Section 4. We obtained almost similar results with a slight fluctuation. In this paper, we optimized Tausworthe generators in terms of the t-value for consecutive output values, so we adopted the scheme (Equation13
(13)
(13) ) without discarding r−s points, which seems to be closer to the condition (Equation1
(1)
(1) ). We refer the reader to [Citation6, Chapter 5] and [Citation32, Chapter 8.2] for more details.
5. Conclusion
We attempted to search for short-period Tausworthe generators over arbitrary finite fields for Markov chain QMC in terms of the t-value. To achieve this, we generalized the search algorithms [Citation9,Citation10] over
to those over
. We conducted an exhaustive search, especially in the case where b = 3, 4, and 5, and implemented Tausworthe generators over
with t-values zero for dimension s = 3, in addition to s = 2, and small for
. We also reported numerical examples in which both Tausworthe generators over
and
optimized in terms of the t-value perform comparable to or better than Tausworthe generators [Citation7] optimized in terms of the equidistribution property.
The two-element field is the most important finite field in applications, but has some restrictions that do not occur over other fields
. Therefore, in future work, it would be interesting to study implementations of other types of QMC points over
, such as polynomial lattice rules [Citation13,Citation15,Citation30] and irreducible Sobol'–Niderreiter sequences [Citation38], which are closely related to the t-value. Furthermore, we are also planning to apply our new generators, including [Citation9], to a large variety of Bayesian computation using real-life data.
To conclude this paper, we mention some recent related works. In past a decade, the application of QMC methods to computational statistics has received a lot of attention for researchers and many novel studies have been proposed. For example, Gerber and Chopin [Citation39] present a class of algorithms where a sequential Monte Carlo strategy is implemented with QMC. Buchholz and Chopin [Citation40] derive approximate Bayesian computation (ABC) algorithms based on QMC for dealing with models with an intractable likelihood. As another direction, research on kernel density estimation using QMC has been actively conducted. We refer the reader to the survey paper [Citation41] for recent progress in this topic.
Disclosure statement
No potential conflict of interest was reported by the author(s).
Additional information
Funding
References
- Liao JG. Variance reduction in Gibbs sampler using quasi random numbers. J Comput Graphical Stat. 1998;7(3):253–266. doi: 10.1080/10618600.1998.10474775.
- Owen AB, Tribble SD. A quasi-Monte Carlo Metropolis algorithm. Proc Natl Acad Sci USA. 2005;102(25):8844–8849. doi: 10.1073/pnas.0409596102
- Chen S, Dick J, Owen AB. Consistency of Markov chain quasi-Monte Carlo on continuous state spaces. Ann Statist. 2011;39(2):673–701. doi: 10.1214/10-AOS831
- Levin MB. Discrepancy estimates of completely uniformly distributed and pseudorandom number sequences. Int Math Res Notices. 1999;1999(22):1231–1251. doi: 10.1155/S1073792899000677
- Tribble SD, Owen AB. Construction of weakly CUD sequences for MCMC sampling. Electron J Stat. 2008;2:634–660. doi: 10.1214/07-EJS162
- Tribble SD. Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences [Thesis (Ph.D.)]. Ann Arbor (MI): ProQuest LLC; Stanford University; 2007.
- Chen S, Matsumoto M, Nishimura T, et al. New inputs and methods for Markov chain quasi-Monte Carlo. In: Monte Carlo and quasi-Monte Carlo methods 2010. Berlin, Heidelberg: Springer; 2012. p. 313–327. (Springer proc. math. stat.; vol. 23).
- L'Ecuyer P, Panneton F. F2-linear random number generators. In: Alexopoulos C, Goldsman D, Wilson JR, editors. Advancing the frontiers of simulation: a festschrift in honor of george samuel fishman. New York: Springer-Verlag; 2009. p. 169–193.
- Harase S. A table of short-period Tausworthe generators for Markov chain quasi-Monte Carlo. J Comput Appl Math. 2021;384:Paper No. 113136, 12. doi: 10.1016/j.cam.2020.113136
- Tezuka S, Fushimi M. Calculation of Fibonacci polynomials for GFSR sequences with low discrepancies. Math Comp. 1993;60(202):763–770. doi: 10.1090/S0025-5718-1993-1160278-0
- Lemieux C. Monte Carlo and quasi-Monte Carlo sampling. New York (NY): Springer; 2009. (Springer series in statistics).
- Lemieux C, L'Ecuyer P. Randomized polynomial lattice rules for multivariate integration and simulation. SIAM J Sci Comput. 2003;24(5):1768–1789. doi: 10.1137/S1064827501393782
- Niederreiter H. Random number generation and quasi-Monte Carlo methods. Philadelphia (PA): Society for Industrial and Applied Mathematics (SIAM); 1992. (CBMS-NSF regional conference series in applied mathematics; Vol. 63).
- Kajiura H, Matsumoto M, Suzuki K. Characterization of matrices B such that (I,B,B2) generates a digital net with t-value zero. Finite Fields Appl. 2018;52:289–300. doi: 10.1016/j.ffa.2018.04.011
- Dick J, Pillichshammer F. Digital nets and sequences. Cambridge: Cambridge University Press; 2010. (Discrepancy theory and quasi-Monte Carlo integration).
- Knuth DE. The art of computer programming. Vol. 2. Reading (MA): Addison-Wesley; 1998. (Seminumerical algorithms 3rd ed.).
- Dick J, Rudolf D. Discrepancy estimates for variance bounding Markov chain quasi-Monte Carlo. Electron J Probab. 2014;19:no. 105, 24. doi: 10.1214/EJP.v19-3132
- Dick J, Rudolf D, Zhu H. Discrepancy bounds for uniformly ergodic Markov chain quasi-Monte Carlo. Ann Appl Probab. 2016;26(5):3178–3205. doi: 10.1214/16-AAP1173
- Chentsov N. Pseudorandom numbers for modelling Markov chains. USSR Comput Math Math Phys. 1967;7(3):218–233. doi: 10.1016/0041-5553(67)90041-9
- L'Ecuyer P. Maximally equidistributed combined Tausworthe generators. Math Comp. 1996;65(213):203–213. doi: 10.1090/S0025-5718-96-00696-5
- L'Ecuyer P. Tables of maximally-equidistributed combined LFSR generators. Math Comp. 1999;68(225):261–269. doi: 10.1090/S0025-5718-99-01039-X
- Tausworthe RC. Random numbers generated by linear recurrence modulo two. Math Comp. 1965;19:201–209. doi: 10.1090/S0025-5718-1965-0184406-1
- L'Ecuyer P, Lemieux C. Quasi-Monte Carlo via linear shift-register sequences. In: Proceedings of the 31st Conference on Winter Simulation: Simulation – a Bridge to the Future -- Volume 1; WSC '99. New York (NY), USA: Association for Computing Machinery; 1999. p. 632–639.
- L'Ecuyer P, Panneton F. Construction of equidistributed generators based on linear recurrences modulo 2. In: Fang KT, Niederreiter H, Hickernell FJ, editors. Monte Carlo and Quasi-Monte Carlo Methods 2000; Berlin, Heidelberg: Springer Berlin Heidelberg; 2002. p. 318–330.
- L'Ecuyer P, Marion P, Godin M, et al. A tool for custom construction of QMC and RQMC point sets. In: Keller A, editor. Monte Carlo and Quasi-Monte Carlo methods 2020. Cham: Springer International Publishing; 2022. p. 51–70.
- Blackburn SR. Orthogonal sequences of polynomials over arbitrary fields. J Number Theory. 1998;68(1):99–111. doi: 10.1006/jnth.1997.2201
- Mesirov JP, Sweet MM. Continued fraction expansions of rational expressions with irreducible denominators in characteristic 2. J Number Theory. 1987;27(2):144–148. doi: 10.1016/0022-314X(87)90058-8
- Friesen C. Rational functions over finite fields having continued fraction expansions with linear partial quotients. J Number Theory. 2007;126(2):185–192. doi: 10.1016/j.jnt.2006.11.009
- Hofer R. Finding both, the continued fraction and the Laurent series expansion of golden ratio analogs in the field of formal power series. J Number Theory. 2021;223:168–194. doi: 10.1016/j.jnt.2020.11.010
- Pirsic G, Schmid WC. Calculation of the quality parameter of digital nets and application to their construction. J Complexity. 2001;17(4):827–839. doi: 10.1006/jcom.2001.0597
- Matsumoto M, Nishimura T. Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans Model Comput Simul. 1998 jan;8(1):3–30. doi: 10.1145/272991.272995
- Chen S. Consistency and convergence rate of Markov chain quasi-Monte Carlo with examples [Thesis (Ph.D.)]. Stanford University; 2011.
- Nelson R. Probability, stochastic processes, and queueing theory : the mathematics of computer performance modelling. New York: Springer; 1995.
- Chib S. Chapter 57 -- Markov Chain Monte carlo methods: computation and inference. Elsevier; 2001. p. 3569–3649. (Handbook of econometrics; Vol. 5).
- Hoff PD. A first course in Bayesian statistical methods. New York (NY): Springer; 2009. (Springer texts in statistics).
- Harrison D, Rubinfeld DL. Hedonic housing prices and the demand for clean air. J Environ Econ Manage. 1978;5(1):81–102. doi: 10.1016/0095-0696(78)90006-2
- Wang X, Fang KT. The effective dimension and quasi-Monte Carlo integration. J Complexity. 2003;19(2):101–124. doi: 10.1016/S0885-064X(03)00003-7
- Faure H, Lemieux C. Implementation of irreducible Sobol' sequences in prime power bases. Math Comput Simul. 2019;161:13–22. doi: 10.1016/j.matcom.2018.08.015
- Gerber M, Chopin N. Sequential quasi Monte Carlo. J R Stat Soc Ser B Stat Methodol. 2015;77(3):509–579. doi: 10.1111/rssb.12104
- Buchholz A, Chopin N. Improving approximate Bayesian computation via quasi-Monte Carlo. J Comput Graph Statist. 2019;28(1):205–219. doi: 10.1080/10618600.2018.1497511
- L'Ecuyer P, Puchhammer F. Density estimation by Monte Carlo and quasi-Monte Carlo. In: Keller A, editor. Monte Carlo and Quasi-Monte Carlo methods 2020. Cham: Springer International Publishing; 2022. p. 3–21.