r********n 发帖数: 6979 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: dclocation (dclocation), 信区: JobHunting
标 题: 碰到一道题
发信站: BBS 未名空间站 (Sat Apr 10 11:23:26 2010, 美东)
一个unit cubic,一只蚂蚁在一个角,准备在这个cubic的edge上开始爬动。蚂蚁爬过一
条边的时间为1,它在任意一个角的时候,往其他三个方向去的概率都是1/3.问蚂蚁从
一个角爬到对角的平均时间是多少?
我印象以前见到过这个题,应该是利用了Markov Chain的一些什么属性。当时只有5分
钟了,我考虑了一下,一下子实在想不出来,就撤了。 |
h*****0 发帖数: 4889 | 2 除非你经常搞概率,否则用“专业”办法很容易出错,在考试的情况下太紧张也弄不出
来的。
用直觉:对于起始角和目的地角,一共有三种角关系:
(a) 立方体对位,设平均时间为Ta
此时不管蚂蚁往哪爬,经过时间1之后都将处于“距离目的地角为一个面对角线位”的
位置。见(b).
Ta = 1 + Tb
(b) 一个面对角线位,设平均时间为Tb
此时蚂蚁和2/3的几率爬到邻位,见(c);有1/3的几率爬到立方体对位,见(a).
Tb = 1 + 2/3 * Tc + 1/3 * Ta
(c) 邻位,设平均时间为Tc
此时有1/3几率直接爬到目的地;有2/3几率爬到一个面对角线位,见(b)
Tc = 1 + 2/3 * Tb
这样,三个方程,三个未知数。可解出:
Ta = 10
Tb = 9
Tc = 7
【在 r********n 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: dclocation (dclocation), 信区: JobHunting : 标 题: 碰到一道题 : 发信站: BBS 未名空间站 (Sat Apr 10 11:23:26 2010, 美东) : 一个unit cubic,一只蚂蚁在一个角,准备在这个cubic的edge上开始爬动。蚂蚁爬过一 : 条边的时间为1,它在任意一个角的时候,往其他三个方向去的概率都是1/3.问蚂蚁从 : 一个角爬到对角的平均时间是多少? : 我印象以前见到过这个题,应该是利用了Markov Chain的一些什么属性。当时只有5分 : 钟了,我考虑了一下,一下子实在想不出来,就撤了。
|
a**u 发帖数: 813 | 3 ....
aren't u supposed to be grading?
【在 h*****0 的大作中提到】 : 除非你经常搞概率,否则用“专业”办法很容易出错,在考试的情况下太紧张也弄不出 : 来的。 : 用直觉:对于起始角和目的地角,一共有三种角关系: : (a) 立方体对位,设平均时间为Ta : 此时不管蚂蚁往哪爬,经过时间1之后都将处于“距离目的地角为一个面对角线位”的 : 位置。见(b). : Ta = 1 + Tb : (b) 一个面对角线位,设平均时间为Tb : 此时蚂蚁和2/3的几率爬到邻位,见(c);有1/3的几率爬到立方体对位,见(a). : Tb = 1 + 2/3 * Tc + 1/3 * Ta
|
h*****0 发帖数: 4889 | 4 what r u doing here!?
do your homework!
【在 a**u 的大作中提到】 : .... : aren't u supposed to be grading?
|
n**********e 发帖数: 43 | 5 平均到达时间也是能用这样的加法原则么?不是很记得了。。。
【在 h*****0 的大作中提到】 : 除非你经常搞概率,否则用“专业”办法很容易出错,在考试的情况下太紧张也弄不出 : 来的。 : 用直觉:对于起始角和目的地角,一共有三种角关系: : (a) 立方体对位,设平均时间为Ta : 此时不管蚂蚁往哪爬,经过时间1之后都将处于“距离目的地角为一个面对角线位”的 : 位置。见(b). : Ta = 1 + Tb : (b) 一个面对角线位,设平均时间为Tb : 此时蚂蚁和2/3的几率爬到邻位,见(c);有1/3的几率爬到立方体对位,见(a). : Tb = 1 + 2/3 * Tc + 1/3 * Ta
|
h*****0 发帖数: 4889 | 6 所谓“平均时间”,就是数学期望:
ET = p_1 * T_1 + p_2 * T_2 + ...
对于第1种情况,可以分成子情况,有T_1 = p_{1,1} * T_{1,1} + p_{1,2} * T_{1,2}
+ ...
而T_{1,i} = 1 + T_i,所以...
基本上就从定义来的。同时利用了“前后无关性”,即当蚂蚁爬到某个点后,之后所有
事情跟之前的历史无关。这样只要数学期望存在,那么就可以这么计算(存在性显然…
…)
【在 n**********e 的大作中提到】 : 平均到达时间也是能用这样的加法原则么?不是很记得了。。。
|
F*****o 发帖数: 1261 | 7 包括向回爬的概率吗?
【在 r********n 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: dclocation (dclocation), 信区: JobHunting : 标 题: 碰到一道题 : 发信站: BBS 未名空间站 (Sat Apr 10 11:23:26 2010, 美东) : 一个unit cubic,一只蚂蚁在一个角,准备在这个cubic的edge上开始爬动。蚂蚁爬过一 : 条边的时间为1,它在任意一个角的时候,往其他三个方向去的概率都是1/3.问蚂蚁从 : 一个角爬到对角的平均时间是多少? : 我印象以前见到过这个题,应该是利用了Markov Chain的一些什么属性。当时只有5分 : 钟了,我考虑了一下,一下子实在想不出来,就撤了。
|
c****t 发帖数: 19049 | 8 此题无解或说“平均时间为无穷大” (没有物理意义) 因为此蚂蚁有 1/3 可能性在
任意偶数步时反回出发点 |
h*****0 发帖数: 4889 | 9 这个显然违反常识
【在 c****t 的大作中提到】 : 此题无解或说“平均时间为无穷大” (没有物理意义) 因为此蚂蚁有 1/3 可能性在 : 任意偶数步时反回出发点
|
y*****i 发帖数: 727 | 10 无穷大可以发生,但是概率为0。所以平均时间还是有限的。
【在 c****t 的大作中提到】 : 此题无解或说“平均时间为无穷大” (没有物理意义) 因为此蚂蚁有 1/3 可能性在 : 任意偶数步时反回出发点
|
|
|
c*****a 发帖数: 38 | 11 那如果蚂蚁从任意角出发,要爬回出发点,平均时间多少?还能用2楼的方法吗? |
h*****0 发帖数: 4889 | 12 那不很显然是Tc + 1 = 8嘛
【在 c*****a 的大作中提到】 : 那如果蚂蚁从任意角出发,要爬回出发点,平均时间多少?还能用2楼的方法吗?
|
h******7 发帖数: 980 | 13 握手,一样的方法,一样的答案。
【在 h*****0 的大作中提到】 : 除非你经常搞概率,否则用“专业”办法很容易出错,在考试的情况下太紧张也弄不出 : 来的。 : 用直觉:对于起始角和目的地角,一共有三种角关系: : (a) 立方体对位,设平均时间为Ta : 此时不管蚂蚁往哪爬,经过时间1之后都将处于“距离目的地角为一个面对角线位”的 : 位置。见(b). : Ta = 1 + Tb : (b) 一个面对角线位,设平均时间为Tb : 此时蚂蚁和2/3的几率爬到邻位,见(c);有1/3的几率爬到立方体对位,见(a). : Tb = 1 + 2/3 * Tc + 1/3 * Ta
|
r********n 发帖数: 6979 | 14 【 以下文字转载自 JobHunting 讨论区 】
发信人: dclocation (dclocation), 信区: JobHunting
标 题: 碰到一道题
发信站: BBS 未名空间站 (Sat Apr 10 11:23:26 2010, 美东)
一个unit cubic,一只蚂蚁在一个角,准备在这个cubic的edge上开始爬动。蚂蚁爬过一
条边的时间为1,它在任意一个角的时候,往其他三个方向去的概率都是1/3.问蚂蚁从
一个角爬到对角的平均时间是多少?
我印象以前见到过这个题,应该是利用了Markov Chain的一些什么属性。当时只有5分
钟了,我考虑了一下,一下子实在想不出来,就撤了。 |
h*****0 发帖数: 4889 | 15 除非你经常搞概率,否则用“专业”办法很容易出错,在考试的情况下太紧张也弄不出
来的。
用直觉:对于起始角和目的地角,一共有三种角关系:
(a) 立方体对位,设平均时间为Ta
此时不管蚂蚁往哪爬,经过时间1之后都将处于“距离目的地角为一个面对角线位”的
位置。见(b).
Ta = 1 + Tb
(b) 一个面对角线位,设平均时间为Tb
此时蚂蚁和2/3的几率爬到邻位,见(c);有1/3的几率爬到立方体对位,见(a).
Tb = 1 + 2/3 * Tc + 1/3 * Ta
(c) 邻位,设平均时间为Tc
此时有1/3几率直接爬到目的地;有2/3几率爬到一个面对角线位,见(b)
Tc = 1 + 2/3 * Tb
这样,三个方程,三个未知数。可解出:
Ta = 10
Tb = 9
Tc = 7
【在 r********n 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: dclocation (dclocation), 信区: JobHunting : 标 题: 碰到一道题 : 发信站: BBS 未名空间站 (Sat Apr 10 11:23:26 2010, 美东) : 一个unit cubic,一只蚂蚁在一个角,准备在这个cubic的edge上开始爬动。蚂蚁爬过一 : 条边的时间为1,它在任意一个角的时候,往其他三个方向去的概率都是1/3.问蚂蚁从 : 一个角爬到对角的平均时间是多少? : 我印象以前见到过这个题,应该是利用了Markov Chain的一些什么属性。当时只有5分 : 钟了,我考虑了一下,一下子实在想不出来,就撤了。
|
a**u 发帖数: 813 | 16 ....
aren't u supposed to be grading?
【在 h*****0 的大作中提到】 : 除非你经常搞概率,否则用“专业”办法很容易出错,在考试的情况下太紧张也弄不出 : 来的。 : 用直觉:对于起始角和目的地角,一共有三种角关系: : (a) 立方体对位,设平均时间为Ta : 此时不管蚂蚁往哪爬,经过时间1之后都将处于“距离目的地角为一个面对角线位”的 : 位置。见(b). : Ta = 1 + Tb : (b) 一个面对角线位,设平均时间为Tb : 此时蚂蚁和2/3的几率爬到邻位,见(c);有1/3的几率爬到立方体对位,见(a). : Tb = 1 + 2/3 * Tc + 1/3 * Ta
|
h*****0 发帖数: 4889 | 17 what r u doing here!?
do your homework!
【在 a**u 的大作中提到】 : .... : aren't u supposed to be grading?
|
n**********e 发帖数: 43 | 18 平均到达时间也是能用这样的加法原则么?不是很记得了。。。
【在 h*****0 的大作中提到】 : 除非你经常搞概率,否则用“专业”办法很容易出错,在考试的情况下太紧张也弄不出 : 来的。 : 用直觉:对于起始角和目的地角,一共有三种角关系: : (a) 立方体对位,设平均时间为Ta : 此时不管蚂蚁往哪爬,经过时间1之后都将处于“距离目的地角为一个面对角线位”的 : 位置。见(b). : Ta = 1 + Tb : (b) 一个面对角线位,设平均时间为Tb : 此时蚂蚁和2/3的几率爬到邻位,见(c);有1/3的几率爬到立方体对位,见(a). : Tb = 1 + 2/3 * Tc + 1/3 * Ta
|
h*****0 发帖数: 4889 | 19 所谓“平均时间”,就是数学期望:
ET = p_1 * T_1 + p_2 * T_2 + ...
对于第1种情况,可以分成子情况,有T_1 = p_{1,1} * T_{1,1} + p_{1,2} * T_{1,2}
+ ...
而T_{1,i} = 1 + T_i,所以...
基本上就从定义来的。同时利用了“前后无关性”,即当蚂蚁爬到某个点后,之后所有
事情跟之前的历史无关。这样只要数学期望存在,那么就可以这么计算(存在性显然…
…)
【在 n**********e 的大作中提到】 : 平均到达时间也是能用这样的加法原则么?不是很记得了。。。
|
F*****o 发帖数: 1261 | 20 包括向回爬的概率吗?
【在 r********n 的大作中提到】 : 【 以下文字转载自 JobHunting 讨论区 】 : 发信人: dclocation (dclocation), 信区: JobHunting : 标 题: 碰到一道题 : 发信站: BBS 未名空间站 (Sat Apr 10 11:23:26 2010, 美东) : 一个unit cubic,一只蚂蚁在一个角,准备在这个cubic的edge上开始爬动。蚂蚁爬过一 : 条边的时间为1,它在任意一个角的时候,往其他三个方向去的概率都是1/3.问蚂蚁从 : 一个角爬到对角的平均时间是多少? : 我印象以前见到过这个题,应该是利用了Markov Chain的一些什么属性。当时只有5分 : 钟了,我考虑了一下,一下子实在想不出来,就撤了。
|
|
|
c****t 发帖数: 19049 | 21 此题无解或说“平均时间为无穷大” (没有物理意义) 因为此蚂蚁有 1/3 可能性在
任意偶数步时反回出发点 |
h*****0 发帖数: 4889 | 22 这个显然违反常识
【在 c****t 的大作中提到】 : 此题无解或说“平均时间为无穷大” (没有物理意义) 因为此蚂蚁有 1/3 可能性在 : 任意偶数步时反回出发点
|
y*****i 发帖数: 727 | 23 无穷大可以发生,但是概率为0。所以平均时间还是有限的。
【在 c****t 的大作中提到】 : 此题无解或说“平均时间为无穷大” (没有物理意义) 因为此蚂蚁有 1/3 可能性在 : 任意偶数步时反回出发点
|
w********e 发帖数: 8594 | |