3元素数组朴素洗牌(Naive Shuffle)为何初期呈现均匀分布?
朴素洗牌初期测试看似均匀的原因分析
你初期测试得到近似均匀的结果,核心原因是错误代码的逻辑相当于在同一个数组上反复执行有偏洗牌,而非每次从初始状态重新洗牌,具体可以拆解为两点:
多次有偏洗牌的“收敛”效应:错误的朴素洗牌(比如未遵循Fisher-Yates的正确逻辑)本身是有偏的,但如果在一个已打乱的数组上重复执行该操作,相当于进行马尔可夫链状态转移。这类洗牌操作构成的马尔可夫链,其平稳分布就是均匀分布——迭代次数足够多后,不管初始状态如何,最终分布会逐渐趋近于均匀。你跑了600万次,相当于让这个链迭代了600万步,自然会收敛到均匀分布,掩盖了单次错误洗牌的偏差。
样本量放大了“收敛”的效果:600万次的样本量足够大,即使迭代过程中存在微小偏差,在统计误差范围内也会表现为近似均匀。只有当每次洗牌都从初始状态出发(修正后的逻辑),单次错误洗牌的有偏性才会在大量样本中累积显现,得到预期的非均匀分布。
简单来说,错误代码是“持续打乱同一个数组”,修正后是“每次从初始数组开始打乱”——前者会不断趋近均匀,后者才会暴露单次错误洗牌的偏差。
内容的提问来源于stack exchange,提问作者user219820
相关产品推荐
相关产品推荐

