University of Cambridge > Mathematics > Statistical Laboratory > Richard Weber > Large Deviations Reading Group

The rate function for a Bernoulli r.v. with P(x=1)=0.6

Background

A number of us have spoken this summer about starting an informal working group for researchers in the Lab and interested outside visitors.

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.

The book "Large Deviations for Performance Analysis" by Shwartz and Weiss has just been published and the workshop this term can focus on reading at least part of that book.

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.

Session 1, October 12: (Richard Weber)

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.)

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.

Session 2, October 26: (Yuri Suhov)

Chapter 3 (theory) Random Walks, Branching Processes (7 pages)
Chapter 4 (theory) Poisson and Related Processes (16 pages)
Pages 243-244 Applications
Chapter 10 (application) Parallel Algorithms: Rollback (5 pages)

Session 3, November 8:

Chapter 5 (theory) Large Deviations for Processes (60 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)

Session 4, November 22:

Chapter 12.1-12.5 (application) Erlang's Model (19 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.

Participants

From rrw1@statslab.cam.ac.ukDate: Wed, 4 Oct 1995 12:30:00 +0100 (BST)From: Richard Weber <rrw1>To: Large Deviations Reading GroupAlastair 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>


Dates and Times

It appears that the best time for the first session of the reading group on Large Deviations will be

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.)

First session

• 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 ...

Minutes of the meetings

First session

Richard Weber spoke about the content of chapters 1, 2 and James Norris made remarks about Chapter 9. See the notes above.

Second session

Yurii Suhov reviewed the results in Chapter 3: the ballot theorem and its use in analyzing the large deviation asymptotic
$P(\sum_{i=1}^j \geq ja \forall j \leq n) \sim e^{-n\ell(a)+o(n)}$

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

to appear ...

Fourth session

Stephen Turner spoke about section 7.3 of Shwartz and Weiss for about 10 or 15 minutes, then James continued with chapter 5.