当前位置： 文江博客话题详情

如何使用一对六面骰子创建有偏差的数字生成器

发布于 2024-08-21 17:32:57 字数 200 浏览 5 评论 0原文

使用一对六面骰子不均匀地生成 [1, 4] 中的随机数的最有效方法是什么：它应该在 40% 的时间内生成 1，在 30% 的情况下生成 2，在 20% 的情况下生成 3，以及 4 10%。

请证明该方法的正确性并给出算法。

骰子可以有不同的颜色。

注意：唯一可用的随机数生成器是两个不同颜色的六面骰子。

原文

What is the most efficient way to use a pair of six sided dice to generate a random number in [1, 4] unevenly: it should produce 1 in 40% of the time, 2 in 30%, 3 in 20%, and 4 in 10%.

Please justify the correctness of the method and give an algorithm.

Dice could be of different colors.

Note: the only random number generators available are two differently coloured six-sided dice.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（8）

櫻之舞 2024-08-28 17:32:57

假设有两个骰子：一白一黑。

  1. 掷两个骰子，得到 1 到 6 两个数字；
  2. 创建一个新数字：6 * (白色骰子 - 1) + 黑色骰子
  3. 该数字介于 1 和 36 之间。如果大于 30，则转到 2 并重复；如果大于 30，则转到 2 并重复；

现在您已拥有所需的内容：

  • 1-12 = 1 (12/30 = 40%)
  • 13-21 = 2 (9/30 = 30%)
  • 22-27 = 3 (6/30 = 20%)
  • 28-30 = 4 (3/30 = 10%)

您需要的不是 4 个可能的结果，而是 10 个，因为这可以代表您想要的加权结果。两个骰子可以通过多种方式产生 36 种可能性，但你需要的是 10 或 10 的倍数，例如上面的。

这种方法的唯一缺点是它是概率性的（这意味着从技术上讲你可以坐在那里永远重新滚动 31+），但我不相信存在确定性和准确的解决方案。

Assume two dice: one white one black.

  1. Roll the two dice giving you two numbers from 1 to 6;
  2. Create a new number: 6 * (white dice - 1) + black dice
  3. This number is between 1 and 36. If it's above 30 go to 2 and repeat;

Now you have what you need:

  • 1-12 = 1 (12/30 = 40%)
  • 13-21 = 2 (9/30 = 30%)
  • 22-27 = 3 (6/30 = 20%)
  • 28-30 = 4 (3/30 = 10%)

What you need is not 4 possible outcomes but 10 because that can represent the weighted result you want. Two dice can produce 36 possibilities in a number of ways but what you need is 10 or a multiple of 10, such as the above.

The only downside to this method is that it's probabilistic (meaning you could sit there rerolling 31+ forever technically) but I'm not convinced a deterministic and accurate solution exists.

回复 原文
韬韬不绝 2024-08-28 17:32:57

一种方法是生成一个随机整数并将其用作指定概率的数组的索引。

例如，以下伪代码将产生 1 2/3 的时间和 2 1/3 的时间。

var randArray = [1, 1, 2];
var randIndex = random(2);
return randArray[randIndex];

One method is to generate a random integer and use that as an index into an array that specifies your probabilities.

For example, the following psuedocode would produce 1 2/3rds of the time, and 2 1/3rd of the time.

var randArray = [1, 1, 2];
var randIndex = random(2);
return randArray[randIndex];
回复 原文
森林散布 2024-08-28 17:32:57

关键是：“在 40% 的情况下，它应该产生 1 分，30% 分之 2 分，20% 分之 3 分，10% 分之 4 分”

一对 6 面骰子掷出有 36 种可能的结果。
红色，蓝色（假设骰子有一定的区别）
1 1
1 2
1 3
1 4
1 5
1 6
2 1
2 2
2 3
2 4
2 5
2 6
3 1
3 2
3 3
3 4
3 5
3 6
4 1
4 2
4 3
4 4
4 5
4 6
5 1
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 6

36 个结果中的 10% 分解为 3.6 个结果.. 这是不可能的，因此您将丢弃 6 个结果，得到 30 个可被 10 整除的结果。为了方便起见，丢弃重复的结果角色 (1-1, 2-2, 3-3, 4-4, 5-5, 6-6)

所以现在如果有 3 个结果，则为 10%。现在，您的分箱 [1-4] 需要适当数量的结果来组成 40%、30%、20%、10%。

