Simulace.info - User contributions [en]

Variance reduction

2019-01-21T11:42:40Z

Dolj04: /* Stratification */

Monte Carlo is important but can be considered a straightforward technique. Its main issue is variance. To try to get rid of it, what can be done is to increase the number of samples N. However, each time we want to reduce variance two times, we need four fold the number of samples (for the blunder to diminish linearly, the quantity of tests needs to increase exponentially). Because of that great deal of research was invested into discovering whether change could be decreased by some other mean than simply expanding N. Luckily, mathematics can help answering this question. Monte Carlo integration typically has an error variance of the form σ^2/N. Even though we get a better answer by sampling with a larger value of N, the computing time grows with N. Sometimes it is conceivable to decrease σ instead. To do this, we construct a new Monte Carlo problem with the same answer as our original one but with a lower σ. This leads to an entire branch in Monte Carlo research focused on what's known as variance reduction methods. <ref>Scratchapixel . Scratchapixel . Monte Carlo Methods in Practice. [Online] [Citation: 19. 1 2019.] https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/variance-reduction-methods.</ref>
<ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref> 
When do we need variance reduction? It is mostly needed in simulations of highly complex models with high computation cost per replication, and in simulations of rare events with too many replications in crude Monte Carlo. There are many applications of these phenomena in a variety of fields, for example: physics, finance, statistics, reliability or systems biology.<ref>Zdravko Botev, Ad Ridder. Variance Reduction. School of Mathematics and Statistics. [Online] 2017. [Citation: 19. 1 2019.] https://web.maths.unsw.edu.au/~zdravkobotev/variancereductionCorrection.pdf</ref>

= Variance reduction techniques =
In this chapter can be found description for some of the popular classic variance reduction techniques, mainly focusing on antithetic variables and common random numbers (CRN). CRN is commonly utilized in a simulation study in which we want to compare performance measures of two distinct systems. Every single other method (for instance antithetic variables, stratification) is valuable in the case that we want to simulate a performance measure of only a single system. These methods all enhance effectiveness by sampling the input values more strategically. Next let’s consider conditioning and control variates. These methods take advantage of closed form solutions to problems similar to the given one. Another major method is importance sampling. Like some of the other methods, importance sampling also changes where we take the sample values, but rather than distributing them in more balanced ways it purposely oversamples from some regions and then corrects for this distortion by reweighting. It is accordingly an extreme reformulation of the issue and can be dubious to do well. <ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>
<ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref> 
Other group of methods consists of heuristic variance reduction techniques. Amongst them we can find some of those popular techniques: Weighting in lieu of absorption, Splitting, Forced collisions, Russian roulette, etc. Underlying idea here is that we want to choose from a probability distribution that we want to use rather than using the one that the physical data indicates.<ref>Pevey, Dr. Ronald E. Variance Reduction Techniques. web.utk.edu. [Online] 9. 3 2015. [Citation: 19. 1 2019.] http://web.utk.edu/~rpevey/public/NE582/Chapter%204.pdf</ref>
 
Last group we will mention here are more modern methods which include Quasi Monte Carlo and Multilevel Monte Carlo Estimator techniques.
<ref>Zdravko Botev, Ad Ridder. Variance Reduction. School of Mathematics and Statistics. [Online] 2017. [Citation: 19. 1 2019.] https://web.maths.unsw.edu.au/~zdravkobotev/variancereductionCorrection.pdf</ref>

== Common Random Numbers ==

Common random numbers (CRN) is the simplest and presumably the most widely used method for increasing the efficiency of comparisons via simulation. It is intuitively appealing and easy to implement in either a custom-made simulation or in a simulation package. In its simplest form, CRN just requires that the systems under study be simulated with the same stream of random numbers. Naturally, this appears to be reasonable since it guarantees that the frameworks are thought about under same conditions. Key idea in the method is that on the off chance X and Y are two random variables, then Var(X−Y) = Var(X) + Var(Y) − 2Cov(X, Y). Thus, for the situation that X and Y are positively correlated, i.e. Cov(X,Y)>0, the variance of X − Y will be smaller than in the case that X and Y are independent. In general, the use of common random numbers leads to positive correlation of the outcomes of a simulation of two systems. As a consequence, it is better to use common random numbers instead of independent random numbers when we compare two different systems.<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>
<ref>Paul Glasserman, David D. Yao. Some Guidelines and guarantees for common random numbers. MANAGEMENT SCIENCE. 38, 1992, No. 6.</ref>

=== Example 1 ===

Assume that a limited number of N jobs must be handled on two indistinguishable machines. The processing times of the jobs are random variables with some common distribution function F. We want to compare the completion time of the last job, Cmax, under two different policies. In the LPTF policy, we always choose the remaining job with the longest processing time first, in the SPTF policy we choose the remaining job with the shortest processing time first. In Table 1 and Table 2 we compare for N = 10 and F(x) = 1 − e^(-x) the estimators and confidence intervals for E(C SPTF max − C LPTF max ) when we do not, resp. do, use CRN. We conclude that in this example the use of CRN reduces the standard deviation of the estimator and hence also the length of the confidence interval with a factor 5.<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>

{| class="wikitable" style="margin: auto;"
|+Table 1: Estimation of E(C SPTF max − C LPTF max) without using common random numbers<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>
|-
|# of runs
|mean
|st. dev
|95% conf. int.
|-
|1000
|0.8138
|2.5745
|[0.645, 0.973]
|-
|10000
|0.8293
|2.4976
|[0.780, 0.878]
|-
|100000
|0.8487
|2.4990
|[0.833, 0.864]
|-
|1000000
|0.8398
|2.4951
|[0.835, 0.845]
|}

 
{| class="wikitable" style="margin: auto;"
|+Table 2: Estimation of E(C SPTF max − C LPTF max) using common random numbers <ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>
|-
|# of runs
|mean
|st. dev
|95% conf. int.
|-
|1000
|0.8559
|0.5416
|[0.822, 0.889]
|-
|10000
|0.8415
|0.5230
|[0.831, 0.852]
|-
|100000
|0.8394
|0.5164
|[0.836, 0.843]
|-
|1000000
|0.8391
|0.5168
|[0.838, 0.840]
|}

=== Example 2 ===

When we want to use CRN, the problem of synchronization can arise: How can we achieve that the same random numbers are used for the generation of the same random variables in the two systems? In the previous example, this synchronization problem did not arise. However, to illustrate this problem, consider the following situation. In a G/G/1 queueing system the server can work at two different speeds, v1 and v2. Aim of the simulation is to obtain an estimator for the difference of the waiting times in the two situations. We want to use the same realizations of the interarrival times and the sizes of the service requests in both systems (the service time is then given by the sizes of the service request divided by the speed of the server). If we use the program of the discrete event simulation of Section 3 of the G/G/1 queue, then we get the synchronization problem because the order in which departure and arrival events take place depends on the speed of the server. Hence, also the order in which interarrival times and sizes of service requests are generated depend on the speed of the server. The synchronization problem can be solved by one of the following two approaches: 1. Use separate random number streams for the different sequences of random variables needed in the simulation. 2. Assure that the random variables are generated in exactly the same order in the two systems. For the example of the G/G/1 queue, the first approach can be realized by using a separate random number stream for the interarrival times and for the service requests. The second approach can be realized by generating the service request of a customer already at the arrival instant of the customer.<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>

== Antithetic variables ==
The method of antithetic variables is a frequently suggested technique for reducing the variability of estimators in computer simulation experiments. In practice the method does not appear to work as well as it might and hence is not used as often as it should. The idea in the technique of antithetic variables is as follows: It makes use of the fact that if U is uniformly distributed on (0, 1) then so is 1 − U and furthermore U and 1 − U are negatively correlated. The key idea is that, if W1 and W2 are the outcomes of two successive simulation runs, then Var(W1 + W2/2)=1/4Var(W1)+1/4Var(W2)+1/2Cov(W1, W2). Hence, in the case that W1 and W2 are negatively correlated the variance of (W1 + W2)/2 will be smaller than in the case that W1 and W2 are independent. The question remains how we can achieve that the outcome of two successive simulation runs will be negatively correlated. From the fact that U and 1 − U are negatively correlated, we may expect that, if we use the random variables U1,...,Um to compute W1, the outcome of the first simulation run, and after that 1 − U1,...,1−Um to compute W2, the outcome of the second simulation run, then also W1 and W2 are negatively correlated. Intuition here is that, e.g., in the simulation of the G/G/1 queue large realizations of the Ui’s corresponding to large service times lead to large waiting times in the first run. Using the antithetic variables, this gives small realizations of the 1−Ui’s corresponding to small service times and hence leading to small waiting times in the second run. <ref>The Use of Antithetic Variates in Computer Simulations, R. C. H. Cheng, The Journal of the Operational Research Society, Vol. 33, No. 3 (Mar., 1982), pp. 229-237</ref>
<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>

== Stratification ==

Now, let’s just briefly mention the thought behind stratified sampling which is to split up the domain D of X into separate regions, take a well-defined sample of points from each such region, and combine the results to estimate E(f(X)). Naturally, on the off chance that every area gets a lot of points then we ought to get an improved answer. Figure 1 shows two little instances of stratified domains. We may have the capacity to improve the situation still by oversampling inside the vital strata and under sampling those in which f is almost consistent (similar to methods of importance sampling). <ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref>

