· 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 + 2x + 3x² + ...
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 Pk(T) = [(lambda T)ke- 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 - P0(T)
= 1 - e- lambda T
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: CMN
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 = CSk
Number of ways to select N-k ordinary objects from M-S =CM-SN-k
Number of ways to select N objects from M =CMN
Therefore, probability of k special objects in a group of N =CSk
× CM-SN-k/CMN
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:
C31 × C21/C52 = 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 21 3 2 31 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.