发信人: wty (~风儿*你是天上最远的那颗星星), 信区: BrainTeaser
标 题: 一个老题：醉汉过桥
发信站: BBS 未名空间站 (Thu Nov 27 10:01:09 2008)

一个老题：醉汉过桥
说一个醉汗初始在一条１００米长的桥上的第１７米位置。然后以0.5的概率随机往前
，或者往后走,每一秒走一米。问，平均需要多少秒他才能走完这座桥。
经典老题，不记得解法了。哪位帮忙解一下，或者给个连接？

--
※ 修改:·wty 於 Nov 27 10:41:31 2008 修改本文·[FROM: 134.58.]

发信人: pcasnik (pcasnik), 信区: BrainTeaser
标 题: Re: 一个老题：醉汉过桥
发信站: BBS 未名空间站 (Wed Dec 3 15:36:11 2008)

presumably, as long as he gets to one end of the bridge, it is considered that he has walked over the bridge?

then it is a typical random-walk with two barriers. if you know optional stopping theorem, the easiest way to get the answer is to construct the following martingale:

x(t)*[x(t)-100]-t.

note x(0)=17, easy to get the average time to reach either end of the bridge is 17*83=1411 seconds.

for reference, try google "gambler's ruin".
--
※ 修改:·pcasnik 於 Dec 3 15:37:59 2008 修改本文·[FROM: 75.34.]