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_
|
|