..或
40% = 12 / 30 结果...所以取前十二个案例..记住重复项被删除 = (1,2) 到 (3,2)
30% = 9 / 30 个结果...取接下来的 9 个结果 = (3,4) 到 (5,1)
20% = 6 / 30 个结果...取接下来的 6 个结果 = (5,2) 到 (6,2)
10% = 3 / 30 个结果...取最后 3 个结果 = (6,3) 到 (6,5)

.. 现在的问题是任何重复的掷骰都会强制重新掷骰，而这种情况可能会发生一遍又一遍，所以效率不高。问题是 6 进制（骰子）和 10 进制（10% = 1/10）缺乏更好的术语 - 互质。这与用二进制表示 1/10 是同样的问题。无论使用多少个钻头，您都只能接近 = 无论有多少卷，您都无法使用 6 面模具生产出完美的 10% 垃圾箱。

您必须使用 5 面或 10 面骰子。

The key: "it should produce 1 in 40% of the time, 2 in 30%, 3 in 20%, and 4 in 10%"

There are 36 possible outcomes of a roll of a pair of 6 sided dice.
red, blue (assume some distinguishment of the dice)
1 1
1 2
1 3
1 4
1 5
1 6
2 1
2 2
2 3
2 4
2 5
2 6
3 1
3 2
3 3
3 4
3 5
3 6
4 1
4 2
4 3
4 4
4 5
4 6
5 1
5 2
5 3
5 4
5 5
5 6
6 1
6 2
6 3
6 4
6 5
6 6

10% of 36 outcomes breaks down to 3.6 outcomes.. which is not possible, so you are going to throw out six outcomes to get it to 30 outcomes which is divisble by 10. For ease, throw out the duplicate roles (1-1, 2-2, 3-3, 4-4, 5-5, 6-6)

So now a unit of 10% if 3 outcomes. Now your bins [1-4] need the appropriate number of outcomes to make up 40%, 30%, 20%, 10%.

.. or
40% = 12 / 30 outcomes... so take the first twelve cases .. remember duplicates are removed = (1,2) through (3,2)
30% = 9 / 30 outcomes... take the next 9 outcomes = (3,4) through (5,1)
20% = 6 / 30 outcomes... take the next 6 outcomes = (5,2) through (6,2)
10% = 3 / 30 outcomes... take the final 3 outcomes = (6,3) through (6,5)

.. now the problem is that any duplicate roll forces a re-roll, and that can happen over and over again, so this is not efficient. The problem is that base 6 (dice) and base 10 (10% = 1/10th) are for lack of a better term - prime to eachother. This is the same problem as representing 1/10th in binary. You can only come close no matter how many bits you use = no matter how many rolls, you can not produce a perfect 10% bin with 6 sided die.

You would have to use 5 or 10 sided die.

回复 原文
阳光下的泡沫是彩色的 2024-08-28 17:32:57

正如其他人指出的那样，没有一种解决方案 100% 有效，您必须使用拒绝抽样。

一般来说，我赞同 Cletus 的答案，但使用他的算法，您将从两个骰子中获得一个结果的概率为 5/6，这意味着预期的“每个骰子的结果数”为 5/12 ~= 0.417。将后者乘以随机结果之一的熵，
即

-(0.1*log2(0.1) + 0.2*log2(0.2) + 0.3*log2(0.3) + 0.4*log2(0.4)) ~= 1.846

我们得到 0.770。换句话说，我们平均使用每个骰子的 0.770 位信息。我们可以做得更好。

例如，掷 9 个骰子，您有 6^9 = 10077696 种可能的结果。按照 Cletus，形成一个从 0 到 10077695 的数字，并且仅当它落在 0 到 9999999 之间时才保留它（这种情况发生的概率约为 0.992）。在这种情况下，您有 7 个均匀分布的随机十进制数字，并且您可以从每个数字中提取一个随机数，如您的问题所示：

0,1,2,3 --> 1
4,5,6   --> 2
7,8     --> 3
9       --> 4

这样，我们每 9 个骰子就有 7 个随机结果，概率为 0.992，或平均值“每个芯片的结果数”为 0.992*7/9 ~= 0.772。将其乘以结果的熵，我们得到 1.846*0.772 ~= 1.425。因此，通过这种方式，我们平均使用每个芯片的 1.425 位。

我们也许可以通过掷更多骰子或采用其他技术来做得更好。当然，上限是骰子的熵，即 log2(6) ~= 2.585 位。

As others have pointed out, there is not a solution that works 100% of the times, and you have to use rejection sampling.

