Programming and Computation: Probability

Chapter 06:(Probability Concepts in Simulation)

6-1:: Stochastic Variables::

Stochastic process: If the output of an activity/ process is random, the activity is said to be stochastic process. Stochastic process is defined as being an ordered set of random variables: the ordering of the set usually being with respect to time. The activity cab be discrete or continuous. The stochastic variable might, for example, represent the number of days in the month (or a sequence of dates), that take only the values 28, 29, 30 or 31; or it might be a variable representing wind velocity, which can very over a continuous range.

Question: What is the use of random numbers in simulation? (’97)/ Why random numbers are needed in discrete system simulation? (’98,’01)

Answer: A simulation of any system or process in which there are inherently random components requires a method of generating or obtaining numbers that are random, in some sense. Random numbers are a necessary basic ingredient in the simulation of almost all-discrete systems. Stochastic process is defined as being an ordered set of random variables: the ordering of the set usually being with respect to time. Stochastic activities used in system simulation give rise to a stochastic variable represented by a sequence of random numbers occurring over time. For example, the queuing and inventory models required inter-arrival times, service times, demanded sizes, etc., that can be “drawn” from some specified distributions. Most computer languages have subroutines or functions that will generate random numbers.

6-2:: Discrete Probability Functions::

Probability functions:

Discrete functions Ê

Ä Probability mass function (pmf)

Ä Cumulative distribution function (cdf)

Continuous functions Ê

Ä Probability density function (pdf)

Ä Cumulative distribution function (cdf)

Probability mass function: If a stochastic variable (random variable) can take I different values,

, and the probability of the value

being taken is

, the set of numbers

is said to be a probability mass functions. Since the variable must take one of the values, it follows that

The probability mass function may be a known set of numbers. For example, with a die, the probability of each of the six faces is

, but, frequently, a probability mass function must be estimated by counting how many times each possible value occur in a sample.

So probability mass function

Number of Items x_I	Number of Customers n_t	Probability Distribution p(x_i) =	Cumulative Distribution P(x_i)
1	25	0.10	0.10
2	128	0.51	0.61
3	47	0.19	0.80
4	38	0.15	0.95
5	12	0.05	1.00
	250=N

Table: Number of Items Bought by Customers.

Cumulative distribution function/ distribution function: It is defined as a function that gives the probability of a random variable’s being less than or equal to a given value. In the case of discrete data, the cumulative distribution function is denoted by

. Values of the cumulative distribution function are estimated by accumulate the values of probability mass function.

Example:

Number of Items x_i	Number of Customers n_t	Probability Distribution p(x_i) =	Cumulative Distribution P(x_i)
1	25	0.10	0.10
2	128	0.51	0.61
3	47	0.19	0.80
4	38	0.15	0.95
5	12 250	0.05	1.00

Table: Number of Items Bought by Customers.

6-3:: Continuous Probability Functions::

Probability density function f(x): When the stochastic variable being observed is continuous and not limited to discrete values, an infinite number of possible values can be assumed by the variable. The probability of any one specific value occurring must logically be considered to be zero. So probability density function f(x) should be consider in a given range. The probability that x falls in the range

is given by

And the integration of the probability density function taken over all possible values is 1. That is

Most variables in the simulation should have a finite lower limit, generally zero. The probability density function at and below this limit is than identically zero, and the lower limit of the integral can be replaced by the finite value. The same effect may occur at upper limit.

Cumulative distribution function: It defines the probability that the random variable is less than or equal to x and is denoted by F(x). It is related to the probability density function, as follows:

From its definition, F(x) is a positive number ranging from 0 to 1, and the probability of x falling in the range

_____________________________________________________________________________________

[Side Note:

]

______________________________________________________________________________

q Question: What are the differences between probability mass function and probability density function? (’98)

Answer:

Probability mass function: If a stochastic variable (random variable) can take I different values,

, and the probability of the value

being taken is

, the set of numbers

is said to be a probability mass functions. Since the variable must take one of the values, it follows that

The probability mass function may be a known set of numbers. For example, with a die, the probability of each of the six faces is

, but, frequently, a probability mass function must be estimated by counting how many times each possible value occur in a sample.

So probability mass function

