← 返回编程题库
coding-box-muller-uniform-to-normal-pairs中等免费版2000ms未尝试

Box-Muller:把均匀对转成标准正态对

Box-Muller: Uniform Pairs to Standard-Normal Pairs

开始编码

蒙特卡洛风险引擎按阶段产生相关的价格路径:先用伪随机数发生器在 (0, 1) 上生成均匀流,再用 Box-Muller 变换把每两个均匀数提升为一对独立标准正态,然后乘上 Cholesky 因子施加目标相关性,最后用逆 CDF 把分布还原回每个边际。这道题孤立地实现第二步:从均匀分布到正态分布的确定性、向量化、无分支的映射。

请实现 solution(uniform_pairs):给定长度 S 的列表,每行是一对 [u1, u2]、两个分量都严格落在开区间 (0, 1) 内,返回长度 S 的列表,每行是 [z1, z2] 一对标准正态样本。对每对输入:

R=2lnu1,θ=2πu2,z1=Rcosθ,z2=Rsinθ. R = \sqrt{-2 \ln u_1}, \qquad \theta = 2 \pi \, u_2, \qquad z_1 = R \cos \theta, \qquad z_2 = R \sin \theta.

每对的开销 O(1),且行序保留——第 i 个输入对应第 i 个输出。函数纯确定性:不维护 PRNG 状态、不修改全局,相同输入的输出位级相同。

solution([[0.5, 0.5]]) 返回约 [[-1.1774100225154747, 1.4419114153575892e-16]]。逐步算:R = sqrt(-2 * ln(0.5)) = sqrt(1.3863) ≈ 1.1774theta = 2 * pi * 0.5 = picos(pi) = -1sin(pi) = 0(浮点尾部约 1.44e-16)。所以 z1 = 1.1774 * (-1) ≈ -1.1774z2 ≈ 0。这一变换其实是「极坐标反向重建」:把 R 看成标准正态对的半径——其平方服从指数分布,于是 R²= -2 ln u1——把 theta 看成均匀分布在整圆上的角度。

实现细节由 stubs/stub.py 提供。

实践背景

Box-Muller(1958)是把均匀 PRNG 输出转成标准正态样本的经典做法、不依赖拒绝采样。在标准的高斯 Copula 采样流水线里,交易台按顺序跑这几步:(1) 用 PRNG 生成均匀数;(2) Box-Muller 把均匀数变成独立标准正态——本题;(3) 乘上目标相关矩阵的下三角 Cholesky 因子,引入相关性;(4) 把每个相关正态过 Phi(.),得到 uniform-margin 的 copula 样本;(5) 把这些均匀数通过经验或参数的逆 CDF,还原到每个边际。每一步都被拆成一个独立的可测试模块——这样底层 PRNG 可以从 Mersenne Twister 切换到 PCG、硬件 RNG 或 Sobol 拟随机序列,下游的线性代数与逆 CDF 步骤都不用改。这个函数本身是确定性的:它不调 PRNG,所以单元测试可以把均匀输入钉死、对数值输出做 rel_tol=1e-9 的精确断言。

约束条件

  • 0 <= S <= 100,其中 `S = len(uniform_pairs)`
  • 每行 `uniform_pairs` 都是长度为 2 的列表 `[u1, u2]`
  • `u1` 与 `u2` 都是严格落在开区间 (0.0, 1.0) 的浮点数;参考实现不做校验(由调用方保证)
  • 输出是 list[list[float]],形状为 (S, 2);行序与输入一致
  • 浮点比较容差:rel_tol = 1e-9、abs_tol = 1e-9

样例

Case 1 · single pair u1=0.5 u2=0.5

输入: [[[0.5,0.5]]]

期望: [[-1.1774100225154747,1.4419114153575892e-16]]

u1=0.5 → R=sqrt(-2·ln 0.5)≈1.1774;u2=0.5 → theta=π,cos=-1、sin=0。所以 (z1, z2) ≈ (-1.1774, 0)。

