Dates and time

Reading assignments

Participants

Notes, handouts, overhead projector
slides

Minutes of the meetings

Other reading, related material

The idea is that we should all read some background material, one person should present ideas (to reinforce reading and put a personal slant on things) and that we should have time to discuss. The subject of the workshop will be some topic that is interesting to a number of us because of its mathematical and application importance.

There seems to be support for starting this with the field of Large Deviations. This is something some of us heard a lot about at the Stochastic Networks Workshop in Edinburgh this summer; it is relevant to the work of several research students in the Lab and it is not presently covered in any of our courses.

*This is the cover picture by Freddy Bruckstein that
Shwartz and Weiss wanted to use for their book cover. But their
publisher said it didn't fit the style of the series. The
picture contains several jokes and references: to the authors'
names, to a problem they have solved using LDs (men and women
at a theatre, queueing for toilets and typically having
different service times), and to the application of LDs to
queueing in general.*

You can find information about this book on http://cm.bell-labs.com/who/apdoo/LD/LargeDeviations.html, including an up-to-date list of errata, of which here is a local copy.

I have placed two copies of the book with Tania, and people are welcome to borrow these. Frank has also deposited a copy. You can also borrow another copy from me in my office if I am in and am not using it at the time. I would be grateful if anyone else who has a spare copy does the same.

Shwartz and Weiss suggest two ways through the book. The second is "application-oriented, Such a course should probably start with Chapter 1, so that some flavour of the theory is provided. The results of 1.4, 2.1 and 2.3 and of Chapter 5-8 can then be stated without proof, with or without intuitive explanation ... then applications can be presented, according to the dependence chart shown in figure 0.1".

Here is a possible schedule for us, based on the table of dependencies on page 4. After reading for the first session, I think 44 pages may be a bit much. With just four sessions, we must necessarily miss much out. I have made some suggestions for the next three sessions that are lighter.

Chapter 1 (theory) Large Deviations of Random Variables

Chapter 2 (theory) General Principles

Chapter 9 (application) Allocating Independent Subtasks

At the first session, I will attempt to review the high points of the material in these chapters and say a few extra things, in no more than 30 minutes. The rest of the time will be filled with questions, comments, and by others sharing their insights. Those who have already worked with LD in their research might like to prepare something short to say (e.g. 5 minutes), such as: a relevant example, a place where the theory has been useful in research, another way to think about things which the book does not mention, etc. (but thinking about things that are relevant to these chapters, very much basics ... rather than things that might fit better in a later session.)

There are a small number of exercises in the chapters. Keen readers might be willing to tell the rest of us how they solved these exercises.

Chapter 4 (theory) Poisson and Related Processes (16 pages)

Pages 243-244 Applications

Chapter 10 (application) Parallel Algorithms: Rollback (5 pages)

James Norris writes: In the seminar on Thursday 9th November I shall discuss large deviations for Markov jump processes around the fluid limit. This is the content of Chapter 5 of Schwarz and Weiss.

If you have time, you could also look at:

Chapter 11 (application) The M/M/1 Queue (28 pages)

This is an important application and a highlight of the book which we should read. The authors write, "we don't suppose that everyone who reads this chapter will have gone through the previous chapters, so we include a fairly simple and straightforward approach". You should refer to the Cahpter 5 and those below, as necessary, concentrating on understanding what the key results state, rather than going into the details of the proofs.

Chapter 6 (theory) Freidlin-Wentzell Theory (39 pages)

Appendic C (theory) Calculus of Variations (12 pages)

Chapter 13.1-13.5 (application) The Anick-Mitra-Sohndi Model (26 pages)

We only have time to read the first parts of these chapters. But you might like to read the introductory paragraphs to the later parts, to see what else is covered.

From rrw1@statslab.cam.ac.uk

Date: Wed, 4 Oct 1995 12:30:00 +0100 (BST)

From: Richard Weber <rrw1>

To:Large Deviations Reading Group

Alastair Young [alastair@statslab.cam.ac.uk],

Anthony Quas [ant@statslab.cam.ac.uk], David Rose [D.Rose@statslab.cam.ac.uk], Doug Kennedy [doug@statslab.cam.ac.uk],

Frank Kelly [frank@statslab.cam.ac.uk],

Damon Wischik [djw1005@hermes.cam.ac.uk],

Dimitris Gatzouras [gatzoura@statslab.cam.ac.uk],

Ganesh [ajg@dcs.ed.ac.uk],

Gareth Roberts [gareth@statslab.cam.ac.uk],

Giles Thompson [giles@statslab.cam.ac.uk],

Geoffrey Grimmett [grg@statslab.cam.ac.uk],

James Norris [james@statslab.cam.ac.uk],

Jean Mairesse [jem@hplb.hpl.hp.com],

John Liechty [jcl@statslab.cam.ac.uk], Meenakshi Lakshman [meena@statslab.cam.ac.uk], Martin Baxter [mwb@statslab.cam.ac.uk],

Neil O'Connell [noc@hplb.hpl.hp.com],

Pat Altham [pat@statslab.cam.ac.uk],

Peter Whittle,

Richard Gibbens [richard@statslab.cam.ac.uk],

Richard Smith [rsmith@statslab.cam.ac.uk],

Richard Weber [rrw1@statslab.cam.ac.uk],

Stephen Turner [sret1@statslab.cam.ac.uk],

Sujit Sahu [sujit@statslab.cam.ac.uk],

Susan Pitts [ucak0sp@ucl.ac.uk],

Yurii Suhov [yms@statslab.cam.ac.uk]

</rrw1>

12-1 pm on Thursday 12 October in S27.

The other three sessions, fortnightly this term, will fill the same slot. Let us begin by reading Chapters 1, 2 and 9 of Shwartz and Weiss (a total 44 pages and quite easy-going). (This selection is based on the table of "chapter dependencies" described on page 4 of the book.)

- Richard Weber's handout of overhead projector slides for the first session (4 per sheet), and also a larger version of the same thing (2 per sheet). (Typos in the proof of Chernoff's upper bound have been corrected.)
- A note about conspiracy vs. individualism, summarising the point made by James Norris.

More to appear ...

\[He then described the application of this to branching random walks and to the analysis of a rollback algorithm in Chapter 10.

P(\sum_{i=1}^j \geq ja \forall j \leq n) \sim e^{-n\ell(a)+o(n)}

\]

- There are some good papers to be found on the site of the group of John Lewis (Dublin). See ftp://stp01.stp.dias.ie/DAPG. These include

- J.T. Lewis, Neil O'Connell and Raymond Russell, "An introduction to large deviations for teletraffic engineers ".

- C. Courcoubetis and R.R. Weber. "
Buffer overflow asymptotics for a switch handling many
traffic sources." To appear in
*J. Appl. Prob.*, September 1996.**(abstract)**. This paper derives a large deviation asymptotic for the overflow of the buffer at the switch when many sources are multiplexed together at the switch.

- A very small bibtex
database of books and papers about, or using, large
deviations.