x*****i
发帖数: 287 | 1 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. 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.
难度增加了，原来是走到对角，先要求走遍所有的角。 |
L**********u
发帖数: 194 | 2 这种题目都被做烂了，
找本讲markov chain 的书看看就全会了。
【在 x*****i 的大作中提到】
: 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. 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.
: 难度增加了，原来是走到对角，先要求走遍所有的角。
|
x*****i
发帖数: 287 | 3 How do you set the states? Thanks a lot :) |
w*******x
发帖数: 489 | 4 怎么做？
【在 x*****i 的大作中提到】
: 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. 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.
: 难度增加了，原来是走到对角，先要求走遍所有的角。
|
w*******x
发帖数: 489 | 5 总么没人给答案 这种题没见过
都不屑吗
模拟了一下 21步遍历
到对角10步check code。
#include
#include
#include
using namespace std;
int A[2][2][2];
int main()
{
double ave = 0;
for(int j=0;j<100000;j++)
{
int *p=&A[0][0][0];
for(int i=0;i<8;i++)p[i]=0;p[0]=1;
int count=0;
int finished=1;
int x[3]={0,0,0};
while(finished<8)
{
++count;
int r=rand()%3;
x[r]=(x[r]+1)%2;
if(A[x[0]][x[1]][x[2]]==0)++finished;
A[x[0]][x[1]][x[2]]=1;
// if(A[1][1][1])finished=10;
}
ave += count;
}
cout<<(ave/=100000)<
}
【在 w*******x 的大作中提到】
: 怎么做？
|
z****g
发帖数: 1978 | 6 1. write transition matrix
2. expected iteration time
standard markov chain problem
【在 x*****i 的大作中提到】
: 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. 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.
: 难度增加了，原来是走到对角，先要求走遍所有的角。
|
w*******x
发帖数: 489 | 7 有人有好方法算出来了的post个答案谢谢
【在 x*****i 的大作中提到】
: 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. 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.
: 难度增加了，原来是走到对角，先要求走遍所有的角。
|
p*****k
发帖数: 318 | 8 xiguapi and washialex,
there was some discussion on mathoverflow and the answer is 1996/95.
many similar problems in this area (cover times) are still unsolved, due
to the prohibitively large number of states and equations involved, and
personally i think this question is not appropriate for interviews... |
w*******x
发帖数: 489 | 9 Great, Thanks
This is what I expected, rather than something trivial as typical Markov
question
【在 p*****k 的大作中提到】
: xiguapi and washialex,
: there was some discussion on mathoverflow and the answer is 1996/95.
: many similar problems in this area (cover times) are still unsolved, due
: to the prohibitively large number of states and equations involved, and
: personally i think this question is not appropriate for interviews...
|
a****e
发帖数: 428 | 10 see our book recommendation in "Quantitative Finance" Group.
http://www.overseatalents.com/node/1781 |
