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，又应该如何计算呢？ | a*******e
发帖数: 253 | 2 我觉得能否把各种情况的概率都算出来，譬如最大两个数都是10的概率，最大两个数是
10和9的概率，分别都算出来，然后算mean和std不就可以了么
std
【在 l*******e 的大作中提到】
: 准备面试的时候，看面经发现一道以前的概率题，完全不知道怎么做。现在求助版上的
: 大神。
: 题目如下：
: 1． 基本问题。一个数据流包含4个整数，每个整数随机分布在1到10之间，两端都
: 包括，每个数的概率是一样的（即都是十分之一）， 这个数据流会被一个函数处理，
: 这个函数会保留这个数据流里面最大的两个数，并且返回这两个最大数的乘积。 假设
: 这个函数会处理很多这样的数据流，请问这个函数返回的乘积的expected value和 std
: 是多少？
: 举几个例子：
: 第一个数据流 包含8,4,9,2。最大的两个数是8和9，返回72.
| l*******e
发帖数: 17 | 3 我也是这么想的，但是具体来实现有点小瑕疵，比如最大两个是（10,10）的话，另外
两个可以是1到10的任何数，然后是要考虑各种排列。如果最大两个是（10,9）的话，
另外两个数可以是1到9的任何数，然后考虑排列。现在我纠结的就是具体每个情况的排
列怎么算（本人非统计和数学出身，所以功底比较差）。而且这个做法要解决follow
up的问题会比较头疼。假如数据流的长度是8，要算最大4个数的乘积的expected value
的话，用这个办法可能比较麻烦。
【在 a*******e 的大作中提到】
: 我觉得能否把各种情况的概率都算出来，譬如最大两个数都是10的概率，最大两个数是
: 10和9的概率，分别都算出来，然后算mean和std不就可以了么
:
: std
| a*******e
发帖数: 253 | 4 4个数里面最大两个数都是10的概率我是这么算的：
只有一个10的概率是(4*9^3)/(10^4),没有10的概率是(9^4)/(10^4),然后所求概率为1
减去前面两个概率之和。其他组合以此类推。。
求版上大神们指正。
value
【在 l*******e 的大作中提到】
: 我也是这么想的，但是具体来实现有点小瑕疵，比如最大两个是（10,10）的话，另外
: 两个可以是1到10的任何数，然后是要考虑各种排列。如果最大两个是（10,9）的话，
: 另外两个数可以是1到9的任何数，然后考虑排列。现在我纠结的就是具体每个情况的排
: 列怎么算（本人非统计和数学出身，所以功底比较差）。而且这个做法要解决follow
: up的问题会比较头疼。假如数据流的长度是8，要算最大4个数的乘积的expected value
: 的话，用这个办法可能比较麻烦。
| l*******e
发帖数: 17 | 5
1
我想的也差不多，但是具体到其他组合这个算法可能要改一下。
举个例子，假设最大的两个数是（8,7），那么剩下的两个数只能是1到7中间选，每个
数的可能性是7，所以两个数就是7^2。然后要算在这种情况下的总排列数，可能的情况
有（8,7,7,7,），（8,7,7,6），（8，7,1,2)......等等。要算这个组合的概率的话，
底数当然是10^4，但是怎么算正确的排列数呢？敢问 apollolee (皮皮狗)兄台，要是
（8,7）的情况，这里的概率应该怎么算呢？另外一种可能的组合是（7,7），我觉得（
7,7）和（8,7）的算法也应该不一样？
【在 a*******e 的大作中提到】
: 4个数里面最大两个数都是10的概率我是这么算的：
: 只有一个10的概率是(4*9^3)/(10^4),没有10的概率是(9^4)/(10^4),然后所求概率为1
: 减去前面两个概率之和。其他组合以此类推。。
: 求版上大神们指正。
:
: value
| b********3
发帖数: 13 | 6 直接算？
次序统计量的联合分布：
P（ X_(1)，X_(2) = （i，j）,i>=j）=( C(4,2)*2!* (1/10) * (1/10)*( j/10 ) *(
j/10））
mean就是 \Sigma P(X_(1)，X_(2) = （i，j）,i>=j)*(i*j), 求和是在i>=j, 1<=i<=
10,1<=j<=10
var就是先算 \Sigma P(X_(1)，X_(2) = （i，j）,i>=j)*(i*j)^2 再减 mean^2
一般情况的话用次序统计量的联合分布得肯定得编程算了
期待大神们的解法 | l*******e
发帖数: 17 | 7
(
我写的程序大概结构就是这样的，唯一觉得不太能拿的准的地方就是这里
P（ X_(1)，X_(2) = （i，j）,i>=j）=( C(4,2)*2!* (1/10) * (1/10)*( j/10 ) *(j
/10））。这貌似是个很基本的排列组合问题，但是我这块基础太差了。。。。。。
【在 b********3 的大作中提到】
: 直接算？
: 次序统计量的联合分布：
: P（ X_(1)，X_(2) = （i，j）,i>=j）=( C(4,2)*2!* (1/10) * (1/10)*( j/10 ) *(
: j/10））
: mean就是 \Sigma P(X_(1)，X_(2) = （i，j）,i>=j)*(i*j), 求和是在i>=j, 1<=i<=
: 10,1<=j<=10
: var就是先算 \Sigma P(X_(1)，X_(2) = （i，j）,i>=j)*(i*j)^2 再减 mean^2
: 一般情况的话用次序统计量的联合分布得肯定得编程算了
: 期待大神们的解法
| l*******e
发帖数: 17 | 8
(
bigswing23 兄台能解释下: P（ X_(1)，X_(2) = （i，j）,i>=j）=( C(4,2)*2!* (1/
10) * (1/10)*( j/10 ) *(j/10））是怎么得到的吗？我考虑了几个例子，假设最大的
两个数是（8,7）或者（7,7），这个算概率的方法貌似不正确。也许是我理解不正确？
？
【在 b********3 的大作中提到】
: 直接算？
: 次序统计量的联合分布：
: P（ X_(1)，X_(2) = （i，j）,i>=j）=( C(4,2)*2!* (1/10) * (1/10)*( j/10 ) *(
: j/10））
: mean就是 \Sigma P(X_(1)，X_(2) = （i，j）,i>=j)*(i*j), 求和是在i>=j, 1<=i<=
: 10,1<=j<=10
: var就是先算 \Sigma P(X_(1)，X_(2) = （i，j）,i>=j)*(i*j)^2 再减 mean^2
: 一般情况的话用次序统计量的联合分布得肯定得编程算了
: 期待大神们的解法
| c**********e
发帖数: 534 | 9 Can't type Chinese.
First note that for i.i.d {X_1,X_2,...,X_n} with c.d.f F, the c.d.f. of max{
X_1,...,X_n} is F^n.
Then condition on the value of the largest one. | b********3
发帖数: 13 | 10 确实错了
原来的想法：一个数取i:1/10,一个数取j:1/10, 剩下的俩数在 1-j之间 j/10, 我原来
的答案这样是认为C(4,2)*2!种取法 是错的，多算了
直接数手算感觉算不出来 有数字可以相互相等的情况会mess up。
换一种想法：P(i,K,T):= 数据流长度是T（T个样本）,数据在1-K之间均匀取，最大值
为i的概率。则
P（ X_(1)，X_(2) = （i，j）,i>=j） = P（ X_(2) = j|X_(1) = i）*P(X_(1) = i)
P(X_(1) = i) = P(i,K,T)
P（ X_(2) = j|X_(1) = i） = P(j,i,T-1)
这样一般情况貌似也能算？
1/
【在 l*******e 的大作中提到】
:
: (
: bigswing23 兄台能解释下: P（ X_(1)，X_(2) = （i，j）,i>=j）=( C(4,2)*2!* (1/
: 10) * (1/10)*( j/10 ) *(j/10））是怎么得到的吗？我考虑了几个例子，假设最大的
: 两个数是（8,7）或者（7,7），这个算概率的方法貌似不正确。也许是我理解不正确？
: ？
|
|
