看到一道随机数生成的算法题

看到一道随机数生成的算法题，大意是给你一堆频率分布，根据这个分布生成随机数
比如，有三种类型，频率分别为0.2，0.3，0.5，要求根据这些频率分布随机抽取一种类型
不知道怎么弄，发到地里来问问大家？

windream1991 发表于 2015-2-28 00:38
那就是说对于这种离散的情况最好的时间复杂度就是o(n)了吗？这样的话不放回抽取k个球最好的时间复杂度似 ...

cumDistribution是单调递增的，所以你可以用Binary Search，这样复杂度是O(logn)。面试的话，我觉得做到这一步就可以了。如果你真的想深入了解的话，你可以去看看一个叫Alias Method的方法。这种方法需要预处理概率分布函数，建立查找表，产生过程则是O(1)的：

http://en.wikipedia.org/wiki/Alias_method

宝贝忆彼岸 发表于 2015-2-27 11:04
感觉是不是这个样子的？

public Type choose(){

差不多是这样，但是这个是hardcode的，能不能有个general的方法？

windream1991 发表于 2015-3-2 14:08
就输出而言，这两者似乎没什么差别。我觉得原题的意思就是，输入为一组频率分布以及要抽取的个数k，输出 ...

就你的描述来看，应该不是。原题的意思应当是让你“产生一组分布满足{0.5, 0.3, 0.2}的随机变量”。换句话说，无论用什么手段，只要达到这个目的即可。“模拟不放回随机抽样的过程”只是达到这个效果的一种方法而已。日常生活中常常使用不放回抽样，因为在日常生活中这样做便于实现。但是对于我们这个算法来说，反而是“放回抽样”实现起来简单。所以，为什么不模拟“放回抽样”呢？

除非是另外一种题，就比如说reservior sampling问题。确实给定了你一个数组，让你从其中随机抽出一个指定长度的subset。这种情况下，“放回”和“不放回”的区别才变得非常关键。在我们这个问题中，“放回”和“不放回”最后会产生同等的效果，只是后者更麻烦而已。

感觉是不是这个样子的？

public Type choose(){
Random random = new Random();
int n = random.nextInt(10);
if(n >= 0 && n < 2){
  return type1;
}
else if(n >= 2 && n < 5){
  return type2;
}
else{
  return type3;
}
}
欢迎指正。。。

可以这样。先求出给定分布的“累积分布”，即cumDistribution = [0.2, 0.5, 1]
然后产生一个0~1的随机数p。然后看p落在cumDistribution中的哪个区间当中，那么就抽取该区间对应的类型：
for (i =0; i < cumDistribution.size(); i++)
{
   if (p < cumDistribution[i])
      return i;
}
return一定会被执行到。因为p小于1，而cumDistribution的最后一个数肯定为1。

一般地，如果现在让你产生一组概率分布为q(x)的变量，那么你可以先求出q(x)的累积分布函数Q(x), 再求出Q的反函数Q^-1(x)。然后生成一组0~1之间的均匀随机数k，此时Q^-1(k)就是满足q(x)分布的随机变量。上面的那段代码其实就是这个意思，只是因为是离散情况，所以使用循环去找Q^-1(k)的位置了。如果能知道Q^-1(k)的表达式的话，是可以直接计算的。

stellari 发表于 2015-2-27 23:48
可以这样。先求出给定分布的“累积分布”，即cumDistribution = [0.2, 0.5, 1]
然后产生一个0~1的随机数p ...

那就是说对于这种离散的情况最好的时间复杂度就是o(n)了吗？这样的话不放回抽取k个球最好的时间复杂度似乎就是o(nk)了。。。。
不知道还有没有更好的时间复杂度？

windream1991 发表于 2015-2-28 00:38
那就是说对于这种离散的情况最好的时间复杂度就是o(n)了吗？这样的话不放回抽取k个球最好的时间复杂度似 ...

另外，下面这个wiki页面应该会有帮助：

http://en.wikipedia.org/wiki/Pse ... crete_distributions

stellari 发表于 2015-2-28 09:31
cumDistribution是单调递增的，所以你可以用Binary Search，这样复杂度是O(logn)。面试的话，我觉得做到 ...

你这两个链接非常有用，不过我后来又想了一下，如果做不放回抽取的话涉及到一个问题就是每次抽取完都要更新cumDistribution，更新的时间是o(n)，所以不管是用binary search还是alias method最后的时间复杂度都是o(nk)

windream1991 发表于 2015-3-2 01:28
你这两个链接非常有用，不过我后来又想了一下，如果做不放回抽取的话涉及到一个问题就是每次抽取完都要更 ...

那么你究竟需要的是“产生满足概率分布为{0.5, 0.3, 0.2}的一组样本”，还是“模拟一个从n个总体(其中三种样本的个数分别为0.5n， 0.3n和 0.2n)中抽取一组样本的抽样过程”呢？” 事实上，进行后者的目的就是得到前者，因为在进行简单不放回随机抽样前，一般是不知道{0.5, 0.3, 0.2}这个概率分布的。我们就是为了估计出这个概率分布才不得不抽样。但是，既然现在你已经知道了这个概率分布，那么就有其他的方法产生出一组满足这个分布的随机事件（比如上面的那些算法），不必非得去模拟当初那个随机抽样的过程。而且简单不放回抽样的样本比例是总体比例(即0.5, 0.3和0.2)的无偏估计，所以这两者得到的结果从数学期望的角度来说是一样的。

stellari 发表于 2015-3-2 11:00
那么你究竟需要的是“产生满足概率分布为{0.5, 0.3, 0.2}的一组样本”，还是“模拟一个从n个总体(其中三 ...

就输出而言，这两者似乎没什么差别。我觉得原题的意思就是，输入为一组频率分布以及要抽取的个数k，输出一种可能的抽取结果，应该是更倾向于根据给定的频率分布模拟这个随机抽取k个数的过程吧