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