· Continuous Probability and the Exponential Distribution

· Combinations and Permutations

We calculate the probability of an event occurring by counting the number of cases in which it occurs, and dividing by the total of all possible cases. For example, a probability of 0.8 (or, 80%) means that out of 10 cases, the event occurs in only 8.

When events occur independently of each other, the probability of both events occurring in a single trial is just the product of their individual probabilities of occurring in that trial. For example, suppose a transmission requires 2 hops in a network where the probability of an error-free 1st hop is 0.7 and the probability of an error-free 2nd hop is 0.8. If we assume that errors at each hop are independent of each other (open to argument!), and since an error-free transmission requires both an error-free 1st hop and an error-free 2nd hop, then the probability of an error-free transmission is 0.8 × 0.7 = 0.56, the product of the individual probabilities.

As another example, suppose that a pair of network nodes communicate with packets and that the 2 nodes are connected by 2 parallel communication lines, one with a probability of 0.2, and the other with a probability of 0.3, of a packet error during transmission. Supposing that, once again, errors occur independently, and that each packet is transmitted over both communication lines simultaneously. What is the probability of a packet being received correctly?

There are 4 possible cases: (1) errors on both lines, (2) no errors on either line, (3) error on line 1 but not on line 2, and (4) no error on line 1, but an error on line 2. The cases of interest are (2), (3) and (4), in which one or both packets is received correctly. The simplest approach here is to calculate the probability of case (1), and then subtract it from 1 to obtain the total probability of the remaining cases of interest: 1 - 0.2 × 0.3 = 0.94.

A special case of calculating the
probability of independent trials has to do with calculating a Packet Error
Rate from Packet Size and Bit Error Rate. For example, given a Bit Error Rate
(i.e. probability that a bit is transmitted erroneously) of 10^{-4} and
given a packet of 100 bits, what is the Packet Error Rate (i.e. the probability
that a packet is transmitted erroneously)?

The probability of a correct packet is
the probability that every bit is correct = (1 - 10^{-4})^{100}.

The Binomial Theorem gives an approximation for this term:

(1 - 10^{-4})^{100} = 1 - 100 × 10^{-4}
+ 100×99/2! × 10^{-8} - ....

in which successive terms decrease in absolute value by about 2 orders of magnitude. An approximation for the Packet Error Rate can therefore be obtained from just the first 2 terms of the Binomial Expansion:

Probability of a correct Packet __~__
1 - 100 × 10^{-4} = 0.99

Therefore, Packet Error Rate = 1 -
Probability of a correct packet __~__ 1 - 0.99 = 0.01

This approximation of (1 - *p*)^{n}__~__ 1 - *p*×*n* is valid only when *p* << *n*.

Given the probability of succes in any one trial of a series of independent trials, we can calculate the mean number of attempts needed for success:

Let *p* = probability of success on
any attempt.

Therefore, probability of failure on any
attempt = 1 - *p*

The probability of success on the very first
trial= *p*

The probability of success only after 2 trials means:

a
failure followed by a success, probability= (1-*p*)×*p*

The probability of success only after 3 trials means:

2
failures followed by a success, probability= (1-*p*)²×*p*

The probability of success
only after *n* trials means:

*n*-1
failures followed by a success, probability= (1-*p*)^{n}^{-1}×*p*

The Mean Number of Attempts before eventual success is calculated by multiplying each number of attempts by its probability, and then summing:

1×*p* + 2×(1-*p*)×*p* + 3×(1-*p*)²×*p*
+ ... + *n*×(1-*p*)^{n}^{-1}×*p*
+ ...

The formula for summing an infinite geometric progression is:

1/(1-*x*) = 1 + *x* + *x*² + *x*³
+ ... when *x* < 1

Taking the derivative of
both sides gives: 1/(1-*x*)² = 1 + 2*x* + 3*x*² + ...

so, setting *x* = 1 - *p*, and
multiplying both sides by *p*:

