如何向他人阐释从给定分布采样的复杂性？寻求直观示例

这问题问得太到位了——我见过好多人都踩过这个误区：因为Python、R里随手就能调用rnorm()或者numpy.random.uniform()，就觉得采样是个毫无门槛的小事。其实这完全是被“常见分布的特殊性”给误导了，咱们好好掰扯清楚：

你提到的正态、均匀这类分布，属于**有闭合式逆累积分布函数（CDF）**的幸运儿。比如均匀分布的逆CDF就是直接的线性变换，正态分布虽然没有解析逆CDF，但可以通过Box-Muller变换、Ziggurat算法等技巧，在O(1)时间内完成采样。这些算法被封装成了现成函数，让我们觉得采样很容易，但这只是分布世界里的极小一部分。

从时间复杂度的角度看，采样的核心挑战在于：绝大多数分布没有可解析的逆CDF，甚至连CDF本身都没法用简单表达式写出来。

比如这些场景：

• 贝叶斯统计中的高维后验分布：当你有几百上千个模型参数时，它们的联合分布是一个极其复杂的高维曲面，没有办法拆分或写出闭合式表达式。
• 自定义的复杂分布：比如“在二维圆环上的正态分布”“混合了5个不同参数的多峰分布”，这类分布的概率密度函数（PDF）可能能写出来，但CDF根本没法积分得到解析形式。

没有逆CDF，就意味着你没法像采样均匀分布那样，直接通过“生成0-1之间的随机数→映射到分布的取值”这个简单流程来采样。这时候你就得用迭代式的方法，而这些方法的时间复杂度远高于O(1)。

咱们拿一个看起来不复杂的二维分布举例：环形正态分布。它的PDF是：
p(x,y) ∝ exp(-((√(x²+y²) - r)²)/(2σ²))
简单说，就是数据点集中在半径为r的圆环附近，而不是整个平面。

现在要采样这个分布，你会发现：

1. 没法直接拆分x和y的边缘分布——它们不是独立的，也没有闭合式的逆CDF。
2. 尝试用“先采样角度θ（均匀分布），再采样半径ρ”的思路：ρ的分布是“平移后的正态分布截断在0到无穷”，它的CDF没有解析逆。这时候你只能用拒绝采样：
   • 先从一个提议分布（比如普通正态分布）采样一个ρ候选值
   • 计算这个候选值的接受概率（目标PDF和提议PDF的比值）
   • 如果随机数小于接受概率就保留，否则重新采样

但拒绝采样的问题是：如果提议分布和目标分布差距大，接受率会极低。比如如果σ很小（圆环很窄），大部分从正态分布采样的ρ都会偏离r，导致你可能要尝试几十上百次才能得到一个有效的样本——时间复杂度变成了O(k)，k是平均尝试次数，最坏情况下可能极高。

如果把这个例子扩展到100维的“环形分布”，拒绝采样几乎完全失效，因为提议分布命中目标区域的概率趋近于0。这时候就必须用到MCMC这类算法了。

MCMC（比如Metropolis-Hastings、Gibbs采样）这类算法的核心逻辑，就是绕开直接计算逆CDF的难题：通过构造一个马尔可夫链，让它的稳态分布等于目标分布。但这是有代价的：

• 你需要等待链“收敛”到目标分布（烧录期），这可能需要几千甚至几万步
• 为了得到独立的样本，你还需要每隔几十步才能取一个样本（因为链的相邻样本是相关的）
• 高维场景下，链可能会陷入局部最优，永远没法探索到整个分布

换句话说，MCMC的时间复杂度是O(N)，N是采样链的总长度，而且N会随着分布复杂度和维度的增加呈指数级增长——这和均匀/正态分布的O(1)采样完全不是一个量级。

如果要给别人讲明白这个点，可以按这个逻辑来：

• 先破误区：“那些现成的采样函数只覆盖了极少数‘数学友好’的分布”，它们的O(1)采样是特例，不是常态。
• 用直观例子：拿环形分布或高维后验分布举例，展示“没法直接用逆CDF”的困境，以及简单方法的低效。
• 关联算法：“MCMC这类算法的存在，恰恰说明大部分分布的采样是计算上的难题”——如果采样很容易，根本不需要这些复杂的迭代算法。

内容的提问来源于stack exchange，提问作者HXD