l*******e
发帖数: 17 | 1 准备面试的时候，看面经发现一道以前的概率题，完全不知道怎么做。现在求助版上的
大神。
题目如下：
1． 基本问题。一个数据流包含4个整数，每个整数随机分布在1到10之间，两端都
包括，每个数的概率是一样的（即都是十分之一）， 这个数据流会被一个函数处理，
这个函数会保留这个数据流里面最大的两个数，并且返回这两个最大数的乘积。 假设
这个函数会处理很多这样的数据流，请问这个函数返回的乘积的expected value和 std
是多少？
举几个例子：
第一个数据流 包含8,4,9,2。最大的两个数是8和9，返回72.
第二个数据流包含10,2,5,10，最大两个数是10,10, 返回 100.
。。。。。。以此类推
先说说我的思路。如果这个题不是问乘积，而是问最大值的expected value，就变得比
较简单。
要算最大值的expected value, 可以用下面的方法。
假设最大值是k,那么k是最大值的概率为(k^4-(k-1)^4)/10^4。也就是说要k是最大值，
这个数据流里面的每个数都只能取1至k,总共有k^4取法。但是还要去除某些不包含k的
组合，这些组合有（k-1）^4种，而总的组合方式有10^4种。两者相除就是上面的答案。
K可以取1至10里面的任意值，所以expected value 就是
10*（10^4-9^4）/10^4 +9*（9^4-8^4）/10^4+……。我算了下，答案是8.4667。我同
时写了个程序模拟了下，模拟的值也和这个大难吻合。所以我觉得这个计算方法应该是
正确的。
但是要算最大乘积的expected value,我现在还没想到好的方法。有几个思路但是都还
觉得有缺陷。我写了个程序模拟了下，答案应该是56.96-57之间。但是用统计的方法不
知道怎么做。希望版上的大神能够提供下思路或者解法。
2. Follow up：如果这个数据流的长度是T,而现在要计算最大的N个数的expected
value和std，又应该如何计算呢？ | b*****s
发帖数: 11267 | 2 order statistics ，这里类比 uniform吧
std
【在 l*******e 的大作中提到】
: 准备面试的时候，看面经发现一道以前的概率题，完全不知道怎么做。现在求助版上的
: 大神。
: 题目如下：
: 1． 基本问题。一个数据流包含4个整数，每个整数随机分布在1到10之间，两端都
: 包括，每个数的概率是一样的（即都是十分之一）， 这个数据流会被一个函数处理，
: 这个函数会保留这个数据流里面最大的两个数，并且返回这两个最大数的乘积。 假设
: 这个函数会处理很多这样的数据流，请问这个函数返回的乘积的expected value和 std
: 是多少？
: 举几个例子：
: 第一个数据流 包含8,4,9,2。最大的两个数是8和9，返回72.
| s**********r
发帖数: 84 | | h********e
发帖数: 95 | 4 最大和第二大order statistic joint distribution X 和 Y有公式求
用这个joint对XY做1，2moments，然后继续套公式做sqrt(var) | g**a
发帖数: 2129 | 5 order statistics x(i) of U(0,1) follow beta(i,n-i+1). where n=4 is the total
number x
x(3)~beta(3,2) and x(4)~beta(4,1)
so (x(3),x(4))~beta(3,2)*beta(4,1) due to iid (1-1)
let u=x(3)*x(4) and v=x(3). You can find f(u,v) by transforming (1-1). Then
integrating out v, you get the marginal dist of u. It is likely a beta. Then
you have the E and var |
|
