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

Figures & data

Figure 1. Distribution of orthogonal multiplicities $M\left(p\right)$ for all monic irreducible polynomials $p\left(x\right)\in {\mathbb{F}}_b\left[x\right]$ with $\mathrm{deg}\left(p\right(x\left)\right)=m$.

Figure 2. Initial part of the tree of Fibonacci polynomials over ${\mathbb{F}}_3$.

Table 1. Number of pairs of polynomials $\left(p\right(x),q(x\left)\right)$ that attain maximal-period Tausworthe generators with t-value zero for dimension $s=3$.

Number of Tausworthe generators over ${\mathbb{F}}_3$ with t-value zero.
m	2	3	4	5	6	7	8	9	10	11	12	13
Num.	8	6	0	0	8	6	0	0	0	0	0	0
Number of Tausworthe generators over ${\mathbb{F}}_4$ with t-value zero.
m	2	3	4	5	6	7	8	9	10	11
Num.	32	72	128	1296	2016	7648	4640	5328	4176	4560
Number of Tausworthe generators over ${\mathbb{F}}_5$ with t-value zero.
m	2	3	4	5	6	7	8
Num.	32	480	1056	16,800	38,720	514,640	706,496

Table 2. Specific parameters of pairs of polynomials $\left(p\right(x),q(x\left)\right)$ over ${\mathbb{F}}_4$ and step sizes σ.

m = 2	${\alpha }^{2}11$
	$\alpha 1$  ($\sigma =8$)
m = 3	${\alpha }^2{\alpha }^2{\alpha }^{2}1$
	$1\alpha {\alpha }^2$  ($\sigma =47$)
m = 4	${\alpha }^2{\alpha }^2{\alpha }^{2}01$
	${\alpha }^{2}11{\alpha }^2$  ($\sigma =131$)
m = 5	${\alpha }^2{\alpha }^2\alpha 101$
	$\alpha {\alpha }^2{\alpha }^2{\alpha }^2{\alpha }^2$  ($\sigma =724$)
m = 6	${\alpha }^{2}101101$
	$11{\alpha }^2{\alpha }^{2}1\alpha$  ($\sigma =2267$)
m = 7	$\alpha {\alpha }^{2}0\alpha {\alpha }^2\alpha \alpha 1$
	$00{\alpha }^2{\alpha }^2\alpha {\alpha }^{2}1$  ($\sigma =1633$)
m = 8	$\alpha {\alpha }^{2}110\alpha 001$
	$111100\alpha {\alpha }^2$  ($\sigma =16423$)
m = 9	${\alpha }^2{\alpha }^2\alpha 01\alpha \alpha 101$
	$\alpha 11{\alpha }^2{\alpha }^2{\alpha }^2\alpha 01$  ($\sigma =36887$)
m = 10	$\alpha {\alpha }^2\alpha 01{\alpha }^{2}00{\alpha }^{2}01$
	${\alpha }^{2}00\alpha 101111$  ($\sigma =1030108$)
m = 11	${\alpha }^2$  α  1  ${\alpha }^2$  α  ${\alpha }^2$  1  ${\alpha }^2$  ${\alpha }^2$  1  α  1
	${\alpha }^2$  α  ${\alpha }^2$  α  α  ${\alpha }^2$  1  ${\alpha }^2$  1  1  α  ($\sigma =3144209$)

Table 3. The t-values for good Tausworthe generators over ${\mathbb{F}}_4$.

$m\mathrm{\setminus s}$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
2	0	0	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
3	0	0	0	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1	1
4	0	0	0	1	1	1	1	2	2	2	2	2	2	2	2	2	2	2	2	2
5	0	0	0	1	1	2	2	2	2	2	2	2	2	2	2	2	2	2	2	2
6	0	0	0	1	2	2	2	2	3	3	3	3	3	3	3	3	3	3	3	3
7	0	0	0	1	2	2	2	3	3	3	3	3	3	4	4	4	4	4	4	4
8	0	0	0	1	2	4	4	4	4	4	4	4	4	4	4	4	4	4	4	4
9	0	0	0	1	3	3	3	3	3	4	4	4	4	4	4	5	5	5	5	5
10	0	0	0	2	2	3	3	3	4	4	4	5	5	6	6	6	6	6	6	6
11	0	0	0	2	3	3	3	4	5	5	5	5	5	5	5	5	5	6	6	6

