p**e
发帖数: 41 | 1 跟zhouxinfeng的书上的那倒题目很相，但是不一样，我就不知道怎么解了？
You draw cards randomly from a pack of 52, getting 2 points for 2
consecutive red cards, and -1 for 2 black ones. Expected gain ? Algo to
compute ? | s*******s
发帖数: 1568 | 2 f(n,m,0) = m/nf(n-1,m-1,1) + (n-m)/nf(n-1,m,0)
f(n,m,1) = m/n(1+f(n-1,m-1,1) ) + (n-m)/nf(n-1,m,0)
where n is number of cards, m is number of red cards.
f(1,1,1) =1 f(1,0,1)= 0
f(1,1,0) =0 f(1,0,0) =0
【在 p**e 的大作中提到】
: 跟zhouxinfeng的书上的那倒题目很相，但是不一样，我就不知道怎么解了？
: You draw cards randomly from a pack of 52, getting 2 points for 2
: consecutive red cards, and -1 for 2 black ones. Expected gain ? Algo to
: compute ?
| p**e
发帖数: 41 | 3 请问f的第三个参数0或者1是什么意思啊？
【在 s*******s 的大作中提到】
: f(n,m,0) = m/nf(n-1,m-1,1) + (n-m)/nf(n-1,m,0)
: f(n,m,1) = m/n(1+f(n-1,m-1,1) ) + (n-m)/nf(n-1,m,0)
: where n is number of cards, m is number of red cards.
: f(1,1,1) =1 f(1,0,1)= 0
: f(1,1,0) =0 f(1,0,0) =0
| h*****d
发帖数: 5 | 4 0: last card is black
1: last card is red
【在 p**e 的大作中提到】
: 请问f的第三个参数0或者1是什么意思啊？
| s*******s
发帖数: 1568 | 5 means condition on draw a red already or not. It is a dynamics programming
problem in probability.
【在 p**e 的大作中提到】
: 请问f的第三个参数0或者1是什么意思啊？
| U**e
发帖数: 876 | 6 你列个DP给人家，难道能给出答案来吗？
我怀疑面试官想要的不是这几个式子
【在 s*******s 的大作中提到】
: means condition on draw a red already or not. It is a dynamics programming
: problem in probability.
| o*p
发帖数: 77 | | p**e
发帖数: 41 | 8 如果last and the one before last都是red， 而你抽下次又得red，算两次加分吗？
【在 s*******s 的大作中提到】
: means condition on draw a red already or not. It is a dynamics programming
: problem in probability.
| p*****k
发帖数: 318 | 9
pere, that's a key question. unfortunately, this is not clear
from how the problem was stated.
if each card could be used twice for consecutive pairs, e.g.,
if one draws 4 red card consecutively, one gets +6 pts instead of
+4 pts. this version of the problem has a nice analytic solution
by exploiting the linearity of the expectation operator:
there are total of 51 spaces between 52 cards; each space
represents a pair. the prob of the two cards beside each space
being same color is (26*25)/(5
【在 p**e 的大作中提到】
: 如果last and the one before last都是red， 而你抽下次又得red，算两次加分吗？
| n****e
发帖数: 629 | 10 Very nice one. This post should be marked
【在 p*****k 的大作中提到】
:
: pere, that's a key question. unfortunately, this is not clear
: from how the problem was stated.
: if each card could be used twice for consecutive pairs, e.g.,
: if one draws 4 red card consecutively, one gets +6 pts instead of
: +4 pts. this version of the problem has a nice analytic solution
: by exploiting the linearity of the expectation operator:
: there are total of 51 spaces between 52 cards; each space
: represents a pair. the prob of the two cards beside each space
: being same color is (26*25)/(5
| p**e
发帖数: 41 | 11 hehe, i always email all pcasnik's posts to my emailbox, as well as other
people's good replies :))
【在 n****e 的大作中提到】
: Very nice one. This post should be marked
| B*****i
发帖数: 831 | 12 这个draw cards的过程是with replacement吗？
【在 p**e 的大作中提到】
: 跟zhouxinfeng的书上的那倒题目很相，但是不一样，我就不知道怎么解了？
: You draw cards randomly from a pack of 52, getting 2 points for 2
: consecutive red cards, and -1 for 2 black ones. Expected gain ? Algo to
: compute ?
| e**********n
发帖数: 359 | 13 A back-of-envelope calculation:
Let x_1 to x_52 be 1 or -1, 1 for red and -1 for black.
With x_i and x_{i+1} the scoring function is
f(x_i, x_{i+1})=1/4 + 1/4(x_i x_{i+1}) + 3/4(x_i + x_{i+1})
The expected total score is
E \sum_{i=1}^{51}f(x_i, x_{i+1}) =51/4 + sum_{i=1}^{51} E(x_i x_{i+1})/4,
because E(x_i) = 0.
Using
E(x_i x_{i+1} ) = E(x_1x_2) = 1/2( 25/51-26/51)*2 = -1/51,
I get the expected score 51/4-1/4 =25/2.
Hopefully the numbers are correct. |
|
