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$
7
  • 1
    $\begingroup$ You should definitely try a function that is not the normal density, i think it will be more illuminating $\endgroup$
    – fGDu94
    Apr 17, 2019 at 18:18
  • $\begingroup$ But it looks like you've done the right thing $\endgroup$
    – fGDu94
    Apr 17, 2019 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, 2019 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, 2019 at 19:00
  • 1
    $\begingroup$ You can also use the theoretical average for comparison, obtained by integrating the pdf $\endgroup$
    – fGDu94
    Apr 17, 2019 at 19:01

1 Answer 1

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$
5
  • $\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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 at 4:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .