SNS oral exam

system

Collection of entities that act and interact with each other and want to accomplish some logical goal

State of a system

The information describing the system at any point in time

Which ways are there to study a system?

• Experiment with the real system

• Experiment with a model of it:

  • physical model

  • mathematical model: simulation (or analytical solution)

Name all simulation types

• Static vs. Dynamic

• Deterministic vs. Stochastic

• Discrete vs. Continuous

Explain static vs. Dynamic simulation

• Static: not based on time

• Dynamic: based on time

Explain discrete vs. Continuous simulation

• Continuous: ticks at given times

• Discrete: time steps are event-based

Explain stochastic vs. Deterministic simulation

Stochastic: random

Deterministic: pre-determined what will happen next if you make a certain more

Explain explanatory vs. Exploratory simulation

• Explanatory: you know what will happen but want to know why ("explain")

• Exploratory: you want to know what will happen (e.g. in the future) ("explore")

Very general, what two ways are there to generate random numbers?

Hardware or software based

Hardware random number generation: name + pros and cons

TRNG (true random number generation)

Pros: results are not determined (that’s why “true”)

Cons: not determined implies that you can’t reproduce the experiment, you also need external hardware (extra costs)

RNGs with software: name, explanation

Pseudo random number generator

Algorithm that has a state (“seed”), from this number you start and update the state as you go

You can decide between integer random numbers [a,b] or floating point between 0.0 and 1.0 (you can convert between them tho)

What methods are there to determine whether a Pseudo-RNG is good or nah

• Plotting points in 2D or 3D and seeing how far apart/together they are, if there are clusters that’s bad

• “Diehard test suite”: e.g. Birthday spacings, overlapping permutations, ranks of matrices

What specific methods are there to generate pseudo random numbers?

• Middle Square Method

• Tiny RNG with full period

• Linear Conguential Generators

• Commodore 64 Random Algorithm

• Mersenne Twister

• Xorshift Algorithm

Middle Square Method: explain it + cons

You start with a seed number, square it, take out the n middle digits

Cons: not good cause it has a fixpoint on 0 and usually a short period

A tiny PRNG with full period: explain it + pros and cons

Uses a single bit-shift and XOR operation

Pros and cons: no fixed points, full period (repeats exactly after one period is over), can be done in 8-bit, 16-bit, etc., not very random in the lower bits (mostly even numbers), for higher bits we get alternating even and odd numbers

Linear Congruential Generators: explain + where used

There’s this one formula with the seed and three constants, for the next number you plug in whatever seed you just got from the equation type shi

Used in BSD and Microsoft C Runtime

Commodore 64 Random Algorithm: explain

Seed is multiplied with a big number and then a small number is added. Then we switch the bytes of the resulting number

Works well for embedded platforms

Mersenne Twister: pros and cons

Pros: very good results, standard algorithm for high quality simulations

Cons: complex and slow in calculation

Xorshift algorithm: explain + pros

It does three bitshift and XOR operations

Pros: Standard algorithm in CUDA, very good results, simple algorithm

Compare Mersenne vs. Xorshift

Mersenne passes more stochastic tests, has a WAY larger period but that doesn’t say much about the quality

Xorshift is faster with way less memory requirement, recovers faster from a poor starting seed

What is a random variate?

The actual number you get from a simulation (the simulation output/result at a specific time ig?)

What methods are there to generate random variates?

We have a random number generator and a distribution function, so we get the variates from there:

• Inverse Transform

• Box-Muller Transform

• For discrete: Discrete Inverse Transform Method

Inverse transform: explain

We use the CDF (cumulative distribution function) to map the (uniformly distributed) random numbers to whatever distribution we want

In the CDF plot, any sattle point becomes a maximum in PDF distribution for example

Box-Muller Transform: explain

Generates values from a standard normal distribution

Has a uniform random source

Takes two independent samples and maps them to two independent standard normally distributed samples

Which RNG algorithm is the most promising one?

Xorshift

What are sample mean and sample variance (before vs. after observation)?

Before observation: random variables

After observation: functions of the data

How can we make the estimation of mean and variance more exact?

By having more observations n. The more the better

Central Limit Theorem: explain

Basically if you have enough samples from literally any population, the average (mean) will always end up following a normal distribution (bell curve thingy)

Confidence interval: explain

It’s an interval that contains the sample mean with a probability of 1 - alpha (level of confidence)

How do you compute the absolute error?

Sample mean - population mean (mu)

How do you compute the relative error?

(Sample mean - mu) / mu

What is the Q-function?

It’s the complementary function of the standard normal CDF

What can you use to estimate the expected steady state waiting time in a non-terminating simulation? Name + explain

M/M/1 Queue: customers served in FIFO manner

Formula is max( Waiting time + Server time - Arrival time, 0 ) (more or less lol)

What can you use to estimate the warmup period of a non-terminating simulation?

Welch’s Method: TODO (slide-set 3 page 33)