[[File:stratifiedSamples.png|The left panel shows 20 points xi ∈ [0, 1]2 of which 5 are sampled uniformly from within each of four quadrants. The right panel shows 21 points from the N (0, I2) distribution. There are 6 concentric rings separating the distribution into 7 equally probable strata. Each stratum has 3 points sampled from within it.|center|500px]]
Figure 1<ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref>

= Measuring variance reduction efficiency =
Using variance reduction can sometimes bring tremendous enhancements in contrast with conducting plain Monte Carlo. It isn’t exceptional for the value σ^2 to be reduced thousand times (or more). Unfortunately, it is likewise possible for a variance reduction technique to bring a very modest improvement, perhaps equivalent to diminishing σ^2 by only 10%. What is more regrettable, few methods will raise σ^2 in unwanted circumstances. The estimation of a variance reduction relies upon more than the change in σ^2. It likewise relies upon the PC's running time, perhaps the memory expended, and significantly, the human time taken to program and test the code. Suppose for simplicity, that a baseline method is unbiased and estimates the desired quantity with variance σ0^2/n, at a cost of nc0, when n function evaluations are used. To get an error variance of τ^2 we need n = σ0^2/τ^2 and this will cost c0σ0^2/τ^2. Here we are assuming that cost is measured in time and that overhead cost is small. On the off chance that an alternative fair-minded method has variance σ1^2/n and cost nc1 under these conditions, then it will cost us c1σ1^2/τ2 to achieve the same error variance τ^2 that the baseline method achieved. The efficiency of the new method, relative to the standard method is E = c0σ0^2/ c1σ1^2. At any fixed level of accuracy, the old method takes E times as much work as the new one. The efficiency has two factors, σ0^2/σ1^2 and c0/c1. The first is a mathematical property of the two methods that we can often handle theoretically. The second is more complicated. It can depend heavily on the algorithms used for each method. It can also depend on details of the computing environment, including the computer hardware, operating system, and implementation language. Note that numerical outcomes for c0/c1 acquired in one setting don't really apply to another. 
There is no settled guideline for how substantial a productivity enhancement must be to make it worth utilizing. In a few settings, for example, rendering PC illustrations for movies, where a large number of CPUs are kept occupied for a considerable length of time, a 10% enhancement (i.e., E = 1.1) brings important reserve funds. In different settings, for example, an irregular calculation, a 60-overlap gain (i.e., E = 60) which transforms a one-minute pause into a one second pause, may not justify the expense of programming a more complicated solution. 
Computation costs so much less than human effort that we commonly require substantial proficiency gains to counterbalance the time spent programming up a variance decrease. The force to search out a productivity enhancement may possibly come when we end up hanging tight quite a while for an outcome, as, when we have to put our whole Monte Carlo figuring inside a loop representing numerous variations of the issue. A very slow computation costs more than just the computer’s time. It may waste time for those waiting for the answer (workforce). Also, slow computations reduce the number of alternatives that one can explore and thus not giving as options to choose from which would be preferable in many situations. 
The effectiveness increase important to justify using a method is less if the programming exertion can be amortized over numerous applications. The edge is very high for a one-time program, lower for something that we are adding to our personal library, lower still for code to share with a few associates and even lower for code to be put into a library or simulation tool for general use. Important is to note that all of the methods mentioned in previous chapter are capable of a great range of efficiency improvements.<ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref>

= Recommended reading =

https://web.maths.unsw.edu.au/~zdravkobotev/variancereductionCorrection.pdf
http://sas.uwaterloo.ca/~dlmcleis/s906/chapt4.pdf
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-mathematical-foundations/variance-and-standard-deviation
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/variance-reduction-methods
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/introduction-quasi-monte-carlo
https://www0.gsb.columbia.edu/mygsb/faculty/research/pubfiles/4261/glasserman_yao_guidelines.pdf

= References =
<references />

WS 2018/2019

2019-01-21T10:09:58Z

Dolj04: /* Papers */

Semestral papers from winter term 2018/2019. Please, put here links to the pages with your paper. First you need to have your [[Assignments WS 2018/2019|assignment approved]]

==Simulations==

--[[User:xvegm00|xvegm00]] [[User:Xvegm00|Xvegm00]] ([[User talk:Xvegm00|talk]]) 22:13, 8 January 2019 (CET) [[Simulation of semi-intelligent algae]]

-- Jan Doležálek [[User:Dolj04|Dolj04]] ([[User talk:Dolj04|talk]]) 16:50, 18 January 2019 (CET) [[Optimal size of HDD for virtual Digitization server]]

-- Jiří Korčák [[User:Xkorj58|Xkorj58]] ([[User talk:Xkorj58|talk]]) 11:09, 19 January 2019 (CET) [[Vacuum cleaner]]

-- Jan Mandík [[User:Manj01|Manj01]] ([[User talk:Manj01|talk]]) 14:46, 19 January 2019 (CET) [[Ticket Solving Process at a Small IT dev Company]]

-- [[User:Martin svejda|Martin svejda]] ([[User talk:Martin svejda|talk]]) 18:43, 19 January 2019 (CET) [[evacuation from burning building]]

-- [[User:Xlazl00|Xlazl00]] ([[User talk:Xlazl00|talk]]) 12:11, 20 January 2019 (CET) [[Medieval Battle Simulation]]

-- [[User:Qnesa01|Qnesa01]] ([User talk:Qnesa01|talk]]) 16:19, 20 January 2019 (CET) [[Argentinska Intersection]]

-- Jan Pippal (xpipj04) [[User:Janpippal|Janpippal]] 16:41, 20 January 2019 (CET) [[You are what you eat]]

-- [[User:Kadj02|Kadj02]] ([[User talk:Kadj02|talk]]) 23:19, 20 January 2019 (CET) [[Slime mold]]

-- [[User:Xkaij00|Xkaij00]] ([[User talk:Xkaij00|talk]]) 01:38, 21 January 2019 (CET) [[Simulation of north korea migration]]

