Simulation and modeling 2071

Simulation is the imitation of the operation of a real-world process or system over time. Simulation involves the generation of an artificial history of the system, and the observation of that artificial history to draw inferences concerning the operating characteristics of the real system that is represented.

Steps in simulation study

1.Problem formulation

     Clearly state the problem.

2. Setting of objectives and overall project plan

     How we should approach the problem.

3. Model conceptualization

     Establish a reasonable model.

4. Data collection

    Collect the data necessary to run the simulation (such as arrival rate, arrival process, service discipline, service rate etc.).

5. Model translation

     Convert the model into a programming language.

6. Verification

     Verify the model by checking if the program works properly. Use common sense.

7. Validation

     Check if the system accurately represent the real system.

8. Experimental design

     How many runs? For how long? What kind of input variations?

9. Production runs and analysis

     Actual running the simulation, collect and analyze the output.

10. Repetition

     Repeat the experiments if necessary.

11. Document and report

     Document and report the results.

12. Implementation: Implement the simulated system in the real world if the simulation results show that it is advantageous to implement the new system or policy.

Limitations of simulation 

If the future states of a process are independent of the past and depend only on the present , the process is called a Markov process. A discrete state Markov process is called a Markov chain. A Markov Chain is a random process with the property that the next state depends only on the current state.

