MinT - Generalized Rao Bound for Nets

Generalized Rao Bound for Nets

Martin and Stinson [1, Theorem 4.1] show that for an even k ≥ 2 an (m−k, m, s)-net in base b can only exist if

b^m ≥ V_b^(s,∞)(k/2),

where V_b^(s,∞)(r) denotes the volume of a ball with radius r in the NRT-space S_b^(s,∞).

The result is obtained by generalizing the Rao Bound for orthogonal arrays to the more general setting of ordered orthogonal arrays. Using the fact that (t, m, s)-nets are equivalent to OOAs with depth T ≥ k, a bound for nets is obtained.

There is also a (slightly more complicated) formula for k odd. However, the same result can always be achieved using the propagation rule m-reduction.

The generalized Rao bound for nets is always at least as stronger as applying the Rao bound for orthogonal arrays to the orthogonal array extracted from the net. This follows from the fact that the Rao bound for OAs is obtained from the formula given above by summing up only terms with h = ρ.

It is shown in [2, Section 5] that the generalized Rao bound follows also from the linear programming bound for OOAs.

For the important class of digital nets an identical result was established earlier by Schmid and Wolf in [3, Proposition 1].

Application to (t, s)-Sequences

By considering (t, t + k, s + 1)-nets in base b with k = 2⌊ ${\frac{{b}}{{(b−1)(b+1)}}}$ s⌋, it is shown in [4, Corollary 1] that t_b(s), defined as the minimum t such that a (t, s)-sequence in base b exists, satisfies

t_b(s) > log_b $\displaystyle {\frac{{b+1}}{{b}}}$ s – O(log s),

and therefore

$\displaystyle \liminf_{{s\to\infty}}^{}$ $\displaystyle {\frac{{t_{b}(s)}}{{s}}}$ ≥ log_b $\displaystyle {\frac{{b+1}}{{b}}}$ .

This is a better bound than the one obtained using the Rao bound for OAs, and for b = 2 also better than the one resulting from the (dual) Plotkin bound for OAs (yielding log₂3/2 ≈ 0.585 instead of 1/2). However, stronger bounds can be derived for all bases from the generalized (dual) Plotkin bound for OOAs.

In [4], Schmid proves this result only for digital sequences based on his bound for digital nets in [3]. However, a result for arbitrary sequences can immediately be obtained based on the general result for nets in [1].

References

[1]	William J. Martin and Douglas R. Stinson. A generalized Rao bound for ordered orthogonal arrays and (t, m, s)-nets. Canadian Mathematical Bulletin, 42(3):359–370, 1999. MR1703696 (2000e:05030)
[2]	Jürgen Bierbrauer. A direct approach to linear programming bounds for codes and tms-nets. Designs, Codes and Cryptography, 42(2):127–143, February 2007. doi:10.1007/s10623-006-9025-6 MR2287187
[3]	Wolfgang Ch. Schmid and Reinhard Wolf. Bounds for digital nets and sequences. Acta Arithmetica, 78(4):377–399, 1997.
[4]	Wolfgang Ch. Schmid. Shift-nets: a new class of binary digital (t, m, s)-nets. In Harald Niederreiter, Peter Hellekalek, Gerhard Larcher, and Peter Zinterhof, editors, Monte Carlo and Quasi-Monte Carlo Methods 1996, volume 127 of Lecture Notes in Statistics, pages 369–381. Springer-Verlag, 1998.

Copyright

Copyright © 2004, 2005, 2006, 2007, 2008, 2009, 2010 by Rudolf Schürer and Wolfgang Ch. Schmid.
Cite this as: Rudolf Schürer and Wolfgang Ch. Schmid. “Generalized Rao Bound for Nets.” From MinT—the database of optimal net, code, OA, and OOA parameters. Version: 2015-09-03. http://mint.sbg.ac.at/desc_NBoundRao.html

Show usage of this method