All Notes

Question 1

What two words sum up Monte Carlo?

Answer 1

Random Simulation

Question 2

What is Monte Carlo?

Answer 2

Studying the behaviour of a random system by stimulating the outcome many times rather than by applying math theory.

Question 3

What is a fundamental building block for everything in Monte Carlo?

Answer 3

Assuming we have an inexchaustible supply of independent random values which are uniformly distributed on (0,1)

Question 4

What are three properties of the uniformly distrubtued independent random values we use in Monte Carlo?

Answer 4

Question 5

What is the c.d.f of U?

Answer 5

Question 6

Draw the p.d.f of U

Answer 6

Question 7

Draw the c.d.f of U

Answer 7

Question 8

What is the algortithm for simulating a fair coin toss?

Answer 8

1. Take one U
2. The coin toss outcome is
   
   1. Head if U ≤ ½
   2. Tails if U > ½

Question 9

Describe the Bernoulli distribution.

Answer 9

The Bernoulli distribution with probability p of “success” has two possible outcomes 0 and 1, and probability of 1 is p ∈ [0,1].

Question 10

What is the algorithm for simulating the Bernoulli distribution?

Answer 10

1. Take one U
2. Set B =
   
   1. 1 if u ≤ p
   2. 0 if u > p

Question 11

Prove that the algorithm for simulating the Bernoulli distribution is the following.

1. Take one U
2. Set B =
   
   1. 1 if u ≤ p
   2. 0 if u > p

Answer 11

Question 12

How do you simulate from any discrete distribution?

Answer 12

* Let Y be a discrete random variable with possible values x₁, …, x_m (possibly no finite m)

• ℙ[Y = x_i] = p_i with p_i ≥ 0 and ∑p_i = 1
• Set Q_j = ∑_i=1^jp_i for j = 1, 2, …., m such that
• Q_o ≤ Q₁ ≤ Q₂ ≤ ….
• Define Q₀ = 0, and note than p_i = Q_i - Q_i-1 for all i and that Q_m = 1 when m is finite
• And use the following algorithm:

1. Take one U
2. Set Y٭= x_i if Q_j-1 < u < Q_i

Question 13

What is the algorithm for simulating any discrete distribution?

Answer 13

1. Take one U
2. Set Y٭= x_i if Q_j-1 < u < Q_i

Question 14

Prove that the algorithm for simulating any discrete distribution is:

1. Take one U
2. Set Y٭= x_i if Q_j-1 < u < Q_i

Answer 14

Question 15

Why do we distinguish Y and Y٭?

Answer 15

• Y٭ is the value from MC sampling
• Y may be a different “real world” quantity

Question 16

What are the two ways to simulatie the binomial distribution?

Answer 16

1. Binomal is discrete so apply the discrete algorithm
2. Each trial corresponds to n Bernoulli random varibles so use the Bernoulli

Question 17

Describe how you can use the Bernoulli random variable to simulate a Binomial trial.

Answer 17

1. Use the Bernoulli algortithm (bern(p)) to generate B₁, …, B_n
2. Set Y = B₁ + … + B_n (couting how many 1’s there are)
3. Y is the number of successes in n independent trials with probability p of sucess in each trial

Question 18

What are three properties of a c.d.f F(x)?

Answer 18

Question 19

What is the cdf for a discrete distribution with possible values x₁ < x₂ < … < x_m with corresponding probabilites p₁, …, p_m?

Answer 19

Question 20

What is the c.d.f for an absolutely continuous distribution?

Answer 20

Question 21

What is the definition of the generalised inverse of a c.d.f.?

Answer 21

For any c.d.f F, define F^-1:(0,1) ➝ ℝ by

F^-1(u) = min {x∈ℝ: F(x) ≥ u}

“The lowest value of x for which F(x) is at least u”

Question 22

Why do we need a generalsied definition for the inverse of cdf?

Answer 22

Because the true inverse does not always exist

Question 23

Finish this theorm: For any c.d.f F, any u ∈ (0,1) and any y ∈ ℝ:

F^-1(u) ≤ y ⟺ … ?

Answer 23

F^-1​(u) ≤ y ⟺ F(y) ≥ u

Question 24

Prove this theorem: For any c.d.f F, any u ∈ (0,1) and any y ∈ ℝ:

F^-1(u) ≤ y ⟺ F(y) ≥ u.

Answer 24

Question 25

What is the algorithm to sample from X with cdf F_X using the inverse transform method?

Answer 25

1. Take one U 2. Set x٭ = F_X^-1(u)

Question 26

Finish this theorm about the inverse transform method: The cdf of X٭ is ... ?

Answer 26

F_X

Question 27

Prove the following theorem: The cdf of X٭ is F_X.

Answer 27

Question 28

What is the algorithm for sampling from Exp(λ) using the inverse transform method?

Answer 28

1. Take one U 2. Set X = -1/λ log(u)

Question 29

How do you find the inverse transform function?

Answer 29

