了解分层抽样与蒙特卡罗重要性抽样相结合的算法

Question

我无法理解一种将分层抽样和蒙特卡罗重要性抽样相结合的算法。它是在第73页的教科书“先进的全球照明”，第二版，由菲利普·杜尔，菲利普·贝卡尔特和卡维塔·巴拉编写。这篇文章几乎没有给出任何关于算法的解释，所以我陷入了线N_i=\lfloor Pn+u\rfloor-N_{sum}。我尽了最大的努力，但我想我的智慧已经到了极限，想弄清楚这行代码或整个密码是如何工作的。我只是没有任何理解。我看了一遍又一遍，盯着图3.9上面的算法很长一段时间，但没有找到任何线索。你能给我一个解释这个算法的方式，一个普通的人可以遵循吗？为了方便您，我按以下方式复制了这一节。我知道有另一个问题线，但这个问题还没有得到回答，我认为我的帖子更详细，所以请不要把我的问题合并到他的文章中。

非常感谢你的帮助。

Answer 1

这是很难解析的，但这是我最好的理解。

在这种情况下，目标是确定N_i在n样本中的数目，以\{p_0, ..., p_n\}中离散pdf给出的概率分布到每一层。

P += p_i的求和是计算i的CDF。

我相信“样本第一项N_i时间”意味着使用新的随机变量在该层中取一个抖动的样本。

让我们举个小例子，我们有一个包含4个元素的pdf。

PDF = \{0.2, 0.1, 0.6, 0.1\}

与之对应的是，在伪码的第一次迭代中，每个元素对应于P。

CDF = \{0.2, 0.3, 0.9, 1.0\}

现在，考虑到\left \lfloor{P*n + u}\right \rfloor，我们可以举例说明几个例子。

用u = 0

\left \lfloor{P*n + u}\right \rfloor = \{0, 1, 3, 4\}

N_i = {0, 1, 2, 1}

用u = 0.5

\left \lfloor{P*n + u}\right \rfloor = \{1, 1, 4, 4\}

N_i = {1, 0, 3, 0}

用u = 0.99

\left \lfloor{P*n + u}\right \rfloor = \{1, 2, 4, 4\}

N_i = {1, 1, 2, 0}

注意，例如，N_3如何对应更多的样本。当我们现在取样第三元素N_3时，我们是按其pdf的比例加权该层。

此外，我不认为样本计数必须与pdf中的离散元素#相同的n。