Gebali F. Analysis Of Computer And Communication Networks

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

1.25 Binomial RV 25

From Appendix A, the above equation becomes

E[n] =

(1 −b)

1.25 Binomial RV

Consider a chance experiment that has two mutually exclusive outcomes A and A

that occur with probabilities a and b, respectively. We define the discrete random

variable K which equals the number of times that A occurs in any order in N trials

or repetitions of the random experiment. We can write the pmf for this distribution as

p(K = k) =





N−k

for 0 ≤ k ≤ N (1.65)

where b = 1 − a. Basically, the probability of event A occurring k times during N

trials and not occurring for N −k times is a

N−k

, and the number of ways of this

event taking place is the binomial coefficient C(N, k).

Alternatively, p(k) can be expressed by a single equation in the form

p(k) =



i=0





N−i

(

k − i

)

for 0 ≤ k ≤ N (1.66)

The mean and variance for K are

μ = Na (1.67)

= Nab (1.68)

The binomial distribution is sometimes referred to as sampling with replacement

as, for example, when we have N objects and each one has a certain property (color,

for example). We pick an object, inspect its property, then place it back in the pop-

ulation. If the selected object is removed from the population after inspection, then

we would have the case of the hypergeometric distribution, which is also known as

sampling without replacement, but this is outside our present interest.

Example 1.19 Assume a classroom has n students. What are the chances that m

students have a birthday today?

The probability that a student has a birthday on a given day is a = 1/365 and the

probability that a student does not have a birthday on a given day is b = 1 − a =

364/365. The probability that m students have a birthday today is

p(m) =





n−m

26 1 Probability

For example, when n = 20 and m = 2, we get

p(2) =





= 1.35 ×10

−3

(1.69)

1.25.1 Approximating the Binomial Distribution

We saw in the binomial distribution that p(k)isgivenby

p(k) =





N−k

(1.70)

where b = 1 − a. When N is large, it becomes cumbersome to evaluate the above

equation. Several approximations exist for evaluating the binomial distribution using

simpler expressions. We discuss two techniques in the following two subsections.

DeMoivre-Laplace Theorem

We can approximate p(k) by the Gaussian distribution provided that the following

condition is satisfied [2].

nab 1 (1.71)

When this condition is true we can write

p(k) ≈

√

−(k−μ)

/σ

(1.72)

where we have to choose the two parameters μ and σ according to the following

two equations.

μ = Na (1.73)

σ =

√

2Nab (1.74)

The above approximation is known as the DeMoivre-Laplace Theorem and is

satisfactory even for moderate values of n such as when n ≈ 5.

Poisson Theorem

If Na is of the order of one (i.e., Na ≈ 1), then DeMoivre-Laplace approximation is

no longer valid. We can still obtain a relatively simple expressions for the binomial

distribution if the following condition applies [2].

na≈ 1 (1.75)

1.25 Binomial RV 27

When this condition is true we can write

p(k) ≈

(na)

−na

(1.76)

Thus we are able to replace the binomial distribution with the Poisson distribution

which is discussed in Section 1.26.

Example 1.20 A file is being downloaded from a remote site and 500 packets are

required to transmit the entire file. It has been estimated that on the average 5 percent

of received packets through the channel are in error. Determine the probability that

10 received packets are in error using the binomial distribution and its approxima-

tions using DeMoivre-Laplace and Poisson approximations.

The parameters for our binomial distribution are

N = 500

a = 0.05

b = 0.95

The probability that 5 packets are in error is

p(10) =



500



(0.05)

(0.95)

490

= 2.9165 ×10

−4

Use the DeMoivre-Laplace Theorem with the parameters

μ = Na= 25

σ =

√

Nab= 6.892

In that case, the required probability is

p(10) = 7.1762 ×10

−4

Use the Poisson Theorem which results in the probability

p(10) = 3.6498 ×10

−4

Under the above parameters, the Poisson approximation gives better results than

the DeMoivre-Laplace approximation.

28 1 Probability

1.26 Poisson RV

The Poisson distribution defines the probability p(k) that an event A occurs k times

during a certain interval. The probability is given by

p(K = k) =

−a

(1.77)

where a > 0 and k = 0, 1, ....

The parameter a in the above formula is usually expressed as

a = λ t

where λ is the rate of event A and t is usually thought of as time. Because we

talk about rates, we usually associate Poisson distribution with time or with aver-

age number of occurrences of an event. So let us derive the expression for Poisson

