请教一道概率题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>DataSciences - 数据科学

请教一道概率题

请教一道概率题# DataSciences - 数据科学

h*r2015-02-06 08:02

1 楼

【以下文字转载自 Poetry 讨论区】
发信人: hualavender (薰衣草), 信区: Poetry
标题: 【龙的传人】诗版和mitOCEF联合看图做诗活动
发信站: BBS 未名空间站 (Thu Feb 9 13:50:18 2012, 美东)
投稿要求：
1. 原创诗词，字数格式不限，必须附图。每个作品奖励80伪币。选图最好和助学有关
，图的link在这里：http://picasaweb.google.com/110242794795874975460?gsessionid=3-kmDEn8yllWrTVU3jTYYg
比如下面三张图，放飞梦想是OCEF去年T-shirt设计比赛的时候一个OCEF赞助的小朋友
画的。西湖小学的图里是OCEF捐款资助的新课桌，我个人很喜欢这张图，新课桌和那个
窟窿里的旧桌椅给人很美好的视觉冲击。贵州织金县的一系列照片里，我挑了这张，纯
属个人爱好。还有很多好图，每个人的视角可能不同，大家随便选啊。
2.为便于统计，参加活动的作品需在诗版首发，转发mitOCEF。请在征文前加入【龙的
传人】的字样。
3. 每个ID上限3个作品，活动截止本月底。奖励由mitOCEF版发行，请关注mitOCEF。
4. 为便于统计，请在征文前加入【龙的传人】的字样。
5. 鼓励朗诵自己的作品，如若被选中可以参加龙年晚会，另有额外奖励。有关晚会的
link在这里：http://www.mitbbs.com/article_t/mitOCEF/13409.html
6. 活动最终解释权归版务组。

a*t2015-02-06 08:02

2 楼

没怎么作研究，稀里糊涂的凭感觉就买了。不过总体还算满意把。

b*62015-02-06 08:02

3 楼

一个快餐店内一排N个座位，顾客进来后随机选位置，唯一的限制条件是不远已经有人
坐下的相邻位置。这样只到所有可选位置都被占。问题是最终被顾客坐下的位置的百分
比的mean, std.只要求给出N=25和50000时的数值解。

p*a2015-02-06 08:02

4 楼

原来薰衣草还是诗社的斑竹，太牛了～
图片是不是可以扩大一些啊？比如ocef网站上的宣传资料里:
http://www.ocef.org/publication/pic-show
比如中国事务网站：
http://china.ocef.org/

【在 h*********r 的大作中提到】

: 【以下文字转载自 Poetry 讨论区】
: 发信人: hualavender (薰衣草), 信区: Poetry
: 标题: 【龙的传人】诗版和mitOCEF联合看图做诗活动
: 发信站: BBS 未名空间站 (Thu Feb 9 13:50:18 2012, 美东)
: 投稿要求：
: 1. 原创诗词，字数格式不限，必须附图。每个作品奖励80伪币。选图最好和助学有关
: ，图的link在这里：http://picasaweb.google.com/110242794795874975460?gsessionid=3-kmDEn8yllWrTVU3jTYYg
: 比如下面三张图，放飞梦想是OCEF去年T-shirt设计比赛的时候一个OCEF赞助的小朋友
: 画的。西湖小学的图里是OCEF捐款资助的新课桌，我个人很喜欢这张图，新课桌和那个
: 窟窿里的旧桌椅给人很美好的视觉冲击。贵州织金县的一系列照片里，我挑了这张，纯

A*a2015-02-06 08:02

5 楼

好漂亮的石头

【在 a****t 的大作中提到】

: 没怎么作研究，稀里糊涂的凭感觉就买了。不过总体还算满意把。

s*h2015-02-06 08:02

6 楼

题目看不懂
第一句很有趣，可是不知道问的是啥？
看懂的解释一下？
25个顾客一起进的话，最多只有13个坐下，剩下12个离开？
1M个顾客的流水席，同时在座位上的人在1-13之间，25个座位都会被坐到吧。

