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

问题描述

假设我有一个 n 面装骰子，其中每个 k 面都有一定的概率 p _k 在我滚动时出现.我很好奇是否有一个很好的数据结构来静态存储此信息(例如，针对一组固定的概率)，以便可以有效地模拟骰子的随机掷骰子.

目前，我对此问题有O(lg n )解决方案.这个想法是存储一张所有 k 的第一张 k 边的累积概率表，然后生成一个在[0，1)范围内的随机实数并执行对表进行二进制搜索以获取最大索引，该索引的累积值不大于所选值.

我更喜欢这种解决方案，但是运行时没有考虑这些可能性似乎很奇怪.尤其是在极端情况下，总是出现一侧或数值均匀分布的情况，可以使用朴素的方法生成O(1)的滚动结果，而我的解决方案仍将采用对数的许多步骤./p>

有人对运行时以某种自适应"方式解决此问题有任何建议吗?

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

解决方案

您正在寻找别名方法提供了一种 O(1)方法，用于生成固定的离散概率分布(假设您可以在恒定时间内访问长度为n的数组中的项)，并且一次性生成O(n)设置.您可以在第3章(PDF)中找到该文档的文档.luc.devroye.org/rnbookindex.html"rel =" noreferrer> Luc Devroye的非均匀随机变量生成" .

这个想法是取你的概率数组p _k 并产生三个新的n元素数组q _k ，a _k ，和b _k .每个q _k 是介于0和1之间的概率，每个a _k 和b _k 是介于1和n之间的整数.

我们通过在0和1之间生成两个随机数r和s来生成1和n之间的随机数.令i = floor(r * N)+1.如果q _i <s然后返回a _i ，否则返回b _i .别名方法的工作是弄清楚如何产生q _k ，a _k 和b _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.

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.

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?

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!

解决方案

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