📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: Linzertorte
跳转到指定楼层
上一主题 下一主题
收起左侧

来一道概率题,大家感受一下

🔗
readman 2015-9-8 23:33:38 | 只看该作者
全局:
aftermath 发表于 2015-9-8 23:10
n个帽子排成一个环,有(n-1)!种方式,这里面每个环拿对应到一列有n种方式,然而这n种方式产生的正确帽子的 ...

为什么不用期望的定义证明?
设个随机变量xi,i是第一个人拿到自己帽子, i不是0就是1, 然后1的可能性是1/n,n个人。。。
回复

使用道具 举报

🔗
 楼主| Linzertorte 2015-9-8 23:46:13 | 只看该作者
全局:
readman 发表于 2015-9-8 23:33
为什么不用期望的定义证明?
设个随机变量xi,i是第一个人拿到自己帽子, i不是0就是1, 然后1的可能性 ...

why 1/n for each person?
回复

使用道具 举报

全局:
本帖最后由 @南岸的风 于 2015-9-9 00:40 编辑
Linzertorte 发表于 2015-9-8 23:46
why 1/n for each person?

我的理解是:随机变量Xi代表第i个人拿到正确帽子的数量,对于每个帽子,Xi的取值范围是0或1. 我们可以用yi表示实际取值。yi = 0表示拿错帽子,yi = 1表示拿对帽子。因为拿到每个帽子的概率是1/n, 那么期望值:
E[Xi]=y1 * 1/n + y2 * 1/n +...+ yn * 1/n = (y1 + y2 +.. + yn) * 1/ n = 1/n,
其中因为只有一个正确帽子,所以y1 + y2 + ... + yn = 1.
回复

使用道具 举报

🔗
readman 2015-9-9 02:16:16 | 只看该作者
全局:
Linzertorte 发表于 2015-9-8 23:46
why 1/n for each person?

比如第一个人, 如果他没拿到自己的帽子, 其余的拿不拿到自己的帽子都无所谓, 所以即使后边的人有人拿到了自己的帽子, 这个实验的整体结果也是0.?
回复

使用道具 举报

🔗
 楼主| Linzertorte 2015-9-9 02:29:28 | 只看该作者
全局:
readman 发表于 2015-9-9 02:16
比如第一个人, 如果他没拿到自己的帽子, 其余的拿不拿到自己的帽子都无所谓, 所以即使后边的人有人拿到了 ...

严谨的论证,我竟无言以对。
回复

使用道具 举报

🔗
readman 2015-9-9 02:57:26 | 只看该作者
全局:
Linzertorte 发表于 2015-9-9 02:29
严谨的论证,我竟无言以对。

晕...这种随机permutation,只要是求固定点的, 期望都是1, 这是学hash的基础课上学的.
理由就是0-1的r.v, 期望e=e[x1]+e[x2]....e[xn]的n可以挪到外边, 所以期望本身和n无关,都是1.
ps: 大神轻拍....
回复

使用道具 举报

🔗
 楼主| Linzertorte 2015-9-9 03:13:06 | 只看该作者
全局:
readman 发表于 2015-9-9 02:57
晕...这种随机permutation,只要是求固定点的, 期望都是1, 这是学hash的基础课上学的.
理由就是0-1的r.v, ...

其实我好奇的是,写个程序来模拟随机发帽子的过程, 发上10万次。 求一下期望。不知道是多少。
回复

使用道具 举报

🔗
readman 2015-9-9 03:28:13 | 只看该作者
全局:
Linzertorte 发表于 2015-9-9 03:13
其实我好奇的是,写个程序来模拟随机发帽子的过程, 发上10万次。 求一下期望。不知道是多少。

额...膜拜..
shuffle permutation的时候,看你的随机函数有多随机了...

借贴问大神, 2016 intern出了么...
回复

使用道具 举报

🔗
 楼主| Linzertorte 2015-9-9 03:41:12 | 只看该作者
全局:
readman 发表于 2015-9-9 03:28
额...膜拜..
shuffle permutation的时候,看你的随机函数有多随机了...
  1. #include<iostream>
  2. #include<random>
  3. using namespace std;
  4. int main(){
  5.   int n = 10;//10个帽子
  6.   int cnt = 100000; // 10万次试验
  7.   double total = 0;
  8.   vector<int> taken(n,0);
  9.   for(int p=0;p<cnt;p++){
  10.     for(int i=0;i<n;i++) taken[i] = 0;
  11.     for(int i=0;i<n;i++){
  12.        int hat_remaining = n-i;
  13.        int pick_hat = rand()%hat_remaining + 1;
  14.        int j = 0;
  15.        for(j=0;j<n;j++)
  16.          if(!taken[j]) {
  17.             pick_hat--;
  18.             if(!pick_hat) break;
  19.          }
  20.        taken[j] = 1;
  21.       if(j==i) total++;
  22.     }
  23.   }
  24.   cout<<total/cnt<<endl;
  25. }
复制代码
回复

使用道具 举报

🔗
 楼主| Linzertorte 2015-9-9 03:41:49 | 只看该作者
全局:
readman 发表于 2015-9-9 03:28
额...膜拜..
shuffle permutation的时候,看你的随机函数有多随机了...

出了出了
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表