v*l2015-02-06 08:02

7 楼

4C, please

b*62015-02-06 08:02

8 楼

sorry, 这里有错别字“唯一的限制条件是不选已经有人坐下的相邻位置。”就是新来
的顾客选座位会和已经有人的地方相隔至少一个位置。等所有这样的位置没有了
，给出百分比的答案。比如25个座位，最多只可能坐13个人，也可能少于13, 但是不会
是只有一个，最终两个顾客间最多可以相隔两个空座相隔三个的话就能多坐一个人了
，求平均值
和平均方差？一个更简单的例子，N=3,最终的情况可能是*-*, -*-, *-*（*表示有人
， -表示没人）,这样平均值是1/3×(2/3+1/3+2/3)=5/9。

a*t2015-02-06 08:02

9 楼

.92, h, ex cut, vs2, vg sym, vg polish

【在 v*l 的大作中提到】

: 4C, please

s*h2015-02-06 08:02

10 楼

貌似比较难啊
F(N) 是N个座位时顾客数的mean,
F(neg) = F(0) = 0
F(1) = F(2) = 1
F(3) = 5/3
有递推公式：F(N) = 1 + 1/N * sum(i from －1 to N-2) ( F(i) + F(N-3-i)
写个程序可以算出来。
用笔算就不会了。

z*y2015-02-06 08:02

11 楼

什么价位？

b*62015-02-06 08:02

12 楼

嗯，这个和我想得差不多，那std呢，可以递推吗？

【在 s****h 的大作中提到】

: 貌似比较难啊
: F(N) 是N个座位时顾客数的mean,
: F(neg) = F(0) = 0
: F(1) = F(2) = 1
: F(3) = 5/3
: 有递推公式：F(N) = 1 + 1/N * sum(i from －1 to N-2) ( F(i) + F(N-3-i)
: 写个程序可以算出来。
: 用笔算就不会了。

s*h2015-02-06 08:02

13 楼

std的公式就复杂了。
需要sum(i from -1 to N-2, j from -1 to N-2) F(i) * F(j) 之类的

l*s2015-02-06 08:02

14 楼

你这题不需要时间概念吗？

【在 b******6 的大作中提到】

: sorry, 这里有错别字“唯一的限制条件是不选已经有人坐下的相邻位置。”就是新来
: 的顾客选座位会和已经有人的地方相隔至少一个位置。等所有这样的位置没有了
: ，给出百分比的答案。比如25个座位，最多只可能坐13个人，也可能少于13, 但是不会
: 是只有一个，最终两个顾客间最多可以相隔两个空座相隔三个的话就能多坐一个人了
: ，求平均值
: 和平均方差？一个更简单的例子，N=3,最终的情况可能是*-*, -*-, *-*（*表示有人
: ， -表示没人）,这样平均值是1/3×(2/3+1/3+2/3)=5/9。

c*32015-02-06 08:02

15 楼

什么时间概念？

【在 l****s 的大作中提到】

: 你这题不需要时间概念吗？

n*y2015-02-06 08:02

16 楼

跟我前两天做的笔试题好像，
我用模拟做了，但是运行速度好慢，
而且我为了加快速度已经做了一些优化：
1) size大的variable用节省存储空间的data type，比如本来用0,1表示座位是不是
available，但是matlab默认0,1是double精度，我现在规定是binary datatype: True/
False
2) 本来是每轮在available的座位中随机产生的下一个要坐的座位，现在改为在一开始
产生全部的随机数(1-N的permutation)
code在这里(Matlab)，大家能不能帮我看看怎样提高速度，谢谢~
clear;
N = 25; %N = 50000; % how many seats in total
repeat = 1e6;
% count how many seats are taken
count = zeros(repeat, 1, 'uint16'); % uint16: 0-65535
for i = 1:repeat % repeat simulations

disp(i);