distribution based on this method of thinking.

Consider a chance experiment where an event A occurs at a rate λ events/second.

In a small time interval (⌬t), the probability that the event A occurs is p = λ⌬t.We

chose ⌬t so small so that event A occurs at most only once. For example, λ might

indicate the average number of packets arriving at a link per unit time. In that case,

the variable t will indicate time. λ might also refer to the average number of bits in

error for every 1000 bits, say. In that case, the variable t would indicate the number

of bits under consideration. In these situations, we express the parameter a in the

form a = λt, where λ expresses the rate of some event and t expresses the size or

the period under consideration.

Typically, the Poisson distribution is concerned with the probability that a spec-

ified number of occurrences of event A take place in a specified interval t.By

assuming a discrete random variable K that takes the values 0, 1, 2, ..., then the

probability that k events occur in a time t is given by

p(k) =

(

λt

)

−λt

(1.78)

Alternatively, p(k) can be expressed by a single equation in the form

p(k) =



i≥0

(λ t)

−λ t

δ(k −i)fork ≥ 0 (1.79)

The mean and variance for K are

μ = λ t (1.80)

= λ t (1.81)

1.26 Poisson RV 29

Deriving Poisson Distribution from Binomial Distribution

We saw in the binomial distribution that p(k)isgivenby

p(k) =





N−k

(1.82)

where b = 1 − a. When N is large, it becomes cumbersome to evaluate the above

equation. We can easily evaluate p(k) in the special case when the number of trials

N becomes very large and a becomes very small such that

Na= μ (1.83)

where μ is non-zero and finite. This gives rise to Poisson distribution

p(k) = lim

N→∞,a→0





N−k

≈

(

)

−μ

(1.84)

We can prove the above equation using the following two simplifying expres-

sions. We start by using Stirling’s formula

N! ≈

√

2π N

−N

(1.85)

and the following limit from calculus

lim

N→∞

(1 −

)

= e

−a

(1.86)

Using the above two expressions, we can write [10]

p(k) =





N−k

(1.87)

k!(N −k)!

(1 −b)

N−k

(1.88)

−N

(

N − k

)

N−k

−

(

N−k

)







1 −



N−k

(1.89)



N −k



N−k



1 −



N−k

(1.90)

≈

−μ

(1.91)

where μ = Na. This gives the expression for the Poisson distribution. This is

especially true when N > 50 and a < 0.1 in the binomial distribution.

30 1 Probability

Example 1.21 Packets arrive at a device at an average rate of 500 packets per sec-

ond. Determine the probability that four packets arrive during 3 ms.

We have λ = 500, t = 3 ×10

−3

and k = 4

p(4) =

(

1.5

)

−1.5

= 4.7 ×10

−2

1.27 Systems with Many Random Variables

We reviewed in Section 1.11 the concept of a random variable where the outcome of

a random experiment is mapped to a single number. Here, we consider random ex-

periments whose output is mapped to two or more numbers. Many systems based on

random phenomena are best studied using the concept of multiple random variables.

For example, signals coming from a Quadrature Amplitude Modulation (QAM) sys-

tem are described by the equation

v(t) = a cos(ωt + φ) (1.92)

Incoming digital signals are modulated by assigning different values to a and φ.

In that sense, QAM modulation combines amplitude and phase modulation tech-

niques. The above signal contains two pieces of information: viz, the amplitude a

and the phase φ that correspond to two random numbers A and ⌽. So every time

we sample the signal v(t), we have to find two values for the associated random

variables A and ⌽.

Figure 1.15 graphically shows the sequence of events leading to assigning mul-

tiple numerical values to the outcome of a random experiment. First we run the

experiment then we observe the resulting outcome. Each outcome is assigned mul-

tiple numerical values.

As an example, we could monitor the random events of packet arrival at the input

of a switch. Several outcomes of this random event could be observed such as (1)

packet length; (2) packet type (voice, video, data, etc.); (3) interarrival time—i.e.

the time interval between arriving packets; and (4) destination address. In these

situations, we might want to study the relationships between these random variables

in order to understand the underlying characteristics of the random experiment we

are studying.

Random

Experiment

Random

Outcome

Corresponding

Number: x, y, ...

Mapping

Function

Fig. 1.15 The sequence of events leading to assigning multiple numerical values to the outcome

of a random experiment

1.28 Joint cdf and pdf 31

1.28 Joint cdf and pdf

