什么是模拟加载骰子的有效数据结构和算法? [英] What are efficient data structures and algorithms for simulating loaded dice?

问题描述

假设我有一个 n 面的骰子，其中每一面 k 都有一些概率 p_k 当我滚动它时出现.我很好奇是否有一个好的数据结构来静态存储这些信息(即，对于一组固定的概率)，以便我可以有效地模拟随机掷骰子.

Suppose that I have an n-sided loaded dice, where each side k has some probability p_k of coming up when I roll it. I’m curious if there is a good data structure for storing this information statically (i.e., for a fixed set of probabilities), so that I can efficiently simulate a random roll of the dice.

目前，我有一个 O(lg n) 解决方案来解决这个问题.这个想法是为所有 k 存储前 k 条边的累积概率表，然后在范围 [0, 1) 中生成一个随机实数并执行对表进行二分查找，得到累计值不大于所选值的最大索引.

Currently, I have an O(lg n) solution for this problem. The idea is to store a table of the cumulative probability of the first k sides for all k, then generate a random real number in the range [0, 1) and perform a binary search over the table to get the largest index whose cumulative value is no greater than the chosen value.

我更喜欢这个解决方案，但运行时没有考虑概率似乎很奇怪.特别是，在一侧总是出现或值均匀分布的极端情况下，可以使用简单的方法在 O(1) 中生成滚动结果，而我的解决方案仍将采取对数许多步骤.

I rather like this solution, but it seems odd that the runtime doesn’t take the probabilities into account. In particular, in the extreme cases of one side always coming up or the values being uniformly distributed, it’s possible to generate the result of the roll in O(1) using a naive approach, while my solution will still take logarithmically many steps.

有没有人对如何以某种在运行时自适应"的方式解决这个问题有任何建议?

Does anyone have any suggestions for how to solve this problem in a way that is somehow "adaptive" in it’s runtime?

更新:根据这个问题的答案，我写了 一篇文章，描述了解决此问题的多种方法，以及他们的分析.看起来 Vose 对别名方法的实现为每个掷骰子提供了 Θ(n) 预处理时间和 O(1) 时间，这确实令人印象深刻.希望这是对答案中包含的信息的有用补充！

Update: Based on the answers to this question, I have written up an article describing many approaches to this problem, along with their analyses. It looks like Vose’s implementation of the alias method gives Θ(n) preprocessing time and O(1) time per die roll, which is truly impressive. Hopefully this is a useful addition to the information contained in the answers!

推荐答案

您正在寻找别名方法 提供了一种 O(1) 方法，用于生成固定的离散概率分布(假设您可以在恒定时间内访问长度为 n 的数组中的条目)，其一次性 O(n)设置.你可以在 第 3 (PDF) 的 非均匀随机变量生成"，作者:Luc Devroye.

You are looking for the alias method which provides a O(1) method for generating a fixed discrete probability distribution (assuming you can access entries in an array of length n in constant time) with a one-time O(n) set-up. You can find it documented in chapter 3 (PDF) of "Non-Uniform Random Variate Generation" by Luc Devroye.

我们的想法是将概率数组 p_k 生成三个新的 n 元素数组，q_k、a_k、和 b_k.每个 q_k 是 0 到 1 之间的概率，每个 a_k 和 b_k 都是 1 到 n 之间的整数.

The idea is to take your array of probabilities p_k and produce three new n-element arrays, q_k, a_k, and b_k. Each q_k is a probability between 0 and 1, and each a_k and b_k is an integer between 1 and n.

我们通过生成两个介于 0 和 1 之间的随机数 r 和 s 来生成介于 1 和 n 之间的随机数.让 i = floor(r*N)+1.如果 q_i i 否则返回 b_i.别名方法的工作是弄清楚如何产生 q_k、a_k 和 b_k.

We generate random numbers between 1 and n by generating two random numbers, r and s, between 0 and 1. Let i = floor(r*N)+1. If q_i < s then return a_i else return b_i. The work in the alias method is in figuring out how to produce q_k, a_k and b_k.

这篇关于什么是模拟加载骰子的有效数据结构和算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！