seq = uint16( randperm(N) );
seats = true(1,N); % seat(i)==true ~ available, ==false ~ unavailable

jj = 0;

while ( any(seats) ) % while any seat available

jj = jj + 1;

if seats( seq(jj) ) == false % if that seat unavailable, skip to
next loop
%disp('skip');
else % if that seat is available:
% sit, making that seat unavailable
seats( seq(jj) ) = false;
count(i) = count(i) + 1; % count how many seats are sit on
% neighboring seat(s) unavailable
if seq(jj) == 1
seats(2) = false;
elseif seq(jj) == N
seats(N-1) = false;
else
seats( seq(jj)+1 ) = false;
seats( seq(jj)-1 ) = false;
end
%disp(seats)
end

end

end
fraction_mean = mean(count1)/N;
fraction_std = std(double(count1))/N;

n*y2015-02-06 08:02

17 楼

谢谢分享！能不能解释一下这个递推公式怎么推导的？谢谢！

【在 s****h 的大作中提到】

s*h2015-02-06 08:02

18 楼

这个很直观啊。
N个座位，1到N，1号被坐，剩下的和N-2个座位一样。
i号被坐，i+1, i-1就不能坐了。
1 ～ i-2 不就是F(i-2),
i+2～N不就是F(N-i-2+1)

【在 n*******y 的大作中提到】

: 谢谢分享！能不能解释一下这个递推公式怎么推导的？谢谢！

T*u2015-02-06 08:02

19 楼

直觉上d&q

b*62015-02-06 08:02

20 楼

递推的python code
import numpy as np
def deduction(N):
"""
For number of seats taken, deduction:
mean(s(0)) = 0;
mean(s(1)) = 1;
mean(s(N)) = sum{1/N*[mean(s(k-2))+mean(s(N-k-1))+1]} sum for k =
1, 2, ..., N;
mean(s(N)) = 1 + 2/N*[mean(s(-1)) + mean(s(0)) + ... + mean(s(N-2
))] for N > 1.
here s(-1) is added for convenience and s(-1)=0.
For variance:
var(s(0)) = 0;
var(s(1)) = 0;
var = mean(s(N)^2) - (mean(s(N)))^2 for N > 1;
(mean(s(N)))^2 is known;
let p(s(k)) be the corresponding probability
mean(s(N)^2) = 1/N*sum{[s(k-2)+s(n-k-1)+1]^2*p(s(k-2))*p(s(n-k-1)
)}
sum for all k and all possible values of s(k-2) and s(n-k-1).
Expand all the terms:
==> mean(s(N)^2) = 1/N*sum{mean(s(k-2)^2)+mean(s(n-k-1)^2)+2*mean(s(k
-2))+\
2*mean(s(n-k-1))+2*mean(s(k-2))*mean(s(n-k-1
))+1} ===>
==> mean(s(N)^2) = 1 + 2/N*{mean(s(-1)^2)+mean(s(0)^2)+...+mean(s(N-2
)^2)}+\
4/N*{mean(s(-1))+mean(s(0))+...+mean(s(N-2))}+\
2/N*{mean(s(-1)*mean(s(N-2))+mean(s(0))*mean(s
(N-3))+...+\
mean(s(k-2))*mean(s(N-k-1))+...+mean(s(N-
k-1))*mean(s(k-2))+\
mean(s(N-3))*mean(s(0))+mean(s(N-2))*mean
(s(-1))}
where k = 1, 2, ..., N
Return (fraction_mean, fraction_std) = (mean(s(N))/N, sqrt(var(s(N))/
N)
"""
if N == 0: return (0.0, 0.0)
if N == 1: return (1.0, 0.0)
# _sum = mean(s(-1)) + mean(s(0)) + mean(s(1)) + ... + mean(s(N-2))
# _prev = [mean(s(-1)), mean(s(0)), mean(s(1)), ..., mean(s(N-1))]
# _prev_sm = mean(s(N-1)^2)
# _sum_sm = mean(s(-1)^2) + mean(s(0)^2) + ... + mean(s(N-2)^2) #sum of
square mean
# using decimal type to avoid float point rounding error
_prev_m = [0.0, 0.0, 1.0]
_prev_sm = 1.0
_sum = 0.0
_sum_sm = 0.0
for i in xrange(2, N+1):
mean = 1.0 + 2.0 / i * _sum
prev = np.array(_prev_m[:-1])
square_mean = (1.0 +
2.0 / i * _sum_sm +
4.0 / i * _sum +
2.0 / i * np.dot(prev, prev[::-1]))
_sum += _prev_m[-1]
_sum_sm += _prev_sm
_prev_m.append(mean)
_prev_sm = square_mean
mean_square = mean*mean
var = square_mean - mean_square
return (float(mean/N), float(np.sqrt(var))/N)
N = 25: mean = 4.442122414e-01, std = 2.864508024e-02
N = 50000: mean = 4.323382983e-01, std = 6.052559416e-04

