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.

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.