Reading 5: Monte Carlo Method and Importance Sampling

For the class on Monday, January 29th

Reading assignments

Hint

This is a rather math-heavy reading; however, you don’t need to be able to follow the proofs. Scroll down to read Question (2) first, and focus on finding where and how those are defined or stated in the textbook.

1. Read the following sections of [Owe13] (Direct link to the PDF of [Owe13] Chap. 9)

   • Chap. 9 “Importance sampling”, lead paragraphs only (i.e., Page 3)

   • Sec. 9.1 Basic importance sampling, up to (not including) Example 9.1 (i.e., Pages 4–6)

   Hint

   Notation used by [Owe13] that may not be immediately clear:

   • \(\boldsymbol{X} \sim q\) denotes a random variable \(\boldsymbol{X}\) that follows the distribution \(q\)

   • \(\mathcal{Q} = \{ x | q(x) > 0 \} \) means that \(\mathcal{Q}\) is the set of all \(x\)’s that satisfy \(q(x) > 0\)

   • \(\mathcal{Q}^c\) denotes the complement of the set \(\mathcal{Q}\)

   • \(\mathcal{D} \cap \mathcal{Q}^c\) denotes the intersection of the set \(\mathcal{D}\) and the complement of the set \(\mathcal{Q}\)

Questions

Hint

Submit your answer on Canvas. Due at noon, Monday, January 29th.

1. List anything from your reading that confuses you. Explain why they confuse you. If nothing confuses you, briefly summarize what you have learned from this reading assignment.

2. Recite from the your reading (you can quote the textbook directly, or cite where it is defined):

   • What is the importance sampling estimate (estimator) of \(\mu = \mathbb{E}[f(\boldsymbol{X})]\)?

   • What is the variance of the importance sampling estimator?

   • What choice of the importance distribution, \(q(x)\), can minimize the variance of the importance sampling estimator?

Discussion Preview

Note

We will discuss the following questions in class. They are included here so that you have a chance to think about them before class. You need not submit your answers as part of this assignment.

1. Some aliens have an advanced machine that allows them to precisely and accurately determine the number of human beings within any area of 100 km² on Earth’s surface. In other words, they can choose any location on Earth’s surface, turn on the machine, and get the number of people with 100 km² of that chosen location.

   However, operating this machine costs a lot of energy. If the aliens want to get an estimate of the total human population on Earth with only 1,000 measurements, how should they choose the 1,000 locations at which they will carry out the measurements to get a more accurate estimate?

   Hint

   For your context, the surface area of the Earth is 5.1 x 10⁸ km². The area of Salt Lake City is about 300 km².