l*m2015-02-06 08:02

21 楼

难道是data incubator？这个simulation呀，很简单呀。递推mean意义就变了吧？

l*m2015-02-06 08:02

22 楼

楼上递推mean和variance的没上过统计课吧？

T*u2015-02-06 08:02

23 楼

我开始也是这么想。不过现在出题的精了流行往多层次嘛。25个好模拟，给个
100000000出来就算死了，所以怎么模拟也东东脑筋。

【在 l********m 的大作中提到】

: 难道是data incubator？这个simulation呀，很简单呀。递推mean意义就变了吧？

l*m2015-02-06 08:02

24 楼

50000 simulation确实要时间多些。楼主这是什么面试题呀？我做了一道一样的是data
incubator。

b*62015-02-06 08:02

25 楼

是data incubator的。确实没上过统计，见笑了。可以解释下为什不不能推导吗？那
比如说最简单的coin toss也要模拟？

l*m2015-02-06 08:02

26 楼

Simulation 的意义在于通过对实际情况的大尺度模拟（或者说Sampling）来估算true
mean. 我们不知道true mean。所以true mean. 简单的说不能推他的patern. 就算推
也是带erorr term 的。你那个算法是用两个 sample mean 来推三个sample 的mean
，在推四个sample 的sample mean。推的都不是一个x 呀！
模拟是要考虑random ness的。不考虑randomness的叫数值计算。coin toss 每投一次
可能是正面可能是背面。
那个data incubator 我也做了。不知道啥前有消息呀？招多少个人呀？你知道吗？

b*62015-02-06 08:02

27 楼

我也不知道

true
mean

【在 l********m 的大作中提到】

: Simulation 的意义在于通过对实际情况的大尺度模拟（或者说Sampling）来估算true
: mean. 我们不知道true mean。所以true mean. 简单的说不能推他的patern. 就算推
: 也是带erorr term 的。你那个算法是用两个 sample mean 来推三个sample 的mean
: ，在推四个sample 的sample mean。推的都不是一个x 呀！
: 模拟是要考虑random ness的。不考虑randomness的叫数值计算。coin toss 每投一次
: 可能是正面可能是背面。
: 那个data incubator 我也做了。不知道啥前有消息呀？招多少个人呀？你知道吗？

s*h2015-02-06 08:02

28 楼

肯定弄错了，mean怎么可能这么小？
mean > N / 3

=
-2

【在 b******6 的大作中提到】

