Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Monte Carlo > All Notes > Flashcards

All Notes Flashcards

1
Q

What two words sum up Monte Carlo?

A

Random Simulation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is Monte Carlo?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is the c.d.f of U?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Draw the p.d.f of U

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Draw the c.d.f of U

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the algortithm for simulating a fair coin toss?

A
  1. Take one U
  2. The coin toss outcome is
    1. Head if U ≤ ½
    2. Tails if U > ½
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Describe the Bernoulli distribution.

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the algorithm for simulating the Bernoulli distribution?

A
  1. Take one U
  2. Set B =
    1. 1 if u ≤ p
    2. 0 if u > p
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

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
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

How do you simulate from any discrete distribution?

A

* Let Y be a discrete random variable with possible values x1, …, xm (possibly no finite m)

  • ℙ[Y = xi] = pi with pi ≥ 0 and ∑pi = 1
  • Set Qj = ∑i=1jpi for j = 1, 2, …., m such that
  • Qo ≤ Q1 ≤ Q2 ≤ ….
  • Define Q0 = 0, and note than pi = Qi - Qi-1 for all i and that Qm = 1 when m is finite
  • And use the following algorithm:
  1. Take one U
  2. Set Y٭= xi if Qj-1 < u < Qi
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the algorithm for simulating any discrete distribution?

A
  1. Take one U
  2. Set Y٭= xi if Qj-1 < u < Qi
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Prove that the algorithm for simulating any discrete distribution is:

  1. Take one U
  2. Set Y٭= xi if Qj-1 < u < Qi
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Why do we distinguish Y and Y٭?

A
  • Y٭ is the value from MC sampling
  • Y may be a different “real world” quantity
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What are the two ways to simulatie the binomial distribution?

A
  1. Binomal is discrete so apply the discrete algorithm
  2. Each trial corresponds to n Bernoulli random varibles so use the Bernoulli
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A
  1. Use the Bernoulli algortithm (bern(p)) to generate B1, …, Bn
  2. Set Y = B1 + … + Bn (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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the cdf for a discrete distribution with possible values x1 < x2 < … < xm with corresponding probabilites p1, …, pm?

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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

A

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”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

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

A

Because the true inverse does not always exist

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

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

F-1(u) ≤ y ⟺ … ?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

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

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

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

A
  1. Take one U
  2. Set x٭ = FX-1(u)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

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

A

FX

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

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

A
  1. Take one U
  2. Set X = -1/λ log(u)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

How do you find the inverse transform function?

A
  1. Change x in the cdf to x٭
  2. Set the cdf equal to U
  3. Rearrange to make equal to x٭
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

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

A
  1. Difficult
  2. Computationally expensive to apply
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

In what scenario do yo use the acceptance-rejecting?

A

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 ∈ ℝ.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

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

A

f

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

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

A

The “acceptance rate”.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

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

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

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

A
  1. Take a sample Y1, …., YN of random values of Y
  2. Estimate 𝔼[Y] by Ȳ = (Y1 + … + YN)/N
39
Q

What is the standard deviation of Ȳ?

A

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

40
Q

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

A

The standard error

41
Q

What is the formula for the standard error of Ȳ?

A
42
Q

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

A
43
Q

What is meant by a 95% confidence interval?

A

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

44
Q

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

A
  1. Compute the values h(Y1), …., h(YN)
  2. Use the same formulas as with Y1, … , YN to then calculate 𝔼[h(Y)] and any other statistics
45
Q

What is the indicator function?

A
46
Q

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

A

𝔼[Y] = ℙ[Y ∈ A]

47
Q

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

A

pA

48
Q

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

A

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

49
Q

What is the following equal to?

A
50
Q

What is the standard error of

A
51
Q

What is the 95% confidence interval for

A
52
Q

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

A
53
Q

What is the pth quantile of continuous Y?

A

F-1(p)

54
Q

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

A
55
Q

How do we estiamte quantiles within samples?

A
  1. Sort the sample Y1, …., YN so that the values are increasing
  2. Label the results as Y(1), …., Y(N)
56
Q

What are the two steps in conditional specification?

A
  1. specify distribution for x1
  2. specify conditonal distribution for x2|x1 = x
57
Q

How do you simulate when the two variables x1 and x2 are dependent?

A
  1. generate a value for x1
  2. once x1 is known we have a distribution for x2 and we sample from it
58
Q

Name one example of when you use a conditional simulation.

A

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

59
Q

What is a bivariate normal distribution?

A

When you let z1 and z2 be iid N(0,1), then you have the following. And X is said to have a bivariate normal distribution.

60
Q

Given the following, what is the distribution of X1 and X2?

A

X1 ∼ N(μ1, a112 + a122)

X2 ∼ N(μ2, a212 + a222​)

61
Q

Given the following, prove what the covariance of X1 and X2 is?

A

Cov[X1, X2] = a11a21Var[Z1] + a12a22Var[Z2] + (a11a22 + a12a21)Cov[Z1, Z2] = a11a22 + a12a21 = Cov[X2, X1]

62
Q

What symbol represents the variance matrix?

A

Σ

63
Q

What does Σ represent?

A

The variance matrix

64
Q

Define the variance matrix, Σ.

A
65
Q

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

A
66
Q

Finish the following Lemma.

A
67
Q

Prove the following Lemma.

A
68
Q

Prove the following theorem.

A
69
Q

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

A
  1. Find A such that Σ = AAT (easy to find lower triangular A)
  2. Then carry out the Algorithm
70
Q

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

A
  1. Sample z1, z2 independently from N(0,1)
  2. Set X = μ + Az
71
Q

How does Cov[X1, X2] and correlation relate?

A
  • Cov[X1, X2] = σ1σ2ρ
  • Where σ1 is the standard deviation of X1
  • σ2 is the standard deviation of X2
  • ρ the correlation between X1 and X2
72
Q

Define a copula.

A

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

73
Q

Define a probability integral transform.

A

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.

74
Q

What is the theorem about the probability integral transform?

A

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

75
Q

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.

A
76
Q

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

A

ρ = Σ12/ (Σ11Σ12)1/2

77
Q

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

A
78
Q

What is the algorithm for sampling from a copula?

A
  1. sample (Ũ1, Ũ2)
  2. Set Y1٭ = F1(Ũ1), Y2٭ = F2(Ũ2)
79
Q

What is a good use of copulas?

A

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

80
Q

When is time dependence easy to handle?

A

If time is discrete

81
Q

Why do we use Markov models for time dependence models?

A

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

82
Q

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

A

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

83
Q

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

A

Stationary Markov chain - only depends on y and not t

84
Q

Give two examples of a ‘stopping rule’?

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

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

A
  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
86
Q

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

A
  1. Discrete
  2. Continuous
87
Q

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

A

If 0 ≤ T1 ≤ T2 ≤ … then we are interested in the

  1. Interarrival times: Xj = Tj - Tj-1
  2. The number of events N(t) before some time t if Tj ≤ t ≤ Tj+1 then N(t) = j
88
Q

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

A
  1. Renewal Process
  2. Poisson Process
89
Q

Describe the renewal process.

A

Each X1, X2, … (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 X1, X2, … independently from F and compute T1 = X1, T2 = T1 + X2, T3 = T2 + X3, …

90
Q

Describe the homogeneous Poisson process with rate λ > 0.

A
91
Q

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

A

N(t) ∼ Poisson(λt)

92
Q

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

A
  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”
93
Q

What is the mathematical model for the arrival times?

A

Poisson process

94
Q

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

A

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

Monte Carlo (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions