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

问题描述

假设我有一个n面加载的裸片，当我滚动它时，每边k都有一些概率p _k 。如果存在静态存储这种信息的好算法（即一组固定的概率），我很好奇，这样我就可以有效地模拟一个随机的模具卷。

目前，我有一个O（lg n）解决这个问题。这个想法是存储所有k个第k个k侧的累积概率的表，它们在范围[0，1]中生成一个随机实数，并在表上执行二进制搜索，得到其累积的最大索引值不大于所选值。我更喜欢这个解决方案，但运行时并不考虑概率似乎很奇怪。特别是，在极端情况下，一方总是出现或者均匀分布的值，可以使用朴素的方式在O（1）中生成滚动的结果，尽管我的解决方案仍然采取对数多个步骤。 / p>

有没有人有任何建议，如何解决这个问题，在某种程度上适应在它的运行时间？

编辑：根据这个问题的答案，我已经写了 一篇描述这个问题的许多方法的文章 以及他们的分析。看起来，Vose的别名方法的实现给出了&（n）预处理时间和每个模具滚动的O（1）时间，这是真正令人印象深刻的。希望这是答案中包含的信息的有用补充！

解决方案

您正在寻找别名方法，它提供了一种用于生成固定离散概率分布的 O（1）方法（假设你可以使用一次性O（n）设置来访问长度为n的数组中的条目。您可以在第3章（PDF）中找到不均匀随机变量生成由Luc Devroye。

这个想法是取出您的概率阵列p _{k，并产生三个新的n元素阵列，q k ，a k k} 。每个q k是0和1之间的概率，并且每个k个和b个k个是1和n之间的整数。我们通过生成0和1之间的两个随机数r和s来生成1和n之间的随机数。令i = floor（r * N）+1。如果q s然后返回一个_我 else return b _i 。别名方法的工作是在弄清楚如何产生q _{k k 和b k 。}

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.

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?

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!

解决方案

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.

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.

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屋！