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] 一对标准正态样本。对每对输入:
每对的开销 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.1774;theta = 2 * pi * 0.5 = pi;cos(pi) = -1、sin(pi) = 0(浮点尾部约 1.44e-16)。所以 z1 = 1.1774 * (-1) ≈ -1.1774、z2 ≈ 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 可见样例;服务端提交会运行可见样例和隐藏测试。
默认展示公开样例。点击「运行样例」后会在这里显示实际输出;点击「提交评测」会进入隐藏测试。
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。