l*******z
发帖数: 108 | 1 一个正方型 ABCD，每个顶点走到相邻的两个顶点的概率为0.5，问从A走到D，需要步数
的期望 , 请问，状态方程该怎么列呢 ?
Many thanks
这个问题还可以推广到一个立方体 |
k*****y
发帖数: 744 | 2 If the square looks like
A B
C D,
then look one step ahead and you can find the relations:
n_A = 1 + 0.5*( n_B + n_C)
n_B = 1 + 0.5*( n_A + 0 )
n_C = 1 + 0.5*( n_A + 0 )
and use the symmetry n_B = n_C to reduce the number of variables.
【在 l*******z 的大作中提到】
: 一个正方型 ABCD，每个顶点走到相邻的两个顶点的概率为0.5，问从A走到D，需要步数
: 的期望 , 请问，状态方程该怎么列呢 ?
: Many thanks
: 这个问题还可以推广到一个立方体
|
l*******z
发帖数: 108 | 3 多谢，基本看懂了。
n_i 代表用了 n_i 步走到了顶点 i
比如 n_A = 1 + 0.5*( n_B + n_C)
代表顶点A有可能是从B或是C 走过来，根据对称性，可能各是0.5的概率 （这一点我有
点怀疑！）any comment ?
顶点B和C只有可能是从A走过来的，因为一旦走到D，就结束了。
n_D=0.5*(n_B+n_C)=3
最后得出期望是3步。
【在 k*****y 的大作中提到】
: If the square looks like
: A B
: C D,
: then look one step ahead and you can find the relations:
: n_A = 1 + 0.5*( n_B + n_C)
: n_B = 1 + 0.5*( n_A + 0 )
: n_C = 1 + 0.5*( n_A + 0 )
: and use the symmetry n_B = n_C to reduce the number of variables.
|
l*******z
发帖数: 108 | 4 我还有个问题，
B点只有可能是从A点走过来的啊。因为一旦走到D点就结束了，那为什么概率还是0.5呢？
【在 k*****y 的大作中提到】
: If the square looks like
: A B
: C D,
: then look one step ahead and you can find the relations:
: n_A = 1 + 0.5*( n_B + n_C)
: n_B = 1 + 0.5*( n_A + 0 )
: n_C = 1 + 0.5*( n_A + 0 )
: and use the symmetry n_B = n_C to reduce the number of variables.
|
k*****y
发帖数: 744 | 5 Sorry for the confusion.
n_*是从*到D的平均步数。
A走一步到B或C。B走一步可能已经到D或者回到A。
【在 l*******z 的大作中提到】
: 多谢，基本看懂了。
: n_i 代表用了 n_i 步走到了顶点 i
: 比如 n_A = 1 + 0.5*( n_B + n_C)
: 代表顶点A有可能是从B或是C 走过来，根据对称性，可能各是0.5的概率 （这一点我有
: 点怀疑！）any comment ?
: 顶点B和C只有可能是从A走过来的，因为一旦走到D，就结束了。
: n_D=0.5*(n_B+n_C)=3
: 最后得出期望是3步。
|
l*******z
发帖数: 108 | 6 如果是这样的话，我觉得你的方程有点问题，我觉得应该这样
假如现在B点，那么有可能0.5的盖率到D点(finished)，也有可能0.5的盖率回到A点 |
l*******z
发帖数: 108 | 7 应该这样，假如现在B点, 有可能经过一步回到A点，也有可能直接到达D点，两中事件
概率各为0.5 |
L**********u
发帖数: 194 | 8 it is a typical markov chain problem.
write down the transition matrix
D A B C
1 1/2 0 1/2 D
0 0 1/2 0 A
0 1/2 0 1/2 B
0 0 1/2 0 C
Denote the right-bottom 3 by 3 block by Q. calculate M=(I-Q)^{-1},
the sum of the first column of M is the expected steps.
hehe
【在 l*******z 的大作中提到】
: 应该这样，假如现在B点, 有可能经过一步回到A点，也有可能直接到达D点，两中事件
: 概率各为0.5
|
r****t
发帖数: 10904 | 9 我觉得你没看懂，n_i 意思是：从 i 开始，用了期望 n_i 步走到 D （absorption time)，是个递归。
【在 l*******z 的大作中提到】
: 多谢，基本看懂了。
: n_i 代表用了 n_i 步走到了顶点 i
: 比如 n_A = 1 + 0.5*( n_B + n_C)
: 代表顶点A有可能是从B或是C 走过来，根据对称性，可能各是0.5的概率 （这一点我有
: 点怀疑！）any comment ?
: 顶点B和C只有可能是从A走过来的，因为一旦走到D，就结束了。
: n_D=0.5*(n_B+n_C)=3
: 最后得出期望是3步。
|
r****t
发帖数: 10904 | 10 这个是科班解法, greg lawler上面有
【在 L**********u 的大作中提到】
: it is a typical markov chain problem.
: write down the transition matrix
: D A B C
: 1 1/2 0 1/2 D
: 0 0 1/2 0 A
: 0 1/2 0 1/2 B
: 0 0 1/2 0 C
: Denote the right-bottom 3 by 3 block by Q. calculate M=(I-Q)^{-1},
: the sum of the first column of M is the expected steps.
: hehe
|
A****F
发帖数: 1133 | 11 n_i代表用了多少步从i到D
所以题目是求n_A.
而n_D=0,
kinecty列的这两个式子：
n_B = 1 + 0.5*( n_A + 0 )
n_C = 1 + 0.5*( n_A + 0 )
中的0应该就是n_D
【在 l*******z 的大作中提到】
: 多谢，基本看懂了。
: n_i 代表用了 n_i 步走到了顶点 i
: 比如 n_A = 1 + 0.5*( n_B + n_C)
: 代表顶点A有可能是从B或是C 走过来，根据对称性，可能各是0.5的概率 （这一点我有
: 点怀疑！）any comment ?
: 顶点B和C只有可能是从A走过来的，因为一旦走到D，就结束了。
: n_D=0.5*(n_B+n_C)=3
: 最后得出期望是3步。
|