Case 2 · single pair u1=0.5 u2=0.25

输入: [[[0.5,0.25]]]

期望: [[7.209557076787946e-17,1.1774100225154747]]

u2=0.25 → theta=π/2,cos=0、sin=1,所以 z1≈0、z2≈R≈1.1774。可视化:u2 决定角度、u1 决定半径。

Case 3 · two pairs in input order

输入: [[[0.5,0.25],[0.25,0.75]]]

期望: [[7.209557076787946e-17,1.1774100225154747],[-3.058756019008931e-16,-1.6651092223153954]]

两对独立计算并按输入顺序输出。第二对 R=sqrt(-2·ln 0.25)≈1.6651,theta=3π/2,cos=0、sin=-1,得 (≈0, -1.6651)。

Case 4 · three interior pairs

输入: [[[0.1,0.2],[0.3,0.4],[0.6,0.8]]]

期望: [[0.6631399714746835,2.0409349730505],[-1.255396694924721,0.9120990883801819],[0.31234438201626274,-0.9612971624606308]]

三对内部点。第一对 R=sqrt(-2·ln 0.1)≈2.146、theta=0.4π,所以 (z1, z2)≈(0.663, 2.041)。

Case 5 · u1=1/e gives R=sqrt(2)

输入: [[[0.36787944117144233,0.5]]]

期望: [[-1.4142135623730951,1.7319121124709868e-16]]

u1=1/e ≈ 0.3679,则 -2·ln(1/e)=2、R=sqrt 2≈1.4142;u2=0.5 → theta=π,所以 z1=-R=-sqrt 2、z2≈0。

最近提交

还没有提交记录。

编码区

实现 solution(...)。本地运行当前支持 Python 可见样例;服务端提交会运行可见样例和隐藏测试。

加载编辑器...
计时0:00

默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。

Case 1 · single pair u1=0.5 u2=0.5

输入: [[[0.5,0.5]]]

期望: [[-1.1774100225154747,1.4419114153575892e-16]]

u1=0.5 → R=sqrt(-2·ln 0.5)≈1.1774;u2=0.5 → theta=π,cos=-1、sin=0。所以 (z1, z2) ≈ (-1.1774, 0)。

Case 2 · single pair u1=0.5 u2=0.25

输入: [[[0.5,0.25]]]

期望: [[7.209557076787946e-17,1.1774100225154747]]

u2=0.25 → theta=π/2,cos=0、sin=1,所以 z1≈0、z2≈R≈1.1774。可视化:u2 决定角度、u1 决定半径。

Case 3 · two pairs in input order

输入: [[[0.5,0.25],[0.25,0.75]]]

期望: [[7.209557076787946e-17,1.1774100225154747],[-3.058756019008931e-16,-1.6651092223153954]]

两对独立计算并按输入顺序输出。第二对 R=sqrt(-2·ln 0.25)≈1.6651,theta=3π/2,cos=0、sin=-1,得 (≈0, -1.6651)。

Case 4 · three interior pairs

输入: [[[0.1,0.2],[0.3,0.4],[0.6,0.8]]]

期望: [[0.6631399714746835,2.0409349730505],[-1.255396694924721,0.9120990883801819],[0.31234438201626274,-0.9612971624606308]]

三对内部点。第一对 R=sqrt(-2·ln 0.1)≈2.146、theta=0.4π,所以 (z1, z2)≈(0.663, 2.041)。

Case 5 · u1=1/e gives R=sqrt(2)

输入: [[[0.36787944117144233,0.5]]]

期望: [[-1.4142135623730951,1.7319121124709868e-16]]

u1=1/e ≈ 0.3679,则 -2·ln(1/e)=2、R=sqrt 2≈1.4142;u2=0.5 → theta=π,所以 z1=-R=-sqrt 2、z2≈0。