In general, I second Cletus's answer, but using his algorithm you will obtain one result from two dice with probability 5/6, meaning that the expected "number of results per die" is 5/12 ~= 0.417. Multiplying the latter by the entropy of one of your random results,
which is

-(0.1*log2(0.1) + 0.2*log2(0.2) + 0.3*log2(0.3) + 0.4*log2(0.4)) ~= 1.846

we obtain 0.770. In other words, we are using, on average, 0.770 bits of information from each die. We can do better than this.

For example, throwing 9 dice you have 6^9 = 10077696 possible outcomes. Following Cletus, form a number from 0 to 10077695, and keep it only if it falls between 0 and 9999999 (this happens with probability ~0.992). When this is the case, you have 7 random decimal digits with uniform distribution, and from each of these you can extract a random number as in your problem:

0,1,2,3 --> 1
4,5,6   --> 2
7,8     --> 3
9       --> 4

This way we have 7 random results every 9 dice with probability 0.992, or an average "number of results per die" of 0.992*7/9 ~= 0.772. Multiplying this by the entropy of a result, we have 1.846*0.772 ~= 1.425. Thus, in this way we are using on average 1.425 bits from every die.

We can probably do better throwing more dice or adopting another technique. Of course, an upper bound is the entropy of a die, which is log2(6) ~= 2.585 bits.

回复 原文
天赋异禀 2024-08-28 17:32:57

我对做别人的作业感觉不太舒服，但我可以给出一个提示：看看 这个图表并从那里开始工作。

I don't feel very well about doing somebody else's homework, but I can give a hint: look at this graph and work from there.

回复 原文
如若梦似彩虹 2024-08-28 17:32:57

使用 10 面骰子，标记为 1,1,1,1,2,2,2,3,3,4。或者您（由于某种原因）仅限于六面骰子？对于计算机实现，请参阅 Benny Jobigan 的回答。

然而，如果您仅限于两个六面骰子，一种方法是制作 36 张小方形卡片。将 12 标记为“1”，将 9 标记为“2”，将 6 标记为“3”，将 3 标记为“4”，或者将 6 个留空或标记为“重新滚动”。

将 36 张卡片排列成 6x6 的正方形。用数字 1-6 标记每一行和每一列，并确定哪些骰子对应于列以及哪些骰子对应于行。

掷骰子并找到与所选行和列相对应的卡片。如果卡片上有数字，那就是您想要的数字，如果它是空白的（或说“重新掷”），则再次掷两个骰子。

请注意，网格上数字的确切位置对于公平骰子并不重要，但对于有偏差的骰子会给出不同的结果。

Use a 10-sided die, marked 1,1,1,1,2,2,2,3,3,4. Or are you (for some reason) limited to six-sided dice? For a computer implementation, see Benny Jobigan's answer.

However, if you're restricted to two six-sided dice, one method is to make 36 small square cards. Mark 12 with "1", mark 9 with "2", mark 6 with "3", mark 3 with "4" and eithjer leave six blank or mark them "re-roll".

Arrange the 36 cards in a 6x6 square. Mark each row and column with the numbers 1-6 and decide what die corresponds to the columns and what to the rows.

Roll the dice and find the card that corresponds to the row and column selected. If the card has a number, that's the number you want, if it's blank (or says "re-roll"), roll both dice again.

Note that the exact placement of the numbers on the grid doesn't matter for fair dice, but will give different results for biased dice.

回复 原文
擦肩而过的背影 2024-08-28 17:32:57

这是针对 1 个骰子的，因为我是为遗传算法的偏向轮盘赌轮编写的，但可以进行调整。它采用 C# 语言，但很容易更改为 Java 或其他基于 C 的语言。

首先从一组值开始
如果您想复制实际的骰子，请将这些值交换为数字 1-6。

double[] values =
{
    9,
    66,
    153,
    2,
    42,
    34
};

然后添加您希望其中每个项目显示的百分比。
例如，您希望 153 有偏差，因此它在 25% 的情况下被选择：

double[] percentages = 
{ 
    15, 
    10, 
    25, 
    5, 
    37, 
    8 
};

现在设置一些百分比范围。
这用于掷骰子，因此如果掷出 15-25，您就知道它落在第二个百分比范围内。

double[] ranges = new double[6];
ranges[0] = percentages[0];
ranges[1] = ranges[0] + percentages[1];
ranges[2] = ranges[1] + percentages[2];
ranges[3] = ranges[2] + percentages[3];
ranges[4] = ranges[3] + percentages[4];
ranges[5] = ranges[4] + percentages[5];