Probability density function f(x): When the stochastic variable being observed is continuous and not limited to discrete values, an infinite number of possible values can be assumed by the variable. The probability of any one specific value occurring must logically be considered to be zero. So probability density function f(x) should be consider in a given range. The probability that x falls in the range

is given by

And the integration of the probability density function taken over all possible values is 1. That is

6-5:: Numerical Evaluation of Continuous Probability Functions::

The purpose of introducing a probability function into a simulation is to generate random number with particular distribution.

The customary way of organizing data derived from observations is to display them as a frequency distribution, which shows the number of times the variable falls in different intervals.

A relative frequency distribution: It is the number of observations for each interval is divided by the total number of observations. So sum of all the values of the relative frequency distribution is 1.

If the n intervals for which the frequency distribution has been generated are

and

is the relative frequency count for the ith interval, then

must be interpreted as the integral of the probability density function over the interval; that is,

Density function: So, the value of the density function in each interval is

Cumulative distribution function: If the values of

are accumulated, the successive values,

, represents the value of the cumulative distribution function at points

SHAPE

Figure: Cumulative distribution of telephone call lengths.(fig:6-5,Page-124)

Random Number’s Classification

Continuous Discrete

Uniform Random Non-Uniform Random Uniform Random Non-Uniform random

Numbers Number/Variates Numbers Numbers/Variates

{Every number {Probability of a generated

has a equal random number depends

probability (0.1)} on a given probability

distributed function}

6-6:: Continuous Uniformly Distributed Random Numbers::

Question: Describe the technique to generate continuous uniform random numbers with a given range.

Answer: By a continuous uniform distribution we means that the probability of a variable, X, falling in any interval within a certain range of values is proportional to the ratio of the interval size to the range; that is, every point in the range is equally likely to be chosen.

Suppose the possible range of values is from A to B (B > A), than the probability that X will fall in an interval

. Drawn as a graph, the probability density function is a straight line of height

between the points A and B, as shown in the following figure-1.

SHAPE

Figure-1: Continuous uniform distributions.

There is no loss in generality in assuming that the range is from 0 to 1, because, if

is a sequence of uniformly distributed number in the range 0 to 1 (given input), then

is a uniformly distributed sequence in the range A to B.

So in this case, the probability density function is

as illustrate in figure-2.

SHAPE

Figure: Continuous uniform distributions.

6-7:: Computer Generation of Random Numbers::

Question: Give an algorithm by which uniformly generated random numbers can be found. How can you maximize the number of random numbers? (’98)

(OR)

Question: Describe a procedure to generate random numbers.

(OR)

Question: Describe the procedure to generate congruence/ residue method for generating pseudo-random numbers.

(OR)

Question: Describe the technique to generate continuous uniform random numbers between 0 and 1.

Answer: Congruence/ residue method widely used to generate sequence of uniformly distributed random numbers over a given range (usually 0 to 1).

Given four non-negative integer constant l, m, C₀ and P, the procedure derives the (i + 1)th number from the ith number multiplying by l, adding m and then taken the remainder or residue, upon dividing by P. To begin the process, initial number C₀ is needed, and this is called seed. This procedure is described mathematically by the following expression

(modulo P)

It is apparent that it is impossible to procedure a non-repeating sequence of numbers from the above procedure. Because of the ultimate repetition of the sequence, the term pseudo-random number generator is used to describe the procedure. Therefore

. To obtain random number

(for i = 1,2,…..) on [0,1] need to compute

. In addition to non negativity, the integers P, l, m and C₀ should satisfy 0 < P, l< P, m< P and C₀< P.

It is apparent that it is impossible to produce a non-repeating sequence of numbers from the above procedure. Because of the ultimate repetition of the sequence, the term pseudo-random number generator is used to describe the procedure.

# Types of congruence pseudo-random number generators:

Three types of congruence pseudo-random number generators have been used.

They are j mixed, k additive and l multiplicative congruential generators.

Mixed method is defined by the formula

(modulo P)

If l =1, the method is said to be additive and the formula is

(modulo P)

If m = 0, the method is said to be multiplicative and the formula is

(modulo P)

q How can we test the group of random numbers? /Describe the testing used for random numbers.

Answer:

The desirable properties of random numbers are uniformity and independence. To ensure that these desirable properties are achieved, a number of tests can be performed. The test can be placed in two categories according to the properties of interest. The first entry in the list below concerns testing for uniformity. The second through fifth entries concern testing for independence. A brief description of five types of tests discussed as follows:

1. Frequency test. Uses the Kolmogorov-Smirnov or chi-square test to compare the distribution of the set of numbers generated to a uniform distribution.

2. Runs test.Tests the runs up and down or the runs above and below the mean by comparing the actual values to expected values. The statistics for comparison is the chi-square.

3. Autocorrelation test. Tests the correlation between numbers and compares the sample correlation to the expected correlation of zero.

4. Gap test. Counts the number of digits that appear between repetitions of a particular digit and then uses the Kolmogolrov-Smirnov test to compare with the expected size of gaps.

5. Poker test.Treats numbers grouped together as a poker hand. Then the hands obtained are compared to what expected using the chi-square test.

q Question: How can you test the uniformity of a group of random numbers? (’98)

Answer:

The desirable properties of random numbers are uniformity and independence. Uniformity property is as follows:

If the interval (0,1) is divided into n classes, or subintervals of equal length, the expected number of observations in each interval is N/n, where N is the total number of observations. Frequency test concerns the uniformity. It uses the Kolmogorov-Smirnov or chi-square test to comparing the distribution of the numbers generated to a uniform distribution. Chi-square test is described as follows:

Chi-square test

Chi-square test is used for testing the uniformity of generated random numbers. It is used in frequency test for concerns the uniformity. The chi-square test uses the sample statistics

where

is the observed number in the i th class,

is the expected number in the i th class, and n is the number of classes. For the uniform distribution,

, the expected number in each class is given by

for equally spaced classes, where N is the total number of observations. It can be shown that the sampling distribution of

is approximately the chi-square distribution with n-1 degrees of freedom.

Question: Write short notes on Chi-square test:

Answer:

Chi-square test:

Chi-square test is used for testing the uniformity and independence of generated random numbers. It is used in frequency test; runs test for concerns the uniformity and independence of random numbers respectively. The chi-square test uses the sample statistics

where

is the observed number in the i th class,

is the expected number in the i th class, and n is the number of classes. For the uniform distribution,

, the expected number in each class is given by

for equally spaced classes, where N is the total number of observations. It can be shown that the sampling distribution of

is approximately the chi-square distribution with n-1 degrees of freedom.

6-9:: Generating Discrete Distributions::

Generating Discrete Distributions/ Discrete random numbers:

Question: Describe technique to generate discrete distributions/ discrete random numbers.

Answer:

Generating uniform discrete distributions: For uniform discrete distribution, the requirement is to pick one of N alternatives with equal probability given to each. Given a random number

, the process of multiplying by N and taking the integral portion of the product, which is denoted mathematically by the expression [UN], gives N different outputs. The outputs are the numbers 0, 1, 2, …., (N- 1). The result can be changed to the range of values C to N + C – 1 by adding C.

Question: Describe the technique to Generate Non Uniform Discretely distributed random numbers.

Answer:

Generating Non Uniform Discrete Distributions:

From a given distribution, where x represent number of items, p(x) represents probability and y represents cumulative probability respectively.

Taking the output of a uniform random number generator, U, the value is compared with the values of y. If the value falls in an interval

, the corresponding value of

is taken as the desired output.

For example, it is necessary to generate a random variable representing the number of items bought by a shopper at store, where the probability function is the discrete distribution given in the following table,

Number of Items x_i	Number of Customers n_t	Probability Distribution p(x_i) =	Cumulative Distribution P(x_i)
1	25	0.10	0.10
2	128	0.51	0.61
3	47	0.19	0.80
4	38	0.15	0.95
5	12 250	0.05	1.00

Table: Number of Items Bought by Customers.

If output of a uniform distributed numbers are:

0.1009

0.3754

0.0842

0.9901

0.1280

For

then

For

then

For

then

Similarly we get the outputs 5 and 2.

So the non uniform discrete distribution to representing the number of items bought by a shopper at the store is: 2, 2, 1, 5, 1.

Non-Uniform continuously distributed random number

Inverse transformation method/ Rejection Method

Probability integral transformation theorem

