Gebali F. Analysis Of Computer And Communication Networks

Подождите немного. Документ загружается.

1.5 Permutations 5

Example 1.3 A die is thrown three times and the sequence of numbers is recorded.

Determine the number of 3-digit sequences that could result.

We perform three experiments where each one is the act of throwing the die.

One possible outcome would be the number sequence 312, which corresponds to

obtaining 3 on the first throw, 1 on the second, and 2 on the third. The number of

outcomes of each experiment is 6. Therefore, the total number of outcomes is

N = 6 ×6 ×6 = 216

Example 1.4 In time division multiplexing (also known as synchronous transmis-

sion mode), each slot in a frame is reserved to a certain user. That slot could be

occupied or empty when the user is busy or idle, respectively. Assuming the frame

consists of 10 slots, how many slot occupancy patterns can be received in a single

frame?

Each time slot can be treated as an experiment with only two outcomes, busy or

idle. The experiment is repeated 10 times to form the frame. The total number of

possible outcomes is

N = 2

= 1024

1.5 Permutations

Permutations arise when we are given n objects and we want to arrange them accord-

ing to a certain order. In other words, we arrange the objects by randomly picking

one, then the next, etc. We have n choices for picking the first item, n − 1 choices

for picking the second item, etc.

1.5.1 n Distinct Objects Taken n at a Time

The number of permutations of n distinct objects taken n at a time is denoted by

P(n, n) and is given by

P(n, n) = n! = n ×(n − 1) ×(n − 2) ×···×3 ×2 ×1

The function n! is called Factorial-n and can be obtained using the MATLAB func-

tion factorial(n).

Example 1.5 Packets are sent through the Internet in sequence; however, they are

received out of sequence since each packet could be sent through a different route.

How many ways can a 5-packet sequence be received?

6 1 Probability

If we number our packets as 1, 2, 3, 4, and 5, then one possible sequence of

received packets could be 12543 when packet 1 arrives first followed by packet 2,

then packet 5, etc. The number of possible received packet sequences is given by

P(5, 5) = 5! = 120

1.5.2 n Distinct Objects Taken k at a Time

A different situation arises when we have n distinct objects but we only pick k

objects to arrange. In that case, the number of permutations of n distinct objects

taken k at a time is given by

P(n, k) = n ×(n − 1) ×···×(n −k +1)

(n − k)!

(1.2)

Example 1.6 Assume that 10 packets are sent in sequence, but they are out of se-

quence when they are received. If we observe only a 3-packet sequence, how many

3-packet sequences could we find?

A possible observed packet arrival sequence could be 295. Another might be 024,

etc. We have n = 10 and k = 3.

P(10, 3) =

10!

= 720

1.6 Permutations of Objects in Groups

Now, assume we have n objects in which n

objects are alike, n

objects are alike,

and so on, and n

objects are alike such that

n =



i=1

(1.3)

Here we classify the objects not by their individual labels but by the group in which

they belong. An output sequence will be distinguishable from another if the objects

picked happen to belong to different groups. As a simple example, suppose we have

20 balls that could be colored red, green, or blue. We are now interested not in

picking a particular ball, but in picking a ball of a certain color.

1.6 Permutations of Objects in Groups 7

In that case, the number of permutations of these n objects taken n at a time is

given by

x =

! n

! ··· n

(1.4)

This number is smaller than P(n, n) since several of the objects are alike and this

reduces the number of distinguishable combinations.

Example 1.7 Packets arriving at a terminal could be one of three possible service

classes: class A, class B, or class C. Assume that we received 10 packets and we

found out that there were 2 packets in class A, 5 in class B, and 3 in class C. How

many possible service class arrival order could we have received?

We are not interested here in the sequence of received packets. Instead, we are

interested only in the arrival order of the service classes.

We have n

= 2, n

= 5, and n

= 3 such that n = 10. The number of service

class patterns is

x =

10!

2! 5! 3!

= 2, 520

In other words, there are 10 possibilities for receiving 10 packets such that ex-

actly 2 of them belonged to class A, 5 belonged to class B, and 3 belonged to class C.

Example 1.8 In time division multiplexing, each time slot in a frame is reserved to

a certain user. That time slot could be occupied or empty when the user is busy or

idle, respectively. If we know that each frame contains 10 time slots and 4 users

are active and 6 are idle, how many possible active slot patterns could have been

received?

We are interested here in finding the different ways we could have received 4

active slots out of 10 possible slots. Thus we “color” our slots as active or idle

without regard to their location in the frame.

We have n

= 4 and n

= 6 such that n = 10.

x =

10!

4! 6!

= 210

Example 1.9 A bucket contains 10 marbles. There are 5 red marbles, 2 green mar-

bles, and 3 blue marbles. How many different color permutations could result if we

arranged the marbles in one straight line?

We have n

= 5, n

= 2, and n

= 3 such that n = 10. The number of different

color permutations is

x =

10!

5! 2! 3!

= 2, 520

8 1 Probability

1.7 Combinations

The above permutations took the order of choosing the objects into consideration. If

the order of choosing the objects is not taken into consideration then combinations

are obtained.

