# How can we approximate a function by sampling a distribution proportial to it and making a histogram of samples?

I've read the following (here on page 2):

Suppose that you want to approximate a function $$f$$. One way to do this is to produce a sampling distribution proportional to $$f$$ and then make a histogram of samples taken from the distribution. The resulting histogram will be proportional to $$f$$ (obviously), so it only needs to be scaled to approximate $$f$$.

The procedure can be summarized as follows:

• Create a sampling distribution proportial to $$f$$
• Make a histogram of samples taken from the sampling distribution
• Scale the histogram to approximate $$f$$

The sacle factor $$s$$ needed to make the histogram approximate $$f$$ is the ratio of the average value $$v$$ of $$f$$ over the sampling domain to the average number $$h$$ of samples per bin in the histogram, i.e. $$s=v/h$$.

I'm not sure how seriously this has to be taken, but could anybody explain to me (in a more formal way) what the author is meaning to say?

Let's consider a example: Assume $$f$$ is the density of the standard normal distribution $$\mathcal N_{0,\:1}$$. We could divide an interval $$[a,b]$$ into $$C$$ "bins" of size $$\delta$$. Now we could draw $$n$$ samples from $$\mathcal N_{0,\:1}$$ and record for each bin $$i$$ the number $$B(i)$$ of samples falling into that bin (if $$x\in[a,b)$$ is a sample, it lies in the $$\lfloor\frac{x-a}\delta\rfloor$$-th bin).

Clearly, $$[a,b)\ni x\mapsto B\left(\lfloor\frac{x-a}\delta\rfloor\right)\tag1$$ is an approximation of the shape of $$f$$.

Now, let $$v$$ be the average value of $$f$$ on $$[a,b]$$, $$h$$ be the average number of samples per bin and $$s:=v/h$$. If I got it right, the desired approximation would be $$\tilde f(x):=sB\left(\lfloor\frac{x-a}\delta\rfloor\right)\;\;\;\text{for }x\in[a,b).$$ Here's a plot of the result for $$a=-5$$, $$b=5$$, $$C=2000$$, $$\delta=(b-a)/C$$ and $$n=1000000$$:

Obviously, the scale is not correct. Did I made any mistake or is there something wrong with the description in the paper?

• You should definitely try a function that is not the normal density, i think it will be more illuminating – George Dewhirst Apr 17 at 18:18
• But it looks like you've done the right thing – George Dewhirst Apr 17 at 18:21
• @GeorgeDewhirst Could you elaborate on what exactly you mean? If I've done everything correctly, why is the result obviously not correct? – 0xbadf00d Apr 17 at 18:31
• @GeorgeDewhirst I think so. Each time I draw a sample $sample$, I calculate the bin via $bin=\lfloor\frac{sample-a}\delta\rfloor$ and accumlate $avg=avg+f(a+(bin+\alpha)*\delta)$, where $\alpha\in[0,1]$ ($\alpha=0$ -> evaluate bin at left endpoint, $\alpha=0.5$ -> evaluate bin at the middle, $\alpha=1$ -> evaluate bin at right endpoint). At the end I divide $avg$ by the number of samples drawn. – 0xbadf00d Apr 17 at 19:00
• You can also use the theoretical average for comparison, obtained by integrating the pdf – George Dewhirst Apr 17 at 19:01

It looks like you're taking $$v$$ to be the sample average of $$f(x)$$ where $$x$$ is drawn from $$N_{0,1}$$ (perhaps conditioned to $$x\in[a,b]$$ - this wouldn't make much difference). Instead, $$v$$ should be the average of $$f(x)$$ for the uniform distribution on $$[a,b]$$ - this is what they mean by "selected at random from the sampling domain."
If you add up $$f(x)$$ at the points $$a,a+\delta,\dots,a+(C-1)\delta,$$ you should expect to get about $$vC$$ - the average of $$f$$ multiplied by the number of points. If you add up $$\overline f(x)$$ at these points, you get exactly $$sn.$$ So it makes sense to take $$s=vC/n=v/h.$$
• What is $\overline f$ in your second to last comment? You're right, I've computed the $v$ in the wrong way. So, how should $v$ be computed? Seems like one needs to compute $v$ separately before running the actual algorithm. – 0xbadf00d Apr 18 at 17:31
• @0xbadf00d: I meant the $\tilde{f}$ from your post - the approximation to $f.$ And yes, $v$ has to be computed separately, but this could be done in parallel to the histogram. Section 3.5 in the paper is the relevant bit – Dap Apr 18 at 17:35
• I'm still unsure why $\tilde f$ is a sensible approximation. Please take a look at this question: math.stackexchange.com/q/3221016/47771. – 0xbadf00d May 10 at 14:38
• From your last equation, it seems like you're assuming $n=Ch$. But is that correct? $n$ is the total number of samples drawn from $\mathcal N_{0,\:1}$ in the example. Now $\mathcal N_{0,\:1}$ generates samples on its entire domain $\mathbb R$ (sure, the support of this distribution is much smaller, but suppose we don't know that), while we're only approximating $f$ on $(a,b]$. So, not all of the generated samples lie in the domain of interest $(a,b]$ and hence we only know that $Ch\le n$. – 0xbadf00d May 10 at 18:17
• Oh and while it's clear to me what you're writing, we do not add up the values of $f(x)$ or $\tilde f(x)$ in the computation. So, I don't understand how you derived $s$. – 0xbadf00d May 11 at 4:51