6-10:: Non-Uniform Continuously Distributed Random Numbers::

Question: Describe a technique to generate non-uniform continuously distributed random numbers.

(OR)

Question: Describe the inverse transformation method (/probability integral transformation theorem) to generate non-uniform continuously distributed random numbers. (M.Sc-’97,’01)

Answer: The general requirement in simulation is for a sequence of random numbers drawn from a given distribution that is continuous and non-uniform. The most widely used method is based on an operation in statistics known as the probability integral transformation. The method is generally called the inverse transformation method.

The probability integral transformation theorem can be stated as follows: If

(i = 1, 2, …) are independent, random variables, uniformly distributed over the interval 0 to 1, and

is the inverse of the cumulative distribution function for the random variable X, then the random variables defined by

are a random sample of the variable X; that is, to produce random numbers with a given distribution, the inverse cumulative distribution function must be evaluated with a sequence of uniformly distributed numbers in the range 0 to 1.

SHAPE

Figure: Generation of non-uniform continuous random numbers.

Question: Evaluate the inverse cumulative function to generate continuous random numbers/variates from a given probability density function.

Answer: If the probability density function f(x) can be described mathematically, it is possible to find an expression for the inverse of the cumulative distribution function which can than be evaluated with a sequence of uniformly distributed random numbers between 0 to 1.

If the given probability density function (pdf) is as follows:

Then, cumulative distribution function (cdf):

Now, according to the probability theorem,

Now, if U is the uniform random number distributed between 0 to 1, then

letting

and solving for x, to find the inverse function:

Question: Evaluate the inverse cumulative function to generate continuous random numbers/variates from a given probability density function.

Answer: If the probability density function F(x) can be described mathematically, it is possible to find an expression for the inverse of the cumulative distribution function which can then be evaluated with a sequence between 0 to 1.

If given probability density function (pdf) is as follows:

Then, cumulative distribution function,

Now, according to the probability theorem, we know,

Now, if U is the uniform random number distribution between 0 to 1, then letting

and solve for x, to find inverse function:

Question: Generating Non-uniform Continuously distributed random numbers from a given probability distributions.

Figure: Inversed cumulative distribution of telephone call lengths.

Graphical Method: Graphically, the process of generating the random numbers consists of taking as inputs a series of uniformly distributed random numbers,

(0,1) and reading the outputs,

from the graph.

Tabular Method: From a given distribution of probability density function f(x) and output x, we can calculate the cumulative distribution U as by following table.

U	x_i	a_I
0 0.001 0.002 0.003 0.005 0.013 0.041 0.106 0.227 0.402 0.599 0.774 0.895 0.960 0.988 0.997 0.999 1.000	0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170	10,000.00 10,000.00 10,000.00 5,000.00 1,250.00 357.14 153.85 82.64 57.14 50.76 57.14 82.64 153.85 357.14 1,111.11 5,000.00 10,000.00 ----

Table: Generation of Telephone Call Lengths.

In the case of continuous data represented in tabular form, since all values between the tabulated values are possible, an interpolation between the tabulated values is made. The process is illustrated in the following figure.

SHAPE

Figure: Illustration of interpolation.

If the input entered in the table search falls in an interval between two tabulated input values, the output is taken to be the output value at the lower tabulated input plus an increment that divides the output interval in the same proportion that the input divides the input interval.

We can assume that the cumulative distribution is approximated by straight line segments between the tabulated points. To carry out the process of interpolation numerically, it is necessary to know the slopes of these lines.

The slopes, denoted by

, are defined as follows:

[For U = 0.106, x = 70,

]

If the input should happen to equal one of the tabulated values, the corresponding output value,

, is taken. If U falls in the interval

Then the output is

For example if U = 0.1009 then

Then

Similarly we can get the following outputs (x):

U	x
0.1009 0.3754 0.0842 0.9901 0.1280	69.23 88.48 66.65 142.33 71.82

6-11: The Rejection Method

q Question: Describe rejection method to generate random numbers? (’01)

Answer:

Rejection method used to generate random numbers. It is applicable when the probability density function, f(x), has a lower and upper limit to its range, a and b, respectively, and an upper bound c. The method can be specified as follows:

a) Compute the values of two, independent uniformly distributed variates