d***u 发帖数: 19 | 1 You throw a die with 10 sides , with number ranging from 1 to 10 (each
number comes up with prob. 0.1). You throw the die until until the sum is
greater than 100. What's the expected value of your sum? |
k*******a 发帖数: 772 | 2 挺有意思的题目,再来瞎估算估算,假设不停投
假设 P(n)是这个序列中含有n的概率
那么n,可能从n-1,n-2....n-10来的
P(n)=(P(n-1)+P(n-2)+...+P(n-10))/10
如果n足够大,可以想象 P(n)=constant=p
如果100算比较大的话,那么停止时候和为101,102...110
如果是101,那么101=100+1=99+2...=91+10
所以P(101)=(P(100)+P(99)+...+P(91))/10=p
P(102)=9/10p
....对于110,倒数第二投只能是100,最后一投只能10
P(110)=P(100)/10=p/10
这样可以把p求出来 归一化 p=2/11
于是 E(sum)=101*p+102*9p/10+...+110*p/10=104 |
Y***e 发帖数: 1030 | 3 104.5 ?
【在 d***u 的大作中提到】 : You throw a die with 10 sides , with number ranging from 1 to 10 (each : number comes up with prob. 0.1). You throw the die until until the sum is : greater than 100. What's the expected value of your sum?
|
d***u 发帖数: 19 | 4 how did you get that?
【在 Y***e 的大作中提到】 : 104.5 ?
|
w**********y 发帖数: 1691 | 5 俺给你发了站内信..
想询问一下,你这都是哪里来的题目,作业题还是真正的面试题还是面试习题集
你这两个题目都比一般的公司面试题要难不少啊.
谢谢 |
k*******a 发帖数: 772 | 6 刚刚编程模拟了一下,比较接近104:)
R code
x<-c()
for (i in 1:100000)
{
sum<-0
while(sum<101)
{
sum<-sum+floor(runif(1)*10)+1
}
x<-c(x,sum)
}
mean(x)=103.9928 |
G********d 发帖数: 10250 | 7 吃饱了蛋疼
【在 k*******a 的大作中提到】 : 刚刚编程模拟了一下,比较接近104:) : R code : x<-c() : for (i in 1:100000) : { : sum<-0 : while(sum<101) : { : sum<-sum+floor(runif(1)*10)+1 : }
|
G********d 发帖数: 10250 | 8 楼主在利用你们啊
根本不是面试题
【在 w**********y 的大作中提到】 : 俺给你发了站内信.. : 想询问一下,你这都是哪里来的题目,作业题还是真正的面试题还是面试习题集 : 你这两个题目都比一般的公司面试题要难不少啊. : 谢谢
|
w**********y 发帖数: 1691 | 9 一样.我刚在R里面run了一下.
结果接近104
final=c()
for (i in 1:10000){
s=0
while (s<=100) s=s+sample(sample(1:10,1,replace=T),1,replace=T)
final[i]=s
}
mean(final) |
w**********y 发帖数: 1691 | 10 大哥不要这么直接么..说出了俺心中的邪恶念头..
【在 G********d 的大作中提到】 : 楼主在利用你们啊 : 根本不是面试题
|
|
|
k*******a 发帖数: 772 | 11 看来我的解法还是make sense的。
【在 w**********y 的大作中提到】 : 一样.我刚在R里面run了一下. : 结果接近104 : final=c() : for (i in 1:10000){ : s=0 : while (s<=100) s=s+sample(sample(1:10,1,replace=T),1,replace=T) : final[i]=s : } : mean(final)
|
w**********y 发帖数: 1691 | 12
我觉得要用markov chain去做.
写出转移矩阵..去求 结果分别是101,102,...110的概率.
你的做法..不太sure算不算正确..
睡了..明天起来再写做法吧..
【在 k*******a 的大作中提到】 : 看来我的解法还是make sense的。
|
d***u 发帖数: 19 | 13 我也是用你这种方法近似的。
不过即使这样,最后的和我也花了好长时间去算,还算错了:(
【在 k*******a 的大作中提到】 : 挺有意思的题目,再来瞎估算估算,假设不停投 : 假设 P(n)是这个序列中含有n的概率 : 那么n,可能从n-1,n-2....n-10来的 : P(n)=(P(n-1)+P(n-2)+...+P(n-10))/10 : 如果n足够大,可以想象 P(n)=constant=p : 如果100算比较大的话,那么停止时候和为101,102...110 : 如果是101,那么101=100+1=99+2...=91+10 : 所以P(101)=(P(100)+P(99)+...+P(91))/10=p : P(102)=9/10p : ....对于110,倒数第二投只能是100,最后一投只能10
|
b******n 发帖数: 637 | 14 这种题很伤人的,尤其是不告诉你要近似还是要准确值。解题不难,难得的是练就一眼
就能看出有没有close form的能力。 |
k*******a 发帖数: 772 | 15 君子坦蛋蛋,小人藏鸡鸡
【在 G********d 的大作中提到】 : 吃饱了蛋疼
|
d***u 发帖数: 19 | 16 强烈同意!!
【在 b******n 的大作中提到】 : 这种题很伤人的,尤其是不告诉你要近似还是要准确值。解题不难,难得的是练就一眼 : 就能看出有没有close form的能力。
|
G********d 发帖数: 10250 | 17 这个做不通
【在 w**********y 的大作中提到】 : : 我觉得要用markov chain去做. : 写出转移矩阵..去求 结果分别是101,102,...110的概率. : 你的做法..不太sure算不算正确.. : 睡了..明天起来再写做法吧..
|
l******f 发帖数: 568 | 18 估计是JS家的
【在 w**********y 的大作中提到】 : 俺给你发了站内信.. : 想询问一下,你这都是哪里来的题目,作业题还是真正的面试题还是面试习题集 : 你这两个题目都比一般的公司面试题要难不少啊. : 谢谢
|
w*******n 发帖数: 773 | 19 make sense.
【在 k*******a 的大作中提到】 : 挺有意思的题目,再来瞎估算估算,假设不停投 : 假设 P(n)是这个序列中含有n的概率 : 那么n,可能从n-1,n-2....n-10来的 : P(n)=(P(n-1)+P(n-2)+...+P(n-10))/10 : 如果n足够大,可以想象 P(n)=constant=p : 如果100算比较大的话,那么停止时候和为101,102...110 : 如果是101,那么101=100+1=99+2...=91+10 : 所以P(101)=(P(100)+P(99)+...+P(91))/10=p : P(102)=9/10p : ....对于110,倒数第二投只能是100,最后一投只能10
|
v****s 发帖数: 1112 | 20 cool. this solution makes sense.
【在 k*******a 的大作中提到】 : 挺有意思的题目,再来瞎估算估算,假设不停投 : 假设 P(n)是这个序列中含有n的概率 : 那么n,可能从n-1,n-2....n-10来的 : P(n)=(P(n-1)+P(n-2)+...+P(n-10))/10 : 如果n足够大,可以想象 P(n)=constant=p : 如果100算比较大的话,那么停止时候和为101,102...110 : 如果是101,那么101=100+1=99+2...=91+10 : 所以P(101)=(P(100)+P(99)+...+P(91))/10=p : P(102)=9/10p : ....对于110,倒数第二投只能是100,最后一投只能10
|
|
|
m*********n 发帖数: 1819 | 21 你这是假设90-99出现概率相等啊。问题是不等啊。
对,你也acknowledge n必须足够大了。
【在 k*******a 的大作中提到】 : 挺有意思的题目,再来瞎估算估算,假设不停投 : 假设 P(n)是这个序列中含有n的概率 : 那么n,可能从n-1,n-2....n-10来的 : P(n)=(P(n-1)+P(n-2)+...+P(n-10))/10 : 如果n足够大,可以想象 P(n)=constant=p : 如果100算比较大的话,那么停止时候和为101,102...110 : 如果是101,那么101=100+1=99+2...=91+10 : 所以P(101)=(P(100)+P(99)+...+P(91))/10=p : P(102)=9/10p : ....对于110,倒数第二投只能是100,最后一投只能10
|
D**u 发帖数: 204 | 22 There is indeed a pseudo "closed form" for this problem,
"if" we can find all the root of the characteristic polynomial:
x^10 = (x^9+...+x+1)/10.
But I doubt that was the problem's intention.
1 is one of the roots, and has the
biggest abs value.
The P(n) in kirk's post can be expressed as
c1*x1^n + ... + cn*x10^n
for some c1,...,cn.
Let x1=1, then c1=2/11. If we know these x_i, then c_i
can be fitted using the value of P(1),...,P(10).
But it's almost impossible to give a closed form for x2,...,xn,
due to Hua Luogeng's result ...
【在 b******n 的大作中提到】 : 这种题很伤人的,尤其是不告诉你要近似还是要准确值。解题不难,难得的是练就一眼 : 就能看出有没有close form的能力。
|
w*********d 发帖数: 25 | 23 "这样可以把p求出来 归一化 p=2/11"
p=2/11怎么求出来的? |
D**u 发帖数: 204 | 24 I think the confusion is at the notation.
He means
P(stop at 101) = p (should not be P(101),
which was saved for a different definition).
Then we have
p + 9/10*p + ... + 1/10*p = 1,
which gives p = 2/11.
【在 w*********d 的大作中提到】 : "这样可以把p求出来 归一化 p=2/11" : p=2/11怎么求出来的?
|
k*******a 发帖数: 772 | 25 p+9/10p+...+p/10=1
【在 w*********d 的大作中提到】 : "这样可以把p求出来 归一化 p=2/11" : p=2/11怎么求出来的?
|
k*******a 发帖数: 772 | 26 I can use program to exactly calculate P(n)
R code:
p<-c(.1)
for (i in 2:10)
{
pi<-.1+sum(p)*.1
p<-c(p,pi)
}
for (i in 11:100)
{
pi<-sum(p[(i-10):(i-1)])*.1
p<-c(p,pi)
}
p
[1] 0.1000000 0.1100000 0.1210000 0.1331000 0.1464100 0.1610510 0.1771561
[8] 0.1948717 0.2143589 0.2357948 0.1593742 0.1653117 0.1708428 0.1758271
[15] 0.1800998 0.1834688 0.1857106 0.1865660 0.1857355 0.1828731 0.1775810
[22] 0.1794017 0.1808107 0.1818074 0.1824055 0.1826360 0.1825527 0.1822370
[29] 0.1818041 0.1814109 0.1812647 0.1816331 0.1818562 0.1819608 0.1819761
[36] 0.1819331 0.1818629 0.1817939 0.1817496 0.1817441 0.1817774 0.1818287
[43] 0.1818483 0.1818475 0.1818362 0.1818222 0.1818111 0.1818059 0.1818071
[50] 0.1818128 0.1818197 0.1818239 0.1818235 0.1818210 0.1818183 0.1818165
[57] 0.1818160 0.1818165 0.1818175 0.1818186 0.1818192 0.1818191 0.1818186
[64] 0.1818181 0.1818178 0.1818178 0.1818179 0.1818181 0.1818183 0.1818184
[71] 0.1818183 0.1818182 0.1818182 0.1818181 0.1818181 0.1818181 0.1818182
[78] 0.1818182 0.1818182 0.1818182 0.1818182 0.1818182 0.1818182 0.1818182
[85] 0.1818182 0.1818182 0.1818182 0.1818182 0.1818182 0.1818182 0.1818182
[92] 0.1818182 0.1818182 0.1818182 0.1818182 0.1818182 0.1818182 0.1818182
[99] 0.1818182 0.1818182
>
n>78 所有P都为0.18182=2/11
【在 D**u 的大作中提到】 : There is indeed a pseudo "closed form" for this problem, : "if" we can find all the root of the characteristic polynomial: : x^10 = (x^9+...+x+1)/10. : But I doubt that was the problem's intention. : 1 is one of the roots, and has the : biggest abs value. : The P(n) in kirk's post can be expressed as : c1*x1^n + ... + cn*x10^n : for some c1,...,cn. : Let x1=1, then c1=2/11. If we know these x_i, then c_i
|
x******a 发帖数: 6336 | 27 equivalent question:
let T=inf{t>0: x_1+...+x_{n-1}<=100, x_1+...x_n>100}.
what is E(T)?
【在 d***u 的大作中提到】 : You throw a die with 10 sides , with number ranging from 1 to 10 (each : number comes up with prob. 0.1). You throw the die until until the sum is : greater than 100. What's the expected value of your sum?
|
m***w 发帖数: 404 | 28 我想到一个思路:先算出使骰子的总分数超过100的投掷次数的expected hitting time
,然后去乘以每次骰子的expected value(显然是5.5)。好像觉得不是很对,哪位来
驳斥一下? |
G********d 发帖数: 10250 | |
S**********h 发帖数: 45 | 30
你回复真快,我刚贴完就发现楼上已经说了想法,赶快删了
【在 G********d 的大作中提到】 : 是。。。。那个估算还是靠谱 : : =5
|
|
|
s****p 发帖数: 19 | 31 This is an overshoot problem of arithmetic case (d=1). When the boundary is
large, the expected overshoot can be estimated by:
E(X^2)/2E(X)+d/2
Here X is the result of throwing die once. So the expected overshoot is
around 4, i.e., the answer should be 104 or something close to it.
By the way, I dont think there is a neat close form sol. |
D********G 发帖数: 70 | 32 (101*10+102*9+103*8+104*7+105*6+106*5+107*4 + 108*3 + 109*2+110*1)/(1+2+3+4+
5+6+7+8+9+10) = 5720/55 = 104
【在 d***u 的大作中提到】 : You throw a die with 10 sides , with number ranging from 1 to 10 (each : number comes up with prob. 0.1). You throw the die until until the sum is : greater than 100. What's the expected value of your sum?
|
D**********d 发帖数: 849 | |