Reset option is a special type of path dependent options that the strike
can change at specified times during the life of the option. Under the
Black-Scholes framework, we show that the pricing formula for the
European style reset options involves multivariate normal
distribution functions. Numerical methods for American style reset options
will be proposed. How to hedge such options is as important as pricing
them. We explore the possibilities to hedge reset options using plain
vanilla options.
The relationship between reset options with other path dependent options will
also be studied. In particular, this could provide an efficient
approximation for
reset option prices.
The traditional lower bounds for the number of points in a cubature
formula of a certain trigonometric degree are based on the underlying
moment equations and do not take into account whether the formula is a
lattice rule or not. The concept of critical lattice in the field of
geometry of numbers provides a lower bound for the number of points
needed by a lattice rule of a certain trigonometric degree. Critical
lattices for the s-crosspolytope (octahedron) are however only known
for dimensions 1, 2 and 3. Besides, this lower bound cannot be sharp
for all degrees.
We carried out a large scale computer search for "optimal" lattices in
3 and 4 dimensions. In 3 dimensions we can easily find high degree
rules. In 4 dimensions the amount of work required increases
dramatically. We managed to reach degree 24. A side effect is that our
best results provide a new lower bound for the "density of closest
lattice packing" for the 4-crosspolytope.
Experimental evidence has shown that many high dimensional
integration problems appearing in computational finance can be very
efficiently approximated by deterministic algorithms. However, as the
experimental evidence accumulated, the theoretical explanation of this
phenomenon still remains not completely clear. Recently, papers by
Hickernell, Novak, Sloan, Wasilkowski, and Wozniakowski, have
introduced conditions to guarantee the strong tractability of integration
and have provided upper bounds on the e-exponent of the complexity.
In this talk we show how these techniques can be applied to financial
problems, and we characterize a class of financial problems for which strong
tractability can be proven and good upper bounds on the complexity
can be obtained.
Iterative Monte Carlo algorithms for solving linear multidimensional
problems are considered. A common approach for evaluating linear
functionals of the solution of integral equations of Fredholm type
as well as systems of linear algebraic equations
is studied.
The presented approach uses Monte Carlo iterations with a
resolvent operator of a given operator (matrices are also considered
as linear operators).
For inverting operators and solving linear systems a mapping of the
spectral
parameter domain of convergence is established. This transformation leads to a
new resolvent operator and, respectively, to a new random variable
constructed on the corresponding Markov chain, which allows the use of smaller
number of iterations for reaching a given error.
For calculating of eigenvalues
an additional parameter in resolvent operator is involved to
accelerate the algorithm convergence.
The convergence of the iterative processes is proved and the convergence rate
is compared with the rate of existing Monte Carlo algorithms for similar
problems. An error analysis is done.
The presented approach is apply to some linear algebra problems.
The problems under consideration are inverting a
matrix B, solving systems of linear
algebraic equations of the form B u = b and calculating
eigenvalues of symmetric matrices.
Several algorithms using the same Markov chains with different
random variables are described.
Parallel Monte Carlo algorithms for evaluating
the largest and the smallest eigenvalue of a given matrix are
presented.
Estimates for
computational complexity, speedup and parallel efficiency
for different parallel architectures are obtained. It is shown
that the resolvent approach reduces the
computational complexity of the algorithms under consideration
when parallel machines are used and leads to good
experimental results for speedup and parallel efficiency for large
sparse matrices.
Numerical tests are performed for a number of test matrices
on a cluster of workstations using MPI as well as
on the parallel machine Intel PARAGON using message passing
system.
Experimental results for the speedup and parallel efficiency are
obtained. It is shown that the
algorithm complexity is practically independent of the size of the
matrix.
Similarly to the well-known Komogorov n-width, Maiorov and Ratsaby have
introduced a new non-linear n-width by replacing linear manifolds of
dimension in the definition by
non-linear manifolds of
pseudo-dimension , which is closely
related to entropy number. (The
notion of pseudo-dimension for sets of real-valued functions was suggested
by Pollard and Haussler extending the Vapnik-Chervonenkis dimension). A
central question to be considered is what, if any, are the advantages of
non-linear approximation over approximation by linear manifolds, in the
first place for smoothness classes of functions. The smoothness of
functions to be approximated is more converniently and, maybe more
naturally given by boundedness of Besov (quasi-)norm.We give the
asymptotic orders of this non-linear n-width and entropy number in the
space of the unit ball of the
Besov space of
functions on d-dimensional torus with
common mixed smoothness r.
Moreover, these asymptotic orders are achieved by an explicit algorithm of
n-term approximation by the family formed from the integer translates of
the mixed dyadic scales of the tensor product multivariate de la Vallée
Poussin kernel, which is explicitly constructed.
The report is devoted to the problem of the quasi-random
sequences application in the imitation modeling.
The explicit formal difference between the quasi-random sequences
and the pseudo-random ones is that the discrepancy should be
asymptotically low. It supposes Kolmogorov's criterion to be low
because it is connected with the discrepancy and as a consequence
we have a statistical dependence of the elements of
quasi-random sequences. Such dependence in the simulation leads
to the high accuracy in the average values estimations but it
can also lead to incorrect results in the second moments.
Authors apply the quasi-random Sobol's
-sequence for the modeling of a Gaussian stationary auto-regressive
moving-average process (ARMA). The sequence is
the
vectorial one and we denote through
the j-th component ( ) of the
k-th vector
( ). The variety statistical analysis shows
that the sequences
for are not correlated.
But the sequences for any fixes
component
j are dependent. Hence the Gaussian random values obtained
on the base of the -sequence are in
general case also correlated.
It is well known that the spectral density of ARMA process is
equal to product of the moving-average process spectral density
and of the
kernel which depends on the coefficients of ARMA
process.
The using of the sequence leads to
the distortion of the spectral density of the modeling process,
As the examples show this distortion is larger
in the cases when the maximums of functions
and are close to each
other.
The similar results are valid also for the random fields
obtained by using the sequence. It is
possible that
there exists the ways of construction of non-correlated Gaussian random
sequences with definite length which are based on the
sequence.
In this paper properties and construction of designs under a
centered version of the -discrepancy are
analyzed.
The theoretic expectation and variance of this discrepancy are derived for
random designs
and Latin hypercube designs.
The expectation and variance of Latin hypercube designs are
significantly
lower than that of random designs.
While in dimension one the unique uniform design is also a set of
equidistant points, low-discrepancy designs in higher dimension
have to be generated by explicit optimization. Optimization is
performed using the threshold accepting heuristic which produces
low discrepancy designs compared to theoretic expectation and
variance.
Keywords: uniform design, Latin hypercube design, threshold
accepting heuristic, Quasi Monte-Carlo methods
In this communication, we investigate the relations between the generator
matrices of the
classical (0,s)-sequences in prime base b constructed by H.Niederreiter,
S.Tezuka,
T.Tokuyama and the author.
From these comparisons and from examples we have met in an other context,
we have found
variants of the previous generators matrices which give comparable
(0,s)-sequences in base
b; the proof is based on the general framework of formal Laurent series
introduced by
H.Niederreiter.
We study the classical star-discrepancy in high dimension. In contrast to
previous approaches we seek to understand the dependence not (or not only)
on the number of points, but (also) on the dimension. The title states
the main result of the talk. To explain it, let be
the number of points needed to reach star-discrepancy
less than in dimension d. It is shown that for
fixed
with ,
is of the order d. This result seems to be the first one in this context
in which a sharp order of dimension dependence is obtained. Around this
result various (non-matching) upper and lower bounds for
as a function of both d and are derived.
The upper bounds are based on deep results from empirical process theory.
We explain these tools in detail. To illustrate the basic ideas, we also
give a simple proof of a slightly weaker estimate, which nevertheless
reflects some of the basic underlying ideas.
All this is closely related to the concept of Vapnik-Cervonenkis
dimension, which provides far-reaching generalizations of the upper
estimate, e.g. to various other geometric discrepancies. The techniques
are probabilistic and show that the results hold for randomly chosen sets
of samples, with exponential decay of the failure probability.
Finally, the lower bound technique is presented, which relies on entropy
considerations and, again, on probabilistic estimates.
The talk covers part of joint work with E. Novak, G. Wasilkowski, and H.
Wozniakowski, see also E. Novak's talk for another portion of this
work.
When analyzing the error of multidimensional quadrature one typically
focuses on a set of integrands and a set of quadrature rules. It is then
reasonable to ask what is the quadrature error, , for the
worst-case or average-case integrand, and for the worst, best or average
quadrature rule based on N evaluations of the integrand. The answer may
depend on whether you fix the integrand first or the quadrature rule first.
This talk presents a framework for the variety of ways of one can analyze
quadrature error, and an ordering of results from most pessimistic (worst
integrand and quadrature rule) to least pessimistic (average-case integrand
and best quadrature rule). Beginning with some very general results, we
move to specific cases and relate the work of several authors. In some
cases one can obtain an explicit formula for in terms
of N,
while in other cases one obtains only an asymptotic bound. It is shown
that the price of being more pessimistic may mean a worse asymptotic order
or only a larger leading constant, depending on the sets of integrands and
quadrature rules considered. This talk is based on joint work with Henryk
Wozniakowski.
Recently there has been much interest in developing mathematical and
statistical analyses for problems involving non-linear systems. In part
this has been motivated by the general scientific interest in non-linear
dynamical systems and in part motivated by the advances in computational
power which allows complex systems to be more accurately modelled.
Examples of these systems include animal populations in ecology, disease
spread in epidemiology, climatic and weather variations in meteorology and
environment science, and fluctuating risk in financial time series and
financial markets increase dependence on financial derivatives.
Due to the fact that the completely linear modelling remains attractive
while the non-linear multivariate method neglects some existing linear
dependencies, we suggest using semi-linear (partially linear) methods to
approximate non-linear multivariate models. Before applying semi-linear
methods, contemporary data analysts are invariably confronted with the
generic question:
Can semi-linear methods produce 'models' with better predictive
power than is available from non-linear methods ?
In this talk we propose a cross-validation (CV) selection criterion to
determine whether a semi-linear model is more appropriate for a given
set of data. A feature of this criterion is that it allows data to 'speak'
for themselves. We illustrate the CV criterion using simulated and real
sets of data.
This talk reports our effort to implement Art Owen's random scrambling
of (t,s)-sequences. Because this scrambling involves manipulating all
digits of each number,
the code should be written carefully to reduce extra time required
scrambling. Computed root mean square discrepancies of the scrambled
sequences are compared to known theoretical results. Furthermore,
the performance of these sequences on various test problem are
presented. This is joint work with Fred J. Hickernell.
Financial derivatives which
are multivariate in nature are abundant in the financial markets. The
underlying state variables may be the stock prices, interest rates,
exchange rates, average of stock prices, extremum values of stock prices,
etc. The governing equations for the derivative values resemble the
parabolic equations but with cross derivative terms, a feature which
differs from the usual diffusion equations in engineering. In this
presentation, we discuss the pricing methodologies for multivariate
options with path dependent feature, in particular, terminal payoffs with
lookback feature and quanto feature. The intricacies associated with the
prescription of numerical boundary conditions in pricing algorithms of
these types of options are also addressed.
Lattice rules are quasi-Monte Carlo methods for numerical multiple integration
that are based on the selection of an s-dimensional integration lattice. The
problem of determining good integration lattices has been addressed by both
search strategies and by constructive strategies. Exhaustive searches over all
ranks and generator sets may be prohibitively expensive. On the other hand, it
is often possible to search over a subset of rules formed by scaling and
copying rules of lower rank and order, a technique sometimes called component
scaling. The class of copies of
rank 1 rules provides a well-known
example of this technique. A similar approach has been used with various
constructive strategies: particular constructions of rank 1 lattice rules have
been extended to higher rank/higher order rules by component scaling. Recent
results indicate, however, that a rule obtained by applying component scaling
to a construction of a lower-rank point set may have reduced efficiency with
respect to the high-dimensional components of the integrand. In this paper we
describe a construction of higher-rank rules by applying component scaling to
rank 1 rules. In this method a rank 1 rule is constructed by a generalised
continued fraction algorithm which relies on a weighted Diophantine
approximation error. The weights are chosen to be consistent, in a suitable
sense, with the scaling factors used to obtain the corresponding higher-rank
rule. Numerical results are presented for a range of dimensions and orders.
The jobs of set N= have release dates
,
processing times and due dates
. Let denote maximum
lateness of jobs from N with parameters in
schedule
like , where - the completion
time of job j in the schedule
.
The task of minimizing absolute error.
At first let sort all jobs in following order : . We
consider the following task:
where y- absolute error, ,- new due dates.
For solving the task (1)- (5) was proposed the algorithm with the
complexity . The results of
the algoritm are minimum
absolute error and the new due
dates
.
The schedule with the new due
dates is constructed by
the algorithm with the complexity and ,
where is the optimal schedule.
Kinetic equations provide mathematical models
for the statistical evolution of particles.
A distribution function
,
which represents the density of particles
having position and
velocity at time t, is
solution of a non-stationary integro-differential
equation. One method for approximating kinetic
equations is random particle simulation.
Particles are sampled from some known initial
distribution. Random numbers are used to move
the particles in phase space according to the
dynamics described in the equation.
In this presentation we study the improvement
achieved by using quasi-random sequences in place
of random numbers. We use (t,s)-sequences, which
are sequences satisfying strong uniformity
properties with respect to their distribution in
. Quasi-random points are not
blindly used in place of random numbers: at every
time step, the number order of the particles is
scrambled according to their positions before
assigning a new quasi-random point to each
particle. The method is to first sort the
particles into slabs, according to their first
coordinate. The particles of each slab are then
sorted into boxes according to their second
coordinate, and so on. Convergence is proved for
a quasi-random simulation using reordering of
the particles. Numerical results are presented
for sample problems whose solutions can be
found analytically. The quasirandom sequences of
Faure and Niederreiter are compared with
random sequences.
We design a genetic algorithm called orthogonal genetic algorithm with
quantization for global numerical optimization with continuous variables.
Our objective is to apply the experimental design methods to enhance the
genetic algorithm, so that the resulting algorithm can be more powerful and
statistically-sound. In particular, we propose a quantization technique to
complement an experimental design method called orthogonal design. We apply
the resulting methodology to generate an initial population of points that
are scattered uniformly over the feasible solution space, so that the
algorithm can explore the whole solution space evenly. In addition, we
apply the quantization technique and the orthogonal design to design a new
crossover operator, such that this crossover operator can generate a small
but representative sample of points as the potential offspring. Using this
operator, the algorithm can search the solution space effectively. We
execute the proposed algorithm to solve ten benchmark problems with 30 or 100
dimensions and very large numbers of local minima. The results show that the
proposed algorithm can find optimal or close-to-optimal solutions.
Several algorithms have been given for obtaining pecewise quadric
approximations of implicitly defined manifolds. This paper is concerned
with error estimates for such algorithms.
The use of implicitly defined surfaces in solid modeling or free form
modeling has some principle advantages over parametric surface representations.
Quadric patches are the simplest implicit patches that
can be used for free-form surface constructions. Recently several algorithms
have been given for obtaining pecewise quadric approximations
of implicitly defined manifolds [ Dahmen, 1989], [Guo, 1991]. In this
paper we derive estimates for the algorithms given in [Dahmen, 1989].
Analogous result can also be obtained for other algorithms.
Suppose that , is a smooth
surface. Given points X = of S and
X ,
i.e. . Suppose that is an according
triangulation from X and that is the according
polyhedrale hull.
Moreover, Suppose that
is a piecewise quadratic function. satisfies the
interpolation conditions :
where are the knots of and
are the unit normal vector
of S and at the points , respectively.
is one implicit, picewise quadric interpolating surface. Suppose that
the gradient of on
is continuous.
Estimates for
and
will be given. Here , and
have the smallest distant from w.
In the past orthogonal arrays and nearly orthogonal arrays
were constructed by a number of mathematical tools such as
orthogonal Latin squares, Hadamard matrices, group theory
and finite fields. In this paper we
propose some new criteria for evaluation of orthogonality.
Using these criteria, two algorithms, the forward procedure and
the modified threshold accepting, are proposed for
finding orthogonal and nearly orthogonal arrays. A number
of nearly orthogonal arrays are obtained by this approach.
This approach has some advantages. It can be applied to any nearly n-run
orthogonal arrays with mixed levels and is easily understood by
nonmathematicians and nonstatisticians.
By numerical comparisons we find that most of new designs obtained by
this paper are better than corresponding designs found by Wang-Wu (1992).
We also study the properties of two algorithms to improve algorithm
speeds.
Latin Hypercube sampling is a specific Monte Carlo estimator for numerical
integration of functions on with respect to
some product
probability distribution function. Previous analysis established, that
Latin Hypercube sampling is, at least asymptotically, superior to
independent sampling, especially, if the function to be integrated allows
a good additive fit. We propose a different approach to Latin Hypercube
sampling, based on orthogonal projections in Hilbert spaces, which allows
a rigorous error analysis. Moreover, we indicate why convergence cannot be
uniformly superior to independent sampling on the class of square
integrable functions. We establish a general condition under which
uniformity can be achieved, thereby indicating the rôle of the Sobolev
space .
The talk presents an account of the state of the art in the construction
of low-discrepancy sequences for quasi-Monte Carlo methods. Directions
of future research are also discussed.
We prove that the classical *-discrepancy is tractable.
That is, the minimal number of points
in the dimension d with the *-discrepancy at most
is
polynomial in d and . Our present bounds
are of the form
,
where is arbitrary. The proof
is non-constructive since we use the probabilistic approach
by analyzing the average behavior of the -star
discrepancy for even p.
The average is taken with respect to sample points which are
uniformly distributed in the unit d-dimensional cube.
It is well known that the average -star discrepancy is
of order
. We prove that the same is true for all even
p and provide
an explicit expression for the average -star
discrepancy. Our analysis involves Stirling numbers
of the first and second kind. We need to prove
an identity, which seems to be new, between Stirling numbers.
Although this identity is strictly combinatorial we
could not find a direct proof of it. Instead, we use a deep
result of Kiefer (1961) from probability theory which is a version
of the law of the iterated logarithm.
It is well known that good methods of approximation
can be used to increase the accuracy of numerical
integration methods. If g is a good approximation to
f and the integral of g is known, then an effective
strategy (known as control variates) is based on numerically
integrating the difference f-g.
Conversely, good methods of numerical integration
can be used to improve numerical approximations. The
target function f is expanded in an orthogonal series.
The optimal coefficients in that series are represented
in terms of integrals. The sample coefficients can
be computed by least squares (regression). This entails
computational burdens of O(np +p ) time and O(p )
space. A computational shortcut (quasi-regression)
reduces this cost to O(np) time and O(p) space.
Quasi-regression replaces the sample moment matrix among
the series functions by their known population matrix. This
idea was used earlier by Chui and Diamond to define
quasi-approximation. For a given sample size n, quasi-regression
is typically less accurate than regression. But it is fast
enough to allow much larger values of n. It can also be used
with p > n.
In an example, a measure of the amount of linearity in a function of
1,000,000 variables is computed using only 90,000 observations.
If time permits, some joint work with Jian An will be presented,
in which polynomial expansions are used with quasi-regression
to approximate a function of interest in Chemical Vapor Deposition
of semiconductor wavers.
One main problem in numerical integration over a d-dimensional cube
with the ordinary Smolyak algorithm is that the necessary number of
nodes increases very fast if d is large and the required 'degree of
approximation' is not too small. The 'degree of approximation' can
be measured in several ways, here we use the polynomial degree of
exactness, since it is reflected in error estimates for analytic
functions.
Using a 'retarded' sequence of Kronrod-Patterson quadrature formulae
as ingedient for the Smolyak algorithm, we obtain a smaller number
of nodes than in the Smolyak algorithm with Clenshaw-Curtis quadrature
for example, while the polynomial degree of exactness remains the same.
The mentioned cubature formulae are compared with respect to several
aspects.
In quasi-Monte Carlo methods, point sets of low discrepancy are crucial
for accurate and effective application. A class of point sets with
already low theoretic upper bounds of discrepancy as well as effective
implementability are the digital point sets known as digital
(t,m,s)-nets, resp. (t,s)-sequences.
The parameter t is indicative of the quality of the point set, the
lower t is, the lower also the upper bound of the discrepancy.
We introduce an effective way to establish this quality parameter
t for digital nets constructed to base b, where b is prime.
For this we significantly generalized an earlier algorithm by Wolfgang
Ch. Schmid for the binary case b = 2.
We will briefly mention some applications of this algorithm and present an
outlook concerning further generalizations to finite fields and rings.
A sparse grid is any point set
of arbitrary cardinality n defined as
where is a pre-selected sequence
in one dimension, and with is a set of
indices satisfying
An example of sparse grid is provided by hyperbolic cross
points.
We study bounds on the efficiency of sparse grids for
-discrepancy and average case
d-dimensional
integration with respect to the Wiener sheet measure.
Our main result is that the minimal exponent of sparse grids is
bounded from below by 2.1933. This shows that sparse grids
provide a rather poor exponent since, due to Wasilkowski and
Wozniakowski (1997), the minimal exponent of arbitrary point
sets is at most 1.4778. The proof of the latter is however
non-constructive. The best constructive bound is
and is obtained by a particular hyperbolic cross.
We develop a general technique that allows to obtain not only
lower bounds, but also upper bounds for exponents of sparse grids.
These bounds are basically given as solutions of simple nonlinear
equations.
We note that the well known low discrepancy sequences, such as
(t,s)-sequences and Hammersley points, do not form sparse grids.
Thus there is still room for constructive improvement of
the exponent among known point sets.
We consider systems of stochastic differential equations
and the pathwise (strong) approximation of their solutions.
Strong approximation is needed, for instance, for simulation
and visualization.
First we give a brief survey of known results, which are mainly
upper bounds for suitable approximation schemes in terms of
the maximal step-size. We also discuss several approaches to
adaptive step-size control.
In the main part of the talk we discuss recent results on
optimal step-size control and lower bounds. Hereby we can,
for instance, determine the complexity of strong approximation
of systems with additive noise. Basic ideas are not related
to the theory of ordinary differential equations, while
relations to approximation of stochastic processes are used.
Finally we mention a few modeling issues for information-based
complexity, which arise in the context of so-called higher
order methods.
Joint work with Norbert Hofmann, Erlangen, and
Thomas Müller-Gronbach, FU Berlin.
The efficiency of quasi-Monte Carlo methods mainly depends on the
quality of the underlying deterministic sample points.
The currently most powerful methods of constructing low-discrepancy (finite) point sets in the s-dimensional unit cube are provided by digital (t,m,s)-nets over finite fields.
One special method which is based on the Laurent series expansions of certain rational functions over finite fields was introduced by
Niederreiter in 1992.
To get suitable parameters for explicit constructions, one has to resort to computer search methods for certain polynomials -- this has been done only in the binary case. The best results are obtained by using rational functions with an irreducible denominator, combined with an efficient algorithm for the calculation of the quality parameter of digital nets.
In a joint work with Gottlieb Pirsic, we have generalized this algorithm (and, as a consequence, the computer search method mentioned above) to arbitrary prime bases. A generalization to prime power bases soon will follow.
We will give a short survey of the ``method of optimal polynomials for digital nets'', mention the connection to linear recurring sequences,
and present some tables with many improved parameters for concrete digital (t,m,s)-nets constructed over finite fields of prime order.
Recent calculations, especially in the area of mathematical finance, find
that the quasi-Monte Carlo method can be effective for integrals in
hundreds or even thousands of dimensions. Yet the classical error
estimates, especially the Koksma-Hlawka inequality, suggest that any
benefits from clever choices of the points, compared with the classical
Monte Carlo method in which the points are random, should be lost for
dimensions beyond perhaps 15 or 20.
This talk summarises recent results from a number of research groups which
go some way towards explaining this surprising success. A consistent
theme is that the effective dimension is not as large as the nominal
dimension. Sometimes the reduction in effective dimension is achieved by
an explicit weighting of the successive components, so that the higher
components become progressively less and less important.
We present a new method for the approximation of Wiener
integrals and provide an explicit error bound for a class of smooth integrands. The purely deterministic algorithm is a sequence
of
quadrature formulas for the Wiener measure, where the knots are
piecewise linear functions. It uses ideas of Smolyak, as well as
the multiscale decomposition of the Wiener measure due to Lévy
and Ciesielski. For the class we obtain
,
where is the number of evaluations needed to
guarantee
an error at most for .
An image and its texture can be approximated by spline functions. Some
applications of multivariate spline in image processing will be presented.
Several problems, such as zoom in, will be discussed.
The energy and transverse displacement fluctuations of directed
lines and surfaces in a disordered medium follow power-law
scaling with the length of the system. Exponents characterising
the scaling behavior depend on internal dimension of the manifold
and the dimension of the embedding medium, but are otherwise
universal. Their values are known exactly only in some special
cases. In the case of a line, the ground state of the system
can be determined using a transfer matrix method, from which
the exponents can be determined accurately. The determination of
the exponents for a two-dimensional surface can be done efficiently
with a newly introduced optimisation algorithm. A brief survey
of the theoretical ideas and methods in this field will be given,
together with a discussion of the behavior of the system at finite
temperatures.
In the last five years, it has been found that quasi-Monte Carlo methods,
the deterministic version of Monte Carlo methods, can provide a dramatic
improvement in the efficiency of Monte Carlo computation for the pricing
of financial derivatives. Whereas Monte Carlo methods assume random
numbers to provide probabilistic error bounds via the central limit
theorem, Quasi-Monte Carlo methods use low-discrepancy sequences to give
deterministic error bounds via the Koksma-Hlawka theorem. Since the
discrepancy of a set of points is a measure of its deviation from the
uniform distribution in the unit hypercube, a low-discrepancy sequence
means a sequence of points whose distribution is extremely uniform.
In this talk, we first overview recent advances in the generation of
low-discrepancy sequences for practical use, particularly, such sequences
as generalized Faure and generalized Sobol sequences. Then, we describe
how to apply them to the problems of high-dimensional integration which
appear in the areas of finance, physics, and statistics. Finally, we show
some successful examples of these applications.
We know that the time required to compute the star discrepancy of n
points in the s-dimensional unit cube is
prohibitive and that the
best known upper bounds for the star discrepancy of (t,s)-sequences and
(t,m,s)-nets are useful only for sample sizes that grow exponentially
with the dimension s.
As an alternative, we propose an algorithm to compute upper and lower
bounds for the star discrepancy of an arbitrary sequence in .
The method is based on a particular partition of in
subintervals and on
a specialized procedure for orthogonal range counting. The cardinality of
this partition only depends on s and on an accuracy parameter that has
to be specified.
As an application, we give improved upper bounds for the star discrepancy
of some Faure nets for , a comparison of
the
star discrepancy of various sequences in dimension 7, and a little study
related to a recent theorem of Novak, Wasilkowski, and Wozniakowski.
This paper is concerned with the statistical inference of a truncated
Dirichlet distribution arising in the general context of misclassified
multinomial model (such as medical screening or diagnostic tests), and
experimental design with mixtures. By employing the conditional distribution
method we offer a generating procedure and a stochastic representation of the
truncated Dirichlet distribution only involving the generation of a univariate
truncated Beta distribution. The generating procedure can be utilized to
calculate the relevant moments. In particular, we obtain the uniform design of
experiments with restricted mixtures by the stochastic representation of the
truncated uniform distribution over domain . The
methods for finding
the mode of the truncated Dirichlet distribution are constructed.
Alternatively, a sampling based approach using the Gibbs sampler was provided
as a means for developing the posterior moments of interest. Several examples
are presented to demonstrate the potential applications of the methodology
developed in this paper. Some conclusions are given and comments are made on
a comparison between the conditional distribution method and the Gibbs
sampler.
We can use the quasi-Monte Carlo methods (also known as number-theoretic
methods) to generate an NT-net or a deterministic set of points that
are uniformly scattered in the unit cube . Based
on Theorem 1
it is easy to sample from a truncated Dirichlet distribution by replacing
i.i.d. U[0,1] random numbers with the NT-net in
.
This talk is concerned with the complexity of local solution of
multivariate Fredholm
integral equations of the second kind. We analyze the problem of
computing a
functional , where u is
the solution of the equation
and the kernel k and right-hand side f are in .
The informations we have are linear basis
coefficients like Fourier or wavelet coefficients.
The complexity and optimal algorithms are already known
for Monte Carlo methods in and for
deterministic
ones in .
We are now interested in Sobolev spaces .
The complexity in these spaces will be determined. The proof of the
lower
bound involves techniques of information based complexity. An optimal
Monte
Carlo
algorithm using a Garlerkin like scheme with sparse kernel
representation
verifies the upper bound.
This leads us to interesting results: If p is greater than or equal to
4,
Monte Carlo
is superior to deterministic algorithms with the factor .
For p less than 4 the difference decreases until for p=2, that is,
in Hilbert
space
, randomization does not help at all.
Chinese character recognition is a very difficult problem because even a
small workable library of Chinese characters contains around 5,000
characters and that each character is a 2-dimensional arrangement of strokes
which vary in lengths and shapes depending on the specific character and its
font type. In the case of free-handwriting, the problem is even more acute
since one also has to take into account of the variations in the
individual's style of writing.
Suppose we restrict our attention to a library set of 5000 fixed-font
characters each represented by a different binary 16-by-24 matrix. Treating
each possible binary matrix as a vector, the representation contains
, or around, vectors which can be viewed as distortions of
the 5000 prototypes that define the library. The problem is to efficiently
identify any such vector as one of the the prototypes in the library while
minimizing some measure of recognition errors. In a straightforward
multiple-layer-perceptron approach to pattern recognition, each of the
prototype vectors would be represented by a strong local minimum in an
error-performance surface. In principle, during the recall phase, nearby
vectors would converge to one of the local minima and hence effect character
recognition. Unfortunately, the plethora of representation vectors give rise
to numerous other local minima (so called spurious states) that reduces the
Principal Component Analysis (PCA) is a well studied, popular and powerful
tool in pattern recognition for many years. It is optimal in the sense that
it finds the reduced representation that minimizes the least square errors
of representation, and thus is the best method of redundancy reduction in
the least square sense. However, for most practical problems, there are very
little, if any, theoretical justification that links the minimization of
least square errors with achieving optimal pattern classification. Indeed,
recent studies show that in tasks such as face recognition, much of the
important information is contained in the higher-order statistics of the
face images and hence the PCA approach in which only the second order
statistics are decorrelated would not be optimal.
In this paper, we implement Bell & Sejnowski's neural network which
maximizes the information transferred through the network. Such a network
has been shown to be an effective method of carrying out Independent
Component Analysis (ICA) which is a generalization of PCA taking into
account all the higher order statistics. Thus the network is able to
separate the statistically independent components of the input. We applied
this network to the problem of Chinese Character Recognition and achieved
excellent recongition result in a small scale feasibility study even for the
case of up to 50% binary noise.
Chebyshev polynomials and their topologically conjugated functions are
known to be ergodic with explicitly written invariant measures.
We implement their ergodic mappings
as random-number generators for Monte Carlo computations.
We found the condition that the mean square of the error degreases as
with N successive observations in the s-dimensional integration problems by using the orthogonal property of Chebyshev polynomials. We also discuss
their applications to their applications to financial data with Levy's
stable law[1] and their applications to CDMA communication systems with
chaotic spreading
sequences[2].
K, Umeno, Superposition of chaotic processes with convergence to Levy's
stable law, Physical Review E vol. 58 (1998),pp.2644-2647.
K. Umeno and K. Kitayama, Spreading sequences using periodic orbits of
chaos for CDMA, Electronics Letters vol. 35 (1999),pp.545-546.
The central theme in the research of biological computers is to view
evolution as computation.
We propose a new paradigm from the opposite point of view: regarding
computation as evolution.
We motivate the concepts starting from weighted trees, weighted Monte
Carlo simulation, and genetic algorithms. Our new methodology can turn a
computer with a good pseudo-random number generator into a powerful tool
and drastically increase the efficiency of Monte Carlo simulation, in wide
range of applications of high dimensions.
We illustrate its financial application in asset pricing, sensitivity
analysis, and risk management, calibrating multifactor models using the
market prices of benchmark securities.
We will discuss weighted approximation and integration of multivariate
functions defined over the whole space .
In particular, we will provide
provide conditions under which the complexity of weighted approximation
and integration problems are of the same order as the complexity of the
corresponding classical problems defined over the unit cube.
With Bayesian Inference Procedure, when no
prior information about the distribution or
design is given, the uniform design is the
optimal design, and the uniform distribution
is of Maximum Entropy. Further on, the adaptive
or sequential algorithms for either the integration
or for the importance sampling, should be adjusted
with the updated information of the distribution.
We intend to apply the ME principle for such
procedures to several particular models to
develop some optimized adaptive algorithms.
We deal with multivariate integration of functions of d variables with
large d. We wish to reduce the initial error by a factor of
for functions from the unit ball of
certain spaces.
Multivariate integration is tractable in these classes of functions
if the minimal number of function samples needed to solve the problem is
polynomial in and d.
Tractability of multivariate integration has been recently studied mostly
for Sobolev spaces. We extend this study for Korobov spaces of periodic
functions. Lower bounds are obtained by showing that multivariate
integration for the weighted tensor product of Sobolev spaces is not
easier than the corresponding problem for the weighted tensor product of
Korobov spaces. Upper bounds are obtained by using the fact that the
reproducing kernels of the Korobov spaces are shift-invariant. In the
non-constructive way we get necessary and sufficient conditions on the
weights of the Korobov spaces for tractability of multivariate
integration. This talk is based on joint work with Fred J. Hickernell.
In [1], a new methode for numerical
integration of
functions ( ) defined on a convex
subset C of with respect to a
continuous distribution
has been proposed. It relies on a space
quantization of C by
a n-tuple .
is approximated
by a weighted sum of the 's. The integration
error bound
depends on the distortion
of the Vorno¨i
tessellation of x.
This notion comes from Information Theoretists.
In this communication, we present some distortion propreties
for some classical one and two dimensional
low discrepancy sequences in the case where and
is
the d-dimensional uniform distribution .
1. G. Pagès,
A space quantization method for numerical integration,
Journal of Computational and Applied Mathematics, 89 (1997), 1-38.
Bootstrap was first introduced by Efron in 1979 as a computer-based method
for estimating the standard error of where
is an estimate of , a parameter of
interest. The main assumption
of the bootstrap is that the sample cdf is similar to the population
cdf. Now, bootstrap was applied to many problems such as bias-reduced
estimates and construction of confidence interval. In the past,
Monte-Carlo resampling is typically used in the ordinary bootstrap
simulation. However, few people have applied quasi-Monte Carlo methods,
which have a better uniformity in the bootstrap simulation. In this talk,
I will present some results using quasi-Monte Carlo methods for bootstrap
simulation. Bayesian bootstrap is also discussed. An appropriate
discrepancy for measuring the uniformity of the resampling points will be
discussed.
Consider tractability of integration and approximation based on scramble
sampling according to the base b scrambling scheme proposed by Art Owen
(1995, 1997).
For integration problem on the space of real functions
defined over
the unit cube , we use algorithms
for some weights
to estimate the integration operator
for
. We assume that is a reproducing kernel
Hilbert space
with reproducing kernel .The worst case error of is
defined as
For approximation problem on the space of real functions
over ,
we use algorithms
for some weights and some continuous linear
functionals
on to estimate the approximation operator
for .
We assume that is a Banach space equipped with a Gaussion
measure
with the covariance kernel . The average case error of is
defined as
We apply the general results in Hickernell & Wozniakowski (1998) on tractability and strong
tractability of
integration and approximation to the case where the sample points
are
randomly scrambled versions of n points in . We confine
ourselves to
the case of b=2. Scramble-invariant and non-scramble-invariant
kernels
are considered respectively. The weighted Sobolev space is also
considered for
illustration. Thesis part work with Fred Hickernell.
In computer experiments, for enhancing efficiency of experiments,
Statisticians proposed quite a few sampling and design methods (MacKay
et al (1979), Wang and Fang (1981), Owen (1992) and Tang (1993)).
In this paper, we introduce the uniform
design sampling (UDS) and the orthogonal array-based uniform Latin hypercube
sampling (OAULHS) proposed by Zhang and Wang (1994) and Zhang and Ma
(1997) and some recent works. The UDS is a sampling starting from an uniform
design by a randomly shifting of mod 1, and the OAULHS can be treated as
a development of the UDS by using orthogonal arrays, which is obtained
from an uniform design satisfying orthogonal array properties and by a
special randomly
shifting. We prove that, any sample of the UDS and OAULHS has the
same discrepancy infinitesimal order as that of their initial design as
sampling size .
Also we apply them to numerical integration computation and obtain
that and ,
where
is a bounded multivariate integrable function in ,
X has
uniform distribution in , ,
is a sample of the UDS or OAULHS of X and
Especially, for the OAULHS we have
as ,
where
are the main effect of and
are the interaction effect of and , c
is the sum of some interaction effects of higher order of 's,
is the variance of h(X).
in the definition by
non-linear manifolds of
pseudo-dimension 
of the unit ball 
of the
Besov space of
functions on d-dimensional torus 
with
common mixed smoothness r.
Moreover, these asymptotic orders are achieved by an explicit algorithm of
n-term approximation by the family formed from the integer translates of
the mixed dyadic scales of the tensor product multivariate de la Vallée
Poussin kernel, which is explicitly constructed.
-sequence for the modeling of a Gaussian stationary auto-regressive
moving-average process (ARMA). The sequence 
the j-th component ( 
) of the
k-th vector
( 
). The variety statistical analysis shows
that the sequences
for 
are not correlated.
But the sequences 
and of the
kernel 
which depends on the coefficients of ARMA
process.
The using of the 
-discrepancy of Random
Sampling and Latin Hypercube Design, and Construction of Uniform
Designs
be
the number of points needed to reach star-discrepancy
less than 
in dimension d. It is shown that for
fixed
, 
, for the
worst-case or average-case integrand, and for the worst, best or average
quadrature rule based on N evaluations of the integrand. The answer may
depend on whether you fix the integrand first or the quadrature rule first.
This talk presents a framework for the variety of ways of one can analyze
quadrature error, and an ordering of results from most pessimistic (worst
integrand and quadrature rule) to least pessimistic (average-case integrand
and best quadrature rule). Beginning with some very general results, we
move to specific cases and relate the work of several authors. In some
cases one can obtain an explicit formula for 
copies of
rank 1 rules provides a well-known
example of this technique. A similar approach has been used with various
constructive strategies: particular constructions of rank 1 lattice rules have
been extended to higher rank/higher order rules by component scaling. Recent
results indicate, however, that a rule obtained by applying component scaling
to a construction of a lower-rank point set may have reduced efficiency with
respect to the high-dimensional components of the integrand. In this paper we
describe a construction of higher-rank rules by applying component scaling to
rank 1 rules. In this method a rank 1 rule is constructed by a generalised
continued fraction algorithm which relies on a weighted Diophantine
approximation error. The weights are chosen to be consistent, in a suitable
sense, with the scaling factors used to obtain the corresponding higher-rank
rule. Numerical results are presented for a range of dimensions and orders.
have release dates
,
processing times 
and due dates
. Let denote maximum
lateness of jobs from N with parameters 
in
schedule
like , where 
- the completion
time of job j in the schedule
. We
consider the following task:
,- new due dates.
. The results of
the algoritm are minimum
absolute error 
and the new due
dates
with the new due
dates is constructed by
the algorithm with the complexity 
and 
,
where 
is the optimal schedule.
,
which represents the density of particles
having position 
and
velocity 
at time t, is
solution of a non-stationary integro-differential
equation. One method for approximating kinetic
equations is random particle simulation.
Particles are sampled from some known initial
distribution. Random numbers are used to move
the particles in phase space according to the
dynamics described in the equation.
. Quasi-random points are not
blindly used in place of random numbers: at every
time step, the number order of the particles is
scrambled according to their positions before
assigning a new quasi-random point to each
particle. The method is to first sort the
particles into slabs, according to their first
coordinate. The particles of each slab are then
sorted into boxes according to their second
coordinate, and so on. Convergence is proved for
a quasi-random simulation using reordering of
the particles. Numerical results are presented
for sample problems whose solutions can be
found analytically. The quasirandom sequences of
Faure and Niederreiter are compared with
random sequences.
, is a smooth
surface. Given points X = 
of S and
X 
,
i.e. 
. Suppose that 
is an according
triangulation from X and that 
is the according
polyhedrale hull.
Moreover, Suppose that
satisfies the
interpolation conditions :
are the knots of 
and
are the unit normal vector
of S and 
at the points 
, and 
have the smallest distant from w.
with respect to
some product
probability distribution function. Previous analysis established, that
Latin Hypercube sampling is, at least asymptotically, superior to
independent sampling, especially, if the function to be integrated allows
a good additive fit. We propose a different approach to Latin Hypercube
sampling, based on orthogonal projections in Hilbert spaces, which allows
a rigorous error analysis. Moreover, we indicate why convergence cannot be
uniformly superior to independent sampling on the class of square
integrable functions. We establish a general condition under which
uniformity can be achieved, thereby indicating the rôle of the Sobolev
space 
.
of points
in the dimension d with the *-discrepancy at most 
is
polynomial in d and 
. Our present bounds
are of the form
,
where 
is arbitrary. The proof
is non-constructive since we use the probabilistic approach
by analyzing the average behavior of the 
-star
discrepancy for even p.
The average is taken with respect to sample points which are
uniformly distributed in the unit d-dimensional cube.
-star discrepancy is
of order
. We prove that the same is true for all even
p and provide
an explicit expression for the average 
+p 
) time and O(p 
of arbitrary cardinality n defined as
is a pre-selected sequence
in one dimension, and 
with 
is a set of
indices satisfying
-discrepancy and average case
d-dimensional
integration with respect to the Wiener sheet measure.
Our main result is that the minimal exponent of sparse grids is
bounded from below by 2.1933. This shows that sparse grids
provide a rather poor exponent since, due to Wasilkowski and
Wozniakowski (1997), the minimal exponent of arbitrary point
sets is at most 1.4778. The proof of the latter is however
non-constructive. The best constructive bound is 
and is obtained by a particular hyperbolic cross.
. In this paper, a new
method of point inversion
will be presented. It is proved by using this method that for so called
basic NURBS curves/surfaces, it only needs at most to solve a linear
equation to determine if a given point on the given curves/surfaces except
for their singular points. It is well-known that a NURBS curve/surface has
only finitely many singular points. This means that except only finitely
many points, one only needs at most to solve a linear equation for the
point inversion problem. It is also proved the for each of those
exceptional singular points of a basic NURBS, to solve the point inversion
problem, one only needs to solve an equation of degree not more than the
multiplicity of the singular point. Therefore, for a singular point, the
point inversion problem can be solved in closed form when the multipicity
of this singular point 
. This shows that the
point inversion
problem has nothing relationship with the degree of a NURBS curve/surface.
Thus, our conclution is that for basis NURBS curves/surfaces the
point inversion problem can be solved in closed form except at most those
singular points whose multiplicities > 4.
of smooth integrands. The purely deterministic algorithm is a sequence
of
quadrature formulas for the Wiener measure, where the knots are
piecewise linear functions. It uses ideas of Smolyak, as well as
the multiscale decomposition of the Wiener measure due to Lévy
and Ciesielski. For the class 
,
where 
is the number of evaluations needed to
guarantee
an error at most 
for 
.
is
prohibitive and that the
best known upper bounds for the star discrepancy of (t,s)-sequences and
(t,m,s)-nets are useful only for sample sizes that grow exponentially
with the dimension s.
, a comparison of
the
star discrepancy of various sequences in dimension 7, and a little study
related to a recent theorem of Novak, Wasilkowski, and Wozniakowski.
. The
methods for finding
the mode of the truncated Dirichlet distribution are constructed.
Alternatively, a sampling based approach using the Gibbs sampler was provided
as a means for developing the posterior moments of interest. Several examples
are presented to demonstrate the potential applications of the methodology
developed in this paper. Some conclusions are given and comments are made on
a comparison between the conditional distribution method and the Gibbs
sampler.
. Based
on Theorem 1
it is easy to sample from a truncated Dirichlet distribution by replacing
i.i.d. U[0,1] random numbers with the NT-net in 
, where u is
the solution of the equation
. 
and for
deterministic
ones in 
.
.
For p less than 4 the difference decreases until for p=2, that is,
in Hilbert
space
, or around, 
vectors which can be viewed as distortions of
the 5000 prototypes that define the library. The problem is to efficiently
identify any such vector as one of the the prototypes in the library while
minimizing some measure of recognition errors. In a straightforward
multiple-layer-perceptron approach to pattern recognition, each of the
prototype vectors would be represented by a strong local minimum in an
error-performance surface. In principle, during the recall phase, nearby
vectors would converge to one of the local minima and hence effect character
recognition. Unfortunately, the plethora of representation vectors give rise
to numerous other local minima (so called spurious states) that reduces the
Principal Component Analysis (PCA) is a well studied, popular and powerful
tool in pattern recognition for many years. It is optimal in the sense that
it finds the reduced representation that minimizes the least square errors
of representation, and thus is the best method of redundancy reduction in
the least square sense. However, for most practical problems, there are very
little, if any, theoretical justification that links the minimization of
least square errors with achieving optimal pattern classification. Indeed,
recent studies show that in tasks such as face recognition, much of the
important information is contained in the higher-order statistics of the
face images and hence the PCA approach in which only the second order
statistics are decorrelated would not be optimal.
with N successive observations in the s-dimensional integration problems by using the orthogonal property of Chebyshev polynomials. We also discuss
their applications to their applications to financial data with Levy's
stable law[1] and their applications to CDMA communication systems with
chaotic spreading
sequences[2].
for some positive
constant
C, where p belongs to 
;
Isotropic Case
for functions from the unit ball of
certain spaces.
Multivariate integration is tractable in these classes of functions
if the minimal number of function samples needed to solve the problem is
polynomial in 
and d.
functions ( 
) defined on a convex
subset C of 
with respect to a
continuous distribution
has been proposed. It relies on a space
quantization of C by
a n-tuple 
. 
is approximated
by a weighted sum of the 
's. The integration
error bound
depends on the distortion 
of the Vorno¨i
tessellation of x.
This notion comes from Information Theoretists.
and
.
where 
, a parameter of
interest. The main assumption
of the bootstrap is that the sample cdf is similar to the population
cdf. Now, bootstrap was applied to many problems such as bias-reduced
estimates and construction of confidence interval. In the past,
Monte-Carlo resampling is typically used in the ordinary bootstrap
simulation. However, few people have applied quasi-Monte Carlo methods,
which have a better uniformity in the bootstrap simulation. In this talk,
I will present some results using quasi-Monte Carlo methods for bootstrap
simulation. Bayesian bootstrap is also discussed. An appropriate
discrepancy for measuring the uniformity of the resampling points will be
discussed.
of real functions
defined over
the unit cube 
, we use algorithms
for some weights 
to estimate the integration operator 
for
. We assume that 
.The worst case error of 
is
defined as
of real functions
over 
for some weights 
and some continuous linear
functionals
on 
for 
.
We assume that 
with the covariance kernel 
are
randomly scrambled versions of n points in 
-norm), and sometimes also with bound restrictions
on these adjustments, to make the feasible solution become an optimal
solution under the new parameter values. So far it is unknown that for a
problem which is solvable in polynomial time, whether its inverse problem is
also solvable in polynomial time. We now answer this question by
considering the inverse center location problem and show that even though
the original problem is polynomially solvable, its inverse problem is NP-hard.
.
Also we apply them to numerical integration computation and obtain
that 
and 
,
where 
is a bounded multivariate integrable function in 
,
X has
uniform distribution in 
, 
,
is a sample of the UDS or OAULHS of X and
as 
are the main effect of 
and
are the interaction effect of 
and 
is the variance of h(X).
, if V
can be equi-approximated by the multiresolution then V is a FSES, on the
other hand, if V is a FSES, then V must be equi-approximated by
arbitrary multiresolution. At the same time, we proved that arbitrary
multiresolution consist of a chain of FSES which are monotone
increasing.
order
convergency, that is
