f*********r
发帖数: 30 | 1 偶然看到一个面试题，给一个coin with probability of heads = p,p不一定是0.5。
如何产生1-n的离散均匀分布?
一个很直接但是效率很低的办法是丢n次，然后把其中等概率的n种组合map到1-n，其他
的reject。
如果是fair coin，有一个优化的算法，arxiv.com/ans/1304.1916。
如果是任意p的话，有什么优化算法吗？ |
m******n
发帖数: 453 | 2 把任何random variable放进它自己的CDF里头 得到的就是uniform
【在 f*********r 的大作中提到】
: 偶然看到一个面试题，给一个coin with probability of heads = p,p不一定是0.5。
: 如何产生1-n的离散均匀分布?
: 一个很直接但是效率很低的办法是丢n次，然后把其中等概率的n种组合map到1-n，其他
: 的reject。
: 如果是fair coin，有一个优化的算法，arxiv.com/ans/1304.1916。
: 如果是任意p的话，有什么优化算法吗？
|
b****u
发帖数: 1130 | 3 对的。这个结论很重要的。我刚才都没想到。
【在 m******n 的大作中提到】
: 把任何random variable放进它自己的CDF里头 得到的就是uniform
|
f*********r
发帖数: 30 | 4 谢答，对于连续随机变量我知道这个方法。但是离散的好像没办法直接用啊，因为cdf
纵轴上也是离散的啊
: 把任何random variable放进它自己的CDF里头 得到的就是uniform
【在 m******n 的大作中提到】
: 把任何random variable放进它自己的CDF里头 得到的就是uniform
|
l*******m
发帖数: 1096 | 5 这个典型LOG（N）。把（1 。。。N）用二进制表示。仍硬币决定每一个比特位
cdf
【在 f*********r 的大作中提到】
: 谢答，对于连续随机变量我知道这个方法。但是离散的好像没办法直接用啊，因为cdf
: 纵轴上也是离散的啊
:
:
: 把任何random variable放进它自己的CDF里头 得到的就是uniform
:
|
b****u
发帖数: 1130 | 6 binom 就是离散的啊。
cdf
【在 f*********r 的大作中提到】
: 谢答，对于连续随机变量我知道这个方法。但是离散的好像没办法直接用啊，因为cdf
: 纵轴上也是离散的啊
:
:
: 把任何random variable放进它自己的CDF里头 得到的就是uniform
:
|
f*********r
发帖数: 30 | 7 不一定是fair coin呀
【在 l*******m 的大作中提到】
: 这个典型LOG（N）。把（1 。。。N）用二进制表示。仍硬币决定每一个比特位
:
: cdf
|
l*******m
发帖数: 1096 | 8 那就用你提到的办法做一个virtual fair coin: 扔两次得到：00，01， 10， 11.
reject 00， 11。把01作为fair 0， 01为fair 1。
所以，最后的复杂度是2log（N）
【在 f*********r 的大作中提到】
: 不一定是fair coin呀
|
