使用一个概率集生成另一个 [英] Using one probability set to generate another

问题描述

如何从较小的概率集生成更大的概率集?
这来自算法设计手册-Steven Skiena
问:

How can I generate a bigger probability set from a smaller probability set?
This is from Algorithm Design Manual -Steven Skiena
Q:

使用从 {0,1,2,3,4} 以等概率生成数字的随机数生成器 (rng04) 编写以等概率生成从 0 到 7 (rng07) 的数字的随机数生成器?

Use a random number generator (rng04) that generates numbers from {0,1,2,3,4} with equal probability to write a random number generator that generates numbers from 0 to 7 (rng07) with equal probability?

我现在尝试了大约 3 个小时，主要基于总结两个 rng04 输出.问题在于，在这种情况下，每个值的概率是不同的 - 4 的概率为 5/24，而 0 的概率为 1/24.我尝试了一些方法来掩盖它，但不能.

I tried for around 3 hours now, mostly based on summing two rng04 outputs. The problem is that in that case the probability of each value is different - 4 can come with 5/24 probability while 0 happening is 1/24. I tried some ways to mask it, but cannot.

有人能解决这个问题吗?

Can somebody solve this?

推荐答案

你得想办法把两组随机数(第一个和第二个随机{0,1,2,3,4} ) 并使 n*n 不同的可能性.基本上问题是，通过加法你会得到这样的东西

You have to find a way to combine the two sets of random numbers (the first and second random {0,1,2,3,4} ) and make n*n distinct possibilities. Basically the problem is that with addition you get something like this

        X
      0 1 2 3 4

  0   0 1 2 3 4
Y 1   1 2 3 4 5
  2   2 3 4 5 6
  3   3 4 5 6 7
  4   4 5 6 7 8

其中有重复项，这不是您想要的.组合这两个集合的一种可能方法是 Z = X + Y*5，其中 X 和 Y 是两个随机数.这会给你一组这样的结果

Which has duplicates, which is not what you want. One possible way to combine the two sets would be the Z = X + Y*5 where X and Y are the two random numbers. That would give you a set of results like this

        X
       0  1  2  3  4

  0    0  1  2  3  4
Y 1    5  6  7  8  9
  2   10 11 12 13 14
  3   15 16 17 18 19
  4   20 21 22 23 24

因此，现在您有一组更大的随机数，您需要做相反的事情并使其更小.这个集合有 25 个不同的值(因为你从 5 开始，并且使用了两个随机数，所以 5*5=25).您想要的集合有 8 个不同的值.一种天真的方法是

So now that you have a bigger set of random numbers, you need to do the reverse and make it smaller. This set has 25 distinct values (because you started with 5, and used two random numbers, so 5*5=25). The set you want has 8 distinct values. A naïve way to do this would be

x = rnd(5)  // {0,1,2,3,4}
y = rnd(5)  // {0,1,2,3,4}
z = x+y*5   // {0-24}
random07 = x mod 8

这确实会有 {0,7} 的范围.但是值 {1,7} 会出现 3/25 次，而值 0 会出现 4/25 次.这是因为 0 mod 8 = 0、8 mod 8 = 0、16 mod 8 = 0 和 24 mod8 = 0.

This would indeed have a range of {0,7}. But the values {1,7} would appear 3/25 times, and the value 0 would appear 4/25 times. This is because 0 mod 8 = 0, 8 mod 8 = 0, 16 mod 8 = 0 and 24 mod 8 = 0.

要解决这个问题，您可以将上面的代码修改为这个.

To fix this, you can modify the code above to this.

do {
  x = rnd(5)  // {0,1,2,3,4}
  y = rnd(5)  // {0,1,2,3,4}
  z = x+y*5   // {0-24}
while (z != 24)

random07 = z mod 8

这将取掉你的概率的一个值 (24) 并丢弃它.如果您得到这样的坏"值，则生成一个新的随机数将使您的算法运行时间稍微长一些(在这种情况下，1/25 的时间将花费 2 倍的时间，1/625 将花费 3 倍的时间)长等).但它会给你正确的概率.

This will take the one value (24) that is throwing off your probabilities and discard it. Generating a new random number if you get a 'bad' value like this will make your algorithm run very slightly longer (in this case 1/25 of the time it will take 2x as long to run, 1/625 it will take 3x as long, etc). But it will give you the right probabilities.

这篇关于使用一个概率集生成另一个的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！