<p>It's difficult to parse, but here's my best understanding.</p>

<p>In this case the goal is determine number of <span class="math-container">$N_i$</span> out of <span class="math-container">$n$</span> samples to distribute to each strata with probability given by the discrete pdf in <span class="math-container">$\{p_0, ..., p_n\}$</span></p>

<p>The summation of <span class="math-container">$P$</span> += <span class="math-container">$p_i$</span> is computing the CDF for <span class="math-container">$i$</span>.</p>

<p>I believe "sample the ith term <span class="math-container">$N_i$</span> times" means to take a jittered sample within that strata using new random variables.</p>

<p>Let's take a small example where we have the pdf with 4 elements.
<span class="math-container">$$
PDF = \{0.2, 0.1, 0.6, 0.1\}
$$</span></p>

<p>And it's corresponding cdf, each element corresponds to <span class="math-container">$P$</span> in the ith iteration in the pseudo code.
<span class="math-container">$$
CDF = \{0.2, 0.3, 0.9, 1.0\}
$$</span></p>

<p>Now given <span class="math-container">$\left \lfloor{P*n + u}\right \rfloor$</span> we can illustrate for a few example cases.</p>

<p>With <span class="math-container">$u = 0$</span>
<span class="math-container">$$
\left \lfloor{P*n + u}\right \rfloor = \{0, 1, 3, 4\}
$$</span>
<span class="math-container">$$
N_i = {0, 1, 2, 1}
$$</span></p>

<p>With <span class="math-container">$u = 0.5$</span>
<span class="math-container">$$
\left \lfloor{P*n + u}\right \rfloor = \{1, 1, 4, 4\}
$$</span>
<span class="math-container">$$
N_i = {1, 0, 3, 0}
$$</span></p>

<p>With <span class="math-container">$u = 0.99$</span>
<span class="math-container">$$
\left \lfloor{P*n + u}\right \rfloor = \{1, 2, 4, 4\}
$$</span>
<span class="math-container">$$
N_i = {1, 1, 2, 0}
$$</span></p>

<p>Notice how for example <span class="math-container">$N_3$</span> corresponds to a higher number of samples. When we now sample the 3rd element <span class="math-container">$N_3$</span> times we are weighting that strata in proportion to its pdf.</p>

<p>Also, I don't see any reason that the sample count has to be the same <span class="math-container">$n$</span> as the # of discrete elements in the pdf.</p>

CC BY-SA 4.0
2018-12-02T02:26:05.830Z
2018-12-02T02:26:05.830Z
Calvin
<p>I cannot understand an algorithm which combines stratified sampling and importance sampling of Monte Carlo. It is introduced in Page 73 of a textbook "Advanced Global Illumination", 2nd edition, written by Philip Dutre, Philippe Bekaert and Kavita Bala. The text gives almost no explanation on the algorithm so I got stuck at the line <span class="math-container">$N_i=\lfloor Pn+u\rfloor-N_{sum}$</span>. I tried my best but I think I'm at my wit's end to figure out how this line or the whole psudo-code works. I just don't have any understanding. I read the text again and again and stared at Fig 3.9 above the algorithm for a long time but could not find any clue. Could you please give me an explanation of this algorithm in a way a common human can follow? For your convenience, I copied this section as follows. I know there is <a href="https://computergraphics.stackexchange.com/questions/5480/an-example-of-combining-stratified-sampling-and-importance-sampling-in-agi">another question thread</a> but that question has not been answered and I think my post is more detailed so please do not merge mine to his.</p>

<p>Thanks a lot for your help.</p>

<p><a href="https://i.sstatic.net/ydkVN.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/ydkVN.png" alt="enter image description here"></a>
<a href="https://i.sstatic.net/oDB4P.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/oDB4P.png" alt="enter image description here"></a></p>

CC BY-SA 4.0
2019-12-27T16:54:59.673Z
You can technically feed any pointset in the inverse transform mapping. As a special case this pointset may be produced by jittering the points if a regular grid, so that each sample is jittered within its cell. What they have done there is just mix up the two. I'd suggest keeping it modular.
lightxbulb
<monte-carlo>
Ask for help on understand an algorithm which combines stratified sampling and importance sampling of Monte Carlo
user5280911
# Ask for help on understand an algorithm which combines stratified sampling and importance sampling of Monte Carlo

(Asked by: username_0 on 2018-11-28)

I cannot understand an algorithm which combines stratified sampling and importance sampling of Monte Carlo. It is introduced in Page 73 of a textbook "Advanced Global Illumination", 2nd edition, written by Philip Dutre, Philippe Bekaert and Kavita Bala. The text gives almost no explanation on the algorithm so I got stuck at the line $N\_i=\lfloor Pn+u\rfloor-N\_{sum}$. I tried my best but I think I'm at my wit's end to figure out how this line or the whole psudo-code works. I just don't have any understanding. I read the text again and again and stared at Fig 3.9 above the algorithm for a long time but could not find any clue. Could you please give me an explanation of this algorithm in a way a common human can follow? For your convenience, I copied this section as follows. I know there is [another question thread](https://computergraphics.stackexchange.com/questions/5480/an-example-of-combining-stratified-sampling-and-importance-sampling-in-agi) but that question has not been answered and I think my post is more detailed so please do not merge mine to his.

Thanks a lot for your help.

[![enter image description here](https://i.sstatic.net/ydkVN.png)](https://i.sstatic.net/ydkVN.png)
[![enter image description here](https://i.sstatic.net/oDB4P.png)](https://i.sstatic.net/oDB4P.png)

**Tags:** monte-carlo

> **Comments:**
> **username_1**: You can technically feed any pointset in the inverse transform mapping. As a special case this pointset may be produced by jittering the points if a regular grid, so that each sample is jittered within its cell. What they have done there is just mix up the two. I'd suggest keeping it modular.  

---

## 1 answers

### Answer by username_2 on 2018-12-02. Score: 1

It's difficult to parse, but here's my best understanding.

In this case the goal is determine number of $N\_i$ out of $n$ samples to distribute to each strata with probability given by the discrete pdf in $\{p\_0, ..., p\_n\}$

The summation of $P$ += $p\_i$ is computing the CDF for $i$.

I believe "sample the ith term $N\_i$ times" means to take a jittered sample within that strata using new random variables.

Let's take a small example where we have the pdf with 4 elements.
$$
PDF = \{0.2, 0.1, 0.6, 0.1\}
$$

And it's corresponding cdf, each element corresponds to $P$ in the ith iteration in the pseudo code.
$$
CDF = \{0.2, 0.3, 0.9, 1.0\}
$$

Now given $\left \lfloor{P\*n + u}\right \rfloor$ we can illustrate for a few example cases.

With $u = 0$
$$
\left \lfloor{P\*n + u}\right \rfloor = \{0, 1, 3, 4\}
$$
$$
N\_i = {0, 1, 2, 1}
$$

With $u = 0.5$
$$
\left \lfloor{P\*n + u}\right \rfloor = \{1, 1, 4, 4\}
$$
$$
N\_i = {1, 0, 3, 0}
$$

With $u = 0.99$
$$
\left \lfloor{P\*n + u}\right \rfloor = \{1, 2, 4, 4\}
$$
$$
N\_i = {1, 1, 2, 0}
$$

Notice how for example $N\_3$ corresponds to a higher number of samples. When we now sample the 3rd element $N\_3$ times we are weighting that strata in proportion to its pdf.

Also, I don't see any reason that the sample count has to be the same $n$ as the # of discrete elements in the pdf.


---

