Large Deviations Reading Group

Dates and time
Reading assignments
Participants
Notes, handouts, overhead projector slides
Minutes of the meetings
Other reading, related material

Background

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.

Reading assignments

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)

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)

Session 3, November 8:

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:

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

Dates and Times

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

Notes, handouts, overhead projector slides

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

Second session

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

Third session

Fourth session

Other reading, related material

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