Assume our random experiment gives rise to two discrete random variables X and

Y . We define the joint cdf of X and Y as

(x, y) = p(X ≤ x, Y ≤ y) (1.93)

When the two random variables are independent, we can write

p(X ≤ x, Y ≤ y) = p(X ≤ x) p(Y ≤ y) (1.94)

Thus for independent random variables the joint cdf is simply the product of the

individual cdf’s.

(

x, y

)

= F

(

)

(

)

(1.95)

For continuous RVs, the joint pdf is defined as

(x, y) =

⭸

⭸x ⭸y

(1.96)

The joint pdf satisfies the following relation.



x,y

(x, y) dx dy = 1 (1.97)

The two random variables are independent when the joint pdf can be expressed

as the product of the individual pdf’s.

(x, y) = f

(x) f

(y) (1.98)

For discrete RVs, the joint pmf is defined as the probability that X = x and

Y = y

(x, y) = p(X = x, Y = y) (1.99)

The joint pmf satisfies the following relation.



(x, y) = 1 (1.100)

Two random variables are independent when the joint pmf can be expressed as

the product of the individual pmf’s.

(x, y) = p(X = x) p(Y = y) (1.101)

32 1 Probability

Example 1.22 Assume arriving packets are classified according to two properties:

packet length (short or long) and packet type (voice or data). Random variable X =

0, 1 is used to describe packet length and random variable Y = 0, 1isusedto

describe packet type. The probability that the received packet is short is 0.9 and

probability that it is long is 0.1. When a packet is short, the probability that it is a

voice packet is 0.4 and probability that it is a data packet is 0.6. When a packet is

long, the probability that it is a voice packet is 0.05 and probability that it is a data

packet is 0.95. Find the joint pmf of X and Y .

We have the mapping:

X =



0 short packet

1 long packet

Y =



0 voice packet

1 data packet

Based on the above mapping, and assuming independent RVs, we get

(0, 0) = 0.9 ×0.4 = 0.36

(0, 1) = 0.9 ×0.6 = 0.54

(1, 0) = 0.1 ×0.05 = 0.005

(1, 1) = 0.1 ×0.95 = 0.095

Note that the sum of all the probabilities must add up to 1.

1.29 Individual pmf From a Given Joint pmf

Sometimes we want to study an individual random variable even though our random

experiment generates multiple RVs. An individual random variable is described by

its pmf which is obtained as

(x) = p(X = x) (1.102)

If our random experiment generates two RVs X and Y, then we have two indi-

vidual pmf’s given by

(x) =



(x, y) (1.103)

(y) =



(x, y) (1.104)

1.30 Expected Value 33

From the definition of pmf we must have



(x) = 1 (1.105)



(y) = 1 (1.106)

Example 1.23 Assume a random experiment that generates two random variables

X and Y with the given joint pmf.

(x, y) x = 1 x = 2 x = 3

y = 00.10.05 0.1

y = 30.10.05 0

y = 70 0.10.1

y = 90.20 0.2

Find the individual pmf for X and Y.AreX and Y independent RVs?

We have

(x) x = 1 x = 2 x = 3

0.4 0.2 0.4

and

(y) y = 0 y = 3 y = 7 y = 9

0.25 0.15 0.2 0.4

1.30 Expected Value

The joint pmf helps us find the expected value of one of the random variables.

= E(X) =



(x, y) (1.107)

Example 1.24 Using values in Example 1.23, find the expected values for the ran-

dom variables X and Y .

We can write

= 1 ×0.4 +2 ×0.2 +3 ×0.4 = 2

= 0 ×0.25 +3 ×0.15 +7 ×0.2 +9 ×0.4 = 5.45

34 1 Probability

1.31 Correlation

The correlation between two random variables is defined as

= E[XY]



xyp

(x, y) (1.108)

We say that the two random variables X and Y are orthogonal when r

= 0.

1.32 Variance

The variance of a random variable is defined as

= E[(X −μ

)

]



(x −μ

)

(x, y) (1.109)

The following equation can be easily proven.

= E[X

] −μ

(1.110)

1.33 Covariance

The covariance between two random variables is defined as

= E[(X −μ

)(Y −μ

)]



(x −μ

)(y − μ

) p

(x, y) (1.111)

The following equation can be easily proven.

= r

−μ

(1.112)

We say that the two random variables X and Y are uncorrelated when c

= 0.

The correlation coefficient ρ

is defined as

= c



(1.113)