1. Change x in the cdf to x٭ 2. Set the cdf equal to U 3. Rearrange to make equal to x٭

Question 30

Give two reasons why you might not want to use the inverse transform method?

Answer 30

1. Difficult 2. Computationally expensive to apply

Question 31

In what scenario do yo use the acceptance-rejecting?

Answer 31

We want to sample from a pdf f(x) and we have another pdf h(x) for which we already know how to sample from h and ∃ c ∈ ℝ such that ch(x) ≥ f(x) ∀ x ∈ ℝ.

Question 32

What is the algorithm for sampling using the acceptance-rejction method?

Answer 32

Question 33

Draw a picture of the two pdfs for the acceptance-rejection method.

Answer 33

Question 34

Finish this theorem: the pdf of x from the acceptance-rejection algorithm is .. ?

Answer 34

f

Question 35

Prove the following theorem: The pdf of x from the acceptance-rejection algorithm is f.

Answer 35

Question 36

In the acceptane-rejection sampling what is 1/c known as?

Answer 36

The "acceptance rate".

Question 37

What s the P[accept X^∼] in acceptance-rejection sampling?

Answer 37

Question 38

How can we approximate the 𝔼[Y] of a random variable Y?

Answer 38

1. Take a sample Y₁, ...., Y_N of random values of Y 2. Estimate 𝔼[Y] by Ȳ = (Y₁ + ... + Y_N)/N

Question 39

What is the standard deviation of Ȳ?

Answer 39

σ²/N where σ² = Var[Y]

Question 40

What is the estimation of the standard deviation of Ȳ known as?

Answer 40

The standard error

Question 41

What is the formula for the standard error of Ȳ?

Answer 41

Question 42

What is an approximate 95% confidence interval for 𝔼[Y]?

Answer 42

Question 43

What is meant by a 95% confidence interval?

Answer 43

There is a 95% chance that the interval will contain 𝔼[Y]

Question 44

What do you do the find 𝔼[h(Y)] where h is any function of Y?

Answer 44

1. Compute the values h(Y₁), ...., h(Y_N) 2. Use the same formulas as with Y₁, ... , Y_N to then calculate 𝔼[h(Y)] and any other statistics

Question 45

What is the indicator function?

Answer 45

Question 46

If h(Y) is an indicator function of some set A os possible values of Y. What is the 𝔼[Y] equal to?

Answer 46

𝔼[Y] = ℙ[Y ∈ A]

Question 47

What is a shorthand way to write ℙ[Y ∈ A]?

Answer 47

p_A

Question 48

If h(Y) is an indicator function what is Var[h(Y)]?

Answer 48

Var[h(y)] = p_A(1 - p_A)

Question 49

What is the following equal to?

Answer 49

Question 50

What is the standard error of

Answer 50

Question 51

What is the 95% confidence interval for

Answer 51

Question 52

Given the matrix below how do we find a column vector Y?

Answer 52

Question 53

What is the p^th quantile of continuous Y?

Answer 53

F^-1(p)

Question 54

How does the basic Monte Carlo method enable us to estiamte F(x) for any value of x?

Answer 54

Question 55

How do we estiamte quantiles within samples?

Answer 55

1. Sort the sample Y₁, ...., Y_N so that the values are increasing 2. Label the results as Y₍₁₎, ...., Y_(N)

Question 56

What are the two steps in conditional specification?

Answer 56

1. specify distribution for x₁ 2. specify conditonal distribution for x₂|x₁ = x

Question 57

How do you simulate when the two variables x₁ and x₂ are dependent?

Answer 57

1. generate a value for x₁ 2. once x₁ is known we have a distribution for x₂ and we sample from it

Question 58

Name one example of when you use a conditional simulation.

Answer 58

Customers arriving in a shop, spending different amounts of time in there. Then the toal time spent by customers in day.

Question 59

What is a bivariate normal distribution?

Answer 59

When you let z₁ and z₂ be iid N(0,1), then you have the following. And _X_ is said to have a bivariate normal distribution.

Question 60

Given the following, what is the distribution of X₁ and X₂?

Answer 60

X₁ ∼ N(μ₁, a₁₁² + a₁₂²) X2 ∼ N(μ₂, a₂₁² + a₂₂²​)

Question 61

Given the following, prove what the covariance of X₁ and X₂ is?

Answer 61

Cov[X₁, X₂] = a₁₁a₂₁Var[Z₁] + a₁₂a₂₂Var[Z₂] + (a₁₁a₂₂ + a₁₂a₂₁)Cov[Z₁, Z₂] = a₁₁a₂₂ + a₁₂a₂₁ = Cov[X₂, X₁]

Question 62

What symbol represents the variance matrix?

Answer 62

Σ

Question 63

What does Σ represent?

Answer 63

The variance matrix

Question 64

Define the variance matrix, Σ.

Answer 64

Question 65

What is the theorem about the pdf of _X_ when it has a bivariate normal distribution?

Answer 65

Question 66

Finish the following Lemma.

