概率有关问题的证明

求一个概率问题的证明
也是以前讨论过的问题，也给过证明，
但我忘记证明过程了，也不想翻帖子了。。。

这个问题是：
给定n个数（n事先未知），
从中随机选择数，
如何保证每个数被选中的概率相同。

答案似乎是：

C/C++ code

for i = [1,n]  p = 1/i; //第i个数选中的概率  if( rand() < p )     select Arr[i] //选中第i个数

要是上述答案没错的话，
证明过程是怎样的来着？

[解决办法]
数学归纳法，假设i = n时成立，那么i = n+1时，Arr[i]被选中的概率是1/n+1，
之前的每个元素被选中的概率是1/n，他们不被替换的概率是n/n+1，
因此得以保留的概率是1/n * n/n+1 = 1/n+1
[解决办法]
这就说明每个元素被选中的概率都是1/n+1，每个元素被选中的概率都是相等的。

探讨

但在i=n+1时，每个数被选中的概率本身就是1/(n+1)，

要是2楼最后得到的1/(n+1)是对的，

那这两个1/(n+1)说明了什么问题吗。。。

[解决办法]
1、
用一个数组把它们装起来。
就等于有了编号1.2.3.4
这样就可以按照你说的方法选了。

2、
这样的东西不需要证明吧。 给n个数，随机选一个，概率就是1/n。是通过大量的实验得出来的结果。

一枚硬币 扔两面，你怎么能证明正方概率都是1/2

探讨

原题似乎是从n（未知数量）个数中，只随机的选择一个数，
问如何保证随机性。

首先以1/1=100%的概率选择第1个数，

在遍历后续的数的同时，
是否用当前遍历到的数，替换目前选中的数，
是看rand()%n是否等于0到n-1中的某个定值，其概率是1/n；
否则不替换已经选中的数，其概率也是(n-1)/n * 1/(n-1) = 1/n。

[解决办法]
看似简单的问题,如果用数学给出严谨的证明则比较麻烦,,
知道有这回事就可以啦...
[解决办法]
同意楼上的看法，哈哈
[解决办法]
上测试代码：

Java code

public static void main(String []args) throws Exception{   int size = 200;   int []result = new int[size];   for(int i = 0;i<result.length;i++){    result[i] = 0;   }   int index;   for(int j=0;j<2000000;j++){    index = MainClass.getResult(size);    result[index]++;   }   System.out.println(Arrays.toString(result));}public static int getResult(int size){   int result = 0;   for(int i=0;i<size;i++){    if(Math.random()>(((i+0.0))/(i+1))){     result = i;    }   }   return result;}
[解决办法]
证明的问题是啥？看你描述的不是一个“命题”啊？只有命题才能被证明啊
探讨

也是以前讨论过的问题，也给过证明，
但我忘记证明过程了，也不想翻帖子了。。。

这个问题是：
给定n个数（n事先未知），
从中随机选择数，
如何保证每个数被选中的概率相同。

答案似乎是：

C/C++ code

for i = [1,n]
 p = 1/i; //第i个数选中的概率
 if( rand() < p )
    select Arr[i] //……

[解决办法]
个人认为没必要用数学归纳法这汇总偷懒的方法，就一个条件概率公式就ok了。怎么人总是忘记书本上的简单方法呢
[解决办法]
探讨

原题似乎是从n（未知数量）个数中，只随机的选择一个数，
问如何保证随机性。

首先以1/1=100%的概率选择第1个数，

在遍历后续的数的同时，
是否用当前遍历到的数，替换目前选中的数，
是看rand()%n是否等于0到n-1中的某个定值，其概率是1/n；
否则不替换已经选中的数，其概率也是(n-1)/n * 1/(n-1) = 1/n。
 

 

查看更多 下一篇