Markov chains are used to analyze trends and predict the future. (Weather, stock market, genetics, product success, etc.

Formally,

A Markov chain is a sequence of random variables X₁, X₂, X₃, ... with the Markov property, namely that, given the present state, the future and past states are independent.

The conditional probability above gives us the probability that a process in state i_n at time n moves to i_n+1 at time n + 1. We call this the transition probability for the Markov chain. If the transition probability does not depend on the time n, we have a stationary Markov chain, with transition probabilities

Now we can write down the whole Markov chain as a matrix P:

Example:

Weather Problem:

• raining today  ⇒ 40 % rain tomorrow

                                ⇒ 60 % no rain tomorrow

• not raining today  ⇒ 20 % rain tomorrow

                                      ⇒ 80 % no rain tomorrow

What will be probability if todays is not raining then not rain the day after tomorrow?

Markov chain diagram:

Transition matrix:

Thus, the probability of not rainy the day after tomorrow is 0.76.

Applications of Markov Chain

1. Physics: Markovian systems appear extensively in thermodynamics and statistical mechanics, whenever probabilities are used to represent unknown or unmodelled details of the system, if it can be assumed that the dynamics are time-invariant, and that no relevant history need be considered which is not already included in the state description.

2. Internet applications: The Page Rank of a webpage as used by Google is defined by a Markov chain. It is the probability to be at page i in the stationary distribution on the following Markov chain on all (known) web pages

3. Statistics: Markov chain methods have also become very important for generating sequences of random numbers to accurately reflect very complicated desired probability distributions, via a process called Markov chain Monte Carlo (MCMC) And many more.

The testing for uniformity can be achieved through different frequency test. These tests use the Kolmogorov-Smirnov or the chi- square test to compare the distribution of the set of numbers generated to a uniform distribution.

The Poker Test is the test for independence based on the frequency with which certain digits are repeated with in a series of numbers. This test not only tests for the randomness of the sequence of numbers, but also the digits comprising of each of the numbers. The expected value of each of the combination of digits in a number is compared with the observed value by means of the chi-square test for independence. The acceptance is done if the observed value of chi-square sums for all the possible combinations of digits is less than the acceptable value for the given degree of freedom at the specified confidence interval.

Example:

Poker test for three digit numbers

In each case, a pair of like digits appears in the number that was generated. In three-digit numbers there are only three possibilities, as follows:

    1. The individual numbers can all be different.

    2. The individual numbers can all be the same.

    3. There can be one pair of like digits.

The probability associated with each of these possibilities is given by the following

    P (three different digits) = (0.9)*(0.8) = 0.72

    P (three like digits) = (0.1)*(0.1) = 0.01

    P (exactly one pair) = 1 - 0.72 - 0.01 = 0.27

E.g.

Suppose a sequence of 1000 three-digit numbers has been generated and an analysis indicates that 680 have three different digits, 289 contain exactly one pair of like digits, and 31 three like digits. Based on the poker test, we are going to check are these number independent? Let α = 0.05..

Since, 47.65 > X²_0.05,2 = 5.99 (tabulated value), the independence of the numbers is rejected on the basis of this test.

The key elements of queuing systems are customer and server. Customer refers to anything that arrives at a facility and requires service. E.g. people, machines, trucks, emails. Servers refers to any resource that provides the requested service. E.g. receptionist, tellor, CPU, washing machine etc.

1. Calling Population

The population of potential customers those require service from system is called calling population. It may be finite or infinite. System having large calling population is usually considered as infinite. For e.g. customers at banks, restaurant. And System having less and countable population is usually considered as finite. For e.g. a certain number of machines to be repaired by a service man.

    In finite population model, arrival rate depends on the number of customers being served and waiting. But in infinite population model, arrival rate is not affected by the number of customer being served and waiting.

2. Arrival Process

The arrival process for infinite-population models is usually characterized in terms of interarrival times of successive customers. Arrivals may occur at scheduled times or at random times. When at random times, the inter arrival times are usually characterized by a probability distribution and most important model for random arrival is the poisson process. In schedule arrival interarrival time of customers are constant.

3. Service Process

Service process can be measured by the number of customers served per some unit of time or the time taken to complete the service. Once entities have entered to the system they must be served. The service can be provided in single or batch. if it is batch, as in the case of arrival the batch size can be fixed or random. Service time may be of constant duration or of random duration.

4. Queueing Discipline and Queueing Behaviour

Queue discipline refers to the rule that a server uses to choose the next customer from the queue when the server completes the service of the current customer. Common queue disciplines include first-in-first-out (FIFO); last-in-first-out (LIFO); service in random order (SIRO); shortest processing time first (SPT); and service according to priority (PR).

Queue behavior refers to the actions of customers while in a queue waiting for service to begin.

5. Number of Servers: 

Servers represent the entity that provides service to the customer. A system may consist of single server or multiple servers.
- A system with multiple servers is able to provide parallel services to the customers.

Pseudo random numbers are the random numbers that are generated by using some known methods (algorithms) so as to produce a sequence of numbers in [0,1] that can simulates the ideal properties of random numbers. They are not completely random as the set of random numbers can be replicated because of use of some known method.

Every new number is generated from the previous ones by an algorithm. This means that the new value is fully determined by the previous ones. But, depending on the algorithm, they often have properties making them very suitable for simulations.

When generating pseudo-random numbers, certain problems or errors can occur. Some examples include the following:

1. The generated numbers might not be uniformly distributed.
2. The generated numbers might be discrete valued instead of continuous valued.
3. The mean of the generated numbers might be too high or too low.
4. The variance of the generated numbers might be too high or too low.
5. There might be presence of correlation between the generated numbers.

The important considerations that should be made while generating pseudo random numbers are as follows:

1. The method used to generate random number should be fast because the simulation problem requires a large set of random numbers which can increase time complexity of the system.
2. The method used should be portable to different platform and programming languages so as to generate same results wherever it is executed.
3. The method should have long cycle.
4. The random numbers should be replicable. It means that the same set of random numbers should be generated with same starting point.
5. The generated random numbers should approximate the uniformity and independence properties.

Autocorrelation Test is a statistical test that determines whether a random number generator is producing independent random number in a sequence. The test for the auto correlation is concerned with the dependence between numbers in a sequence.

The test computes the autocorrelation between every m numbers (m is also known as lag) starting with i^th index. Thus the autocorrelation  between the following numbers would be of interest.

The value M is the largest integer such that  where N is the total number of values in the sequence.

For large values of M, the distribution of the estimator , denoted as , is approximately normal if the values  are uncorrelated.

Form the test statistic:

The actual formula for  and the standard deviation is

and  

After computing , do not reject the null hypothesis of independence if  where  is the level of significance.

Validation is concerned with building the right model. It is utilized to determine that a model is an accurate representation of the real system. It is usually achieved through the calibration of the model.

Calibration means to validate the model with the real system, look out for the places for betterment of the models and revising the model to form next better model repeatedly until a satisfiable model is not achieved. The initial model is developed and is calibrated using Naylor-Finger calibration steps with the real system. It is then revised and a first revision model is generated. The first revision model is then calibrated with the real system. It is revised to form a second revision model. This process is continued until the model becomes acceptable.

Naylor and Finger formulated a three step approach:-

1. Build a model that has high face validity.

2. Validate model assumptions.

3. Compare the model input-output transformations to corresponding input-output transformations for the real system.

The following figure shows the relationship of the model calibration to the overall validation process.

The comparison of the model to reality is carried out by verity of test. Some test are subjective and other are objective.

• Subjective test usually involve people, who are knowledgeable about one or more aspects of the system, making judgments about the model and its output.
• Objective test always require data on the system's behavior plus the corresponding data produced by the model.

Replication of runs

This approach is used to obtain independent results by repeating the simulation. Repeating the experiment with different random numbers for the same sample size n gives a set of independent determinations of the sample mean  .The mean of the means and the mean of the variances are then used to estimate the confidence interval.

Suppose the experiment is repeated p times with independent random values of n sample sizes. Let x_ij be the i^th observation in j^th run and let the sample mean and the variance for the j^th run is denoted by  and  respectively. Then for j^th run, the estimates are

Combining the result of p independent measurement gives the following estimate for the mean and variance s² of the populations as:

Given,

    X₀ = 118, 

    α = 45,

    m=1000

We have,

For multiplicative congruential method:

        X_i+1 = (α X_i ) mod m

The sequence of random integers are calculated as follows:

X₀ = 118

X₁ = (α X₀) mod m = (45*118) mod 1000 = 5310 mod 1000 = 310

X₂ = (α X₁) mod m = (45*310) mod 1000 = 13950 mod 1000 = 950

X₃ = (α X₂) mod m = (45*950) mod 1000 = 42750 mod 1000 = 750

X₄= (α X₃ ) mod m = (45*750) mod 1000 = 33750  mod 1000 = 750

X₅= (α X₄ ) mod m = (45*750) mod 1000 = 33750 mod 1000 = 750

Simulation tool is a software which is used for simulating hardware, software and network. It is a type of software based on the process of modeling a real world phenomenon with mathematical formula. This program allows the user to observe the operation without actually performing that operation . Its main importance is: how it actually supports the model building.

Verification is the process of determining that a model implementation and its associated data accurately represent the developer's conceptual description and specifications.  Verification answers the question "Have we built the model right?". The verification focuses on comparing the elements of a simulation model of the system with the description of what the requirements and capabilities of the model were to be. Verification is an iterative process aimed at determining whether the product of each step in the development of the simulation model fulfills all the requirements levied on it by the previous step and is internally complete, consistent, and correct enough to support the next phase.

Example:

Let us say that you are developing a cell phone to be launched in the market. You conducted the market research and then collected the numbers of functionalities to be included in the cell phone. Then you design the procedures to be used to build the product and specify the quality requirements for it. Now the production process has been started. To make sure that everything is going according to plan, you perform the inspection activities to the process, then, you would say that product has been verified and is being developed as you planned for it.

a. Discrete system modeling

In discrete systems, the changes in the system state are discontinuous and each change in the state of the system is called an event. The model used in a discrete system simulation has a set of numbers to represent the state of the system, called as a state descriptor. 

b. Feedback system

The system takes feedback from the output i.e. input is coupled with output. A significant factor in the performance of many systems is that coupling occurs between the input and output of the system. The term feedback is used to describe the phenomenon.

One example of feedback system in which there is continuous control is the aircraft system. Here the input is a desired aircraft heading and the output is the actual heading. The gyroscope of the autopilot is able to detect the difference between the two headings. A feedback is established by using the difference to operate the control surface. Since change of heading will then affect the signal being used to control the heading.

The difference between the desired signal θ_t and actual heading θ₀ is called the error signal, since it is a measure of the extent to which the system from the desired condition. It is denoted by є.

We also know that, in terms of angular acceleration

From equation (1), (2) & (3)

Dividing both sides by I, and making the following substitutions in equation (4)

 (where  is damping factor)

    This is a second order differential equation.