Gebali F. Analysis Of Computer And Communication Networks

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

1.34 Transforming Random Variables 35

When we are dealing with two random variables obtained from the same random

process, the correlation coefficient would be written as

X(n)

= c

(n)/σ

(1.114)

We expect that the correlation coefficient would decrease as the value of n becomes

large to indicate that the random process “forgets” its past values.

1.34 Transforming Random Variables

Mathematical packages usually have functions for generating random numbers

following the uniform and normal distributions only. However, when we are sim-

ulating communication systems, we need to generate network traffic that follows

other types of distributions. How can we do that? Well, we can do that through

transforming random variables, which is the subject of this section. Section 1.35

will show how to actually generate the random numbers using the techniques of this

section.

1.34.1 Continuous Case

Suppose we have a random variable X with known pdf and cdf and we have another

random variable Y that is a function of X

Y = g(X) (1.115)

X is named the source random variable and Y is named the target random vari-

able. We are interested in finding the pdf and cdf of Y when the pdf and cdf of X are

known. The probability that X lies in the range x and x +dx is given from (1.28) by

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

(x) dx (1.116)

But this probability must equal the probability that Y lies in the range y and

y + dy. Thus we can write

(y) dy = f

(x) dx (1.117)

where f

(y) is the pdf for the random variable Y and it was assumed that the func-

tion g was monotonically increasing with x.Ifg was monotonically decreasing with

x, then we would have

(y) dy =−f

(x) dx (1.118)

36 1 Probability

The above two equations define the fundamental law of probabilities, which is

given by

(y) dy

(x) dx

(1.119)

(y) = f

(x)



(1.120)

since f

(y) and f

(x) are always positive.

In the discrete case the fundamental law of probability gives

(y) = p

(x) (1.121)

where p

(x) is the given pmf of the source random variable and p

(y) is the pmf

of the target random variable.

Example 1.25 Given the random variable X whose pdf has the form

(x) = e

−x

x ≥ 0 (1.122)

Find the pdf for the random variable Y that is related to X by the relation

Y = X

(1.123)

We have

x =±

√

y (1.124)

=±

√

(1.125)

From (1.120) we can write

(y) =

√

×e

−x

(1.126)

By substituting the value of x in terms of y, we get

(y) =

√

−y

y ≥ 0 (1.127)

Example 1.26 Assume the sinusoidal signal

x = cos ωt

1.34 Transforming Random Variables 37

where the signal has a random frequency ω that varies uniformly in the range ω

≤

ω ≤ ω

. The frequency is represented by the random variable ⍀. What are the

expected values for the random variables ⍀ and X?

We can write

⍀

= 1/

(

−ω

)

and E[⍀] is given by the expression

E[⍀] =

−ω



ω dω (1.128)

+ω

(1.129)

We need to find f

and E[X]. For that we use the fundamental law of probability.

First, we know that −1 ≤ x ≤ 1 from the definition of the sine function, so f

(

)

0for

> 1. Now we can write

(

)

= f

⍀

(

)



dω



≤ 1 (1.130)

Now

ω =

cos

−1

x (1.131)

and



dω



√

1 − x

≤ 1 (1.132)

Thus we get

(

)

−ω

√

1 − x

≤ 1 (1.133)

The expected value for X is given by

E[X] =

(

−ω

)



−1

√

1 − x

dx = 0 (1.134)

due to the odd symmetry of the function being integrated.

Example 1.27 Suppose our source random variable is uniformly distributed and our

target random variable Y is to have a pdf given by

(

)

= λe

−λy

λ>0 (1.135)

38 1 Probability

Derive Y as a function of X.

This example is fundamentally important since it shows how we can find the

transformation that allows us to obtain random numbers following a desired pdf

given the random numbers for the uniform distribution. This point will be further

discussed in the next section.

We use (1.120) to write

λe

−λy

= f

(

)



(1.136)

Assume the source random variable X is confined to the range 0–1. From Section

1.17 we have f

(

)

= 1 and we can write

λe

−λy

(1.137)

By integrating (1.137), we get

−λy

= x (1.138)

and we obtain the dependence of Y on X as

Y = g(X) =−

ln X

0 ≤ x ≤ 1 (1.139)

1.34.2 Discrete Case

In the discrete case the fundamental law of probability gives

(y) = p

(x) (1.140)

where p

(x) is the given pmf of the source random variable and p

(y) is the pmf

of the target random variable. The values of Y are related to the values of X by the

equation

Y = g(X) (1.141)

The procedure for deriving the pmf for Y given the pmf for X is summarized as

follows:

1. For each value of x obtain the corresponding value p(X = x) through observa-

tion or modeling.

2. Calculate y = g(x).

3. Associate y with the probability p(X = x).

1.35 Generating Random Numbers 39

1.35 Generating Random Numbers

We review briefly in this section how to generate sequences of random numbers

obeying one of the distributions discussed in the previous section. This background

