数据结构装骰子？ [英] Data structure for loaded dice?

问题描述

假设我有每个边k具有一定的概率上来时，我把它卷的P <子> K n边装模。我很好奇，如果有好的算法，静态存储该信息（即一组固定的概率），这样我就可以有效地模拟一个随机卷的模具。

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

目前，我对这个问题的O（LG n）的解决方案。我们的想法是存储的前k侧面对于所有的k的累积概率的表，它们产生在范围[0的随机实数，1）和在表执行二进制搜索，获得的累积最大索引值不大于所选择的值越大。我比较喜欢这样的解决方案，但似乎奇怪的是，运行时不走的概率考虑。特别是，在一侧的极值情况下，总是想出或值均匀分布，这是可能的（1）用幼稚的方式，以产生辊为O的结果，但我的解决方案仍然需要logarithmicallh许多步骤。

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, them to 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. I rather like this solution, but it seems odd that the runtime doesn't take the probabilities into account. In particular, in the extremal 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, though my solution will still take logarithmicallh 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）preprocessing时间和O（1）每掷骰，这是真正的即时通讯pressive时间。希望这是一个有用的除了包含在答案的信息！

EDIT: 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）中的"Non-Uniform随机变量的一代由吕克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 ，一个<子> K ，和b <子> K 。各q <子> K 是0和1之间，并各自为<子> 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.

我们产生介于1和n通过产生两个随机数，r和s，0和1之间设i =地板（R * N）1随机数。当Q <子>我＆LT;记者随后返回<子>我其他回复B <子>我。在别名方法的工作是​​搞清楚如何产生q <子> K ，一个<子> 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屋！