# Ask for help on understand an algorithm which combines stratified sampling and importance sampling of Monte Carlo

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

• 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. Dec 27, 2019 at 16:54

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.