The number of combinations of n objects taken k at a time is called the binomial

coefficient and is given by

C(n, k) =





k!(n − k)!

(1.5)

MATLAB has the function nchoosek (n,k) for evaluating the above equation

where 0 ≤ k ≤ n.

Example 1.10 Assume 10 packets are received with 2 packets in error. How many

combinations are there for this situation?

We have n = 10 and k = 2.

C(10, 2) =





10!

2! 8!

= 45

Example 1.11 Assume 50 packets are received but 4 packets are received out of

sequence. How many combinations are there for this situation?

We have n = 50 and k = 4.

C(50, 4) =





50!

4! 46!

= 230, 300

1.8 Probability

We define probability using the relative-frequency approach. Suppose we perform

an experiment like the tossing of a coin for N times. We define event A is when the

coin lands head up and define N

as the number of times that event A occurs when

the coin tossing experiment is repeated N times. Then the probability that we will

get a head when the coin is tossed is given by

p(A) = lim

N→∞

(1.6)

This equation defines the relative frequency that event A happens.

1.10 Other Probability Relationships 9

1.9 Axioms of Probability

We defined our sample space S as the set of all possible outcomes of an experiment.

An impossible outcome defines the empty set or null event ∅. Based on this we can

state four basic axioms for the probability.

1. The probability p(A)ofaneventA is a nonnegative fraction in the range 0 ≤

p(A) ≤ 1. This can be deduced from the basic definition of probability in (1.6).

2. The probability of the null event ∅ is zero, p(∅) = 0.

3. The probability of all possible events S is unity, p(S) = 1.

4. If A and B are mutually exclusive events (cannot happen at the same time), then

the probability that event Aorevent B occurs is

p(A ∪ B) = p(A) + p(B) (1.7)

Event E and its complement E

are mutually exclusive. By applying the above

axioms of probability, we can write

p(E) + p(E

) = 1 (1.8)

p(E ∩ E

) = 0 (1.9)

1.10 Other Probability Relationships

If A and B are two events (they need not be mutually exclusive), then the probability

that event A or event B occurring is

p(A ∪ B) = p(A) + p(B) − p(A ∩ B) (1.10)

The probability that event A occurs given that event B occurred is denoted by

P(A|B) and is sometimes referred to as the probability of A conditioned by B.This

is given by

p(A|B) =

p(A ∩ B)

p(B)

(1.11)

Now, if A and B are two independent events, then we can write p(A|B) = p(A)

because the probability of event A taking place will not change whether event B

occurs or not. From the above equation we can now write the probability that event

A and event B occurs is

p(A ∩ B) = p(A) × p(B) (1.12)

provided that the two events are independent.

10 1 Probability

The probability of the complement of an event is given by

p(A

) = 1 − p(A) (1.13)

1.11 Random Variables

Many systems based on random phenomena are best studied using the concept of

random variables. A random variable allows us to employ mathematical and numer-

ical techniques to study the phenomenon of interest. For example, measuring the

length of packets arriving at random at the input of a switch produces as outcome a

number that corresponds to the length of that packet.

According to references [1–4], a random variable is simply a numerical descrip-

tion of the outcome of a random experiment. We are free to choose the function

that maps or assigns a numerical value to each outcome depending on the situa-

tion at hand. Later, we shall see that the choice of this function is rather obvious

in most situations. Figure 1.3 graphically shows the steps leading to assigning a

numerical value to the outcome of a random experiment. First we run the experi-

ment, then we observe the resulting outcome. Each outcome is assigned a numerical

value.

Assigning a numerical value to the outcome of a random experiment allows us to

develop uniform analysis for many types of experiments independent of the nature

of their specific outcomes [1].

We denote a random variable by a capital letter (the name of the function) and

any particular value of the random variable is denoted by a lower case letter (the

value of the function).

The following are the examples of random variables and their numerical values.

1. Number of arriving packets at a given time instance is an example of a discrete

random variable N with possible values n = 0, 1, 2, ···.

2. Tossing a coin and assigning 0 when a tail is obtained and 1 when a head is

obtained is an example of a discrete random variable X with values x ∈{0, 1}.

3. The weight of a car in kilograms is an example of a continuous random variable

W with values in the range 1000 ≤ w ≤ 2000 kg typically.

4. The temperature of a day at noon is an example of random variable T .This

random variable could be discrete of continuous depending on the type of ther-

mometer (analog or digital).

Random

Experiment

Random

Outcome

Corresponding

Number: x

Mapping

Function

Fig. 1.3 The steps leading to assigning a numerical value to the outcome of a random experiment

1.12 Cumulative Distribution Function (cdf) 11

5. The atmospheric pressure at a given location is an example of a random vari-

able P. This random variable could be discrete of continuous depending on the

accuracy of the barometer (analog or digital).

1.12 Cumulative Distribution Function (cdf)

The cumulative distribution function (cdf) for a random variable X is denoted by

(x) and is defined as the probability that the random variable is less than or equal

to x. Thus the event of interest is X ≤ x and we can write

(x) = p(X ≤ x) (1.14)

The subscript X denotes the random variable associated with the function while