1/*p* = 1×*p* + 2×(1-*p*)×*p*
+ 3×(1-*p*)²×*p* + ...

which matches the expression above for the Mean Number of Attempts before eventual success.

Therefore, Mean Number of Attempts before
eventual success = 1/*p*

where *p* is the probability of success on any attempt.

In situations where we
need to estimate the probability of a real variable taking on values less than
or equal to some bound, we need the idea of a *Probability Distribution
Function*:

A Probability
Distribution function, *P[x <= T]*, is the probability that a
randomly distributed variable, *x*, takes on a value less than or equal
to real value *T*.

We can plot function *P[x
<= T]* with *T* values on the x-axis, and probability values
(from 0 to 1) on the y-axis. It is a monotonically increasing function. (There
is a related non-monotonic function, the *Probability Density Function*,
which is the derivative of the Probability Density Function.)

There are various probability
distribution functions, but we are most interested in the *Exponential
Distribution*, which results from *Poisson Distributed* events.
Informally, Poisson Distributed events correspond to naturally occuring random
events in time. For example, the number of clicks per unit time on a Geiger
Counter, or the number of raindrops falling per unit time, are Poisson
Distributed events. In a sense, they are random with the property that the
longer you wait, the more of them happen. The Exponential Distribution is the
probability distribution for inter-event times between Poisson Distributed
events.

The Exponential Distribution simplifies analyses of communication systems where we assume that events such as arrivals of packets, or attempts to transmit, are Poisson Distributed. Here is the definition of the Poisson Distribution:

Probability of *k* events occuring in a
period of time *T* is *P _{k}(T) = [(lambda T)^{k}e^{-
lambda T}]/k!*

where *lambda*
is the *Mean Arrival Rate* of events, with units of *per time*.

The Exponential Distribution is the
probability of 1 or more events in a period of time *T*

= 1 - *P _{0}(T)*

= 1 -

By observing the behavior of the
Exponential Distribution, you can verify that: when *T*=0, the
probability of an event is 0; and, when *T*->*infinity*, the
probability of an event ->1. These two facts correspond with intuition about
the behavior of random events occurring in nature.

An important property of the Exponential Distribution is that it simplifies the analysis of simple first-come first-served queues. It turns out that when customers (i.e. packets) arrive at random with exponentially distributed inter-arrival periods, and when the customers have exponentially distributed random service (i.e. processing) periods, then the following simple formulas relate mean queue length, and mean time spent awaiting service.

Let *lambda* be
the mean arrival rate, and let µ be the mean service rate. Then:

Mean
queue length (including the customer currently begin served), *N = lambda /
(µ - lambda)*

Mean time spent in the queue + time spent being served, *T = 1 / (µ -
lambda)*

When selecting *N*
different objects, 1 at a time, the number of possible sequences in which the
selection can be made is *N!* (*N* factorial). If there are *M*
different objects available for selection, then the number of possible
sequences becomes. *M!/(M-N)!*. If the order in which the objects are
selected does not matter, but only which objects are selected, then the number
of possible combinations of selected objects is obtained by dividing the number
of sequences by the number of permutations of the *N* selected objects: *M!/[(M-N)!×N!]*
which is often expressed in the following equivalent Binomial Coefficient
notation: **C**^{M}_{N}

Suppose now that the original group
of *M* objects contains 2 kinds of objects- *S* special objects
and *M-S* ordinary objects. What is the probability that a group of *N*
objects selected at random from the *M* objects contains exactly *k*
special objects and *N-k* ordinary ones?

Number of ways to select *k*
special objects from *S* = **C**^{S}_{k}

Number of ways to select *N-k* ordinary objects from *M-S* =**C**^{M-S}_{N-k}

Number of ways to select *N* objects from *M* =**C**^{M}_{N}

Therefore, probability of *k* special objects in a group of *N* =**C*** ^{S}_{k}*
×

Let us verify this formula with a
numerical example. Suppose that in a group of *M*=5 balls there are *S*=3
black ones and 2 white ones. Suppose that we intend to pick *N*=2 balls
at random from the 5. What is the probability that we pick 1 white one and 1
black one? According to the formula above, the probability we seek is:

**C**^{3}_{1} × **C**^{2}_{1}/**C**^{5}_{2}
= 3×2/(5×4/2) = 0.6

To verify this, suppose that balls 1, 2 and 3 are black, and balls 4 and 5 are white. The following 10 pairs are possible, with the combinations of interest (1 black and 1 white) starred:

` `

`1 2`

`1 3 2 3`

`1 4 `^{*} 2 4 ^{*} 3 4 ^{*}

`1 5 `^{*} 2 5 ^{*} 3 5 ^{*} 4 5

This gives a total of 6 starred cases out of 10 possible cases, i.e. probability 0.6, which verifies the formula above.