# Exercise - Inverse Transform Sampling

## Introduction

Inverse sampling is a usefull method to sample from a distribution$p(x)$, where it is hard to sample from but easy to find and invert the$cdf$ (cumulative distribution function). Having the inverse of the$cdf$ we just need to draw a sample from$\mathcal U (0,1)$ and act with the inverse$cdf$ on it to get our desired sample for$p(x)$. In this notebook you will implement this for the sample example of a linear distribution function.

## Requirements

### Knowledge

To complete this exercise notebook, you should possess knowledge about the following topics.

• Monte Carlo estimator
• Inverse transform sampling

The following material can help you to acquire this knowledge:

### Python Modules

# External Modules
import matplotlib.pyplot as plt
import numpy as np
from numpy.testing import assert_almost_equal

%matplotlib inline

## Exercise

Write a function, which estimates$\mathbb E_{x \sim p} [f(x)]$ with the use of$n$ drawn samples, with the given functions:

$f(x)=x^2$

and

$$p(x) = \begin{cases} \frac{1}{2}x & \text{for } x \in [0, 2] \\ 0 & \text{for } x \notin [0, 2] \\ \end{cases}$$

Hint:

To complete this task, do the following for all$i \in \{1, 2, \dots, n \}$:

1. Draw one$x_i$ from$p(x)$ using inverse transform sampling, also called Smirnov Transform

2. Calculate$f_i = f(x_i)$

Then Calculate the mean value of all$f_i$s

# Complete this function

x = np.linspace(0,2, int(10e5))

np.random.seed(42) # for reproducable results

def sample_x(n=1):
"""
Samples n values from the pdf p(x)=Cx
using inverse transform sampling.

:param n: The number of samples to draw and return
:type n: int

:returns: Sampled xs as 1D numpy.ndarray,
uniformly distributed ys used to sample xs
:rtype: numpy.ndarray[float],
numpy.ndarray[float]
"""
raise NotImplementedError()

x_, y_ = sample_x(50000)
plt.hist(x_, density=True)
plt.plot(x,0.5*x)
plt.xlabel("x")
_ = plt.ylabel("p(x)")
# Complete this function. Use your implemented sample_x function inside.

f = lambda x:x**2
def estimate_f(n=100, f=f):
"""
Estimates the expected value of function f with respect
to p(x)=Cx using inverse transform sampling.

:param n: The number of samples to draw and return
:type n: int
:param f: The function to estimate
:type f: lambda-function

:returns: the estimated expected value as mean,
a list of the single results of f from the sampled xs,
x values of the drawn samples,
y values used to draw the samples
:rtype: float,
List[float],
numpy.ndarray[float],
numpy.ndarray[float]
"""
raise NotImplementedError()

fs_mean, fs, x_, y_ = estimate_f(1000,f)
print(f_mean)
# Executing this cell must not throw an Exception
# The solution is obfuscated, so you can solve the exercise without unintendedly spoiling yourself

obfuscated_solution = 24.911757965 / 54345 * 4363
assert_almost_equal(fs_mean,obfuscated_solution, decimal=1)

## Literature

### Notebook License (CC-BY-SA 4.0)

The following license applies to the complete notebook, including code cells. It does however not apply to any referenced external media (e.g., images).

Exercise - Inverse Transform Sampling
by Christian Herta, Klaus Strohmenger