I briefly want to point to some (online) books on probability theory. There are a few good ones available online, like the book of of Robert Ash entitled Basic Probability Theory or some books by Robert Gray, e.g. Probability, Random Processes, and Ergodic Properties or Introduction to Statistical Signal Processing. However, when going for printed copies, one may look at books authored by Geoffrey Grimmett, especially Probability and Random Processes. The latter illustrates the right level of probability theory needed in most of the research fields in computer science in a comprehensive and understandable way. A strong feature of this book is its large collection of exercises (there is even a second book dedicated to exercises only, which is more helpful to the learner as it contains also the solutions to each exercise posed in that book) and good examples ilustrating the most important theorems.

Do we need mathematicians? This question was addressed by Ian Steward, professor of mathematics at the university of Warwick, UK, during this years Queen’s Lecture at the Technical University of Berlin. The annual queen’s lecture is held in Berlin since 1965 and were initially a present by queen Elizabeth II on the occasion of her visit to Berlin. In this year, the attendees were looking forward to get an answer to Do We Need Mathematicians – will Ian Steward make his profession obsolete by answering with no or will there be more support for mathematics in the German Year of Mathematics?

Of course, everyone knew the answer, as many of the luxuries of the 20th century have their base in mathematics, and Ian Steward immediately rephrased his opening question to Why Do We Need Mathematicians? This may be essential in times when many countries are worried about decreasing amounts of first-semester students in “tough subjects”, such as mathematics.

He then quickly moved on to present some believes and showed why they are wrong:

• The only job one can get holding a degree in mathematics is becoming a school teacher: Less then 5% of the British students graduating in mathematics go into school politics, 25% are employed in the financial sector.
• We did all the math in school. There is nothing new happen in mathematics. If there would be something new, we would have heard about it. Why would someone invent even more math, there is already too much – There are about 1-2 million pages of math published per year.
• We don’t use maths in our daily life: Mathematics is the Cinderella that doesn’t come to the ball. It’s working behind the scenes and only some will notice it.
• We have computers: Drugs don’t make doctors obsolete, telescopes do not make astronomers obsolete and microscopes doesn’t obsolete biologists. In fact, a computer is just a tool that helps the mathematician with getting routine work done and concentrating on actually solving problems. But one always need a professional to use a tool efficiently.

Ninety Mile Beach in Australia (Source: Wikipedia)

A large part of his talk was devoted to demonstrating where mathematics is used in daily life by following the example of going on holiday from the early stage of looking for possible locations, over flying to the actual destination to lying at the beach taking pictures. In the course of his demonstration he showed that maths is inside everywhere.

When using the Internet to holiday planing, a user will use a search engine whose results are ranked by the Page Rank Algorithm and the data communication to the travel agency might be secured using several cryptographic techniques.

Aeroplane (Source: Wikipedia)

When using the air-plane to fly to the chosen destination, one will encounter a huge complexity. a) Why does the aeroplane fly? One needs the principles of fluid dynamics and Navier-Stokes equations. A digital wind tunnel is used to simulate and study the aerodynamics of a planed aircraft. The Navier-Stokes equations are thus solved in the simulator. b) How do they navigate? A bunch of number theory is involved in the Global Positioning System. c) How do they know when to send the plane where? Addressing this subject involves network analysis, which is a hot topic in mathematics and spreads from computer networks such as the Internet to biological networks such as epidemic of diseases.

Digital Camera (Source: Wikipedia)

Arrived at the beach, one wants to take souvenir photos, but how does the camera manage to store so many pictures in one memory card? Shrinking the amount of data without loosing the picture involves complex techniques of data compression, which Ian Steward demonstrated by explaining the basics of JPEG.

When the queen’s lecture was over, there was a nice reception where the university orchestra played traditional and modern British music and the university served food and drinks.

All in all, I really enjoyed listening to his talk. He presented a nice collection of examples showing why mathematics is neccessary. However, I belive the talk was addressed to a different audience and was somewhat less relevant for students and employees at a technical university that a very familiar with the presented topics. From a computer scientists perspective, the examples were well known and thus can be considered as boring—the way he presented them was not. Actually his audience consisted of exactly those people that did not need to be convienced that mathematics is important. However, he is doing a great job in actually communicating science and I believe such a powerful talk will have a very strong effect on an audience that is less technophile.

