1
$\begingroup$

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$:

plot

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

$\endgroup$
  • 1
    $\begingroup$ You should definitely try a function that is not the normal density, i think it will be more illuminating $\endgroup$ – George Dewhirst Apr 17 at 18:18
  • $\begingroup$ But it looks like you've done the right thing $\endgroup$ – George Dewhirst Apr 17 at 18:21
  • $\begingroup$ @GeorgeDewhirst Could you elaborate on what exactly you mean? If I've done everything correctly, why is the result obviously not correct? $\endgroup$ – 0xbadf00d Apr 17 at 18:31
  • 1
    $\begingroup$ @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. $\endgroup$ – 0xbadf00d Apr 17 at 19:00
  • 1
    $\begingroup$ You can also use the theoretical average for comparison, obtained by integrating the pdf $\endgroup$ – George Dewhirst Apr 17 at 19:01
1
+50
$\begingroup$

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.$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – 0xbadf00d Apr 18 at 17:31
  • $\begingroup$ @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 $\endgroup$ – Dap Apr 18 at 17:35
  • $\begingroup$ I'm still unsure why $\tilde f$ is a sensible approximation. Please take a look at this question: math.stackexchange.com/q/3221016/47771. $\endgroup$ – 0xbadf00d May 10 at 14:38
  • $\begingroup$ 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$. $\endgroup$ – 0xbadf00d May 10 at 18:17
  • $\begingroup$ 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$. $\endgroup$ – 0xbadf00d May 11 at 4:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.