# Monte Carlo Methods: Assignment 04 *Assigned 2023-09-19, due 2023-09-26 on Gradescope* ## Written ### (1) Sampling from a continuous 2D distribution using the inversion method Use the inversion method to derive an algorithm for uniformly sampling from the surface of a hemisphere \(\Omega\) (uniformly w.r.t. surface area) with radius \(R\) and centered at the origin. In particular, the parametric equations are \[ \begin{align*} x &= R\cos\left(2\pi s\right)\sin\left(\frac{\pi}{2}t\right) \\ y &= R\sin\left(2\pi s\right)\sin\left(\frac{\pi}{2}t\right) \\ z &= R\cos\left(\frac{\pi}{2}t\right) \end{align*} \] where \(s,t\in[0,1]\). In particular, derive an algorithm that uses two random numbers \(u,v\) sampled uniformly at random from \([0, 1]\), and applies a transformation such that the uniform distribution on \([0,1]^2\) is mapped to the uniform distribution on the surface of the hemisphere. Hint: First derive the determinant of the Jacobian \[ \det(D\phi) = \left\|\frac{\partial \phi}{\partial s} \times \frac{\partial \phi}{\partial t}\right\| \] where \(\phi : [0,1]^2 \rightarrow \Omega\), defined by \[ \begin{align*} \phi(s,t) = (x, y, z) \hspace{2cm} u,v\in [0,1]. \end{align*} \] **Clarifications:** There are a few typos on Slides 86 and 87 of Lecture 6. The correct steps for the inversion method in 2D are * Compute \(\rho(s,t) := \det J_\phi(s,t)\), where \(\phi:[0,1]^2 \to\Omega\). * Define the CDFs \[ \begin{align*} F(s) &= \frac{\int_0^1\int_0^s \rho(\xi_1,\xi_2)d\xi_1d\xi_2}{\int_0^1\int_0^1 \rho(\xi_1,\xi_2)d\xi_1d\xi_2} \\ G_s(t) &= \frac{\int_0^t \rho(s,\xi_2)d\xi_2}{\int_0^1 \rho(s,\xi_2)d\xi_2} \end{align*} \] * Invert the CDFs: \[ \begin{align*} f(u) &:= F^{-1}(u) \\ g(u, v) &:= G_u^{-1}(v) \end{align*} \] * One can now sample uniformly on \(\Omega\) by warping \(u,v\sim U_{[0,1]}\) via \(f\) and \(g\). ### (2) How else can we sample from a hemisphere? Apart from the inversion method derived in question 1, what's one alternative way to uniformly sample from the hemisphere? Describe your sampling strategy from end to end, assuming that you start with a PRNG that provides uniform samples in \([0,1]\). If your random number generator provides stratified samples, which of the two methods would you expect to better preserve stratification (and why)? Note: it's ok if you're not 100% certain about the relative performance of stratification; we simply want to see that you can reason about the process. ## Coding Download this Jupyter notebook: [download here](sampling.ipynb). In this week's coding assignment, you will implement a few methods discussed in class for sampling from continuous and discrete distributions. All instructions are contained within text cells in the notebook. When you're done implementing all the specified functions in the notebook, submit your completed notebook on Gradescope **with all output left visible in the notebook**. *Notes:* Part of the assignment asks you to implement different strategies for sampling from a discrete distribution, in particular using the inversion method and the alias method. While the alias method has better asymptotic time complexity, the actual wall-clock time of your implementations can vary depending on if and what library functions you use. For instance, different PRNGs can have significantly different runtimes. In addition, many library functions in Python are much faster than anything you can code yourself because they are already compiled and optimized in C -- for example, Python's `bisect` functions are so efficient that using them in the inversion sampler can make it beat the alias table! As long as you implement the samplers with the right logic, don't worry about making their (relative) runtimes match their expected performance based on time complexity.