is useful to know even if packages exist that fulfill our objective.

Before we start, we are reminded of Von Neumann’s remark on the topic:

Anyone who considers arithmetical methods of producing random digits is, of course, in a

state of sin. (John Von Neumann 1951)

1.35.1 Uniform Distribution

To generate a sequence of integer random numbers obeying the uniform distribu-

tion using C programming, one invokes the function srand(seed). This function

returns an integer in the range 0 to RAND

MAX [11]. When a continuous random

number is desired, drand is used. The function rand in MATLAB is used to

generate random numbers having uniform distribution.

1.35.2 Inversion Method

To generate a number obeying a given distribution, we rely on the fundamental law

of probabilities summarized by (1.120). When X has a uniform distribution over the

range 0 ≤ x ≤ 1, we can use the following procedure for obtaining y. We have

= f

(

)

(1.142)

where f (x) = 1 and f (y) is the function describing the pdf of the target distribution.

By integrating (1.142), we get



f (z) dz = x (1.143)

Thus we have

F(y) = x (1.144)

y = F

−1

(x) (1.145)

The procedure then to obtain the random numbers corresponding to y is to generate

x according to any standard random number generator producing a uniform distri-

bution. Then use the above equation to provide us with y. Thus the target random

number value y is obtained according to the following steps:

40 1 Probability

Fig. 1.16 Transformation

method for finding y given x

F(y)

Input x

Output y

1. Obtain the source random number x having a uniform distribution.

2. Lookup the value of F(y) that is numerically equal to x according to (1.144).

F(y) is either computed or stored in a lookup table.

3. Find the corresponding value of y according to (1.145). If the inverse function

is not available, then a lookup table is used and y is chosen according to the

criterion F

(

)

≤ x ≤ F

(

y + 

)

, where y + denotes the next entry in the table.

Graphically, the procedure is summarized in Fig. 1.16.

The inversion technique was used to generate random numbers that obey the

Pareto distribution using MATLAB. In that case, when x is the trial source input,

the output y is given from the F

−1

by the equation

y =−

exp

[

(

1/b

)

(

1 − x

)

]

(1.146)

Figure 1.11 shows the details of the method for generating random numbers fol-

lowing the Pareto distribution. The Pareto parameters chosen were a = 2, b = 2.5,

minimum value for data was x

min

= a. One thousand samples were chosen to gen-

erate the data. Note that the minimum value of the data equals a according to the

restrictions of the Pareto distribution.

1.35.3 Rejection Method

The previous method requires that the target cdf be known and computable such that

the inverse of the function can be determined either analytically or through using a

lookup table. The rejection method is more general since it only requires that the

target pdf is known and computable. We present here a simplified version of this

method.

Assume we want to generate the random numbers y that lie in the range a ≤ y

< b and follow the target pdf distribution specified by f (y). We choose the uniform

distribution g(y) that covers the same range a–b such that the following condition

is satisfied for y in the range a ≤ y < b

g(y) =

b −a

> f (y) (1.147)

1.35 Generating Random Numbers 41

Fig. 1.17 The rejection

method

g(y)

f(y)

1/(b-a)

If this condition cannot be satisfied, then a different g(y) must be chosen that

might not follow the uniform distribution. We proceed as follows.

1. Obtain the source random number x using any random number generator having

the uniform distribution.

2. Accept the candidate value x as the target value y = x with probability

(

acceptx

)

f (y)

g(y)

(1.148)

= (b −a) f (y) (1.149)

We are assured by (1.147) that the above expression for the probability is always

valid. This technique is not efficient when f (y) is mostly small with few large peaks

since most of the candidate points will be rejected. Graphical representation of the

rejection method is given in Fig. 1.17.

1.35.4 Importance Sampling Method

Importance sampling is a generalization of the rejection method. A trial pdf, g

(

)

is chosen as in the rejection method. It is not necessary here to choose g

(

)

such

that it is larger than f (y). Each point y has a weight associated with it given by

w(y) =

f (y)

(

)

(1.150)

Based on this array of weights, we choose a weight W that is slightly larger than

the maximum value of w(y)

W = max

[

w(y)

]

+>0 (1.151)

The method is summarized in the following steps.

1. Obtain the source random number x that has a uniform distribution.

2. Apply the inversion method using g

(

)

to obtain a candidate value for y.

3. Accept the candidate y value with probability

(

accept y

)

w(y)

(1.152)

42 1 Probability

Problems

The Multiplication Principle

1.1 A pair of fair dice is rolled once. Identify one possible outcome and identify

the sample space of this experiment.

1.2 Consider the above experiment where we are interested in the event that

“seven” will show. What are the outcomes that constitute the event?

1.3 A student has to take three courses from three different fields. Field A offers 5

courses, field B offers 10 courses, and field C offers 3 courses. In how many

ways can the student select the course load?

