d***u
发帖数: 19 | 1 1. You roll an n sided die. If the result is 1, you may re-roll or take
the result. Otherwise (i.e., the result is 2,3,...,n), you can only take
the result. On the re-roll, you may re-roll if the result is a 2 or less,
then a 3 or less, ect. On the nth re-roll, you may re-roll if the result
is n or less (any result). Each re-roll is optional. What is the maximum
expected value of this game?
2. A spider starts at one corner of a cube. Each second, he randomly
chooses one of the edges he is adjacent to and walks along it. What's the
expected number of seconds before the spider has visited every corner of
the cube.
完全没有概念该怎么做呀？哪位大牛指点一下。。谢谢～ | f********y
发帖数: 278 | 2 这些都是基本的markov chain的题目.你可以search "one-step analysis".
【在 d***u 的大作中提到】
: 1. You roll an n sided die. If the result is 1, you may re-roll or take
: the result. Otherwise (i.e., the result is 2,3,...,n), you can only take
: the result. On the re-roll, you may re-roll if the result is a 2 or less,
: then a 3 or less, ect. On the nth re-roll, you may re-roll if the result
: is n or less (any result). Each re-roll is optional. What is the maximum
: expected value of this game?
: 2. A spider starts at one corner of a cube. Each second, he randomly
: chooses one of the edges he is adjacent to and walks along it. What's the
: expected number of seconds before the spider has visited every corner of
: the cube.
| w*********i
发帖数: 77 | 3 第一题我觉得是dynamic programming吧？
请问如果用markov chain的话，第二题的状态空间如何定义？
多谢指教 ～～
【在 f********y 的大作中提到】
: 这些都是基本的markov chain的题目.你可以search "one-step analysis".
| f********y
发帖数: 278 | 4 你对的,应该用DP,:-(
因为求optimal action,
【在 w*********i 的大作中提到】
: 第一题我觉得是dynamic programming吧？
: 请问如果用markov chain的话，第二题的状态空间如何定义？
: 多谢指教 ～～
| w*********i
发帖数: 77 | 5 那请问第二题的状态空间如何定义？
【在 f********y 的大作中提到】
: 你对的,应该用DP,:-(
: 因为求optimal action,
| d***u
发帖数: 19 | 6 第一题当n小的时候还好算，当n变大的时候，感觉太复杂了，不知道有什么巧妙的方法
可以得到通式
呢？
第二题也不知道该怎么算，用martingale可以解吗？对martingale不熟:(
【在 w*********i 的大作中提到】
: 第一题我觉得是dynamic programming吧？
: 请问如果用markov chain的话，第二题的状态空间如何定义？
: 多谢指教 ～～
| b******n
发帖数: 637 | | u******s
发帖数: 157 | | M********t
发帖数: 163 | 9 第二题不同的状态之间转换好算吗？即使知道是MARKOV CHAIN，怎么能够确保转移矩阵
算对？另外有没有巧妙的方法？ | f********y
发帖数: 278 | 10 跟coupon collection有点类似阿。
【在 b******n 的大作中提到】
: 第二题感觉不是很trivial啊，求解
| | | p*b
发帖数: 30 | 11 For the first problem, observe the fact that if you are allowed to re-roll
every time for whatever result, then you will roll the die until 'n' comes
out to achieve maximum outcome. Hence, the optimal strategy is to re-roll
every time if you satisfy the re-roll criterion. Under this strategy, we
know
For k=2,...,n-1, the probability that you will get k as the outcome is (k-2)
!/n^(k-1)
For P(X=n) = 1-P(X=2)-...-P(X=n-1)
then you can get the expected value easily.
【在 d***u 的大作中提到】
: 1. You roll an n sided die. If the result is 1, you may re-roll or take
: the result. Otherwise (i.e., the result is 2,3,...,n), you can only take
: the result. On the re-roll, you may re-roll if the result is a 2 or less,
: then a 3 or less, ect. On the nth re-roll, you may re-roll if the result
: is n or less (any result). Each re-roll is optional. What is the maximum
: expected value of this game?
: 2. A spider starts at one corner of a cube. Each second, he randomly
: chooses one of the edges he is adjacent to and walks along it. What's the
: expected number of seconds before the spider has visited every corner of
: the cube.
| p*b
发帖数: 30 | 12 但是比coupon collection难，每次能选到的‘coupon’depend on the last ‘coupon
’selected...
【在 f********y 的大作中提到】
: 跟coupon collection有点类似阿。
| w*********m
发帖数: 196 | 13 是比coupon collection难，用monte carlo先试试再说 | d***u
发帖数: 19 | 14 No. Because the objective is to maximize the expected value, and you can
only roll a limited number of times. For example, on the n-th roll,
although you can re-roll for whatever result, but the optimal strategy is
to re-roll only if the result is smaller than (n+1)/2 (the expected value
of the (n+1)-th roll)
roll
comes
roll
(k-2)
【在 p*b 的大作中提到】
: For the first problem, observe the fact that if you are allowed to re-roll
: every time for whatever result, then you will roll the die until 'n' comes
: out to achieve maximum outcome. Hence, the optimal strategy is to re-roll
: every time if you satisfy the re-roll criterion. Under this strategy, we
: know
: For k=2,...,n-1, the probability that you will get k as the outcome is (k-2)
: !/n^(k-1)
: For P(X=n) = 1-P(X=2)-...-P(X=n-1)
: then you can get the expected value easily.
| d****r
发帖数: 135 | 15 第一题一共能roll几次啊？是不是n次，还是说没上限啊？ | d***u
发帖数: 19 | 16 最多可以roll n+1次
【在 d****r 的大作中提到】
: 第一题一共能roll几次啊？是不是n次，还是说没上限啊？
| d****r
发帖数: 135 | 17 第一题一共能roll几次啊？是不是n次，还是说没上限啊？ | p*b
发帖数: 30 | 18 I misunderstood for rolling as many as you want...
If the maxmimum roll is n+1, then the optimal strategry shall be stop as
soon as you get some value larger or equal to the ceiling of (n+1)/2, denote
which as m.
Then P(X=1) = (m-1)! (m-1)^(n-m+1)/n^(n+1)
for k = 2,...,m-1
P(X=k) = sum_{i from 2 to k} (i-2)!/n^(i-1) + P(X=1)
for k = m,...,n
P(X=k) = sum_{i from 2 to m} (i-2)!/n^(i-1) + (m-1)!/n^m [1+ (m-1)/n + (m-1)
^2/n^2 + ... + (n-m)^(n-m+1)/n^(n-m+!)]
【在 d***u 的大作中提到】
: 最多可以roll n+1次
| d***u
发帖数: 19 | 19 No....
denote
(m-1)
【在 p*b 的大作中提到】
: I misunderstood for rolling as many as you want...
: If the maxmimum roll is n+1, then the optimal strategry shall be stop as
: soon as you get some value larger or equal to the ceiling of (n+1)/2, denote
: which as m.
: Then P(X=1) = (m-1)! (m-1)^(n-m+1)/n^(n+1)
: for k = 2,...,m-1
: P(X=k) = sum_{i from 2 to k} (i-2)!/n^(i-1) + P(X=1)
: for k = m,...,n
: P(X=k) = sum_{i from 2 to m} (i-2)!/n^(i-1) + (m-1)!/n^m [1+ (m-1)/n + (m-1)
: ^2/n^2 + ... + (n-m)^(n-m+1)/n^(n-m+!)]
| x******a
发帖数: 6336 | 20 第一题通式是不是这样的
E（X_k）= (k-1)*E(X_{k+1})/n +(n+k)(n-k+1)/(2n);
with boundary condition
E(X_(n+1))=(n+1)/2.
【在 d***u 的大作中提到】
: 1. You roll an n sided die. If the result is 1, you may re-roll or take
: the result. Otherwise (i.e., the result is 2,3,...,n), you can only take
: the result. On the re-roll, you may re-roll if the result is a 2 or less,
: then a 3 or less, ect. On the nth re-roll, you may re-roll if the result
: is n or less (any result). Each re-roll is optional. What is the maximum
: expected value of this game?
: 2. A spider starts at one corner of a cube. Each second, he randomly
: chooses one of the edges he is adjacent to and walks along it. What's the
: expected number of seconds before the spider has visited every corner of
: the cube.
| | | c******r
发帖数: 300 | 21 For 1:
f(n+1) = (n+1)/2.
t(k) = min(k, floor(k+1)) - the threshold to determine whether a re-roll is
allowable and better
f(k) = (\sum_{i = t(k) + 1}^{n} i + f(k+1) * t(k)) / n
【在 d***u 的大作中提到】
: 1. You roll an n sided die. If the result is 1, you may re-roll or take
: the result. Otherwise (i.e., the result is 2,3,...,n), you can only take
: the result. On the re-roll, you may re-roll if the result is a 2 or less,
: then a 3 or less, ect. On the nth re-roll, you may re-roll if the result
: is n or less (any result). Each re-roll is optional. What is the maximum
: expected value of this game?
: 2. A spider starts at one corner of a cube. Each second, he randomly
: chooses one of the edges he is adjacent to and walks along it. What's the
: expected number of seconds before the spider has visited every corner of
: the cube.
| d***u
发帖数: 19 | 22 实际上这个过程可以分解成2个部分，前半段是只要有机会reroll就一定reroll，而后
半段实际上需
要比较扔出的结果X_k和 E(X_{k+1}),只有当点数小于E(X_{k+1})的时候才重新扔。递
推公示大概
是这样的
E（X_k）= f(k+1)*f(k+1)/n +(f(k+1)+n+1)(n-f(k+1))/(2n);
where f(k+1)=min{k, E(X_(k+1))}
可是写出通式，得到boundary condition，还是推不出解来啊:( 想了好多天了
【在 x******a 的大作中提到】
: 第一题通式是不是这样的
: E（X_k）= (k-1)*E(X_{k+1})/n +(n+k)(n-k+1)/(2n);
: with boundary condition
: E(X_(n+1))=(n+1)/2.
| c******r
发帖数: 300 | 23 For 2, I can only think of a dumb approach: define a unique state by the
nodes traversed so far and the location of the current step and define the
traversal time for each unique state, you can then have an equation
according to first-step analysis that links the traversal times for
different states, note that there are many isometry here which may simply
things a little bit. Still this approach seems to be too complicated to work
out ...
【在 d***u 的大作中提到】
: 1. You roll an n sided die. If the result is 1, you may re-roll or take
: the result. Otherwise (i.e., the result is 2,3,...,n), you can only take
: the result. On the re-roll, you may re-roll if the result is a 2 or less,
: then a 3 or less, ect. On the nth re-roll, you may re-roll if the result
: is n or less (any result). Each re-roll is optional. What is the maximum
: expected value of this game?
: 2. A spider starts at one corner of a cube. Each second, he randomly
: chooses one of the edges he is adjacent to and walks along it. What's the
: expected number of seconds before the spider has visited every corner of
: the cube.
| d***u
发帖数: 19 | 24 可恶的是，2 还有一个扩展版，
Let the spider be in a corner of a regular polyhedron with n sides. What
is the expected number of seconds until the spider has visited every
corner.
。。。。。。
这几天就为了这几道题，吃不好，睡不好。。。
the
simply
work
【在 c******r 的大作中提到】
: For 2, I can only think of a dumb approach: define a unique state by the
: nodes traversed so far and the location of the current step and define the
: traversal time for each unique state, you can then have an equation
: according to first-step analysis that links the traversal times for
: different states, note that there are many isometry here which may simply
: things a little bit. Still this approach seems to be too complicated to work
: out ...
| x*a
发帖数: 48 | 25 define a markov chain with 4 states (total steps + 1), state s=0,1,2,3
contains points that are s steps away from the start point.
state 0: start point
state 3: end point
state 1 and 2 contains 3 points each.
P = [
0 1 0 0
1/3 0 2/3 0
0 2/3 0 1/3
0 0 0 1
]
X0 X1 X2 X3 are the expected steps from state s to state 3; so
X0 = 1+X1
X1 = 1+(X0+2*X2)/3
X2 = 1+(2*X1+X3)/3
X3 = 0
[X0 X1 X2 X3] = [10 9 7 0]
If by regular polyhedron you mean an n-dim cube, then
X0 = 1 + X1
X_k = 1 + [ k*X_{k-1} + (n-k)*X_{k+1} ] / n , k=1...n-1
X_n = 0
If by regular polyhedron you mean one of the nine regular polyhedra in
http://en.wikipedia.org/wiki/Regular_polyhedron, you'll have to do some counting first before forming your own equations.
For 1，
Denote X_k the k-th result (if ever reached this point) and T_k its
threshold to proceed to the next round, ie, if X_k<=T_k; also E_k the
expectation starting from k-th round, then E_1 is what we want to calculate.
E_{n+1} = (n+1)/2
T_k = min ( k, floor(E_{k+1}) )
E_k = [ T_k*E_{k+1} + sum(T_k +1 to n) ] / n
Matlab script is rather simple (at least the result matches with manual
calculation when n=2)
n=3;
E=(n+1)/2;
for k=n:-1:1
T=min(k,floor(E));
E=(T*E+sum(T+1:n))/n;
end
E
A closed form solution may be impossible due to the non-linear min() and
floor() functions.
Just found 1 has been solved in a previous post.
【在 d***u 的大作中提到】
: 可恶的是，2 还有一个扩展版，
: Let the spider be in a corner of a regular polyhedron with n sides. What
: is the expected number of seconds until the spider has visited every
: corner.
: 。。。。。。
: 这几天就为了这几道题，吃不好，睡不好。。。
:
: the
: simply
: work
| d***u
发帖数: 19 | 26 好像看错题目了。。。
【在 x*a 的大作中提到】
: define a markov chain with 4 states (total steps + 1), state s=0,1,2,3
: contains points that are s steps away from the start point.
: state 0: start point
: state 3: end point
: state 1 and 2 contains 3 points each.
: P = [
: 0 1 0 0
: 1/3 0 2/3 0
: 0 2/3 0 1/3
: 0 0 0 1
| l******e
发帖数: 470 | 27 2就是个random walk的cover time.
有standard的方法，running time 是 图的size的指数
当然就一个cube，指数不指数没什么关系
【在 d***u 的大作中提到】
: 1. You roll an n sided die. If the result is 1, you may re-roll or take
: the result. Otherwise (i.e., the result is 2,3,...,n), you can only take
: the result. On the re-roll, you may re-roll if the result is a 2 or less,
: then a 3 or less, ect. On the nth re-roll, you may re-roll if the result
: is n or less (any result). Each re-roll is optional. What is the maximum
: expected value of this game?
: 2. A spider starts at one corner of a cube. Each second, he randomly
: chooses one of the edges he is adjacent to and walks along it. What's the
: expected number of seconds before the spider has visited every corner of
: the cube.
| p*******o
发帖数: 3564 | 28 做过类似马踏棋盘的题目，马从棋盘上指定一格开始跳，最后遍历棋盘的平均步数
结果好像是 Sum_{n!=i} pi_n/pi_i
设初始位置是i，如此结果就是7，太简单了？
【在 d***u 的大作中提到】
: 可恶的是，2 还有一个扩展版，
: Let the spider be in a corner of a regular polyhedron with n sides. What
: is the expected number of seconds until the spider has visited every
: corner.
: 。。。。。。
: 这几天就为了这几道题，吃不好，睡不好。。。
:
: the
: simply
: work
| c****o
发帖数: 1280 | 29 well, think about the second in terms of random walk, for clockwise +1, for
counterclockwise -1, then the problem transfer to what is the expected time
to first reach +3 or -3, and this is easy.
【在 d***u 的大作中提到】
: 1. You roll an n sided die. If the result is 1, you may re-roll or take
: the result. Otherwise (i.e., the result is 2,3,...,n), you can only take
: the result. On the re-roll, you may re-roll if the result is a 2 or less,
: then a 3 or less, ect. On the nth re-roll, you may re-roll if the result
: is n or less (any result). Each re-roll is optional. What is the maximum
: expected value of this game?
: 2. A spider starts at one corner of a cube. Each second, he randomly
: chooses one of the edges he is adjacent to and walks along it. What's the
: expected number of seconds before the spider has visited every corner of
: the cube.
| e*******k
发帖数: 3 | 30 it should be:
f(n+1) = (n+1)/2.
f(k) = (k+1+k+2+...+n)/n + (\sum_1^k max(i, a(k+1))/n | | | M********t
发帖数: 163 | 31 如果是你这么理解的题，确实是简单。但这是个三维空间，何来clockwise?
for
time
【在 c****o 的大作中提到】
: well, think about the second in terms of random walk, for clockwise +1, for
: counterclockwise -1, then the problem transfer to what is the expected time
: to first reach +3 or -3, and this is easy.
| m*********g
发帖数: 646 | 32 why do I find the 1st one is so hard....I don't think it is easy to come up
a final answer during an interview...
【在 d***u 的大作中提到】
: 1. You roll an n sided die. If the result is 1, you may re-roll or take
: the result. Otherwise (i.e., the result is 2,3,...,n), you can only take
: the result. On the re-roll, you may re-roll if the result is a 2 or less,
: then a 3 or less, ect. On the nth re-roll, you may re-roll if the result
: is n or less (any result). Each re-roll is optional. What is the maximum
: expected value of this game?
: 2. A spider starts at one corner of a cube. Each second, he randomly
: chooses one of the edges he is adjacent to and walks along it. What's the
: expected number of seconds before the spider has visited every corner of
: the cube.
| o******y
发帖数: 35 | 33 how can there be a maximum expected value for number 1. This is a trick
interview? |
|
