c*****o
发帖数: 178 | 1 On an empty chessboard, a horse starts from a point (say location x, y) and
it starts moving randomly, but once it moves out of board, it can’t come
inside. So what is the total probability that it stays within the board
after N steps？ | c**********e
发帖数: 2007 | 2 Can be done by iteration. Let P(x,y,n) be the probability of
starting from (x,y) and moving out in n steps.
Initial condition: P(x,y,0)=0 for all 1=
For convenience, denote P(0,y,n)=P(9,y,n)=P(x,0,n)=P(x,9,n)=1,
and P(-1,y,n)=P(10,y,n)=P(x,-1,n)=P(x,10,n)=1.
Then the iterative formula is
P(x,y,n)=(P(x-2,y-1,n-1)+P(x-2,y+1,n-1)+P(x-1,y-2,n-1)+P(x-1,y+2,n-1)
P(x+1,y-2,n-1)+P(x+1,y+2,n-1)+P(x+2,y-1,n-1)+P(x+2,y+1,n-1))/8.
It is easy to use computer to do the iteration.
As the prob | c**********e
发帖数: 2007 | 3 One may want to do it in matrix form. Then the iteration can be written as
P_{n+1}=A P_n + b.
Here A is a 64 by 64 matrix, and b and P_n are both 64 by 1 column vector.
P_n=(P(1,1,n) P(1,2,n) ... P(1,8,n);P(2,1,n) ... ...P(8,8,n))^T
The the general solution is:
P_n=(A^n+A^{n-1}+...+A+I)*b = (I-A)^{-1}(I-A^n)*b
Where I is a 64*64 unit matrix. It is easy but tedious to write out A and b. | c*****o
发帖数: 178 | 4 这个马的规则好像不对，有8种可能。至于方法我也是这么想的，但是原文里面提示用
Fibonacci数列，我不太明白。
【在 c**********e 的大作中提到】
: Can be done by iteration. Let P(x,y,n) be the probability of
: starting from (x,y) and moving out in n steps.
: Initial condition: P(x,y,0)=0 for all 1=: For convenience, denote P(0,y,n)=P(9,y,n)=P(x,0,n)=P(x,9,n)=1,
: and P(-1,y,n)=P(10,y,n)=P(x,-1,n)=P(x,10,n)=1.
: Then the iterative formula is
: P(x,y,n)=(P(x-2,y-1,n-1)+P(x-2,y+1,n-1)+P(x-1,y-2,n-1)+P(x-1,y+2,n-1)
: P(x+1,y-2,n-1)+P(x+1,y+2,n-1)+P(x+2,y-1,n-1)+P(x+2,y+1,n-1))/8.
: It is easy to use computer to do the iteration.
: As the prob
| n******h
发帖数: 50 | | c*****o
发帖数: 178 | 6 Fibonacci number of n-1. It can be solved by using fibonacci number and
series information.
【在 n******h 的大作中提到】
: 是可以写成数列的形式进行计算。原文怎么说？
| n******h
发帖数: 50 | 7 well. the possibilities for each grid near the piece follow the binomial
form of Fibonacci series. check that out.
【在 c*****o 的大作中提到】
: Fibonacci number of n-1. It can be solved by using fibonacci number and
: series information.
| c**********e
发帖数: 2007 | 8 You are right. The knight can move to 8 places. I have corrected it.
【在 c*****o 的大作中提到】
: 这个马的规则好像不对，有8种可能。至于方法我也是这么想的，但是原文里面提示用
: Fibonacci数列，我不太明白。
|
|
