Monthly Archives: June 2010

How to generate higher order Sobol points in Matlab and some numerical examples

Higher order digital nets and sequences are quasi-Monte Carlo point sets \{\boldsymbol{x}_{n-1}\}_{n=1}^N, where N=b^m for digital nets and N=\infty for digital sequences (for more background information on this topic see Chapters 1-4 and Chapter 8 in the book; several sample chapters of this book can be downloaded here), which satisfy the following property:

\displaystyle \left|\int_{[0,1]^s} f(\boldsymbol{x}) \, \mathrm{d} \boldsymbol{x}  -  \frac{1}{b^m} \sum_{n=0}^{b^m-1} f(\boldsymbol{x}_n) \right|  \le C_{s,\alpha} \frac{(\log N)^{s \alpha}}{N^\alpha}, \hspace{2cm} (1)

where \alpha \ge 1 is the smoothness of the integrand {}f and C_{s,\alpha} \textgreater 0 is a constant which only depends on {}s and {}\alpha (but not on {}N). For instance, if {}f has square integrable partial mixed derivatives up to order {}2 in each variable, then we get a convergence rate of \mathcal{O}(N^{-2+\varepsilon}), where {}N is the number of quadrature points used in the approximation and \varepsilon >0 can be chosen arbitrarily small. If {}f has {}3 derivatives then we get a convergence of \mathcal{O}(N^{-3+\varepsilon}), and so on.

This method has been introduced in the papers:

The first paper only deals with periodic functions, whereas the second paper also includes nonperiodic functions.

For some heuristic explanation how higher order digital nets and sequences work see the paper:

  • J. Dick, On quasi-Monte Carlo rules achieving higher order convergence. In: Proceedings of the MCQMC’08 conference, Montreal, Canada, P. L’Ecuyer and A. Owen (eds.), pp. 73–96, 2009. doi: 10.1007/978-3-642-04107-5_5 An earlier version can be found here.

In this entry we provide a Matlab program which generates point sets which satisfy the property (1). Continue reading

Walsh functions II: Walsh functions in general base and Walsh functions over groups

In a previous post we introduced Walsh functions. We showed that this set of functions is orthogonal and complete. In this post we generalize the Walsh function system such that the orthonormality and completeness of the new Walsh function system still holds. A table of contents for the posts on Walsh functions can be found here. Continue reading

The connection between the logarithmic Walsh degree of exactness, the t value of digital nets and an idea for future research

In this entry we show how the Walsh degree of a digital net is connected to its t value. This can lead to future research by using ideas developed for finding lattice rules with large trigonometric degree. Continue reading

Multiple light switches which control one light and modular arithmetic

The problem I would like to discuss is the following. Most people have seen a room where there are two independent light switches. For instance, in some bedrooms the light can be turned on and off at the entrance door and also at a switch next to the bed. In this case you can turn on the light when you enter the room at night and then later turn off the light when you are already in bed. You can then turn on the light again using the switch at the door. Of course you can also turn on the light again using the switch at the bed. In fact, the light can be turned on and off at any switch in any sequence – i.e. each switch works independently of the state of the other switch.

The question is, how does this work? Continue reading

Solution: Multiple light switches which control one light

In a previous post (see here) I stated the problem of how to design an electric circuit with multiple light switches where the light can be turned on and off independently at each switch. Here I present the solution. Continue reading