: 递推的python code
: import numpy as np
: def deduction(N):
: """
: For number of seats taken, deduction:
: mean(s(0)) = 0;
: mean(s(1)) = 1;
: mean(s(N)) = sum{1/N*[mean(s(k-2))+mean(s(N-k-1))+1]} sum for k =
: 1, 2, ..., N;
: mean(s(N)) = 1 + 2/N*[mean(s(-1)) + mean(s(0)) + ... + mean(s(N-2

b*62015-02-06 08:02

29 楼

ratio

【在 s****h 的大作中提到】

: 肯定弄错了，mean怎么可能这么小？
: mean > N / 3
:
: =
: -2

d*e2015-02-06 08:02

30 楼

mean可以用Law of total expectation来递归。
variance可以用Law of total variance来递归，不过也忒麻烦点了。

【在 s****h 的大作中提到】

: std的公式就复杂了。
: 需要sum(i from -1 to N-2, j from -1 to N-2) F(i) * F(j) 之类的

l*m2015-02-06 08:02

31 楼

递推不叫模拟吧？

l*m2015-02-06 08:02

32 楼

你用law of total expectation, conditional probability 怎么算呢？这个题每个
座位两边是一个位子还是两个位子不确定呀，分三种情况，一边一个（1/4），一边一
个另一边两个（1/2），两边两个（1/4）？还有两个把头的座位也不一样。

【在 d******e 的大作中提到】

: mean可以用Law of total expectation来递归。
: variance可以用Law of total variance来递归，不过也忒麻烦点了。

n*y2015-02-06 08:02

33 楼

哦！这就是recursive方法是吧~ 谢谢分享！
请问一下，是不是recursive比起重复模拟（就是随机的一个一个位子坐）快？

【在 s****h 的大作中提到】

: 这个很直观啊。
: N个座位，1到N，1号被坐，剩下的和N-2个座位一样。
: i号被坐，i+1, i-1就不能坐了。
: 1 ～ i-2 不就是F(i-2),
: i+2～N不就是F(N-i-2+1)

n*y2015-02-06 08:02

34 楼

我也做了对是the data incubator的
你第三题做什么了？
我想不出什么特有商业价值的
只要做了chicago crime data的分析，说商业上也会关心local安全

data

【在 l********m 的大作中提到】

: 50000 simulation确实要时间多些。楼主这是什么面试题呀？我做了一道一样的是data
: incubator。

d*e2015-02-06 08:02

35 楼

X_N,N个椅子上的人数。
Y第一个人做在J把椅子上。
P(Y=1) = ... = P(Y=N) = 1/N
E(X_N) = \sum_{J=1}^N P(Y=J)*[E(X_{J-2}) + 1 + E(X_{N-J-1})]
第1把到第J-2把第J+2把到底N把。

【在 l********m 的大作中提到】

: 你用law of total expectation, conditional probability 怎么算呢？这个题每个
: 座位两边是一个位子还是两个位子不确定呀，分三种情况，一边一个（1/4），一边一
: 个另一边两个（1/2），两边两个（1/4）？还有两个把头的座位也不一样。

d*e2015-02-06 08:02

36 楼

我觉得对于面试来说递归就已经到头了。
但话说回来，递归并不算是数值解法。Simulation的话又闲得太无聊了。
问的挺奇怪。

【在 n*******y 的大作中提到】

: 哦！这就是recursive方法是吧~ 谢谢分享！
: 请问一下，是不是recursive比起重复模拟（就是随机的一个一个位子坐）快？

g*22015-02-06 08:02

37 楼

for n = 50000 case,
x y mean((x+y)/50000)
sd((x+y)/50000)
this should be a good enough approximation

d*c2015-02-06 08:02

38 楼

我是直接求distribution然后再递推，N数字大了以后太慢，python程序优化之后到N＝
500都是立刻
出来，但是N到800以后就越来越慢，到50000不知道要算多久，拟合一下可能能估计出
来，没再试了。因为中间那些情形的计算是组合爆炸的，没什么办法能绕开，上map
reduce用并行倒是可以。
上面直接对sd递推可能比我这个要少计算很多。

b*x2015-02-06 08:02

39 楼

搭车同问有关这个data incubator的项目，有人收到回复了吗，它家会默拒申请人吗？

m*92015-02-06 08:02

40 楼

还没有收到回复，估计3月1号左右能知道结果。

【在 b********x 的大作中提到】

: 搭车同问有关这个data incubator的项目，有人收到回复了吗，它家会默拒申请人吗？