==Papers==
-- [[User:Martin svejda|Martin svejda]] ([[User talk:Martin svejda|talk]]) 20:43, 12 January 2019 (CET) [https://en.wikipedia.org/wiki/Data_flow_diagram Complete redo of DFD wikipedia]~

-- [[User:Xvegm00|Xvegm00]] ([[User talk:Xvegm00|talk]]) 10:44, 17 January 2019 (CET) [[http://www.simulace.info/index.php/Multi-agent_systems Multi-agent systems]]

-- Jan Pippal (xpipj04) [[User:Janpippal|Janpippal]] 4:48, 20 January 2019 (CET) [https://en.wikipedia.org/wiki/Draft:MMABP MMABP in English]

-- [[User:Qnesa01|Qnesa01]] ([User talk:Qnesa01|talk]]) 17:19, 20 January 2019 (CET) [[Limits to Growth_ver2]] (WIP)

-- Tomáš Smysl (xsmyt00) [[User:Xsmyt00|Xsmyt00]] ([[User talk:Xsmyt00|talk]]) 22:36, 20 January 2019 (CET) [[https://en.wikipedia.org/wiki/ArchiMate ArchiMate wiki]] Note: I had some issues with the Wikipedia image upload - they did not approve my images. So the visual part of the Paper is missing examples of models that would ilustrate the text, which is quite unfortunate considering the topic is a visual modeling tool. I hope it can be solved later on. I even redrew some of the models so there would not be an issue with rights.

-- Jan Doležálek [[User:Dolj04|Dolj04]] ([[User talk:Dolj04|talk]]) 11:09, 21 January 2019 (CET) [[http://www.simulace.info/index.php/Variance_reduction Variance reduction]]

WS 2018/2019

2019-01-21T10:09:18Z

Dolj04: /* Papers */

Semestral papers from winter term 2018/2019. Please, put here links to the pages with your paper. First you need to have your [[Assignments WS 2018/2019|assignment approved]]

==Simulations==

--[[User:xvegm00|xvegm00]] [[User:Xvegm00|Xvegm00]] ([[User talk:Xvegm00|talk]]) 22:13, 8 January 2019 (CET) [[Simulation of semi-intelligent algae]]

-- Jan Doležálek [[User:Dolj04|Dolj04]] ([[User talk:Dolj04|talk]]) 16:50, 18 January 2019 (CET) [[Optimal size of HDD for virtual Digitization server]]

-- Jiří Korčák [[User:Xkorj58|Xkorj58]] ([[User talk:Xkorj58|talk]]) 11:09, 19 January 2019 (CET) [[Vacuum cleaner]]

-- Jan Mandík [[User:Manj01|Manj01]] ([[User talk:Manj01|talk]]) 14:46, 19 January 2019 (CET) [[Ticket Solving Process at a Small IT dev Company]]

-- [[User:Martin svejda|Martin svejda]] ([[User talk:Martin svejda|talk]]) 18:43, 19 January 2019 (CET) [[evacuation from burning building]]

-- [[User:Xlazl00|Xlazl00]] ([[User talk:Xlazl00|talk]]) 12:11, 20 January 2019 (CET) [[Medieval Battle Simulation]]

-- [[User:Qnesa01|Qnesa01]] ([User talk:Qnesa01|talk]]) 16:19, 20 January 2019 (CET) [[Argentinska Intersection]]

-- Jan Pippal (xpipj04) [[User:Janpippal|Janpippal]] 16:41, 20 January 2019 (CET) [[You are what you eat]]

-- [[User:Kadj02|Kadj02]] ([[User talk:Kadj02|talk]]) 23:19, 20 January 2019 (CET) [[Slime mold]]

-- [[User:Xkaij00|Xkaij00]] ([[User talk:Xkaij00|talk]]) 01:38, 21 January 2019 (CET) [[Simulation of north korea migration]]

==Papers==
-- [[User:Martin svejda|Martin svejda]] ([[User talk:Martin svejda|talk]]) 20:43, 12 January 2019 (CET) [https://en.wikipedia.org/wiki/Data_flow_diagram Complete redo of DFD wikipedia]~

-- [[User:Xvegm00|Xvegm00]] ([[User talk:Xvegm00|talk]]) 10:44, 17 January 2019 (CET) [[http://www.simulace.info/index.php/Multi-agent_systems Multi-agent systems]]

-- Jan Pippal (xpipj04) [[User:Janpippal|Janpippal]] 4:48, 20 January 2019 (CET) [https://en.wikipedia.org/wiki/Draft:MMABP MMABP in English]

-- [[User:Qnesa01|Qnesa01]] ([User talk:Qnesa01|talk]]) 17:19, 20 January 2019 (CET) [[Limits to Growth_ver2]] (WIP)

-- Tomáš Smysl (xsmyt00) [[User:Xsmyt00|Xsmyt00]] ([[User talk:Xsmyt00|talk]]) 22:36, 20 January 2019 (CET) [[https://en.wikipedia.org/wiki/ArchiMate ArchiMate wiki]] Note: I had some issues with the Wikipedia image upload - they did not approve my images. So the visual part of the Paper is missing examples of models that would ilustrate the text, which is quite unfortunate considering the topic is a visual modeling tool. I hope it can be solved later on. I even redrew some of the models so there would not be an issue with rights.

-- [[User:Dolj04|Dolj04]] ([[User talk:Dolj04|talk]]) 11:09, 21 January 2019 (CET) [[http://www.simulace.info/index.php/Variance_reduction]]

Variance reduction

2019-01-21T10:07:13Z

Dolj04: /* Stratification */

Monte Carlo is important but can be considered a straightforward technique. Its main issue is variance. To try to get rid of it, what can be done is to increase the number of samples N. However, each time we want to reduce variance two times, we need four fold the number of samples (for the blunder to diminish linearly, the quantity of tests needs to increase exponentially). Because of that great deal of research was invested into discovering whether change could be decreased by some other mean than simply expanding N. Luckily, mathematics can help answering this question. Monte Carlo integration typically has an error variance of the form σ^2/N. Even though we get a better answer by sampling with a larger value of N, the computing time grows with N. Sometimes it is conceivable to decrease σ instead. To do this, we construct a new Monte Carlo problem with the same answer as our original one but with a lower σ. This leads to an entire branch in Monte Carlo research focused on what's known as variance reduction methods. <ref>Scratchapixel . Scratchapixel . Monte Carlo Methods in Practice. [Online] [Citation: 19. 1 2019.] https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/variance-reduction-methods.</ref>
<ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref> 
When do we need variance reduction? It is mostly needed in simulations of highly complex models with high computation cost per replication, and in simulations of rare events with too many replications in crude Monte Carlo. There are many applications of these phenomena in a variety of fields, for example: physics, finance, statistics, reliability or systems biology.<ref>Zdravko Botev, Ad Ridder. Variance Reduction. School of Mathematics and Statistics. [Online] 2017. [Citation: 19. 1 2019.] https://web.maths.unsw.edu.au/~zdravkobotev/variancereductionCorrection.pdf</ref>

= Variance reduction techniques =
In this chapter can be found description for some of the popular classic variance reduction techniques, mainly focusing on antithetic variables and common random numbers (CRN). CRN is commonly utilized in a simulation study in which we want to compare performance measures of two distinct systems. Every single other method (for instance antithetic variables, stratification) is valuable in the case that we want to simulate a performance measure of only a single system. These methods all enhance effectiveness by sampling the input values more strategically. Next let’s consider conditioning and control variates. These methods take advantage of closed form solutions to problems similar to the given one. Another major method is importance sampling. Like some of the other methods, importance sampling also changes where we take the sample values, but rather than distributing them in more balanced ways it purposely oversamples from some regions and then corrects for this distortion by reweighting. It is accordingly an extreme reformulation of the issue and can be dubious to do well. <ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>
<ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref> 
Other group of methods consists of heuristic variance reduction techniques. Amongst them we can find some of those popular techniques: Weighting in lieu of absorption, Splitting, Forced collisions, Russian roulette, etc. Underlying idea here is that we want to choose from a probability distribution that we want to use rather than using the one that the physical data indicates.<ref>Pevey, Dr. Ronald E. Variance Reduction Techniques. web.utk.edu. [Online] 9. 3 2015. [Citation: 19. 1 2019.] http://web.utk.edu/~rpevey/public/NE582/Chapter%204.pdf</ref>
 
Last group we will mention here are more modern methods which include Quasi Monte Carlo and Multilevel Monte Carlo Estimator techniques.
<ref>Zdravko Botev, Ad Ridder. Variance Reduction. School of Mathematics and Statistics. [Online] 2017. [Citation: 19. 1 2019.] https://web.maths.unsw.edu.au/~zdravkobotev/variancereductionCorrection.pdf</ref>

== Common Random Numbers ==

Common random numbers (CRN) is the simplest and presumably the most widely used method for increasing the efficiency of comparisons via simulation. It is intuitively appealing and easy to implement in either a custom-made simulation or in a simulation package. In its simplest form, CRN just requires that the systems under study be simulated with the same stream of random numbers. Naturally, this appears to be reasonable since it guarantees that the frameworks are thought about under same conditions. Key idea in the method is that on the off chance X and Y are two random variables, then Var(X−Y) = Var(X) + Var(Y) − 2Cov(X, Y). Thus, for the situation that X and Y are positively correlated, i.e. Cov(X,Y)>0, the variance of X − Y will be smaller than in the case that X and Y are independent. In general, the use of common random numbers leads to positive correlation of the outcomes of a simulation of two systems. As a consequence, it is better to use common random numbers instead of independent random numbers when we compare two different systems.<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>
<ref>Paul Glasserman, David D. Yao. Some Guidelines and guarantees for common random numbers. MANAGEMENT SCIENCE. 38, 1992, No. 6.</ref>

=== Example 1 ===

Assume that a limited number of N jobs must be handled on two indistinguishable machines. The processing times of the jobs are random variables with some common distribution function F. We want to compare the completion time of the last job, Cmax, under two different policies. In the LPTF policy, we always choose the remaining job with the longest processing time first, in the SPTF policy we choose the remaining job with the shortest processing time first. In Table 1 and Table 2 we compare for N = 10 and F(x) = 1 − e^(-x) the estimators and confidence intervals for E(C SPTF max − C LPTF max ) when we do not, resp. do, use CRN. We conclude that in this example the use of CRN reduces the standard deviation of the estimator and hence also the length of the confidence interval with a factor 5.<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>

{| class="wikitable" style="margin: auto;"
|+Table 1: Estimation of E(C SPTF max − C LPTF max) without using common random numbers<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>
|-
|# of runs
|mean
|st. dev
|95% conf. int.
|-
|1000
|0.8138
|2.5745
|[0.645, 0.973]
|-
|10000
|0.8293
|2.4976
|[0.780, 0.878]
|-
|100000
|0.8487
|2.4990
|[0.833, 0.864]
|-
|1000000
|0.8398
|2.4951
|[0.835, 0.845]
|}

 
{| class="wikitable" style="margin: auto;"
|+Table 2: Estimation of E(C SPTF max − C LPTF max) using common random numbers <ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>
|-
|# of runs
|mean
|st. dev
|95% conf. int.
|-
|1000
|0.8559
|0.5416
|[0.822, 0.889]
|-
|10000
|0.8415
|0.5230
|[0.831, 0.852]
|-
|100000
|0.8394
|0.5164
|[0.836, 0.843]
|-
|1000000
|0.8391
|0.5168
|[0.838, 0.840]
|}

=== Example 2 ===

When we want to use CRN, the problem of synchronization can arise: How can we achieve that the same random numbers are used for the generation of the same random variables in the two systems? In the previous example, this synchronization problem did not arise. However, to illustrate this problem, consider the following situation. In a G/G/1 queueing system the server can work at two different speeds, v1 and v2. Aim of the simulation is to obtain an estimator for the difference of the waiting times in the two situations. We want to use the same realizations of the interarrival times and the sizes of the service requests in both systems (the service time is then given by the sizes of the service request divided by the speed of the server). If we use the program of the discrete event simulation of Section 3 of the G/G/1 queue, then we get the synchronization problem because the order in which departure and arrival events take place depends on the speed of the server. Hence, also the order in which interarrival times and sizes of service requests are generated depend on the speed of the server. The synchronization problem can be solved by one of the following two approaches: 1. Use separate random number streams for the different sequences of random variables needed in the simulation. 2. Assure that the random variables are generated in exactly the same order in the two systems. For the example of the G/G/1 queue, the first approach can be realized by using a separate random number stream for the interarrival times and for the service requests. The second approach can be realized by generating the service request of a customer already at the arrival instant of the customer.<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>

== Antithetic variables ==
The method of antithetic variables is a frequently suggested technique for reducing the variability of estimators in computer simulation experiments. In practice the method does not appear to work as well as it might and hence is not used as often as it should. The idea in the technique of antithetic variables is as follows: It makes use of the fact that if U is uniformly distributed on (0, 1) then so is 1 − U and furthermore U and 1 − U are negatively correlated. The key idea is that, if W1 and W2 are the outcomes of two successive simulation runs, then Var(W1 + W2/2)=1/4Var(W1)+1/4Var(W2)+1/2Cov(W1, W2). Hence, in the case that W1 and W2 are negatively correlated the variance of (W1 + W2)/2 will be smaller than in the case that W1 and W2 are independent. The question remains how we can achieve that the outcome of two successive simulation runs will be negatively correlated. From the fact that U and 1 − U are negatively correlated, we may expect that, if we use the random variables U1,...,Um to compute W1, the outcome of the first simulation run, and after that 1 − U1,...,1−Um to compute W2, the outcome of the second simulation run, then also W1 and W2 are negatively correlated. Intuition here is that, e.g., in the simulation of the G/G/1 queue large realizations of the Ui’s corresponding to large service times lead to large waiting times in the first run. Using the antithetic variables, this gives small realizations of the 1−Ui’s corresponding to small service times and hence leading to small waiting times in the second run. <ref>The Use of Antithetic Variates in Computer Simulations, R. C. H. Cheng, The Journal of the Operational Research Society, Vol. 33, No. 3 (Mar., 1982), pp. 229-237</ref>
<ref>Resing, Jacques. Variance Reduction Techniques. Lecture notes. [Online] [Citation: 19. 1 2019.] https://www.win.tue.nl/~resing/2S540/week6.pdf</ref>

== Stratification ==

Now, let’s just briefly mention the thought behind stratified sampling which is to split up the domain D of X into separate regions, take a well-defined sample of points from each such region, and combine the results to estimate E(f(X)). Naturally, on the off chance that every area gets a lot of points then we ought to get an improved answer. Figure 1 shows two little instances of stratified domains. We may have the capacity to improve the situation still by oversampling inside the vital strata and under sampling those in which f is almost consistent (similar to methods of importance sampling). <ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref>

[[File:stratifiedSamples.png|The left panel shows 20 points xi ∈ [0, 1]2 of which 5 are sampled uniformly from within each of four quadrants. The right panel shows 21 points from the N (0, I2) distribution. There are 6 concentric rings separating the distribution into 7 equally probable strata. Each stratum has 3 points sampled from within it.|center|500px]]
<ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref>

= Measuring variance reduction efficiency =
Using variance reduction can sometimes bring tremendous enhancements in contrast with conducting plain Monte Carlo. It isn’t exceptional for the value σ^2 to be reduced thousand times (or more). Unfortunately, it is likewise possible for a variance reduction technique to bring a very modest improvement, perhaps equivalent to diminishing σ^2 by only 10%. What is more regrettable, few methods will raise σ^2 in unwanted circumstances. The estimation of a variance reduction relies upon more than the change in σ^2. It likewise relies upon the PC's running time, perhaps the memory expended, and significantly, the human time taken to program and test the code. Suppose for simplicity, that a baseline method is unbiased and estimates the desired quantity with variance σ0^2/n, at a cost of nc0, when n function evaluations are used. To get an error variance of τ^2 we need n = σ0^2/τ^2 and this will cost c0σ0^2/τ^2. Here we are assuming that cost is measured in time and that overhead cost is small. On the off chance that an alternative fair-minded method has variance σ1^2/n and cost nc1 under these conditions, then it will cost us c1σ1^2/τ2 to achieve the same error variance τ^2 that the baseline method achieved. The efficiency of the new method, relative to the standard method is E = c0σ0^2/ c1σ1^2. At any fixed level of accuracy, the old method takes E times as much work as the new one. The efficiency has two factors, σ0^2/σ1^2 and c0/c1. The first is a mathematical property of the two methods that we can often handle theoretically. The second is more complicated. It can depend heavily on the algorithms used for each method. It can also depend on details of the computing environment, including the computer hardware, operating system, and implementation language. Note that numerical outcomes for c0/c1 acquired in one setting don't really apply to another. 
There is no settled guideline for how substantial a productivity enhancement must be to make it worth utilizing. In a few settings, for example, rendering PC illustrations for movies, where a large number of CPUs are kept occupied for a considerable length of time, a 10% enhancement (i.e., E = 1.1) brings important reserve funds. In different settings, for example, an irregular calculation, a 60-overlap gain (i.e., E = 60) which transforms a one-minute pause into a one second pause, may not justify the expense of programming a more complicated solution. 
Computation costs so much less than human effort that we commonly require substantial proficiency gains to counterbalance the time spent programming up a variance decrease. The force to search out a productivity enhancement may possibly come when we end up hanging tight quite a while for an outcome, as, when we have to put our whole Monte Carlo figuring inside a loop representing numerous variations of the issue. A very slow computation costs more than just the computer’s time. It may waste time for those waiting for the answer (workforce). Also, slow computations reduce the number of alternatives that one can explore and thus not giving as options to choose from which would be preferable in many situations. 
The effectiveness increase important to justify using a method is less if the programming exertion can be amortized over numerous applications. The edge is very high for a one-time program, lower for something that we are adding to our personal library, lower still for code to share with a few associates and even lower for code to be put into a library or simulation tool for general use. Important is to note that all of the methods mentioned in previous chapter are capable of a great range of efficiency improvements.<ref>Owen, Art B. Monte Carlo theory, methods and examples. Stanford.edu. [Online] 2013. [Citation: 19. 1 2019.] https://statweb.stanford.edu/~owen/mc/Ch-var-basic.pdf</ref>

= Recommended reading =

https://web.maths.unsw.edu.au/~zdravkobotev/variancereductionCorrection.pdf
http://sas.uwaterloo.ca/~dlmcleis/s906/chapt4.pdf
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-mathematical-foundations/variance-and-standard-deviation
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/variance-reduction-methods
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/introduction-quasi-monte-carlo
https://www0.gsb.columbia.edu/mygsb/faculty/research/pubfiles/4261/glasserman_yao_guidelines.pdf

= References =
<references />

File:StratifiedSamples.png

2019-01-21T10:06:35Z

Dolj04:

File:Dolj04 Optimal size of HDD for virtual Digitization server.xlsx

2019-01-21T10:05:58Z

Dolj04:

Optimal size of HDD for virtual Digitization server

2019-01-21T10:05:33Z

Dolj04: /* Derivation of probability distributions */

=Introduction=

Proper usage of server space and capacity is very important for companies these days as the volume of data gathered and produced is growing rapidly and is essential for proper operation of modern companies.
This simulation is designed to calculate optimal HDD size for a server which is used for processing documents and is based on real data obtained from a company production server.

=Problem definition=
The simulation is based on data gathered by a server application in database, observations of the server (mainly focused on batch count and their size) and additional information about the solution running on the server gathered from documentation:
*Processing takes place only on work days
*Every document scanned to the server is processed by a digitization application which creates batch that contains original scanned document, extracted data in XML files, log files, enhanced images and searchable PDF
*Application saves all important information about batches in database
*Backup images from scanning will stay on the server for 6 months (those are additional ~50 % of the batch size) and are in separate folder from the batch folders
*Successfully processed batches older than 14 days are deleted every day by another application that also produces log files about the successful/failed deletion
*For precaution let’s assume 5% of batches could fail to be processed correctly (however in obtained sample all batches were processed correctly)
**Those will stay on the server and will be processed every 6 months by admins when deleting backup

==Observation==
First observation was made to assess the data available and to decide about proper approach when designing the simulation.
Information gathered during observation:
*Each day an average of 17 batches were processed by the server with average size per batch of 24 MB
*The number of batches changes a lot and can’t be easily predicted so it will have to be taken into consideration
*Information about deleted batches can be found in database on the server

==Simulation environment==
MS Excel 2016
==Simulation method==
Monte Carlo

=Obtaining real data=
The data for simulation was extracted from a database which contains information about all the batches that were processed on the server during the last 65 working days. Total of 1124 batches were processed during those days. Important part of the database table needed for simulation is included in the MS Excel file.

=Derivation of probability distributions=
After the data was gathered and analyzed through a contingency table, graphs were made to display the average batch size (in bins with increment of 5000 KB) and the average batch count per day. Both those graphs are from the log-normal distribution and so the random values were generated based on those distributions for average batch size as well as the average batch count.

[[File:lognormaldistribution1.png|Number o batches in size bins (batch size range of 5000 KB, average)|center|500px|]]

[[File:lognormaldistribution2.png|Number of different batch count occurances (average)|center|500px|]]

=Simulation=
For the simulation 132 working days (6 months) were considered as the time before backup deletion and error fix-up takes place. For both average batch size and average batch count random values were generated from the log-normal distribution based on scaled mean (m) and standard deviation (s) of the original data set. 

Those random values were generated 132 times and then multiplied. After multiplication of those 2 values followed calculating the error and backup size and the cumulative size which was reduced each step starting at 10 steps (14 days for deletion of the oldest batch). Overall size after 6 months was used in excel data table to generate this simulation 1000 times.

=Results=
After generating 1000 simulations the AVG, highest and lowest space needed was calculated and is displayed in table below:

{| class="wikitable" style="margin: auto;"
|+1000 simulations results
|-
|
|In KB
|In MB
|In GB
|-
|'''AVG Space needed:'''
|35189448.7
|34364.7
|33.55927
|-
|'''Highest space needed:'''
|105577213
|103102.7
|100.6863
|-
|'''Lowest space needed:'''
|21607404.9
|21100.98
|20.60643
|}

Issue with the results is that the highest space needed changes a lot (because the batch size and count changes a lot as was mentioned at the beginning of the paper) even when running the simulation 1000 times. It had to be taken into consideration when deriving conclusions.

=Conclusion=
One option for the company when deciding how much space should be reserved for document processing based on the simulation would be to take into consideration the highest space needed from 1000 simulations which is nearly 101 GB. Second recommendation, when using this option, would be to monitor the server at least once a month as the highest value varies a lot and adjust the size if needed. Upside of this approach is that it requires less initial work. 
Due to high variance another approach for defining the space needed is to consider only the average space needed so the HDD would have “only” 34 GB free space starting each 6 months. However, when using this approach, if the HDD starts getting full, increasing the size automatically based on the last month when backup deletion took place is necessary. Upside of this solution is proper space utilization as most of the time big part of disk space would be unused if one considers only the highest size needed (based on the average space needed).

=Code=

The Excel file with simulation can be found here:
https://app.box.com/s/duj71rtgvf4g1u9gi011tcib2umnjdil

[[File:dolj04_Optimal size of HDD for virtual Digitization server.xlsx]]

Optimal size of HDD for virtual Digitization server

2019-01-21T10:04:51Z

Dolj04: /* Derivation of probability distributions */

=Introduction=

Proper usage of server space and capacity is very important for companies these days as the volume of data gathered and produced is growing rapidly and is essential for proper operation of modern companies.
This simulation is designed to calculate optimal HDD size for a server which is used for processing documents and is based on real data obtained from a company production server.

=Problem definition=
The simulation is based on data gathered by a server application in database, observations of the server (mainly focused on batch count and their size) and additional information about the solution running on the server gathered from documentation:
*Processing takes place only on work days
*Every document scanned to the server is processed by a digitization application which creates batch that contains original scanned document, extracted data in XML files, log files, enhanced images and searchable PDF
*Application saves all important information about batches in database
*Backup images from scanning will stay on the server for 6 months (those are additional ~50 % of the batch size) and are in separate folder from the batch folders
*Successfully processed batches older than 14 days are deleted every day by another application that also produces log files about the successful/failed deletion
*For precaution let’s assume 5% of batches could fail to be processed correctly (however in obtained sample all batches were processed correctly)
**Those will stay on the server and will be processed every 6 months by admins when deleting backup

==Observation==
First observation was made to assess the data available and to decide about proper approach when designing the simulation.
Information gathered during observation:
*Each day an average of 17 batches were processed by the server with average size per batch of 24 MB
*The number of batches changes a lot and can’t be easily predicted so it will have to be taken into consideration
*Information about deleted batches can be found in database on the server

==Simulation environment==
MS Excel 2016
==Simulation method==
Monte Carlo

=Obtaining real data=
The data for simulation was extracted from a database which contains information about all the batches that were processed on the server during the last 65 working days. Total of 1124 batches were processed during those days. Important part of the database table needed for simulation is included in the MS Excel file.

=Derivation of probability distributions=
After the data was gathered and analyzed through a contingency table, graphs were made to display the average batch size (in bins with increment of 5000 KB) and the average batch count per day. Both those graphs are from the log-normal distribution and so the random values were generated based on those distributions for average batch size as well as the average batch count.

[[File:lognormaldistribution1.png|Number o batches in size bins (batch size range of 5000 KB, average)|center]]

[[File:lognormaldistribution2.png|Number of different batch count occurances (average)|center]]

=Simulation=
For the simulation 132 working days (6 months) were considered as the time before backup deletion and error fix-up takes place. For both average batch size and average batch count random values were generated from the log-normal distribution based on scaled mean (m) and standard deviation (s) of the original data set. 

Those random values were generated 132 times and then multiplied. After multiplication of those 2 values followed calculating the error and backup size and the cumulative size which was reduced each step starting at 10 steps (14 days for deletion of the oldest batch). Overall size after 6 months was used in excel data table to generate this simulation 1000 times.

=Results=
After generating 1000 simulations the AVG, highest and lowest space needed was calculated and is displayed in table below:

{| class="wikitable" style="margin: auto;"
|+1000 simulations results
|-
|
|In KB
|In MB
|In GB
|-
|'''AVG Space needed:'''
|35189448.7
|34364.7
|33.55927
|-
|'''Highest space needed:'''
|105577213
|103102.7
|100.6863
|-
|'''Lowest space needed:'''
|21607404.9
|21100.98
|20.60643
|}

Issue with the results is that the highest space needed changes a lot (because the batch size and count changes a lot as was mentioned at the beginning of the paper) even when running the simulation 1000 times. It had to be taken into consideration when deriving conclusions.

=Conclusion=
One option for the company when deciding how much space should be reserved for document processing based on the simulation would be to take into consideration the highest space needed from 1000 simulations which is nearly 101 GB. Second recommendation, when using this option, would be to monitor the server at least once a month as the highest value varies a lot and adjust the size if needed. Upside of this approach is that it requires less initial work. 
Due to high variance another approach for defining the space needed is to consider only the average space needed so the HDD would have “only” 34 GB free space starting each 6 months. However, when using this approach, if the HDD starts getting full, increasing the size automatically based on the last month when backup deletion took place is necessary. Upside of this solution is proper space utilization as most of the time big part of disk space would be unused if one considers only the highest size needed (based on the average space needed).

=Code=

The Excel file with simulation can be found here:
https://app.box.com/s/duj71rtgvf4g1u9gi011tcib2umnjdil

[[File:dolj04_Optimal size of HDD for virtual Digitization server.xlsx]]

File:Lognormaldistribution2.png

2019-01-21T10:03:08Z

Dolj04:

2019-01-20T15:01:14Z

Dolj04: /* Antithetic variables */

Monte Carlo can be considered a straightforward (but important) technique as one can notice. Its main issue though is variance. To try to get rid of it, what can be done is to increase the number of samples N. However, each time we want to reduce variance two times, we need four fold the number of samples (for the blunder to diminish linearly, the quantity of tests needs to increase exponentially). Because of that great deal of research was invested into discovering whether change could be decreased by some other mean than simply expanding N. Luckily, mathematics can help answering this question. Monte Carlo integration typically has an error variance of the form σ2/N. Even though we get a better answer by sampling with a larger value of N, the computing time grows with N. Sometimes it is conceivable to decrease σ instead. To do this, we construct a new Monte Carlo problem with the same answer as our original one but with a lower σ. This leads to an entire branch in Monte Carlo research focused on what's known as variance reduction methods. 
When do we need variance reduction? It is mostly needed in simulations of highly complex models with high computation cost per replication, and in simulations of rare events with too many replications in crude Monte Carlo. There are many applications of these phenomena in a variety of fields, for example: physics, finance, statistics, reliability or systems biology.

= Variance reduction techniques =
In this chapter can be found description for some of the popular classic variance reduction techniques, mainly focusing on antithetic variables and common random numbers (CRN). CRN is commonly utilized in a simulation study in which we want to compare performance measures of two distinct systems. Every single other method (for instance antithetic variables, stratification) is valuable in the case that we want to simulate a performance measure of only a single system. These methods all enhance effectiveness by sampling the input values more strategically. Next let’s consider conditioning and control variates. These methods take advantage of closed form solutions to problems similar to the given one. Another major method is importance sampling. Like some of the other methods, importance sampling also changes where we take the sample values, but rather than distributing them in more balanced ways it purposely oversamples from some regions and then corrects for this distortion by reweighting. It is accordingly an extreme reformulation of the issue and can be dubious to do well. 
Other group of methods consists of heuristic variance reduction techniques. Amongst them we can find some of those popular techniques: Weighting in lieu of absorption, Splitting, Forced collisions, Russian roulette, etc. Underlying idea here is that we want to choose from a probability distribution that we want to use rather than using the one that the physical data indicates. 
Last group we will mention here are more modern methods which include Quasi Monte Carlo and Multilevel Monte Carlo Estimator techniques.

== Common Random Numbers ==

Common random numbers (CRN) is the simplest and presumably the most widely used method for increasing the efficiency of comparisons via simulation. It is intuitively appealing and easy to implement in either a custom-made simulation or in a simulation package. In its simplest form, CRN just requires that the systems under study be simulated with the same stream of random numbers. Naturally, this appears to be reasonable since it guarantees that the frameworks are thought about under same conditions. Key idea in the method is that on the off chance X and Y are two random variables, then Var(X−Y) = Var(X) + Var(Y) − 2Cov(X, Y). Thus, for the situation that X and Y are positively correlated, i.e. Cov(X,Y)>0, the variance of X − Y will be smaller than in the case that X and Y are independent. In general, the use of common random numbers leads to positive correlation of the outcomes of a simulation of two systems. As a consequence, it is better to use common random numbers instead of independent random numbers when we compare two different systems.

== Antithetic variables ==
The method of antithetic variables is a frequently suggested technique for reducing the variability of estimators in computer simulation experiments. In practice the method does not appear to work as well as it might and hence is not used as often as it should. The idea in the technique of antithetic variables is as follows: It makes use of the fact that if U is uniformly distributed on (0, 1) then so is 1 − U and furthermore U and 1 − U are negatively correlated. The key idea is that, if W1 and W2 are the outcomes of two successive simulation runs, then Var(W1 + W2/2)=1/4Var(W1)+1/4Var(W2)+1/2Cov(W1, W2). Hence, in the case that W1 and W2 are negatively correlated the variance of (W1 + W2)/2 will be smaller than in the case that W1 and W2 are independent. The question remains how we can achieve that the outcome of two successive simulation runs will be negatively correlated. From the fact that U and 1 − U are negatively correlated, we may expect that, if we use the random variables U1,...,Um to compute W1, the outcome of the first simulation run, and after that 1 − U1,...,1−Um to compute W2, the outcome of the second simulation run, then also W1 and W2 are negatively correlated. Intuition here is that, e.g., in the simulation of the G/G/1 queue large realizations of the Ui’s corresponding to large service times lead to large waiting times in the first run. Using the antithetic variables, this gives small realizations of the 1−Ui’s corresponding to small service times and hence leading to small waiting times in the second run.

== Stratification ==

Now, let’s just briefly mention the thought behind stratified sampling which is to split up the domain D of X into separate regions, take a well-defined sample of points from each such region, and combine the results to estimate E(f(X)). Naturally, on the off chance that every area gets a lot of points then we ought to get an improved answer. Figure 1 shows two little instances of stratified domains. We may have the capacity to improve the situation still by oversampling inside the vital strata and under sampling those in which f is almost consistent (similar to methods of importance sampling).

= Measuring variance reduction efficiency =
Using variance reduction can sometimes bring tremendous enhancements in contrast with conducting plain Monte Carlo. It isn’t exceptional for the value σ2 to be reduced thousand times (or more). Unfortunately, it is likewise possible for a variance reduction technique to bring a very modest improvement, perhaps equivalent to diminishing σ2 by only 10%. What is more regrettable, few methods will raise σ2 in unwanted circumstances. The estimation of a variance reduction relies upon more than the change in σ2. It likewise relies upon the PC's running time, perhaps the memory expended, and significantly, the human time taken to program and test the code. Suppose for simplicity, that a baseline method is unbiased and estimates the desired quantity with variance σ20/n, at a cost of nc0, when n function evaluations are used. To get an error variance of τ2 we need n = σ20/τ2 and this will cost c0σ20/τ2. Here we are assuming that cost is measured in time and that overhead cost is small. On the off chance that an alternative fair-minded method has variance σ21/n and cost nc1 under these conditions, then it will cost us c1σ21/τ2 to achieve the same error variance τ2 that the baseline method achieved. The efficiency of the new method, relative to the standard method is E = c0σ20/ c1σ21. At any fixed level of accuracy, the old method takes E times as much work as the new one. The efficiency has two factors, σ20/ σ21 and c0/c1. The first is a mathematical property of the two methods that we can often handle theoretically. The second is more complicated. It can depend heavily on the algorithms used for each method. It can also depend on details of the computing environment, including the computer hardware, operating system, and implementation language. Note that numerical outcomes for c0/c1 acquired in one setting don't really apply to another. 
There is no settled guideline for how substantial a productivity enhancement must be to make it worth utilizing. In a few settings, for example, rendering PC illustrations for movies, where a large number of CPUs are kept occupied for a considerable length of time, a 10% enhancement (i.e., E = 1.1) brings important reserve funds. In different settings, for example, an irregular calculation, a 60-overlap gain (i.e., E = 60) which transforms a one-minute pause into a one second pause, may not justify the expense of programming a more complicated solution. 
Computation costs so much less than human effort that we commonly require substantial proficiency gains to counterbalance the time spent programming up a variance decrease. The force to search out a productivity enhancement may possibly come when we end up hanging tight quite a while for an outcome, as, when we have to put our whole Monte Carlo figuring inside a loop representing numerous variations of the issue. A very slow computation costs more than just the computer’s time. It may waste time for those waiting for the answer (workforce). Also, slow computations reduce the number of alternatives that one can explore and thus not giving as options to choose from which would be preferable in many situations. 
The effectiveness increase important to justify using a method is less if the programming exertion can be amortized over numerous applications. The edge is very high for a one-time program, lower for something that we are adding to our personal library, lower still for code to share with a few associates and even lower for code to be put into a library or simulation tool for general use. Important is to note that all of the methods mentioned in previous chapter are capable of a great range of efficiency improvements. 

= Recommended reading =

https://web.maths.unsw.edu.au/~zdravkobotev/variancereductionCorrection.pdf
http://sas.uwaterloo.ca/~dlmcleis/s906/chapt4.pdf
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-mathematical-foundations/variance-and-standard-deviation
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/variance-reduction-methods
https://www.scratchapixel.com/lessons/mathematics-physics-for-computer-graphics/monte-carlo-methods-in-practice/introduction-quasi-monte-carlo
https://www0.gsb.columbia.edu/mygsb/faculty/research/pubfiles/4261/glasserman_yao_guidelines.pdf

Variance reduction

2019-01-20T14:56:25Z

Dolj04: /* Measuring variance reduction efficiency */

Variance reduction

2019-01-20T14:38:11Z

Dolj04: /* Variance reduction techniques */

Variance reduction

2019-01-20T14:33:09Z

Dolj04: Variance reduction (textbook text)

Optimal size of HDD for virtual Digitization server

2019-01-19T14:44:31Z

Dolj04:

=Introduction=

Proper usage of server space and capacity is very important for companies these days as the volume of data gathered and produced is growing rapidly and is essential for proper operation of modern companies.
This simulation is designed to calculate optimal HDD size for a server which is used for processing documents and is based on real data obtained from a company production server.

=Problem definition=
The simulation is based on data gathered by a server application in database, observations of the server (mainly focused on batch count and their size) and additional information about the solution running on the server gathered from documentation:
*Processing takes place only on work days
*Every document scanned to the server is processed by a digitization application which creates batch that contains original scanned document, extracted data in XML files, log files, enhanced images and searchable PDF
*Application saves all important information about batches in database
*Backup images from scanning will stay on the server for 6 months (those are additional ~50 % of the batch size) and are in separate folder from the batch folders
*Successfully processed batches older than 14 days are deleted every day by another application that also produces log files about the successful/failed deletion
*For precaution let’s assume 5% of batches could fail to be processed correctly (however in obtained sample all batches were processed correctly)
**Those will stay on the server and will be processed every 6 months by admins when deleting backup

==Observation==
First observation was made to assess the data available and to decide about proper approach when designing the simulation.
Information gathered during observation:
*Each day an average of 17 batches were processed by the server with average size per batch of 24 MB
*The number of batches changes a lot and can’t be easily predicted so it will have to be taken into consideration
*Information about deleted batches can be found in database on the server

==Simulation environment==
MS Excel 2016
==Simulation method==
Monte Carlo

=Obtaining real data=
The data for simulation was extracted from a database which contains information about all the batches that were processed on the server during the last 65 working days. Total of 1124 batches were processed during those days. Important part of the database table needed for simulation is included in the MS Excel file.

=Derivation of probability distributions=
After the data was gathered and analyzed through a contingency table, graphs were made to display the average batch size (in bins with increment of 5000 KB) and the average batch count per day. Both those graphs are from the log-normal distribution and so the random values were generated based on those distributions for average batch size as well as the average batch count.

[[File:lognormaldistribution1.png|Number o batches in size bins (batch size range of 5000 KB, average)]]

[[File:lognormaldistribution2.png|Number of different batch count occurances (average)]]

=Simulation=
For the simulation 132 working days (6 months) were considered as the time before backup deletion and error fix-up takes place. For both average batch size and average batch count random values were generated from the log-normal distribution based on scaled mean (m) and standard deviation (s) of the original data set. 

Those random values were generated 132 times and then multiplied. After multiplication of those 2 values followed calculating the error and backup size and the cumulative size which was reduced each step starting at 10 steps (14 days for deletion of the oldest batch). Overall size after 6 months was used in excel data table to generate this simulation 1000 times.

=Results=
After generating 1000 simulations the AVG, highest and lowest space needed was calculated and is displayed in table below:

{| class="wikitable"
|+1000 simulations results
|-
|
|In KB
|In MB
|In GB
|-
|'''AVG Space needed:'''
|35189448.7
|34364.7
|33.55927
|-
|'''Highest space needed:'''
|105577213
|103102.7
|100.6863
|-
|'''Lowest space needed:'''
|21607404.9
|21100.98
|20.60643
|}

Issue with the results is that the highest space needed changes a lot (because the batch size and count changes a lot as was mentioned at the beginning of the paper) even when running the simulation 1000 times. It had to be taken into consideration when deriving conclusions.

=Conclusion=
One option for the company when deciding how much space should be reserved for document processing based on the simulation would be to take into consideration the highest space needed from 1000 simulations which is nearly 101 GB. Second recommendation, when using this option, would be to monitor the server at least once a month as the highest value varies a lot and adjust the size if needed. Upside of this approach is that it requires less initial work. 
Due to high variance another approach for defining the space needed is to consider only the average space needed so the HDD would have “only” 34 GB free space starting each 6 months. However, when using this approach, if the HDD starts getting full, increasing the size automatically based on the last month when backup deletion took place is necessary. Upside of this solution is proper space utilization as most of the time big part of disk space would be unused if one considers only the highest size needed (based on the average space needed).

=Code=

The Excel file with simulation can be found here:
https://app.box.com/s/duj71rtgvf4g1u9gi011tcib2umnjdil

[[File:dolj04_Optimal size of HDD for virtual Digitization server.xlsx]]

Optimal size of HDD for virtual Digitization server

2019-01-18T16:26:22Z

Dolj04:

=Introduction=

Proper usage of server space and capacity is very important for companies these days as the volume of data gathered and produced is growing rapidly and is essential for proper operation of modern companies.
This simulation is designed to calculate optimal HDD size for a server which is used for processing documents and is based on real data obtained from a company production server.

=Problem definition=
The simulation is based on data gathered by a server application in database, observations of the server (mainly focused on batch count and their size) and additional information about the solution running on the server gathered from documentation:
*Processing takes place only on work days
*Every document scanned to the server is processed by a digitization application which creates batch that contains original scanned document, extracted data in XML files, log files, enhanced images and searchable PDF
*Application saves all important information about batches in database
*Backup images from scanning will stay on the server for 6 months (those are additional ~50 % of the batch size) and are in separate folder from the batch folders
*Successfully processed batches older than 14 days are deleted every day by another application that also produces log files about the successful/failed deletion
*For precaution let’s assume 5% of batches could fail to be processed correctly (however in obtained sample all batches were processed correctly)
**Those will stay on the server and will be processed every 6 months by admins when deleting backup

==Observation==
First observation was made to assess the data available and to decide about proper approach when designing the simulation.
Information gathered during observation:
*Each day an average of 17 batches were processed by the server with average size per batch of 24 MB
*The number of batches changes a lot and can’t be easily predicted so it will have to be taken into consideration
*Information about deleted batches can be found in database on the server

==Simulation environment==
MS Excel 2016
==Simulation method==
Monte Carlo

=Obtaining real data=
The data for simulation was extracted from a database which contains information about all the batches that were processed on the server during the last 65 working days. Total of 1124 batches were processed during those days. Important part of the database table needed for simulation is included in the MS Excel file.

=Derivation of probability distributions=
After the data was gathered and analyzed through a contingency table, graphs were made to display the average batch size (in bins with increment of 5000 KB) and the average batch count per day. Both those graphs are from the log-normal distribution and so the random values were generated based on those distributions for average batch size as well as the average batch count.

[[File:lognormaldistribution1.png|Number o batches in size bins (batch size range of 5000 KB, average)]]

[[File:lognormaldistribution2.png|Number of different batch count occurances (average)]]

=Simulation=
For the simulation 132 working days (6 months) were considered as the time before backup deletion and error fix-up takes place. For both average batch size and average batch count random values were generated from the log-normal distribution based on scaled mean (m) and standard deviation (s) of the original data set. 

Those random values were generated 132 times and then multiplied. After multiplication of those 2 values followed calculating the error and backup size and the cumulative size which was reduced each step starting at 10 steps (14 days for deletion of the oldest batch). Overall size after 6 months was used in excel data table to generate this simulation 1000 times.

=Results=
After generating 1000 simulations the AVG, highest and lowest space needed was calculated and is displayed in table below:

{| class="wikitable"
|+1000 simulations results
|-
|
|In KB
|In MB
|In GB
|-
|'''AVG Space needed:'''
|35189448.7
|34364.7
|33.55927
|-
|'''Highest space needed:'''
|105577213
|103102.7
|100.6863
|-
|'''Lowest space needed:'''
|21607404.9
|21100.98
|20.60643
|}

Issue with the results is that the highest space needed changes a lot (because the batch size and count changes a lot as was mentioned at the beginning of the paper) even when running the simulation 1000 times. It had to be taken into consideration when deriving conclusions.

=Conclusion=
One option for the company when deciding how much space should be reserved for document processing based on the simulation would be to take into consideration the highest space needed from 1000 simulations which is nearly 101 GB. Second recommendation, when using this option, would be to monitor the server at least once a month as the highest value varies a lot and adjust the size if needed. Upside of this approach is that it requires less initial work. 
Due to high variance another approach for defining the space needed is to consider only the average space needed so the HDD would have “only” 34 GB free space starting each 6 months. However, when using this approach, if the HDD starts getting full, increasing the size automatically based on the last month when backup deletion took place is necessary. Upside of this solution is proper space utilization as most of the time big part of disk space would be unused if one considers only the highest size needed (based on the average space needed).

=Code=

[[File:dolj04_Optimal size of HDD for virtual Digitization server.xlsx]]

User:Dolj04

2019-01-18T16:18:18Z

Dolj04: Created page with "File:lognormaldistribution1.png"

[[File:lognormaldistribution1.png]]

Optimal size of HDD for virtual Digitization server

2019-01-18T16:12:53Z

Dolj04: Monte carlo simulation - Calculating optimal size of HDD for virtual Digitization server

=Introduction=

Proper usage of server space and capacity is very important for companies these days as the volume of data gathered and produced is growing rapidly and is essential for proper operation of modern companies.
This simulation is designed to calculate optimal HDD size for a server which is used for processing documents and is based on real data obtained from a company production server.

=Problem definition=
The simulation is based on data gathered by a server application in database, observations of the server (mainly focused on batch count and their size) and additional information about the solution running on the server gathered from documentation:
*Processing takes place only on work days
*Every document scanned to the server is processed by a digitization application which creates batch that contains original scanned document, extracted data in XML files, log files, enhanced images and searchable PDF
*Application saves all important information about batches in database
*Backup images from scanning will stay on the server for 6 months (those are additional ~50 % of the batch size) and are in separate folder from the batch folders
*Successfully processed batches older than 14 days are deleted every day by another application that also produces log files about the successful/failed deletion
*For precaution let’s assume 5% of batches could fail to be processed correctly (however in obtained sample all batches were processed correctly)
**Those will stay on the server and will be processed every 6 months by admins when deleting backup

==Observation==
First observation was made to assess the data available and to decide about proper approach when designing the simulation.
Information gathered during observation:
*Each day an average of 17 batches were processed by the server with average size per batch of 24 MB
*The number of batches changes a lot and can’t be easily predicted so it will have to be taken into consideration
*Information about deleted batches can be found in database on the server

==Simulation environment==
MS Excel 2016
==Simulation method==
Monte Carlo

=Obtaining real data=
The data for simulation was extracted from a database which contains information about all the batches that were processed on the server during the last 65 working days. Total of 1124 batches were processed during those days. Important part of the database table needed for simulation is included in the MS Excel file.

=Derivation of probability distributions=
After the data was gathered and analyzed through a contingency table, graphs were made to display the average batch size (in bins with increment of 5000 KB) and the average batch count per day. Both those graphs are from the lognormal distribution and so the random values were generated based on those distributions for average batch size as well as the average batch count.

[[File:BatchesGraph1.jpg|Number o batches in size bins (batch size range of 5000 KB, average)]]

[[File:BatchesGraph2.jpg|Number of different batch count occurances (average)]]

=Simulation=
For the simulation 132 working days (6 months) were considered as the time before backup deletion and error fixup takes place. For both average batch size and average batch count random values were generated from the lognormal distribution based on scaled mean (m) and standard deviation (s) of the original data set. 

Those random values were generated 132 times and then multiplied. After multiplication of those 2 values followed calculating the error and backup size and the cumulative size which was reduced each step starting at 10 steps (14 days for deletion of the oldest batch). Overall size after 6 months was used in excel data table to generate this simulation 1000 times.

=Results=
After generating 1000 simulations the AVG, highest and lowest space needed was calculated and is displayed in table below:

{| class="wikitable"
|+1000 simulations results
|-
|
|In KB
|In MB
|In GB
|-
|'''AVG Space needed:'''
|35189448.7
|34364.7
|33.55927
|-
|'''Highest space needed:'''
|105577213
|103102.7
|100.6863
|-
|'''Lowest space needed:'''
|21607404.9
|21100.98
|20.60643
|}

Issue with the results is that the highest space needed changes a lot (because the batch size and count changes a lot as was mentioned at the beginning of the paper) even when running the simulation 1000 times. It had to be taken into consideration when deriving conclusions.

=Conclusion=
One option for the company when deciding how much space should be reserved for document processing based on the simulation would be to take into consideration the highest space needed from 1000 simulations which is nearly 101 GB. Second recommendation, when using this option, would be to monitor the server at least once a month as the highest value varies a lot and adjust the size if needed. Upside of this approach is that it requires less initial work. 
Due to high variance another approach for defining the space needed is to consider only the average space needed so the HDD would have “only” 34 GB free space starting each 6 months. However, when using this approach, if the HDD starts getting full, increasing the size automatically based on the last month when backup deletion took place is necessary. Upside of this solution is proper space utilization as most of the time big part of disk space would be unused if one considers only the highest size needed (based on the average space needed).

=Code=

[[File:dolj04_Optimal size of HDD for virtual Digitization server.xlsx]]

WS 2018/2019

2019-01-18T15:50:33Z

Dolj04: /* Simulations */

Assignments WS 2018/2019

2018-12-19T22:23:17Z

Dolj04:

{{Ambox
| text = <div>
Please, put here your assignments. Do not forget to sign them. You can use <nowiki>~~~~</nowiki> (four tildas) for an automatic signature. Use Show preview in order to check the result before your final sumbition.
</div>
}}

{{Ambox
| text = <div>
Please, strive to formulate your assignment carefully. We expect an adequate effort to formulate the assignment as it is your semestral paper. Do not forget that your main goal is a research paper. It means your simulation model must generate the results that are specific, measurable and verifiable. Think twice how you will develop your model, which entities you will use, draw a model diagram, consider what you will measure. No sooner than when you have a good idea about the model, submit your assignment. And of course, read [[How to deal with the simulation assignment|How to deal with the simulation assignment]].
</div>
}}

{{Ambox
| text = <div>
Topics on gambling, cards, etc. are not welcome.
</div>
}}

{{Ambox
| type = content
| text = <div>
In order to avoid possible confusion, please, check if you have added '''approved''' in bold somewhere in our comment under your submission. If there is no '''approved''', it means the assignment was not approved yet.
</div>
}}

[[Xvegm00|Xvegm00]]

[[Xkorj58|Xkorj58 (not approved yet)]]

----

== Simulation proposal (dolj04) ==

Topic/goal: '''Optimal size of HDD for virtual Digitization server'''

Definition of the problem: 
- each day an average of 47 batches of documents is being processed by the server with average size per batch of 32 MB (calculated from customers server) 
- the number of batches changes a lot and cant be easily predicted so it will have to be taken into consideration (from sample: lowest number of batches scanned in a day is 13, the highest is 134) 
- the average size is not changing that much 
- (batch contains original scanned documents, extracted data in XML files, log files, enhanced images and searchable PDF) 
- backup images from scanning will stay on the server for 6 months (those are ''additional'' ~50 % of the batch size) 
- successfully processed batches older than 14 days are deleted every day 
- for precaution lets say around 5% of batches wont be processed correctly 
- those will stay on the server and will be processed every month by admins 

Simulation environment: Vensim

:: on what data you will base the simulation? I do not see any causal loops in the issue you are trying to solve, using Vesim does not make much sense then- this topic suits the Monte Carlo if you have the data to derive the parameters from. [[User:Oleg.Svatos|Oleg.Svatos]] ([[User talk:Oleg.Svatos|talk]]) 22:38, 18 December 2018 (CET)

:::: I would like to take the data at work as I have access to production server which is used by one of our customers for digitization and I will use Monte Carlo as you suggested.

== Simulation proposal (svem02 [[User:Martin svejda|Martin svejda]] ([[User talk:Martin svejda|talk]]) 18:42, 18 December 2018 (CET)) ==

Topic: '''likelihood of infection with flu'''

Definition of the problem: 
- everyone has a certain probability of getting sick with a flu, this model calculates the probability based on the people you are in contact with (two types of people, infected, not infected). Other variables and levels are available (e.g. infestation, total population 

Simulation environment: Vensim

:: on what data you would set up the simulation? how would you simulate the individual people and their connection in Vensim? (in my opinon this topic fits multiagent simulation) [[User:Oleg.Svatos|Oleg.Svatos]] ([[User talk:Oleg.Svatos|talk]]) 22:30, 18 December 2018 (CET)

:::: I would base the simulation on how much one person interacts with others, depending on this variable the person would have some probability of getting sick thus the number of ill people would increase thus the probability of him getting sick would be higher and higher. The variable infestation would represent how much the illness is easily transimited to other people. [[User:Martin svejda|Martin svejda]] ([[User talk:Martin svejda|talk]]) 14:04, 19 December 2018 (CET)
:::::: I do not see it as simulation - not much of randomness, no causal feedback loops and pretty obvious result (the longer the simulation would run, the more sick people or that one gets sick) with no practical use. Not to mention, there is no data to derive the equations needed. Either reformulate it for the Netlogo so that it has some useful results based on some real data, or try something else. [[User:Oleg.Svatos|Oleg.Svatos]] ([[User talk:Oleg.Svatos|talk]]) 14:27, 19 December 2018 (CET)
:::::::: Ok, I will try something else. New proposal at the bottom of the page [[User:Martin svejda|Martin svejda]] ([[User talk:Martin svejda|talk]]) 16:46, 19 December 2018 (CET)
----

== Simulation proposal ([[User:xkaij00|xkaij00]] ([[User talk:xkaij00|talk]]) 21:20, 18 December 2018 (CET)) ''(Not approved yet)'' ==

Topic: '''Social and economical effects of reunification of North & South Korea''' 
'''Definition of the problem:''' 
Let's hope one day South and North Korea will be reunited. That would mean a big fluctuation of people between the two separated states: 
- North Koreans will migrate to South Korea area, look for flats, try to get jobs and receive welfare. 
- South Koreans will invest in North Korea area and create jobs and factories there. 
''I would like to simulate:'' 
- What will be the population ratio of the two areas per square meter. 
- How many North Koreans will move to South Korea area after the reunification and how many of them will be on welfare and how much that will cost the new reunited country. 
- How much will the suicide rate change in Korea after the reunification since it's a known fact that defected North Koreans have a high suicide rate due to the fact they have difficulties to adjust to the new lifestyle and process propaganda-free information. 
- What will be the housing situation after the reunification. 
- How will the GDP of the new country possibly develop. 
- Possibly how much money will be needed from international help. 
'''Simulation environment:''' NetLogo

----
: I must say it is a really interesting topic, but I am afraid it is a bit too ambitious. Please, if you are interested in this topic, elaborate in detail, how you would solve it. What agents would you use, what parameters, how the simulation would look like, on what data it should be based (and where you get them). And perhaps focus on fewer goals. To be honest, I am still not sure if this is doable, because of the need for extensive research. But, try to think about it yourself. [[User:Tomáš|Tomáš]] ([[User talk:Tomáš|talk]]) 19:26, 19 December 2018 (CET)

== Simulation proposal (bobj00) ([[User:Bobrekjiri|Bobrekjiri]] ([[User talk:Bobrekjiri|talk]]) 13:49, 19 December 2018 (CET)) ''(Not approved yet)'' ==

Topic/goal: '''Comparing the efficiency of Diamond interchange and Diverging diamond interchange'''

'''Definition of the problem:''' 
- [https://en.wikipedia.org/wiki/Diverging_diamond_interchange Diverging diamond interchange] is an alternative to Diamond interchange that is being used in France since 1970s and was brought to light recently (2009) in USA because it should be more effective than Diamond interchange in terms of waiting times and also in terms of safety (fewer crossing points of traffic). 
- Goal of the simulation is to measure if the statement about lower waiting times is correct and under which conditions (traffic load, traffic lights setup). 
- Throughput and waiting times will be measured under several traffic conditions, for example: most cars exiting highway are heading south or most cars entering highway are heading west, etc. 
- Model does not include simulation of traffic accidents, so the safety cannot be measured and will not be part of the simulation. 

'''Simulation environment:''' Netlogo
----

== Simulation proposal [[User:Martin svejda|Martin svejda]] ([[User talk:Martin svejda|talk]]) 16:52, 19 December 2018 (CET) ==

Topic/goal: '''Maze runner vs fire'''

'''Definition of the problem:''' 
- There will be a maze, in one corner a person, who tries to find the way out, in the other corner will be fire spreading rapidly. Does the person survives or dies by fire? Person and fire wont be able to jump through walls.

'''Simulation environment''': Netlogo

----

==Simulation proposal [[User:qnesa01|qnesa01]] ''(Not approved yet)'' ==

Topic/goal: '''Traffic simulation Argentinska street'''

'''Situation:''' 
- Argentinska street is one of the important roads in Prague that connects Bubenské nábřeží with bridge “Barikádníků”. It leads from city centre and other parts of city outside to the northern part of the country, and to Germany or Poland. Moreover, Argentinska street connects hospital “Na Bulovce” with city centre and other parts. For emergency vehicles it is the way how to get faster, where help is needed.

'''Definition of the problem:''' 
- There is traffic on the road during mornings and evenings, which makes people wait sometimes hours to get out and more important it makes difficult pass for emergency vehicles.

'''Purpose of simulation:''' 
In the scope is part of Argentinska street from Bubenské nábřeží till Dělnická street plus street Za Viaduktem, part of Jateční and part of Tusarova street as they have influence on the whole situation of Argentinska traffic. The purpose of the simulation is to find ways how to make traffic less. In order to do it will be checked, first, if it is possible to change lights more efficiently for cars flow. Second, answer the question – if we can add only one line only to one direction, which direction we have to choose: to city centre or from city centre?

'''Simulation environment''': Simprocess; SUMO (for traffic representation)

'''Brief process of simulation :''' 
1) Data collection. Data will be collected manually (observation) and from HERE traffic API. Manually for morning, midday and evening during 30 mins each part of the day within one week. At the end of data collecting the average distribution will be made based on the data.
2) Real situation simulation
3) Based on simulation of real situation will be checked the efficiency of lights changes
4) The hypothetical model of adding one more line will be created based on simulation of real situation
5) Summary

----

== Simulation proposal [[User:Kadj02|Kadj02]] ([[User talk:Kadj02|talk]]) (Jindřich Kadoun) 18:52, 19 December 2018 (CET) ==

Topic/goal: '''Survival of the apocalypse'''

'''Definition of the problem:''' 
- This simulation would aim to showcase in what conditions can humanity survive in the zombie-apocalyptic scenario. 

The usual scenario in which zombie appears is very simple: there are some number of patiants zero and the rules
for spreading the plague is to get bitten by the infected. There is also a percantual chance of beeing immune against
the plague. Zombies are usually slower than human beeings and behave on the basic of their nearest vision.

Numerous factors can be acounted for survival, like ability for humanity to reproduce, their number, immunity,
effectivnes of the plague.

'''Simulation environment''': Netlogo

----

== Simulation proposal [[User:Xlazl00|Xlazl00]] ([[User talk:Xlazl00|talk]]) 22:33, 19 December 2018 (CET) ==

Topic/goal: '''Medieval Battle Simulation'''

'''Definition of the problem:''' 

Two kingdoms come to a dispute and after extensive diplomacy had failed, they take up arms and go to battle. 
Each kingdom can have different number of units, but they each choose from the same kind of units (unit types are better against some and weaker to other). 
Each side has their own staging area, but within that area the units can spawn at random locations to test different strategic formations. 
When they meet in battle, they fight to the last man who wins the dispute for his king.

'''Purpose of simulation:''' 
It simulates medieval combat on battlefield between two sides. 
The user can select which type of units and how many will each kingdom have. 
Repeated simulation can lead to conclusions on what strategy the kings should focus on and which units they should train for successful reign when facing a violent foe.

'''Simulation environment:''' NetLogo

Assignments WS 2018/2019

2018-12-17T14:56:26Z

Dolj04: