A1.3 Discrete Probability Distributions

There are a number of probability distributions that will prove useful to us in the pursuit of software engineering measurement. These are grouped into two categories based on the nature of the random variables they represent. First there is the case of the discrete random variable that assumes a countable number of possible values. Second is the case where the random variable is continuous and can assume values from an interval of real numbers. There are a very large number of probability distributions. Some of these are more relevant to our software engineering investigations than others. There follows a discussion about three discrete probability distributions and four continuous probability distributions that are particularly relevant to our needs in this book.

A1.3.1 The Binomial Distribution

Many discrete events that we wish to model have only two possible outcomes. Consider the example of a program in test. The program will run successfully, Pr(x = S) = p, or it will fail during test, Pr(x = F) = 1 - p . After the program has been tested n times, the number of successful executions x in these tests is given by the probability function:

The mean of this distribution is:

μ = np

and the variance is:

σ² = np(1-p)

A1.3.2 The Multinomial Distribution

Let

where S_i is one of k mutually exclusive sets of events. Further, let Pr(S_i) = p_i and p_k = 1 - p₁ - p₂ - ... - p_k_-1. In this case, p_i is the probability that the outcome of a random experiment is an element of the set S_i. If this experiment is conducted over a period of n trials, then the random variable X_i will represent the frequency of S_i outcomes. Note that X_k = n - X₁ - X₂ - ... - X_k_-1

This particular distribution will be useful in the modeling of a program with a set of k modules. During a set of n program steps, each of the modules can be executed. These, of course, are mutually exclusive events. If module i is executing, then module j cannot be executing.

The multinomial distribution function for this execution scenario is given by:

where x_i represents the frequency of execution of the i^th program module.

The mean values for the x_i are given by:

μ₁ = np₁

μ₂ = np₂

•

μ_k = np_k

and the variances by

A1.3.3 The Poisson Distribution

Yet another discrete probability distribution that is used very frequently in modeling applications in the operating systems environment is the Poisson distribution. It is frequently used to model events of a temporal nature. For example, we might wish to model the number of I/O interrupts in a particular time interval t. The probability that there will be x such calls in an interval dependent on λ is:

where λ > 0. This distribution has the remarkable property that:

μ = σ² = λ

This interesting property greatly simplifies a number of queuing model scenarios.

This distribution raises an interesting specter. Sometimes, a probability distribution will be used for modeling purposes, not because we observe that nature has chosen that probability distribution but rather because it makes the modeling process much easier. Solutions of this nature are called Procrustean solutions after an ancient Greek who invented them. Old Procrustes, as the story goes, ran a motel in ancient Greece. He was most concerned about the comfort of his guests. Although all the beds in every room in his motel were the same size, not all of the guests were of a size to fit the beds. So, Procrustes hit upon an interesting solution. Those guests who were too tall for his beds, he simply cut off a little of the legs of these guests. Those guests who were too short, he put upon a rack and stretched them out a bit. The long and short of this story is that Procrustes made each person fit his beds. Similarly, queuing theorists tend to see all queuing problems in a Poisson light.