最后，生成一个随机数。
如果该数字落在某个范围之间，请从值中选择该索引。

static Random _random = new Random();

static void Main(string[] args)
{
    ...

    for (int i = 0; i < percentages.Length; i++)
    {
        int rand = _random.Next(0, 100);
        double x = ranges.First(n => n >= rand);
        int index = ranges.ToList().IndexOf(x);
        Console.WriteLine(values[index]);
    }
}

我确信有一些方法可以改进这一点，并且我有兴趣了解它们。

This is for 1 dice as I wrote it for a biased roulette wheel for a genetic algorithm, but can be adapted. It's in C# but will easily change for Java or other C-based languages.

First start with a set of values
Swap these values for numbers 1-6 if you want to replicate an actual dice.

double[] values =
{
    9,
    66,
    153,
    2,
    42,
    34
};

Then add the percentages you want each of these to appear.
For example, you want 153 to be biased so it's chosen 25% of the time:

double[] percentages = 
{ 
    15, 
    10, 
    25, 
    5, 
    37, 
    8 
};

Now setup some ranges for the percentages.
This is used for the dice roll, so if 15-25 is rolled, you know it's fallen within the second percentage range.

double[] ranges = new double[6];
ranges[0] = percentages[0];
ranges[1] = ranges[0] + percentages[1];
ranges[2] = ranges[1] + percentages[2];
ranges[3] = ranges[2] + percentages[3];
ranges[4] = ranges[3] + percentages[4];
ranges[5] = ranges[4] + percentages[5];

And lastly, generate a random number.
If that number falls between one of the ranges, pick that index from the values.

static Random _random = new Random();

static void Main(string[] args)
{
    ...

    for (int i = 0; i < percentages.Length; i++)
    {
        int rand = _random.Next(0, 100);
        double x = ranges.First(n => n >= rand);
        int index = ranges.ToList().IndexOf(x);
        Console.WriteLine(values[index]);
    }
}

I'm sure there's ways to improve this and I'd be interested to know them.

回复 原文
反目相谮 2024-08-28 17:32:57

由于这项作业现在可能已经上交，我将给出我的答案：我们的想法是逐步完善您的卷，直到您可以确定选择了哪种颜色。

首先，将 0 到 1 的范围划分为与概率相对应的块：在数轴上标记 0.4、0.7、0.9 和 1.0，它们定义标记为 1 到 4 的区域。掷骰子 n 和运行计数器 p。最初，设置n=1，p=0。

  1. 掷骰子并除以 6*n，并将该值添加到 p。在数轴上标记这个点。
  2. 如果 p 和 p + 1/6n 位于同一“区域”（它们不跨越上面定义的边界），则完成，颜色是 p 所在区域的颜色。
  3. 否则增加 n 并转到 1这样

，大多数时候您只需要滚动一两次即可确定选择哪种颜色，尽管有时如果您最终接近边界，则需要滚动更多。根据您的体重，40% 的时间您只需要 1 卷，44% 的时间您需要 2 卷，13% 的时间您需要 3 卷，大约 3% 的时间您需要更多。

Since this homework has probably been turned in by now, I'll give my answer: The idea is to progressively refine your roll until you can be sure which color was chosen.

First, divide the span from 0 to 1 into chunks corresponging to the probabilities: Mark off 0.4, 0.7, 0.9 and 1.0 on a number line, which define regions labelled 1 to 4. You will need to keep track of the number of times you have rolled the dice, n, and a running counter, p. Initially, set n=1, p=0.

  1. Roll a die and divide by 6*n, and add this value to p. Mark this spot on the number line.
  2. If p and p + 1/6n are in the same 'region' (they do not cross the boundaries you defined above) you are done, and the color is the color of the region p falls in.
  3. Otherwise increment n and go to 1.

This way, most of the time you will only need one or two rolls to figure out which color gets chosen, although ocasionally you will have to roll more if you end up near a boundary. With your weights, 40% of the time you only need 1 roll, 44% of times you need two, 13% you need 3, and around 3% of the time you will need more.

回复 原文
~没有更多了~

关于作者

〃安静

暂无简介

0 文章
0 评论
22 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

留蓝

文章 0 评论 0

18790681156

文章 0 评论 0

zach7772

文章 0 评论 0

Wini

文章 0 评论 0

ayeshaaroy

文章 0 评论 0

初雪

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文