Coding‐theoretic constructions for (t,m,s)‐nets and ordered orthogonal arrays

(t,m,s)‐nets are point sets in Euclidean s‐space satisfying certain uniformity conditions, for use in numerical integration. They can be equivalently described in terms of ordered orthogonal arrays, a class of finite geometrical structures generalizing orthogonal arrays. This establishes a link between quasi‐Monte Carlo methods and coding theory. The ambient space is a metric space generalizing the Hamming space of coding theory. We denote it by NRT space (named after Niederreiter, Rosenbloom and Tsfasman). Our main results are generalizations of coding‐theoretic constructions from Hamming space to NRT space. These comprise a version of the Gilbert‐Varshamov bound, the (u,u+υ)‐construction and concatenation. We present a table of the best known parameters of q‐ary (t,m,s)‐nets for qε{2,3,4,5} and dimension m≤50. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 403–418, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10015     

The spectrum of additive BIB designs

In this article, the existence of additive BIB designs is discussed with direct and recursive constructions, together with investigation of a property of resolvability. Such designs can be used to construct infinite families of BIB designs. In particular, we obtain a series of B(sⁿ, ts^m, λt (ts^m ? 1) (s^n‐m ? 1)/[2(s^m ? 1)]) for any positive integer λ, such that sⁿ (sⁿ ? 1) λ ≡ 0 (mod s^m (s^m ? 1) and for any positive integer t with 2 ≤ t ≤ s^n‐m, where s is an odd prime power. Connections between additive BIB designs and other combinatorial objects such as multiply nested designs and perpendicular arrays are discussed. A construction of resolvable BIB designs with v = 4k is also proposed. © 2007 Wiley Periodicals, Inc. J Combin Designs 15: 235–254, 2007     

Scrambling Sobol' and Niederreiter–Xing Points

Hybrids of equidistribution and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the latter. In particular, randomized (0, m, s)-nets in basebproduce unbiased estimates of the integral, have a variance that tends to zero faster than 1/nfor any square integrable integrand and have a variance that for finitenis never more thane?2.718 times as large as the Monte Carlo variance. Lower bounds thaneare known for special cases. Some very important (t, m, s)-nets havet>0. The widely used Sobol' sequences are of this form, as are some recent and very promising nets due to Niederreiter and Xing. Much less is known about randomized versions of these nets, especially ins>1 dimensions. This paper shows that scrambled (t, m, s)-nets enjoy the same properties as scrambled (0, m, s)-nets, except the sampling variance is guaranteed only to be belowb^t[(b+1)/(b−1)]^stimes the Monte Carlo variance for a least-favorable integrand and finiten.     

Combinatorial methods in the construction of point sets with uniformity properties

It is well known that (t, m, s)-nets are useful in numerical analysis. Many of the constructions of such nets arise from number theoretic or algebraic constructions. Less well known is the fact that combinatorial constructions also yield nets with very good and in many cases, optimal parameters. In this paper, we provide a survey of such combinatorial constructions of (t, m, s)-nets.     

Calculation of the Quality Parameter of Digital Nets and Application to Their Construction

In quasi-Monte Carlo methods, point sets of low discrepancy are crucial for accurate results. A class of point sets with low theoretic upper bounds of discrepancy are the digital point sets known as digital (t, m, s)-nets which can be implemented very efficiently. The parameter t is indicative of the quality; i.e., small values of t lead to small upper bounds of the discrepancy. We introduce an effective way to establish this quality parameter t for digital nets constructed over arbitrary finite fields and give an application to the construction of digital nets of high quality.     

On linear programming bounds for nets

It is well known that there are close connections between low-discrepancy point sets and sequences on the one hand, and certain combinatorial and algebraic structures on the other hand. E. g., Niederreiter [1] showed the equivalence between (t, t + 2, s)-nets and orthogonal arrays of strength 2. Some years later this was generalized and made precise in the work of Lawrence [2] as well as Mullen and Schmid [3] by introducing ordered orthogonal arrays. This large class of combinatorial structures yields both new constructions and bounds for the existence of nets and sequences. The linear programming bound for ordered orthogonal arrays was first derived by Martin and Stinson [4]. As in the case of error-correcting codes and orthogonal arrays, it yields a very strong bound for ordered orthogonal arrays, and consequently for nets and sequences. Solving linear programming problems in exact arithmetics is very time-consuming. Using different approaches to reduce the computing time, we have calculated the linear programming bound for a wide parameter range. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A combinatorial characterization of (t,m,s)-nets in base b

We consider (t,m,s)-nets in base b, which were introduced by Niederreiter in 1987. These nets are highly uniform point distributions in s-dimensional unit cubes and have applications in the theory of numerical integration and pseudorandom number generation. A central question in their study is the determination of the parameter values for which these nets exist. Niederreiter has given several methods for their construction, all of which are based on a general construction principle from his 1987 paper. We define a new family of combinatorial objects, the so-called “generalized orthogonal arrays,” and then discuss a combinatorial characterization of (t.m.s)-nets in base b in terms of these generalized orthogonal arrays. Using this characterization, we describe a new method for constructing (t.m.s)-nets in base b that is not based on the aforementioned construction principle. This method gives rise to some very general conditions on the parameters (involving a link with the theory of orthogonal arrays) that are sufficient to ensure the existence of a (t.m.s)-net in base b. In this way we construct many nets that are new. © 1996 John Wiley & Sons, Inc.     

The decomposability of simple orthogonal arrays on 3 symbols having t + 1 rows and strength t

It is well‐known that all orthogonal arrays of the form OA(N, t + 1, 2, t) are decomposable into λ orthogonal arrays of strength t and index 1. While the same is not generally true when s = 3, we will show that all simple orthogonal arrays of the form OA(N, t + 1, 3, t) are also decomposable into orthogonal arrays of strength t and index 1. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 442–458, 2000     

Resolutions of PG(5, 2) with point‐cyclic automorphism group

A t‐(υ, k, λ) design is a set of υ points together with a collection of its k‐subsets called blocks so that all subsets of t points are contained in exactly λ blocks. The d‐dimensional projective geometry over GF(q), PG(d, q), is a 2‐(q^d + q^d−1 + … + q + 1, q + 1, 1) design when we take its points as the points of the design and its lines as the blocks of the design. A 2‐(υ, k, 1) design is said to be resolvable if the blocks can be partitioned as ℛ = {R₁, R₂, …, R_s}, where s = (υ − 1)/(k−1) and each R_i consists of υ/k disjoint blocks. If a resolvable design has an automorphism σ which acts as a cycle of length υ on the points and ℛ^σ = ℛ, then the design is said to be point‐cyclically resolvable. The design associated with PG(5, 2) is known to be resolvable and in this paper, it is shown to be point‐cyclically resolvable by enumerating all inequivalent resolutions which are invariant under a cyclic automorphism group G = 〈σ〉 where σ is a cycle of length 63. These resolutions are the only resolutions which admit a point‐transitive automorphism group. Furthermore, some necessary conditions for the point‐cyclic resolvability of 2‐(υ, k, 1) designs are also given. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 2–14, 2000     

Cubic and higher degree bounds for codes and (<Emphasis Type="Italic">t</Emphasis>, <Emphasis Type="Italic">m</Emphasis>, <Emphasis Type="Italic">s</Emphasis>)-nets

The Plotkin bound and the quadratic bound for codes and (t, m, s)-nets can be obtained from the linear programming bound using certain linear and quadratic polynomials, respectively. We extend this approach by considering cubic and higher degree polynomials to find new explicit bounds as well as new non-existence results for codes and (t, m, s)-nets.     

On the root mean square weighted L2 discrepancy of scrambled nets

Until now (t,m,s)-nets in base b are the most important representatives in the family of low-discrepancy point sets. Such nets are often used for quasi-Monte Carlo approximation of high-dimensional integrals. Owen introduced a randomization of such point sets such that the net property is preserved. In this paper we consider the root mean square weighted L₂ discrepancy of (0,m,s)-nets in base b. The concept of weighted discrepancy was introduced by Sloan and Woźniakowski to give a general form of a Koksma–Hlawka inequality that takes into account imbalances in the “importance” of the projections of the integrand.     

Topological minors in bipartite graphs

For a bipartite graph G on m and n vertices, respectively, in its vertices classes, and for integers s and t such that 2 ≤ s ≤ t, 0 ≤ m − s ≤ n − t, and m + n ≤ 2s + t − 1, we prove that if G has at least mn − (2(m − s) + n − t) edges then it contains a subdivision of the complete bipartite K _(s,t) with s vertices in the m-class and t vertices in the n-class. Furthermore, we characterize the corresponding extremal bipartite graphs with mn − (2(m − s) + n − t + 1) edges for this topological Turan type problem.     

The Microstructure of (t, m, s)-Nets

In an article of A. B. Owen (1998, J. Complexity14, 466–489) the question about the distribution properties of digital (t, m, s)-nets in small intervals was raised. We give upper and lower bounds for the maximum number of points of a (t, m, s)-net in these intervals and also provide a way of improving the distribution properties in some cases.     

Point sets with uniformity properties and orthogonal hypercubes

The theory of (t, m, s)-nets is useful in the study of sets of points in the unit cube with small discrepancy. It is known that the existence of a (0, 2,s)-net in baseb is equivalent to the existence ofs–2 mutually orthogonal latin squares of orderb. In this paper we generalize this equivalence by showing that fort0 the existence of a (t, t+2,s)-net in baseb is equivalent to the existence ofs mutually orthogonal hypercubes of dimensiont+2 and orderb. Using the theory of hypercubes we obtain upper bounds ons for the existence of such nets. Forb a prime power these bounds are best possible. We also state several open problems.This author would like to thank the Mathematics Department of the University of Tasmania for its hospitality during his sabbatical when this paper was written. The same author would also like to thank the NSA for partial support under grant agreement # MDA904-87-H-2023.This author's research was supported by a grant from the Commonwealth of Australia through the Australian Research Council.     

Exact simulation of final, minimal and maximal values of Brownian motion and jump-diffusions with applications to option pricing

We introduce a method for generating (W_x,T^(m,s),m_x,T^(m,s),M_x,T^(m,s))(W_{x,T}^{(\mu,\sigma)},m_{x,T}^{(\mu,\sigma)},M_{x,T}^{(\mu,\sigma)}) , where W_x,T^(m,s)W_{x,T}^{(\mu,\sigma)} denotes the final value of a Brownian motion starting in x with drift μ and volatility σ at some final time T, m_x,T^(m,s) = inf_{0 ￡ t ￡ T}W_x,t^(m,s)m_{x,T}^{(\mu,\sigma)} = {\rm inf}_{0\leq t \leq T}W_{x,t}^{(\mu,\sigma)} and M_x,T^(m,s) = sup_{0 ￡ t ￡ T} W_x,t^(m,s)M_{x,T}^{(\mu,\sigma)} = {\rm sup}_{0\leq t \leq T} W_{x,t}^{(\mu,\sigma)} . By using the trivariate distribution of (W_x,T^(m,s),m_x,T^(m,s),M_x,T^(m,s))(W_{x,T}^{(\mu,\sigma)},m_{x,T}^{(\mu,\sigma)},M_{x,T}^{(\mu,\sigma)}) , we obtain a fast method which is unaffected by the well-known random walk approximation errors. The method is extended to jump-diffusion models. As sample applications we include Monte Carlo pricing methods for European double barrier knock-out calls with continuous reset conditions under both models. The proposed methods feature simple importance sampling techniques for variance reduction.     

Particle simulations of the Kac model of the Boltzmann equation

We consider a simplified mathematical model of the Boltzmann equation which was introduced by Kac. A quasi-Monte-Carlo particle simulation using (t, m, s)-nets is described. The particle movement is shown to be an evaluation of the volume of a subset of I⁴=[0,1)⁴. An error bound for quasi-Monte-Carlo approximation of the volume of a generalized quadrant set is derived, when a (t, m, s)-net is used. Convergence of the simulation is proved when the particles are reordered according to their velocity in every time step. Quasi-Monte-Carlo and Monte-Carlo particle simulations are compared in computational experiments. The results indicate that quasi-Monte-Carlo simulation outperforms standard Monte-Carlo approaches.     

Discretization of multidimensional submanifolds associated with spin-valued spectral problems

We present a large family of Spin(p, q)-valued discrete spectral problems. The associated discrete nets generated by the so-called Sym-Tafel formula are circular nets (i.e., all elementary quadrilaterals are inscribed into circles). These nets are discrete analogues of smooth multidimensional immersions in ℝ^m including isothermic surfaces, Guichard nets, and some other families of orthogonal nets. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 12, No. 1, pp. 253–262, 2006.     

Generalized orthogonal arrays: Constructions and related graphs

Generalized orthogonal arrays were first defined to provide a combinatorial characterization of (t, m, s)-nets. In this article we describe three new constructions for generalized orthogonal arrays. Two of these constructions are straightforward generalizations of constructions for orthogonal arrays and one employs new techniques. We construct families of generalized orthogonal arrays using orthogonal arrays and provide net parameters obtained from our constructions. In addition, we define a set of graphs associated with a generalized orthogonal array which provide information about the structure of the array. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 31–39, 1999     

On the existence of Hadamard matrices

Given any natural number q > 3 we show there exists an integer t ? [2log₂(q ? 3)] such that an Hadamard matrix exists for every order 2^sq where s > t. The Hadamard conjecture is that s = 2.This means that for each q there is a finite number of orders 2^υq for which an Hadamard matrix is not known. This is the first time such a statement could be made for arbitrary q.In particular it is already known that an Hadamard matrix exists for each 2^sq where if q = 2^m ? 1 then s ? m, if q = 2^m + 3 (a prime power) then s ? m, if q = 2^m + 1 (a prime power) then s ? m + 1.It is also shown that all orthogonal designs of types (a, b, m ? a ? b) and (a, b), 0 ? a + b ? m, exist in orders m = 2^t and 2^t+2 · 3, t ? 1 a positive integer.