一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 880|回复: 21
收起左侧

[编程题] 来一道概率题,大家感受一下

[复制链接] |试试Instant~ |关注本帖
Linzertorte 发表于 2015-9-8 13:33:50 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
n个顾客把自己的帽子给寄存处,寄存处随机发还个这n个顾客,得到自己帽子的人数的数学期望是多少。
@南岸的风 发表于 2015-9-8 14:31:41 | 显示全部楼层
每个人拿到自己帽子的期望是1/n, n个人的期望就是1了
回复 支持 1 反对 0

使用道具 举报

OneMoreBrick 发表于 2015-9-8 13:40:45 | 显示全部楼层
本帖最后由 OneMoreBrick 于 2015-9-8 13:41 编辑

答案是1么 字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数
回复 支持 反对

使用道具 举报

jeff_xu001 发表于 2015-9-8 13:47:00 | 显示全部楼层
1/n ? 俺naive 了没?
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-9-8 14:02:04 | 显示全部楼层
OneMoreBrick 发表于 2015-9-8 13:40
答案是1么 字数字数字数字数字数字数字数字数字数字数字数字数字数字数字数

是的是的。
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-8 14:07:44 | 显示全部楼层
1/n + 1/n + 1/n + 1/n .............n个..
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-8 14:10:08 | 显示全部楼层
follow up:
n个顾客每个人的帽子不同,随机返还, 问返还几次能至少每个帽子都拿到一次
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-9-8 14:12:27 | 显示全部楼层
readman 发表于 2015-9-8 14:07
1/n + 1/n + 1/n + 1/n .............n个..

你能证明一下吗。。
回复 支持 反对

使用道具 举报

jeff_xu001 发表于 2015-9-8 14:38:02 | 显示全部楼层
@南岸的风 发表于 2015-9-8 14:31
每个人拿到自己帽子的期望是1/n, n个人的期望就是1了

貌似证明会复杂一些
回复 支持 反对

使用道具 举报

aftermath 发表于 2015-9-8 23:10:38 | 显示全部楼层
本帖最后由 aftermath 于 2015-9-8 23:17 编辑

n个帽子排成一个环,有(n-1)!种方式,这里面每个环拿对应到一列有n种方式,然而这n种方式产生的正确帽子的发放个数总是n,所以期望是(n-1)!*n/(n!)=1
回复 支持 反对

使用道具 举报

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:38:02 | 显示全部楼层
本帖最后由 @南岸的风 于 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的时候,看你的随机函数有多随机了...

出了出了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 03:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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