Centre for Mathematical
Sciences
Wilberforce Road, Cambridge, CB3 0WB
Tel: (01223) 337958
Fax: (01223) 337956
Email: secretary@statslab.cam.ac.uk
All interested are welcome
This list is subject to revision
Select a date to view the relevant seminar abstracts:
Abstract to follow
The Odds-Theorem (B. 2000, B. 2003)) is an elementary result in the theory of optimal stopping . It attracts interest because it can deal with a certain class stopping problems in a unified way and yields an optimal-solution algorithm which is optimal itself. We call the class of problems " last-success-problems " and motivate this type of problems by examples ranging from search and selection problems, over investment problems (B. and Ferguson 2002), to problems in clinical trials. We then discuss what generalizations would be desirable. For some of these, an approximation approach (Poisson clumping heuristic, Aldous (1989)) gives useful first answers, in other problems it does not, and we shall explain why. In particular, we present a "string-success version" which opens further new perspectives . It is solved for the so-called uncorrelated case (B. and Louchard (2003)). An outlook to further research for the most general shows the kind of problems we have to face.
NB. The presentation is intended to be accessible for probabilists and statisticians of all inclinations.
References.
Aldous D. (1989). Probability Approximations via the Poisson Clumping Heuristic. Springer Verlag, New York.
Bruss F.T. (2000). Sum the Odds to One and Stop.. Annals of Probability, Vol. 28, No 3, 1384-1391.
Bruss F.T. and Ferguson T.S. (2002) High Risk and Competitive Investment Problems. Annals of Applied Probability, Vol. 12, 1202-1226.
Bruss F.T. and Louchard G. (2003) Optimal Stopping on Patterns in Strings Generated by Random Sources Journal of Applied Probability, Vol. 40, 49-72.
Bruss, F.T. (2003) A Note on Bounds for the Odds-Theorem of Optimal Stopping. Annals of Probability, Vol 31, No 4, 1859-1861.
Abstract: Consider a random walk $S_n=\xi_1+...+\xi_n$ with i.i.d. increments and assume that these increments are heavy-tailed. The exact asymptotics for the tail distribution of the supremum $M=\sup_{n\ge 0}S_n$ and for tha tail distribution of the maximum $M_\tau=\max_\{0\le i \le \tau\} S_i$ on the random time interval $\tau=\min\{n\ge 1: S_n\le 0\}$ are known when $E\xi_1$ is negative and finite. We revisit these theorems and give complementary results in the case $E|\xi_1|=\infty$.
The talk is dedicated to localization of the principal eigenvalue (PE) of the Stokes operator under the Dirichlet condition on the boundary of a fine-grained random domain contained in a large cubic block. The random microstructure is assumed essentially independent and identically distributed in distinct unit cubic cells. As the volume of the containing block goes to infinity, the PE exhibits deterministic behaviour. It converges to zero at the same rate as the corresponding quantity for a domain that is obtained by dilation from a set of fixed shape and has volume proportional to the logarithm of that of the containing block. The main result in this talk is a theorem extending from the planar case to higher dimensions the authors earlier result on convergence of the appropriately normalized Stokes PE to a non-random limit in probability. It develops a new approach to the study of deterministic asymptotics of the PE that is based on recent work of F.Merkl and M.V.Wutrich [3].
Localization of the principal eigenvalue (PE) of an elliptic operator with random elements acting on functions in a standard domain of very large volume attracts considerable interest since mid-eighties. Rigorous research in this field, which remains active, was started by A.-S. Sznitman (see, e.g., [1]). The investigation originated in physics of disordered media: the PE of the Laplacian in a domain with random fine-grained boundary carrying zero Dirichlet condition determines the rate at which diffusing particles are absorbed by randomly positioned traps.
Known versions of the greyscale techniques originating in work of A.-S. Sznitman exploit the possibility to exclude from the domain those parts where the boundary is massively present (see, e.g., [1,2] and the references therein; this approach remains efficient when the boundary is substituted by a random positive potential). The restriction to the effective domain is done on the basis of a selection rule, which identifies the vacuities consisting of cubic cells where the boundary (or potential term) is inessential. The maximal volume of a connected vacuity, which determines the PE, is estimated by techniques used in the percolation theory to analyse random lattice animals. An additional difficulty in the case of the Stokes operator is the necessity to use only divergence-free test functions.
The localization of the PE in [3] for the Schrdinger operator with a small positive random potential is based on the analysis of feasibility of specific values of the Rayleigh quotient for individual test functions. The results of [3] include a description of transition from the limiting PE values for the small random potential to those appearing in the original problem with random boundary (or a large potential term).
The new approach suggested in [3] proved efficient in the derivation of the lower bound on PE also for the Stokes operator [4], which is discussed in the present talk. In [4], a lower bound for the Stokes PE is derived through low compressibility approximation using methods of [3], and the corresponding upper bound is obtained by construction of a test function with low Rayleigh quotient that is compatible with a typical configuration of random structure using an argument inspired by the cited greyscale techniques.
REFERENCES
[1] Sznitman A.-S. Brownian Motion, Obstacles and Random Media. Springer-Verlag, New York, 1998.
[2] Yurinsky V.V. Localization of spectrum bottom for the Stokes operator in a random porous medium. Siber. Math. J. (2001) vol.42, No.2, 386-413.
[3] Merkl F., Wtrich M. Infinite volume asymptotics of the ground state energy in a scaled Poissonian potential. Ann. Inst. H.Poincare. Probability and Statistics (2002) v.38, No 3, 253-284.
[4] Yurinsky V.V. Localization of the Principal Eigenvalue for the Stokes Operator in a Random Domain. Depto de Matemtica Centro de Matemtica, Universidade da Beira Interior, Pre-publicacao No 1, 2003. Available at http://www.ubi.pt/externo
To follow
To follow
At the core of a typical high-capacity Internet router there is an input-queued switch. This consists of a collection of queues, together with a "generalized server". The server, in each timeslot, chooses a subset of queues to serve, and serves these queues simultaneously; but only certain subsets are allowed. (The family of allowed subsets is determined by constraints on the layout of the silicon chip, relating to matchings on bipartite graphs.)This raises two questions: What algorithm should the server use, to decide which subset to serve in a given timeslot? What can one say about the resulting queue sizes?
Various algorithms have been described [1], and for some of these it is known whether the system is stable [2]. I will describe some new results (in collaboration with D.Shah, Stanford) concerning the queue size distribution when the system is in heavy traffic. These results draw on both combinatorial arguments and stochastic process limits.
[1] e.g. by Nick McKeown, Stanford, http://klamath.stanford.edu/~nickm/
[2] J.G.Dai & B.Prabhakar, "The throughput of data switches with and without speedup", IEEE INFOCOM 2000. http://www.stanford.edu/~balaji/na.html#sr"
I will review some recent results on the metastability in the context on Markov processes. I will first present a structural rather model independent result linking in a precise asymptotic way mean exit times from metastable states, small eigenvalues of the generator, and certain capacities. Then I will show that the latter can be very well estimated (model dependently) in many cases. Specifically, I will discuss results for diffusion processes, Glauber dynamics at low temperatures, and Kawasaki dynamics for a lattice gas in an open box.