1.4 A car dealer specializes in selling three types of vehicles: sedans, trucks,

and vans. Each vehicle could be rated as excellent, okay, lemon, or “bring

your own jumper cables”. In how many different ways can a customer buy a

vehicle?

1.5 Car license plates in British Columbia consist of three letters followed by three

numbers. How many different license plate numbers could be formed?

Permutations

1.6 Internet packets have different lengths. Assume 10 packets have been received

such that two are over-length, four have medium length, and four are short.

How many different packet patterns are possible?

1.7 In Time Division Multiple Access (TDMA) communication, a time frame is

divided into ten time slots such that each time slot can be used by any user.

Suppose that a frame is received that contains three packets due to user 1, two

due to user 2, and the rest of the time slots were empty. How many frame

patterns are possible?

1.8 A router receives 15 packets from 15 different sources. How many ways could

these packets be received?

1.9 In Problem 1.8, of the 15 packets received, five were due to one user and the

rest were due to 10 different users. How many ways could the packets types

be received?

Combinations

1.10 A packet buffer has 50 packets. If it is known that 15 of those packets be-

long to a certain user and the rest belong to different users then in how many

possibilities can these packets be stored in the buffer?

1.11 A router receives 10 packets such that four of them are in error. How many

different packet patterns are possible?

Problems 43

1.12 In a cellular phone environment, a cell has 100 users that want access and

there are only 16 available channels. How many different possibilities exist

for choosing among these users?

Probability

1.13 A signal source randomly moves from being active to being idle. The active

period lasts 5 seconds and the idle period lasts 10 seconds. What is the proba-

bility that the source will be active when it is sampled?

1.14 In a wireless channel a certain user found that for each 1000 packets transmit-

ted 10 were lost, 100 were in error, and 50 were delayed. Find the following.

(a) Probability that a packet is lost.

(b) Probability that a packet is received without delay.

(d) Probability that a packet is received without delay or without errors.

1.15 Assume a gambler plays double or nothing game using a fair coin and starts

with one dollar. What is the probability that he/she will wind up winning

$1,024?

1.16 Four friends decide to play the following game. A bottle is spun and the person

that the bottle points to is unceremoniously thrown out of the game. What is

the probability that you are still in the game after n spins? Is there an upper

limit on the value of n?

1.17 A bird breeder finds that the probability that a chick is male is 0.2 and a female

is 0.8. If the nest has three eggs, what is the probability that two male chicks

will be produced?

Random Variables

1.18 Indicate the range of values that the random variable X may assume and

classify the random variable as finite/infinite and continuous/discrete in the

following experiments.

(a) The number of times a coin is thrown until a head appears.

(b) The wait time in minutes until a bus arrives at the bus stop.

(d) The number of students in a classroom.

(e) The number of retransmissions until a packet is received error free.

1.19 A packet is received either correctly or in error on a certain channel. A random

variable X is assigned a value equal to the number of error free packets in a

group of three packets. Assume that the error in a packet occurs independent

of the other packets.

44 1 Probability

(a) List all the possible outcomes for the reception of three packets.

(b) List all the possible values of X.

(x) and F

(x).

1.20 In some communication scheme, when a packet is received in error, a request

for retransmission is issued until the packet is received error free. Let the ran-

dom variable Y denote the number of retransmission requests. What are the

values of Y ?

1.21 Packets arrive at a certain input randomly at each time step (a time step is

defined here as the time required to transmit or receive one complete packet).

Let the random variable W denote the wait time (in units of time steps) until a

packet is received. What values may W assume?

The Cumulative Distribution Function (cdf)

1.22 Assume a random variable X whose cdf is F(x). Express the probability

p(X > x)asafunctionofF(x).

1.23 A system monitors the times between packet arrivals, starting at time t = 0.

This time is called the interarrival time of packets. The interarrival time is a

random variable T with cdf F

(t). The probability that the system receives a

packet in the time interval (t, t +δt)isgivenbypδt.

(a) Find the probability that the system receives a packet in a time less than

or equal to t.

(b) Find the probability that the system receives a packet in a time greater

than t.

1.24 Plot the cdf for the random variable in Problem 1.19.

1.25 Explain the meaning of equations (1.15) to (1.19) for the cdf function. Note

that (1.19) is really a restatement of (1.7) since the events X ≤ x

and x

≤

X ≤ x

are mutually exclusive.

1.26 A buffer contains ten packets. Four packets contain an error in their payload

and six are error free. Three packets are picked at random for processing. Let

the random variable X denote the number of error-free packets selected.

(a) List all possible outcomes of the experiment.

(b) Find the value of X for each outcome.

(d) Plot the cdf for this random variable.

Note that this problem deals with sampling without replacement: i.e. we pick a

packet but do not put it back in the buffer. Hence the probability of picking an

error-free packet will vary depending on whether it was picked first, second,

or third.

1.27 Sketch the pdf associated with the random variable in Problem 1.26.