由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Quant版 - 再请教一个掷骰子的面试题,谢谢~
相关主题
[合集] 发个面试题求解个面试题
[合集] 两个面试题(probability)[ Prob ] 面试题求助~
问个掷骰子的概率问题 (转载)请教两个面试题
MS quant finance program新题一道再向大家请教一道面试题
问个题一道题
一个面试题how to calculate E[X|X]?
[合集] 一个概率问题A random walk problem.
合集 Questions Summary一道Barclays的面试题
相关话题的讨论汇总
话题: 10话题: sum话题: 101话题: 100话题: 面试题
进入Quant版参与讨论
1 (共1页)
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 的大作中提到】
: 楼主在利用你们啊
: 根本不是面试题

相关主题
一个面试题求解个面试题
[合集] 一个概率问题[ Prob ] 面试题求助~
合集 Questions Summary请教两个面试题
进入Quant版参与讨论
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

相关主题
再向大家请教一道面试题A random walk problem.
一道题一道Barclays的面试题
how to calculate E[X|X]?问一个面试题,关于概率的
进入Quant版参与讨论
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
29
是。。。。那个估算还是靠谱

=5
S**********h
发帖数: 45
30

你回复真快,我刚贴完就发现楼上已经说了想法,赶快删了

【在 G********d 的大作中提到】
: 是。。。。那个估算还是靠谱
:
: =5

相关主题
一道面试题 谁来帮解答一下[合集] 两个面试题(probability)
请教两道题目,请大家帮忙帮忙。。。问个掷骰子的概率问题 (转载)
[合集] 发个面试题MS quant finance program新题一道
进入Quant版参与讨论
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
33
104
1 (共1页)
进入Quant版参与讨论
相关主题
一道Barclays的面试题问个题
问一个面试题,关于概率的一个面试题
一道面试题 谁来帮解答一下[合集] 一个概率问题
请教两道题目,请大家帮忙帮忙。。。合集 Questions Summary
[合集] 发个面试题求解个面试题
[合集] 两个面试题(probability)[ Prob ] 面试题求助~
问个掷骰子的概率问题 (转载)请教两个面试题
MS quant finance program新题一道再向大家请教一道面试题
相关话题的讨论汇总
话题: 10话题: sum话题: 101话题: 100话题: 面试题