Figure 3. RMSEs for $E\left[X_1\right]$, $E\left[X_2\right]$, and $E\left[X_3\right]$ with true value 0.

Figure 4. RMSEs for $E\left[X_1{X}_2\right]$, $E\left[X_1{X}_3\right]$, and $E\left[X_2{X}_3\right]$ with true values 0.3, −0.2, and 0.5.

Figure 5. RMSEs for $E\left[X_1{X}_2{X}_3\right]$ with true value 0.

Figure 6. RMSEs for the average waiting time of the M/M/1 queuing model.

Figure 7. Histograms of ${\text{β}}_0$ and ${\text{β}}_8$ using $2^{14}$ IID uniform random points and QMC points generated by our new generator over ${\mathbb{F}}_4$.

Table 4. Variances of posterior mean estimates for $\text{β}=({\text{β}}_0,\dots ,{\text{β}}_{13}{)}^{\mathrm{\top }}$ and ${\tau }^2$.

$N=2^{12}$
Parameter	${\text{β}}_0$	${\text{β}}_1$	${\text{β}}_2$	${\text{β}}_3$	${\text{β}}_4$	${\text{β}}_5$	${\text{β}}_6$
IID	6.51e−06	3.56e−10	6.31e−11	1.26e−09	2.53e−07	3.28e−06	3.79e−10
Chen	1.15e−09	6.29e−14	1.03e−14	2.52e−13	4.55e−11	5.38e−10	8.95e−14
Harase	2.98e−10	1.41e−14	2.77e−15	5.60e−14	1.18e−11	1.27e−10	1.72e−14
New	5.35e−10	3.59e−14	5.40e−15	1.40e−13	2.99e−11	3.85e−10	7.83e−14
Parameter	${\text{β}}_7$	${\text{β}}_8$	${\text{β}}_9$	${\text{β}}_{10}$	${\text{β}}_{11}$	${\text{β}}_{12}$	${\text{β}}_{13}$	${\tau }^2$
IID	7.17e−11	2.92e−07	9.45e−08	3.60e−12	5.69e−09	3.07e−12	1.48e−07	1.22e−09
Chen	1.37e−14	5.02e−11	1.60e−11	7.22e−16	1.18e−12	4.97e−16	3.19e−11	2.59e−13
Harase	2.03e−15	1.18e−11	3.33e−12	1.59e−16	2.05e−13	1.16e−16	6.78e−12	1.27e−13
New	7.26e−15	2.89e−11	1.06e−11	4.11e−16	6.26e−13	3.09e−16	2.09e−11	1.34e−13
$N=2^{14}$
Parameter	${\text{β}}_0$	${\text{β}}_1$	${\text{β}}_2$	${\text{β}}_3$	${\text{β}}_4$	${\text{β}}_5$	${\text{β}}_6$
IID	1.34e−06	1.17e−10	1.57e−11	3.13e−10	7.18e−08	7.61e−07	1.12e−10
Chen	1.24e−10	9.66e−15	1.21e−15	3.27e−14	2.14e−11	6.62e−11	8.80e−15
Harase	2.23e−11	1.75e−15	2.40e−16	5.19e−15	1.07e−12	1.26e−11	8.91e−15
New	1.31e−11	6.83e−16	1.12e−16	4.55e−15	9.99e−13	1.09e−11	1.09e−15
Parameter	${\text{β}}_7$	${\text{β}}_8$	${\text{β}}_9$	${\text{β}}_{10}$	${\text{β}}_{11}$	${\text{β}}_{12}$	${\text{β}}_{13}$	${\tau }^2$
IID	1.83e−11	6.36e−08	2.36e−08	9.15e−13	1.66e−09	6.75e−13	4.37e−08	3.00e−10
Chen	1.46e−15	5.42e−12	1.81e−12	7.96e−17	1.29e−13	5.71e−17	3.32e−12	2.88e−14
Harase	2.46e−15	6.10e−12	2.74e−12	9.44e−17	1.27e−13	7.52e−17	4.07e−12	2.34e−14
New	1.29e−16	5.94e−13	1.69e−13	8.36e−18	1.26e−14	6.15e−18	3.43e−13	5.58e−15
$N=2^{16}$
Parameter	${\text{β}}_0$	${\text{β}}_1$	${\text{β}}_2$	${\text{β}}_3$	${\text{β}}_4$	${\text{β}}_5$	${\text{β}}_6$
IID	3.07e−07	2.74e−11	4.13e−12	8.43e−11	1.64e−08	1.72e−07	2.22e−11
Chen	9.28e−12	6.59e−16	1.07e−16	2.37e−15	4.71e−13	4.73e−12	6.69e−16
Harase	1.40e−12	9.12e−17	1.82e−17	3.55e−16	1.71e−13	7.11e−13	7.65e−17
New	1.73e−12	9.86e−17	1.71e−17	4.20e−16	7.31e−14	9.01e−13	1.24e−16
Parameter	${\text{β}}_7$	${\text{β}}_8$	${\text{β}}_9$	${\text{β}}_{10}$	${\text{β}}_{11}$	${\text{β}}_{12}$	${\text{β}}_{13}$	${\tau }^2$
IID	4.26e−12	1.54e−08	5.87e−09	2.25e−13	3.48e−10	1.89e−13	1.09e−08	7.35e−11
Chen	1.14e−16	4.70e−13	1.67e−13	6.91e−18	1.08e−14	4.52e−18	2.34e−13	2.36e−15
Harase	8.86e−18	4.47e−14	1.42e−14	1.18e−18	1.36e−15	6.42e−19	3.02e−14	9.24e−16
New	1.63e−17	7.71e−14	3.20e−14	1.36e−18	2.28e−15	1.20e−18	4.68e−14	1.00e−15
$N=2^{18}$
Parameter	${\text{β}}_0$	${\text{β}}_1$	${\text{β}}_2$	${\text{β}}_3$	${\text{β}}_4$	${\text{β}}_5$	${\text{β}}_6$
IID	9.16e−08	5.65e−12	9.53e−13	1.85e−11	4.39e−09	5.28e−08	6.81e−12
Chen	5.65e−13	3.33e−17	5.70e−18	1.36e−16	2.55e−14	2.73e−13	4.09e−17
Harase	4.62e−14	2.48e−18	4.95e−19	1.07e−17	2.44e−15	2.40e−14	4.26e−18
New	7.02e−14	5.55e−18	9.27e−19	2.10e−17	3.93e−15	4.46e−14	5.85e−18
Parameter	${\text{β}}_7$	${\text{β}}_8$	${\text{β}}_9$	${\text{β}}_{10}$	${\text{β}}_{11}$	${\text{β}}_{12}$	${\text{β}}_{13}$	${\tau }^2$
IID	9.29e−13	3.75e−09	1.48e−09	5.92e−14	9.52e−11	3.47e−14	2.59e−09	1.52e−11
Chen	6.90e−18	2.74e−14	9.00e−15	3.51e−19	5.77e−16	2.69e−19	1.56e−14	2.31e−16
Harase	6.80e−19	2.49e−15	8.37e−16	3.47e−20	5.11e−17	2.51e−20	1.48e−15	3.08e−17
New	8.56e−19	4.08e−15	1.19e−15	5.45e−20	7.38e−17	3.27e−20	1.89e−15	2.56e−17

Figure 8. Sample paths and ACFs of ${\text{β}}_0,{\text{β}}_1,{\text{β}}_2$, and ${\tau }^2$ using $2^{14}$ IID uniform random points.