概率相关问题

根据1到m生成1到n随机数

问题1：给定一个函数rand()能产生1到m之间的等概率随机数，产生1到n之间等概率的随机数？

int rand10()
{
int x;
do
{
    x = (rand7()-1)*7+rand7();
}while(x > 40)  //【1, 40】的范围
return (x-1） / 4+1; //分为10段，0～9 + 1 =》 1 ～ 10
}

考虑如果rand（）返回的是浮点呢？

这种情况下可以简化为，如何把[a,b]线段上的点等概率的映射到[c,d]

另外，为啥不能考虑rand（） * rand()呢？

因为不等概率，76与67的计算结果都是42，这样子就使得出现42的概率是1/49 + 1/49；出现1的概率是1/49。

参考：

https://www.cnblogs.com/double-win/archive/2014/04/07/3650314.html

https://my.oschina.net/u/4401597/blog/4038277

p & 1 -p 生成等概率

问题2：有一个随机生成器randA()，以p的概率返回0，1-p的概率返回1，利用这个randA()构造randB()，使randB()等概率的返回0和1，即0.5的概率返回0，0.5的概率返回1。

分析比较简单：出现00的概率是p^2; 出现10的概率是p(1-p)，出现01的概率是p(1-p); 出现11的概率是（1-p）^2;

以上，只要丢弃掉00，01的结果； 10与01的出现概率就是相等的；也就各为50%。

int randB()
{
int x1, x2;
do
{
    x1 = randA();
    x2 = randA();
}while(x1+x2 != 1)
return x1;
}

已知一随机发生器，产生0的概率是p，产生1的概率是1-p，
现在要你构造一个发生器，
使得它构造0和1的概率均为 1/2；
构造一个发生器，使得它构造1、2、3 的概率均为 1/3； …，
构造一个发生器，使得它构造 1、2、3、…n 的概率均为1/n，要求复杂度最低。

思路：
由于需要产生1/2，而用1位0，或1位1无法产生等概率，
因此，考虑将随机数扩展成2位：
00 pp
01 p(1-p)
10 (1-p)p
11 (1-p)(1-p)
有上述分析知道，01和10是等概率的，因此我们只需要产生01和10就行了。
于是可以，遇到00和11就丢弃，只记录01和10。可以令，01表示0,10表示1，则等概率1/2产生0和1了。
对于n=2，一次性生成两个数字，认为01表示0，10表示1，
其它情况放弃，它们的概率都是p(1-p)；
对于n=3，一次性生成三个数字，认为001表示0，010表示1，100表示2，
其它情况放弃，它们的概率都是pp(1-p)；
对于n=4，一次性生成是个数字，认为0001表示0，0010表示1，0100表示2，1000表示3，
其它情况放弃，它们的概率都是ppp(1-p)；
5为例，此时我们取x=2，因为C(2x,x)=C(4,2)=6是比5大的最小的x，
此时我们就是一次性生成4位二进制，把1出现个数不是2的都丢弃，
这时候剩下六个:0011,0101,0110,1001,1010,1100，
取最小的5个，即丢弃1100，那么我们对于前5个分别编号1到5，
这时候他们的概率都是pp(1-p)*(1-p)相等了。
关键是找那个最小的x，使得C(2x,x)>=n这样能提升查找效率。
因为C(n,i)最大是在i接近n/2的地方取得，此时我有更大比率的序列用于生成，
换句话说被抛掉的更少了，这样做是为了避免大量生成了丢弃序列而使得生成速率减慢，
实际上我之所以将x取定是为了让我取得的序列生成的概率互相相等，
比如C(2x,x)的概率就是[p(1-p)]^x，
互等的样例空间内保证了对应的每个值取得的样例等概率。

Shuffle算法

一个从1到n的序列，随机打乱，保证每个数出现在任意一个位置的概率相同。

基于交换，将a[i]与arr[rand(i, n - 1)]随机交换；

// 得到一个在闭区间 [min, max] 内的随机整数
int randInt(int min, int max);

void shuffle(int[] arr) {
    int n = arr.length();
    for (int i = 0 ; i < n; i++) {
        // 从 i 到最后随机选一个元素
        int rand = randInt(i, n - 1);
        swap(arr[i], arr[rand]);
    }
}

N个数随机选M

问题3：程序的输入包含两个整数m和n，其中$m \lt n $。输出是0~n-1范围内m个随机整数的有序列表，不允许重复。从概率的角度来说，我们希望得到没有重复的选择，其中每个选择出现的概率相等。

选出这个序列的概率是：$m/n (m-1) / (n-1) … * (1)/(n-m)$

void generate(int m,int n)
{
int t = m;
for(int i = 0; i < n; i++)
    if(Rand(0,n-1-i) < t) //即以t/(n-i)的概率执行下面的语句
    {
        printf("%d\n",i); //这里打印的是i，一直在增长；所以不会重复！！！
        t--;
    }
}
//随着算法继续，i越大，rand（0，n-1-i)得到的数值越小，就容易被选中，
//如果i已经等于n-1-t了，则后面的必然全不都被选中。

蓄水池采样算法

问题4：如何数据流中随机选出N个元素

蓄水池采样算法，具体步骤如下：

（1）先把N个坑位填上

（2）对于后面新来的第i元素，做如下概率处理：令X=rand(0, i), i > N

A. 如果X在[0, N]之间，则用swap(X, i)

B. 否则啥也不做

int i = 0;
vector<int> res;
while (cin >> Elem) {
    i++;
    if (i < N) {
        res.push(Elem);
        continue;
    }

    X = rand(0, i); 
    if (X < N) {
        swap(res[X], res[i]);
    }
}

深入一下，分布式蓄水池算法： https://www.jianshu.com/p/7a9ea6ece2af

Probability simulation

You are given a fair coin. Can you design a simple game using the fair coin so that your
probability of winning is p, 0 < p < 1

把p表示为2进制小数；例如0.100011100110101

开始抛硬币，正面1；反面0，计作s[i]

如果第i次抛出1，而p[i] = 0, 则win；
如果第i次抛出0，而p[i] = 1, 则lose；
如果s[i] == p[i]，则继续新的循环

概率分布

男孩女孩问题

如果一个地区所有人都生了女孩就继续生，直到生出男孩立马停下，这个地区会趋于什么样的男女比例？

1:1 ，几何分布

https://www.zhihu.com/question/355605125

一根绳子分三段，能够合成三角形的概率

线性规划 + 几何概率， 1/4

如果在高速公路上30分钟内到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过的几率是多

Neo's Blog