For some reason, that is not obvious to me at the moment, a correct understanding of the Gilbert-Elliott model seems to be hard. After giving a talk in October last year, where I also mentioned the model, someone said to me: “It’s great, you were actually the first person that explained the model correctly”. This confirmed my impression I got from reading papers dealing with this model some time ago. The explanations were not wrong, but some things were sometimes a bit mixed up. I’m wondering where this comes from as the model is actually quite simple. After I found another misunderstanding of the model in the web today, I thought it’s time to write a blog post covering Gilbert-Elliott.

However, what exactly is the Gilbert-Elliott model? Well, consider you want to describe the characteristic of a packet loss process where packets are dropped by a router in cases of overload on a given line. So what you want is to describe the behaviour of a channel and thus create a channel model. (The Gilbert-Elliott model was designed for describing bit errors and not packet losses, but is also used for the latter which I also find more demonstrative)

A very simplistic channel model is the memoryless channel, sometimes also called Binary Symmetric Channel (BSC) or Poisson channel, but I don’t want to go into details why there exist different names for it. In this channel model, a packet is dropped with a certain probability p and not dropped with probability 1-p. This decision is made for every packet separately. Therefore, packet drops are independent and identically distributed (iid). Longer bursts (longer than 1 lost packet in sequence) only rarely occur.

However, this simplistic model is not adequate to model channels were bad channel conditions tend to persist, e.g. when considering packet drops caused by finite queueing systems in routers. In 1960, Gilbert published a paper where he proposes a model to describe burst noise channels. His model is based on a 2-state Markov chain and thus adds memory to the Binary Symmetric Channel. Roughly speaking, the memory of the chain allows to define a probability of a packet being lost of the previous packet was also lost and thus to generate error bursts. The model looks as follows:

The Gilbert-Elliott Model

It consists of two states: the good (G) and bad (B) channel state. There are two transition probabilities, p and r. A transition from the good to the bad state happens with probability p and from the bad to the good state with r. Each state generates an error free packet with probability k (h), respectively. So the Gilbert-Elliott model has four model parameters that need to be estimated during training.

However, there are three commonly used versions of the model that should be differentiated. Let’s start with the most simple model version which I tend to call just ‘Simple Gilbert’. It only consists of two model parameters, the transition probabilities p and r. The state dependent error probabilities are set to k=1 and h=0, leading to a good state that generates no errors at all whereas the bad state generates nothing but errors. Model parameters for the ‘Simple Gilbert’ model can be easily obtained from an packet loss trace, as the state sequence is directly observable.

The model Gilbert published in his paper consisted of three model parameters: p,r and h. Thus, the above described ‘Simple Gilbert’ model is just a simplification of what Gilbert has originally published. However, Gilbert suggests in this paper to set h to 0.5, but his model allows h to be in the interval [0,1]. So the original Gilbert model is more general than most of the simplifications which are also entitled ‘the Gilbert model’. Moreover, something interesting happens when allowing h to be different to 0–the concrete state sequence is no longer observable in the output generated by the model or contained in the loss trace, as it is not obvious whether the symbol “packet not dropped” has been generated by the good or bad state. As there exists a doubly embedded stochastic process now, the Gilbert model forms an Hidden Markov Model.

What about the error probability in the good state, 1-k? Well, I did not forget about it in the last paragraph, this model parameter simply does not exist in the Gilbert model and k is always set to 1. Gilbert left the extension to the model by including k and thus allowing errors to be generated in both states to Elliott (1963). Model parameters in the Gilbert-Elliott model are usually set such that the bad state generates loss bursts, whereas the good states generates rare, single packet drops.

However, I read some papers that were only dealing with the simplified version of the Gilbert model, but entitled it as ‘Gilbert-Elliott’. This is one of the misunderstandings I often find in the literature. Another one, which I found quite often, is the misspelled name of ‘Elliott’ where authors forgot about one t at the end of the name (I guess this finding is somewhat related to Did They Read What They Cited? *g*).

Original papers:

• E. N. Gilbert, “Capacity of a Burst-Noise Channel,” Bell System Technical Journal, vol. 39, pp. 1253–265, Sep. 1960.
• E. O. Elliott, “Estimates of Error Rates for Codes on Burst-Noise Channels,” Bell System Technical Journal, vol. 42, pp. 1977–1997, Sep. 1963.