Re: BOUNCE discussion@mcqmc.org: Admin request: /^subject:\s*help\b/i

• To: hsm@cti.com.cn, discussion@www.mcqmc.org
• Subject: Re: BOUNCE discussion@mcqmc.org: Admin request: /^subject:\s*help\b/i
• From: "Fred J. Hickernell" <fred@hkbu.edu.hk>
• Date: Tue, 07 Sep 1999 16:59:40 +0800
• Content-Type: TEXT/PLAIN; CHARSET=US-ASCII
• In-Reply-To: <199908311013.SAA22705@euler.math.hkbu.edu.hk>
• Reply-To: fred@hkbu.edu.hk
• Sender: discussion-owner@www.mcqmc.org

This message is send from "Fred J. Hickernell" <fred@hkbu.edu.hk>
============================================

Dear Simin,

Thank you for the several interesting questions.  Let me take a stab at
answering them.

>Hi,
>
>I have read a survey on derandomization in
>computaional geometry. It seems that derandomiztion in geometry is more
>different from than similar to quasi-monte carlo method. 

I am not familiar with derandomization.  Can you give a reference for the
survey you mention?  My comments below apply only to QMC.

>May I list some for
>your confirmation:
>(0) These two approaches are similar in that they both want to get rid of
>the randomness inside the algorithm.

In my opinion QMC does not want to get rid of randomness, necessarily.  Some
good randomized QMC methods exist.  (You might think of them as highly
stratified MC.)  However, QMC seeks faster convergence.

>(1) Quasi Monte Carlo approach is to seek BETTER results than purely random
>algorithm, but derandomization is to reach the SAME result of randomized
>algorithm by a derterministic one.

QMC seeks the same answer to the problem (e.g. integral, optimum) as MC, in
that there is assumed to be a single answer, but QMC wants to approximate it
more accurately.

>(2) Quasi Monte Carlo approach can be understood directly or
>intuitionistic, while derandomized algorithms can be hardly understood
>without appealing to their underlying randomized counterpart, as you
>mentioned in the paper.

Not sure about this.

>(3) Quasi Monte Carlo approach are mainly based on number-theoretic
>construction, while dedandomization is based on quite different yet more
>approaches.

Besides number-theoretic constructions of low discrepancy sequences for QMC,
there are also constructions based on optimization (see Pierre L'Ecuyer's work
on good lattice point sets)

>
>Are these assertions true? Please tell me if they are in fact irrelevant  to
>each other?
>
>I am more interested in QMC method at present, I have some further
>questions:
>(1) It seems that  discrepancy=sup|.| is popular. I know there are other
>measures of uniformity of a point set, such as dispersion=max.min.d(.).
>Which is the best from the viewpoint of theretic property, easiness to
>construct, easiness to compute, symmetry? When possible, it seems that
>points by orthogonal design is the best. How do you think of them?

In terms of ease of evaluation, discrepancies like the L2 discrepancy are the
best. Some of these have nice symmetry properties.  The two papers below and
others on my web page address these issues.

F. J. Hickernell, A generalized discrepancy and quadrature error bound, Math.
Comp. 67 (1998), pp. 299-322. 

F. J. Hickernell, What affects the accuracy of quasi-Monte Carlo quadrature?,
in Monte Carlo and Quasi-Monte Carlo Methods 1998 (H. Niederreiter and J.
Spanier, eds.), Springer-Verlag, Berlin, 1999, to appear. 

Orthogonal designs are good.  The points are uniform in any 1 or 2 dimensional
projections, but usually they are not good if you look at higher order
projections.

>(2) Besides numerical integration, any other applications? Optimization? Can
>you mention a few concrete examples? How if the dimension is too large?

Pricing financial derivatives (dimension = hundreds or thousands), pariticle
transport (dimension = infinity), and image rendering are just some
applications.  The proceedings of the biennial MCQMC conferences is a good
reference.

>(3) It seems to me that discrepancy is not symmetric, and can not be
>extended to discrete domain, e.g. to construct a uniform point set of K
>points in a space of {0,1}^N. ?

The star discrepancy is not symmetric, but there are others that are (see the
Math. Comp. paper above.  Yes, one can extend it to {0,1}^N.  See the paper 

F. J. Hickernell, Goodness-of-fit statistics, discrepancies and robust designs,
Statist. Probab. Lett. 44 (1999), pp. 73-78. 

for a brief description how.  Actually, a student and I are working on this
problem now.  It arises in statistical permulation tests.

>
>Sorry to ask so many questions. I wish I did not bother you too much.
>
>Yours,
>
>Simin He

May I ask you a question?  Which institution are you from?  You may be
interested in the 

Workshop on the Complexity of Multivariate Problems, October 4-8, 1999 and

the Fourth International Conference on MC and QMC Methods in Scientific
Computing, November 27 - December 1, 2000

both being held in Hong Kong.  See my web page for more details.

Best regards,
Fred

_______________________________________________________________________________
Fred J. Hickernell                                      Email: fred@hkbu.edu.hk
Department of Mathematics                               Office: (852) 2339 7015
Hong Kong Baptist University                               Fax: (852) 2339 5811
Kowloon Tong                                              Home: (852) 2609 1816
HONG KONG                                URL: http://www.math.hkbu.edu.hk/~fred


============================================
You are welcome to sent mail to discussion for discussion.
To list the index file, send email to majordomo@mcqmc.org,
use command,
index discussion

To get the index file, send email to majordomo@mcqmc.org,
use command,
get discussion filename
============================================

• References:
  • BOUNCE discussion@mcqmc.org: Admin request: /^subject:\s*help\b/i
    • From: discussion-owner@www.mcqmc.org

• Prev by Date: BOUNCE discussion@mcqmc.org: Admin request: /^subject:\s*help\b/i
• Prev by thread: BOUNCE discussion@mcqmc.org: Admin request: /^subject:\s*help\b/i
• Index(es):
  • Date
  • Thread