the argument x denotes a numerical value. For simplicity we shall drop the subscript

and write F(x) when we are dealing with a single random variable and there is no

chance of confusion. Because F(x) is a probability, it must have the same properties

of probabilities. In addition, F(x) has other properties as shown below.

F(−∞) = 0 (1.15)

F(∞) = 1 (1.16)

0 ≤ F(x) ≤ 1 (1.17)

F(x

) ≤ F(x

) whenx

≤ x

(1.18)

p(x

< X ≤ x

) = F(x

) − F(x

) (1.19)

The cdf is a monotonically increasing function of x. From the last equation, the

probability that x lies in the region x

< x ≤ x

+ (where  is arbitrarily small) is

given by

p(x

< X ≤ x

+) = F(x

+) − F(x

) (1.20)

Thus the amount of jump in cdf at x = x

is the probability that x = x

Example 1.12 Consider the random experiment of spinning a pointer around a cir-

cle and measuring the angle it makes when it stops. Plot the cdf F

⌰

(θ).

Obviously, the random variable ⌰ is continuous since the pointer could point

at any angle. The range of values for θ is between 0

◦

and 360

◦

. Thus the function

⌰

(θ) has the following extreme values

(

−0

◦

)

= p

(

θ ≤−0

◦

)

= 0

(

360

◦

)

= p

(

θ ≤ 360

◦

)

= 1

There is no preference for the pointer to settle at any angle in particular and the

cdf will have the distribution as shown in Fig. 1.4.

12 1 Probability

Fig. 1.4 Cumulative

distribution function for a

continuous random variable

360

(θ)

1.12.1 cdf in the Discrete Case

For the case of a discrete random variable, we make use of the cdf property in

(1.20). The cdf for a discrete random variable will be a staircase as illustrated in the

following example.

Example 1.13 Consider again the case of the spinning pointer experiment but define

the discrete random variable Q which identifies the quadrant in which the pointer

rests in. The quadrants are assigned the numerical values 1, 2, 3, and 4. Thus the

random variable Q will have the values q = 1, 2, 3, or 4.

Since the pointer has equal probability of stopping in any quadrant, we can write

p(q = 1) =

p(q = 2) =

p(q = 3) =

p(q = 4) =

The cdf for this experiment is shown in Fig. 1.5.

Fig. 1.5 Cumulative

distribution function for a

discrete random variable

(q)

01234

0.5

1.14 Probability Mass Function 13

1.13 Probability Density Function (pdf)

The probability density function (pdf) for a continuous random variable X is de-

noted by f

(x) and is defined as the derivative of F

(x)

(x) =

(x)

(1.21)

Because F

(x) is a monotonically increasing function of x, we conclude that

(x) will never be negative. It can, however, be zero or even greater than 1.

We will follow our simplifying convention of dropping the subscript when there

is no chance of confusion and write the pdf as f (x) instead of f

(x). By integrating

the above equation, we obtain



f (x) dx = F(x

) − F(x

) (1.22)

Thus we can write

p(x

< X ≤ x

) =



f (x) dx (1.23)

The area under the pdf curve is the probability p(x

< X ≤ x

)

f (x) has the following properties:

f (x) ≥ 0 for all x (1.24)



∞

−∞

f (x) dx = 1 (1.25)



−∞

f (y) dy = F(x) (1.26)



f (x) dx = p(x

< X ≤ x

) (1.27)

f (x) dx = p(x < X ≤ x + dx) (1.28)

1.14 Probability Mass Function

For the case of a discrete random variable, the cdf is discontinuous in the shape of a

staircase. Therefore, its slope will be zero everywhere except at the discontinuities

where it will be infinite.

The pdf in the discrete case is called the probability mass function (pmf) [5]. The

pmf is defined as the probability that the random variable X has the value x and is

denoted by p

(x). We can write

(x) ≡ p(X = x) (1.29)

14 1 Probability

(θ)

(q)

1/4

1/360

360

(a) (b)

4321

Fig. 1.6 Continuous and discrete random variables. (a) pdf for the continuous case. (b) pmf for

the discrete case

where the expression on the right-hand side (RHS) indicates the probability that the

random variable X has the value x.

We will follow our simplifying convention of dropping the subscript when there

is no chance of confusion and write the pmf as p(x) instead of p

(x). p

(x) has the

following properties:

(x) ≥ 0 for all x (1.30)



(x) = 1 (1.31)

Example 1.14 The pointer spinning experiment was considered for the continuous

case (Example 1.12) and the discrete case (Example 1.13). Plot the pdf for the

continuous random variable ⌰ and the corresponding pmf for the discrete random

variable Q.

Figure 1.6(a) shows the pdf for the continuous case where the random variable

⌰ measures the angle of the pointer. Figure 1.6(b) shows the pmf for the discrete

case where the random variable Q measures the quadrant where the pointer is

located.

1.15 Expected Value and Variance

The pdf and pmf we obtained above help us find the expected value E

[

]

of a

random variable X. For the continuous case, the expected value is given by

[

]



∞

−∞

xf(x) dx (1.32)

For the discrete case, the expected value is given by the weighted sum

[

]



p(x

) (1.33)