Homework Assignment Policy and Guidelines with R

- 首页 >> Algorithm 算法作业

Homework Assignment Policy and Guidelines

(a) Homework assignments should be well organized and reasonably neat. It is required

that you show your work in order to receive credit.

(b) Unless otherwise stated in a problem, please use R Markdown to write homework


(c) Homework assignments are due in class unless otherwise noted. Credit will not be

given for homework turned in late.

(d) You may be asked to submit some homework problems online, in addition to a hard

copy that you turn in in class. Such homework problems will be marked online submission .

Your submission should be combined into one PDF or HTML document.

(e) Unless it is specifically stated otherwise, you may work on and submit your homework

in groups of 1 or 2. If you choose to work as a group of 2, both of you should contribute

significantly to the solution for every question and submit only one copy of the

homework with both your names on it. Whether you submit on your own or with a

partner, discussing homework with your fellow students is encouraged. However, after

discussions, every group must ultimately produce their own homework to be graded.

Verbatim copying of homework is absolutely forbidden.

1. Prove the following results in the notes.

(a) Page 10 of Notes # 12: Prove that the error when using the Trapezoidal rule is O(h



(b) Page 21 of Notes # 13: Prove that the random variable 2(V − 0.5) log U follows a

Laplace distribution with pdf h(x) = 1




for x ∈ R, where V ∼ Ber(0.5) and

U ∼ U(0, 1).

2. online submission A discrete random variable X has probability mass function

Use the inversion method to generate a random sample of size 1000 from the distribution

of X. Construct a relative frequency table and compare the empirical with the theoretical

probabilities. Repeat using the R sample function.

3. online submission For a given u, adapt the bisection method from Notes # 10 to

write a program to find the root of the function Φ(x) − u where Φ(x) is the cdf of N(0,1).


Using the inversion method, write an R program to generate 1000 observations on the N(0,1)

distribution. Compare the proportion of your observations that fall within the interval

(−1, 1) with the theoretical value of 68.3%.

4. online submission The Cauchy distribution with parameter α has pdf

(1) fX(x) = α

π(α2 + x



, −∞ < x < ∞.

Write a program to simulate from the Cauchy distribution using the inversion method.

Now consider using a Cauchy envelope to generate the N(0,1) random variable using the

rejection method. Find the values for α and the scaling constant k that minimize the

probability of rejection. Write an R program to implement the algorithm and to generate a

random sample of size 1000. Graph the histogram of the sample with the theoretical N(0,1)

density superimposed.

5. Recall that a Gamma(α, β) random variable has density function fGamma(x) =







−βx for x > 0. Use the rejection method to simulate a Gamma(2,1) random variable,

but conditional on its value being greater than 4. We will denote the density function

to be f(x).

(a) Show that the density function of this variable is given by:

f(x) = x


(2) exp {−(x − 4)}

(b) The next step would be to pick an envelope and the optimal value k. We consider

three possible envelopes:

• h1(x) being the density of an exponential random variable with rate 1


, conditional

on its value being greater than 4;1

• h2(x) being the density of an exponential random variable with rate 1


, conditional

on its value being greater than 4;

• h3(x) being the density of a standard Cauchy random variable, conditional on its

value being greater than 4. 2

For each of the three envelope densities, derive their density functions, hi(x), and thus

find the corresponding optimal values ki


(c) online submission For each of the three envelope densities, write an R function

called rej sample that:

• generates N = 1, 000 observations from f(x)

• using the rejection method

• by generating random variables from hi(x) via the inversion method

1An exponential random variable with rate λ has pdf fexp(x) = λe−λx for x ≥ 0.

2When α = 1 in (1), this yields the pdf of a standary Cauchy distribution.


• and also reports the total number of random variables rejected (from hi(x))

The function rej sample should be of this form:

rej_sample = function(N, k, fx, hx, ihx){

# fx = f(x)

# hx = envelope h(x)

# ihx = inverse CDF of h(x)

# Code here

# x.sim contains N observations from f(x) using rejection sampler

# N.rej is the total number of observations rejected

return(list(x.sim, N.rej))


Display the graphs of f(x), k1h1(x), k2h2(x), and k3h3(x) on one plot. Ensure the

graphs and the plot are clearly labelled. Is there any relation between the total number

of random variables rejected from the rejection sampler and the plot? Explain.

6. online submission Identify a topic for your project and write up a short report.

• This report is essentially a proposal for your project. It should have an introduction

(what is the project about?), a problem description (why is the project important and

interesting?), objectives (what are the goals of the project?), expected results (what

will be the expected outcome of your project?), and an approach/methogology (how

are you going to conduct the project?). The maximum length of your write-up is 1


• Upon completion of the proposal, you will proceed to conduct further research on this

topic. It is essential that you identify a topic that is feasible for a project.

• You are expected to complete the project in a group. Thus, please provide the name(s)

of your team member(s) in your proposal.