Answer 66

Question 67

Prove the following Lemma.

Answer 67

Question 68

Prove the following theorem.

Answer 68

Question 69

What are the two main steps in sampling from a bivariate normal with mean _μ_ and variance Σ.

Answer 69

1. Find A such that Σ = AA^T (easy to find lower triangular A) 2. Then carry out the Algorithm

Question 70

What is the algorithm for sampling from the bivariate normal distribution?

Answer 70

1. Sample z₁, z₂ independently from N(0,1) 2. Set _X_ = _μ_ + A**_z_**

Question 71

How does Cov[X_1, X₂] and correlation relate?

Answer 71

* Cov[X₁, X₂] = σ₁σ₂ρ * Where σ₁ is the standard deviation of X₁ * σ₂ is the standard deviation of X₂ * ρ the correlation between X₁ and X₂

Question 72

Define a **copula**.

Answer 72

A **copula** is a joint distribution where the marginal distribution of each random variable is U(0,1).

Question 73

Define a **probability integral transform.**

Answer 73

Let X be a random variable with c.d.f. F. Then the r.v. F(x) is called the **probability integral transform** (P.I.T.) of x.

Question 74

What is the theorem about the probability integral transform?

Answer 74

If X is a continuous r.v. with cdf F, then the PIT F(x) has a U(0,1) distribution.

Question 75

Prove the following theorem. If X is a continuous r.v. with cdf F, then the PIT F(x) has a U(0,1) distribution.

Answer 75

Question 76

How do you calculate correlation, ρ from a variance matrix?

Answer 76

ρ = Σ₁₂/ (Σ₁₁Σ₁₂)^1/2

Question 77

What do you set Ũ₁ and Ũ₂ equal to in the Gaussian coupula? And how are they distributed?

Answer 77

Question 78

What is the algorithm for sampling from a copula?

Answer 78

1. sample (Ũ_1, Ũ₂) 2. Set Y₁^٭ = F₁(Ũ₁), Y₂^٭ = F₂(Ũ₂)

Question 79

What is a good use of copulas?

Answer 79

To sample from two different distributions but where the value of one is dependent on the other.

Question 80

When is time dependence easy to handle?

Answer 80

If time is discrete

Question 81

Why do we use Markov models for time dependence models?

Answer 81

Potential complexity grows as t increases, so by making what happens at time t depend only on the value of Y(t-1) and not on Y(t-2) it makes the problem easier

Question 82

In a Markov model for time dependece what do you have to specifcy?

Answer 82

Y(t + 1)|Y(t) = y(t) for all t of interest and all values of y(t)

Question 83

If Y(t + 1)|Y(t) = y in a Markov model, what is the model called? And what does it mean?

Answer 83

Stationary Markov chain - only depends on y and not t

Question 84

Give two examples of a 'stopping rule'?

Answer 84

1. Stop at some fixed time T 2. Or based on the value of Y(t)

Question 85

How do you simulate one monte carlo sample that is time dependent?

Answer 85

1. Generate value for Y(0) from its distribution 2. For t = 1, 2, ... until stopping rules applies generate Y(t + 1) from distribution Y(t + 1)|Y(t), ..., Y(0) 3. Rpeat steps (1) and (2) N times and apply basic mc principle to the result

Question 86

What two types of time are they when you look at time dependence?

Answer 86

1. Discrete 2. Continuous

Question 87

If we are looking at a model with contnuous time what two things are we interested in?

Answer 87

If 0 ≤ T₁ ≤ T₂ ≤ ... then we are interested in the 1. Interarrival times: X_j = T_j - T_j-1 2. The number of events N(t) before some time t if T_j ≤ t ≤ T_j+1 then N(t) = j

Question 88

What is the name of the two models that model continuous time dependence?

Answer 88

1. Renewal Process 2. Poisson Process

Question 89

Describe the renewal process.

Answer 89

Each X_1, X₂, ... (the inter-event times) are iid with some cdf F. So simulation is easy as long as we can sample from F. Then we just sample X_1, X₂, ... independently from F and compute T₁ = X₁, T₂ = T₁ + X₂, T₃ = T₂ + X_{3, ...}

Question 90

Describe the **homogeneous Poisson process** with rate λ \> 0.

Answer 90

Question 91

How is N(t) distributed in the homogeneous Poisson process?

Answer 91

N(t) ∼ Poisson(λt)

Question 92

What are the three kind of events in a single server, single arrival queue system?

Answer 92

1. Arrivals - time between sucessive arrivals is Exp(λ) 2. Service starts - happens when there is one or more in the queue and the server is "idle" 3. Service ends - happens at a random time drawn from Fs, after a service start event - in between start and end the server is "busy"

Question 93

What is the mathematical model for the arrival times?

Answer 93

Poisson process

Question 94

If we don't use the Poisson process to model the arrival times what can we use?

Answer 94

Could repalce with any cdf F_A and sample X ∼ F_A insread of X∼Exp(λ)