Makoto Matsumoto

Makoto Matsumoto, Mutsuo Saito, Kyle Matoba

Let $\mathcal{P} \subset [0,1)^S$ be a finite point set of cardinality $N$ in an $S$-dimensional cube, and let $f:[0,1)^S \to \mathbb{R}$ be an integrable function. A QMC integration of $f$ by $\mathcal{P}$ is the average of values of $f$ at each point in $\mathcal{P}$, which approximates the integration of $f$ over the cube. Assume that $\mathcal{P}$ is constructed from an $\mathbb{F}2$-vector space $P\subset (\F2^n)^S$ by means of a digital net with $n$-digit precision. As an $n$-digit discretized version of Josef Dick's method, we introduce Walsh figure of merit (WAFOM) $\textnormal{WF}(P)$ of $P$, which satisfies a Koksma-Hlawka type inequality, namely, QMC integration error is bounded by $C_{S,n}||f||_n \textnormal{WF}(P)$ under $n$-smoothness of $f$, where $C_{S,n}$ is a constant depending only on $S,n$. We show a Fourier inversion formula for $\textnormal{WF}(P)$ which is computable in $O(n SN)$ steps. This effectiveness enables us a random search for $P$ with small value of $\textnormal{WF}(P)$, which would be difficult for other figures of merit such as discrepancy. From an analogy to coding theory, we expect that random search may find better point sets than mathematical constructions. In fact, a naïve search finds point sets $P$ with small $\textnormal{WF}(P)$. In experiments, we show better performance of these point sets in QMC integration than widely used QMC rules. We show some experimental evidence on the effectiveness of our point sets to even non-smooth integrands appearing in finance.

Josef Dick, Makoto Matsumoto

In this paper we introduce digital nets over finite abelian groups which contain digital nets over finite fields and certain rings as a special case. We prove a MacWilliams type identity for such digital nets. This identity can be used to compute the strict $t$-value of a digital net over finite abelian groups. If the digital net has $N$ points in the $s$ dimensional unit cube $[0,1]^s$, then the $t$-value can be computed in $\mathcal{O}(N s \log N)$ operations and the weight enumerator polynomial can be computed in $\mathcal{O}(N s (\log N)^2)$ operations, where operations mean arithmetic of integers. By precomputing some values the number of operations of computing the weight enumerator polynomial can be reduced further.

Hiroshi Haramoto, Makoto Matsumoto

Xorshift128+ are pseudo random number generators with eight sets of parameters. Some of them are standard generators in many platforms, such as JavaScript V8 Engine. We show that in the 3D plots generated by this method, points concentrate on planes, ruining the randomness.

Makoto Matsumoto, Ryuichi Ohori

Fix an integer $s$. Let $f:[0,1)^s \to \mathbb R$ be an integrable function. Let $P\subset [0,1]^s$ be a finite point set. Quasi-Monte Carlo integration of $f$ by $P$ is the average value of $f$ over $P$ that approximates the integration of $f$ over the $s$-dimensional cube. Koksma-Hlawka inequality tells that, by a smart choice of $P$, one may expect that the error decreases roughly $O(N^{-1}(\log N)^s)$. For any $α\geq 1$, J.\ Dick gave a construction of point sets such that for $α$-smooth $f$, convergence rate $O(N^{-α}(\log N)^{sα})$ is assured. As a coarse version of his theory, M-Saito-Matoba introduced Walsh figure of Merit (WAFOM), which gives the convergence rate $O(N^{-C\log N/s})$. WAFOM is efficiently computable. By a brute-force search of low WAFOM point sets, we observe a convergence rate of order $N^{-α}$ with $α>1$, for several test integrands for $s=4$ and $8$.