r**e 发帖数: 44 | 1 今天刚被电面过,问了这样一道题
4个独立同分布从随机数,在19到39之间均匀分布。
4个数之和为110的概率是多少?4个数之和为N的概率是多少? | s*******0 发帖数: 3461 | | L*********Z 发帖数: 52 | | d********t 发帖数: 9628 | 4 How?
【在 s*******0 的大作中提到】 : 0.030409357 : ?
| s********r 发帖数: 529 | 5 这个是离散分布吧?是从19到39之间的整数?
【在 r**e 的大作中提到】 : 今天刚被电面过,问了这样一道题 : 4个独立同分布从随机数,在19到39之间均匀分布。 : 4个数之和为110的概率是多少?4个数之和为N的概率是多少?
| g*********g 发帖数: 26 | 6 By central limit theorem, we can take approximation of normal distribution.
The approximated answer is 0.0279, while the exact value is 0.0274 which I
calculated by Matlab. | s********r 发帖数: 529 | 7 只有四个数也可以用中心极限定律吗?。。。
【在 g*********g 的大作中提到】 : By central limit theorem, we can take approximation of normal distribution. : The approximated answer is 0.0279, while the exact value is 0.0274 which I : calculated by Matlab.
| g*********g 发帖数: 26 | 8 之前也不太确定 所以才算了一下exact value 发现还挺准的
求大牛指教啊 一般需要多少个值用CLT才精确 不同分布是不是需要的数量不一样?
【在 s********r 的大作中提到】 : 只有四个数也可以用中心极限定律吗?。。。
| s********r 发帖数: 529 | 9 你的每一个随机变量是连续还是离散的呀?算出来方差多少呀?
【在 g*********g 的大作中提到】 : 之前也不太确定 所以才算了一下exact value 发现还挺准的 : 求大牛指教啊 一般需要多少个值用CLT才精确 不同分布是不是需要的数量不一样?
| g*********g 发帖数: 26 | 10 显然是离散的 不然等于某个值的概率一定是0
把分布平移到uniform[1,21]上 110移至37
S~aN(44,146.67)
然后算[36.5,37.5]的概率
不过我有个问题,这是道电面题,要得到这个cdf必须用程序算啊,还是只要求解步骤
么?
莫非有什么心算的方法?
【在 s********r 的大作中提到】 : 你的每一个随机变量是连续还是离散的呀?算出来方差多少呀?
| | | s********r 发帖数: 529 | 11 均值是不是应该移到38?
U[19,39]=18+U[1,21]
110-18*4=38
【在 g*********g 的大作中提到】 : 显然是离散的 不然等于某个值的概率一定是0 : 把分布平移到uniform[1,21]上 110移至37 : S~aN(44,146.67) : 然后算[36.5,37.5]的概率 : 不过我有个问题,这是道电面题,要得到这个cdf必须用程序算啊,还是只要求解步骤 : 么? : 莫非有什么心算的方法?
| g*********g 发帖数: 26 | 12 呃。。。丢人了。。。是38。。。
重新算了下 0.0291
阿弥陀佛 SORRY
【在 s********r 的大作中提到】 : 均值是不是应该移到38? : U[19,39]=18+U[1,21] : 110-18*4=38
| d*c 发帖数: 121 | 13 19-39平移到0-20, N平移到N-19*4
是不是这样?
prob = choose(N-19*4 + 3, 3)/21^4
N=110时候得到0.030769 | p********6 发帖数: 1802 | 14 大于16吧
【在 g*********g 的大作中提到】 : 之前也不太确定 所以才算了一下exact value 发现还挺准的 : 求大牛指教啊 一般需要多少个值用CLT才精确 不同分布是不是需要的数量不一样?
| s********r 发帖数: 529 | 15 这样的方法没有考虑平移之后每个数必须小于20
【在 d*c 的大作中提到】 : 19-39平移到0-20, N平移到N-19*4 : 是不是这样? : prob = choose(N-19*4 + 3, 3)/21^4 : N=110时候得到0.030769
| c*m 发帖数: 1114 | 16 19<=x_i<=39
Define y_i=x_i-18; thus sum(y_i)=sum(x_i)-72
1<=y_i<=21, 求P(sum(y_i))=110-72=38
y1,y2,y3,y4共有21^4选法(without order)
110
假设只考虑y_i>=1, sum(y_i)=38有C(37,3)种选法
再排除掉y_i>21的情况:
因为sum(y_i)=38, 所有顶多只有一个y_i>21, 把这个相应的y_i减去21形成一个新的y_
i'. 这样形成一个去除了21后的新sum()=38-21=17. 一共有C(16,3)种选法,得到的每一
组选法中任何一个数都可以是那个大于21的数,所以总共有C(16,4)*4种选法。
这样最好sum(y_i)=110的概率是(C(37,3)-C(16,3)*4)/21^4=0.0284
如果四个数总和不是110,情况会更复杂一点。
【在 s********r 的大作中提到】 : 这样的方法没有考虑平移之后每个数必须小于20
| g*********g 发帖数: 26 | 17 请问这个C(37,3)是怎么来的?
【在 c*m 的大作中提到】 : 19<=x_i<=39 : Define y_i=x_i-18; thus sum(y_i)=sum(x_i)-72 : 1<=y_i<=21, 求P(sum(y_i))=110-72=38 : y1,y2,y3,y4共有21^4选法(without order) : 110 : 假设只考虑y_i>=1, sum(y_i)=38有C(37,3)种选法 : 再排除掉y_i>21的情况: : 因为sum(y_i)=38, 所有顶多只有一个y_i>21, 把这个相应的y_i减去21形成一个新的y_ : i'. 这样形成一个去除了21后的新sum()=38-21=17. 一共有C(16,3)种选法,得到的每一 : 组选法中任何一个数都可以是那个大于21的数,所以总共有C(16,4)*4种选法。
| c*m 发帖数: 1114 | 18 38个数中有37个间隔,选3个间隔形成一组4个数y1,y2,y3,y4且y1+y2+y3+y4=38, y_i>=
1
【在 g*********g 的大作中提到】 : 请问这个C(37,3)是怎么来的?
| s********r 发帖数: 529 | 19 嗯,这样子答案就看上去很好了,多谢解答啦!
y_
每一
【在 c*m 的大作中提到】 : 19<=x_i<=39 : Define y_i=x_i-18; thus sum(y_i)=sum(x_i)-72 : 1<=y_i<=21, 求P(sum(y_i))=110-72=38 : y1,y2,y3,y4共有21^4选法(without order) : 110 : 假设只考虑y_i>=1, sum(y_i)=38有C(37,3)种选法 : 再排除掉y_i>21的情况: : 因为sum(y_i)=38, 所有顶多只有一个y_i>21, 把这个相应的y_i减去21形成一个新的y_ : i'. 这样形成一个去除了21后的新sum()=38-21=17. 一共有C(16,3)种选法,得到的每一 : 组选法中任何一个数都可以是那个大于21的数,所以总共有C(16,4)*4种选法。
| s*******0 发帖数: 3461 | 20 算错了
【在 d********t 的大作中提到】 : How?
| | | g*********g 发帖数: 26 | 21 多谢!BTW你思路好清晰啊!
>=
【在 c*m 的大作中提到】 : 38个数中有37个间隔,选3个间隔形成一组4个数y1,y2,y3,y4且y1+y2+y3+y4=38, y_i>= : 1
| r**a 发帖数: 536 | 22 可不可以用下面这个方法做:
假设x1, x2, x3, x4是uniformly distributed on[19 , 39]
然后定义z1=x1+x2+x3+x4-116, z2=x1+x2-x3-x4, z3=x1-x2, z4=x3-x4.他们是
independent的。这样我可以用z反解出x1, x2, x3, x4.然后假设z1=N.然后代入x1, x2
, x3, x4的probability的积分表达式。这样可以求出当z1=N的条件概率。
我没有细算数值,哪位大牛说说上面的思路有问题不? | s********r 发帖数: 529 | 23 理论上应该可以,但是这样应该不是在面试级别的时间内可以回答出来近似答案的
x2
【在 r**a 的大作中提到】 : 可不可以用下面这个方法做: : 假设x1, x2, x3, x4是uniformly distributed on[19 , 39] : 然后定义z1=x1+x2+x3+x4-116, z2=x1+x2-x3-x4, z3=x1-x2, z4=x3-x4.他们是 : independent的。这样我可以用z反解出x1, x2, x3, x4.然后假设z1=N.然后代入x1, x2 : , x3, x4的probability的积分表达式。这样可以求出当z1=N的条件概率。 : 我没有细算数值,哪位大牛说说上面的思路有问题不?
| r**a 发帖数: 536 | 24 哦,这个我就不好说了。不过这题情况比较特殊,如果按照我那个方法做得好pdf不用
动的,因为是常函数。唯一比较麻烦的是把那个积分dx1*dx2*dx3*dx4写成dz1*dz2*dz3
*dz4
【在 s********r 的大作中提到】 : 理论上应该可以,但是这样应该不是在面试级别的时间内可以回答出来近似答案的 : : x2
| s********r 发帖数: 529 | 25 嗯,如果可以写出来答案的话就没问题啊,反正只要方法对就可以了
dz3
【在 r**a 的大作中提到】 : 哦,这个我就不好说了。不过这题情况比较特殊,如果按照我那个方法做得好pdf不用 : 动的,因为是常函数。唯一比较麻烦的是把那个积分dx1*dx2*dx3*dx4写成dz1*dz2*dz3 : *dz4
| a****h 发帖数: 126 | 26 牛。还有一个问题,为什么不是 C(16,2)?
y_
每一
【在 c*m 的大作中提到】 : 19<=x_i<=39 : Define y_i=x_i-18; thus sum(y_i)=sum(x_i)-72 : 1<=y_i<=21, 求P(sum(y_i))=110-72=38 : y1,y2,y3,y4共有21^4选法(without order) : 110 : 假设只考虑y_i>=1, sum(y_i)=38有C(37,3)种选法 : 再排除掉y_i>21的情况: : 因为sum(y_i)=38, 所有顶多只有一个y_i>21, 把这个相应的y_i减去21形成一个新的y_ : i'. 这样形成一个去除了21后的新sum()=38-21=17. 一共有C(16,3)种选法,得到的每一 : 组选法中任何一个数都可以是那个大于21的数,所以总共有C(16,4)*4种选法。
| p*****k 发帖数: 318 | 27 this is essentially cem's approach, but slightly cleaner:
consider the prob generating function: [(x^19+x^20+...+x^39)/21]^4,
one needs the coefficient of x^N in the expansion (with 76<=N<=156).
rewrite this as x^76/21^4 * (1-x^21)^4 * (1-x)^(-4) and use the
negative binomial coefficient. thus the prob of getting N is:
sum of n from 0 to floor{(N-76)/21} (-1)^n * C(4,n) * C(N-76-21*n+3,3),
where C(m,n) = m!/[n!*(n-m)!], floor is the floor function
N=110 (two terms in the sum) gives 790/27783 ~ 0.0284 | l*******z 发帖数: 108 | 28 你好,多谢你的解答。
我觉得在算分子的时候应该考虑顺序问题。因为在算分母的时候,21^4其实是考虑了顺
序的。比如1,2,3,4 和4,3,2,1是两种不同的,都是21^4其中的一种。先选第一个数,
有21种选法,再选第二个数,有21种选法,。。。。。。你说的without order我觉得
是不对的。
所以在算分子的时候也应该考虑 顺序问题。要乘上A(4,4)
在计算分母和分子的时候,要么都考虑顺序,要么都不考虑顺序。
你们认为呢?
y_
每一
【在 c*m 的大作中提到】 : 19<=x_i<=39 : Define y_i=x_i-18; thus sum(y_i)=sum(x_i)-72 : 1<=y_i<=21, 求P(sum(y_i))=110-72=38 : y1,y2,y3,y4共有21^4选法(without order) : 110 : 假设只考虑y_i>=1, sum(y_i)=38有C(37,3)种选法 : 再排除掉y_i>21的情况: : 因为sum(y_i)=38, 所有顶多只有一个y_i>21, 把这个相应的y_i减去21形成一个新的y_ : i'. 这样形成一个去除了21后的新sum()=38-21=17. 一共有C(16,3)种选法,得到的每一 : 组选法中任何一个数都可以是那个大于21的数,所以总共有C(16,4)*4种选法。
| c*m 发帖数: 1114 | 29 这个without order的确是我不严谨的瞎写。
结论应该没有错误,分子分母都是ordered with replacement的case.
general case的interpretion/solution在pcasnik的帖子里面清楚的表述出来了。
【在 l*******z 的大作中提到】 : 你好,多谢你的解答。 : 我觉得在算分子的时候应该考虑顺序问题。因为在算分母的时候,21^4其实是考虑了顺 : 序的。比如1,2,3,4 和4,3,2,1是两种不同的,都是21^4其中的一种。先选第一个数, : 有21种选法,再选第二个数,有21种选法,。。。。。。你说的without order我觉得 : 是不对的。 : 所以在算分子的时候也应该考虑 顺序问题。要乘上A(4,4) : 在计算分母和分子的时候,要么都考虑顺序,要么都不考虑顺序。 : 你们认为呢? : : y_
|
|