从(0,21)出发，每次水平或垂直移动一单位，不会到 Y＜0 ，求到 Y=24 移动次数的期望值

luyuanhong

这是台湾网友 YAG 发表在“陆老师的《数学中国》园地”的一个帖子，

欢迎大家一起来想想如何解答：

有一青蛙位於(0，21)，該青蛙每次移動皆隨意地選擇平行X軸或Y軸移動一單位。

而當它移動至Y=0時，它可能隨意地向左、向右、或向上移動(機率相等)，

即它不會移動到Y<0的地方。當它移動到Y=24這條直線後，即停止移動。

求他的移動次數期望值?

Ysu2008

题目：有一青蛙位于(0，21)，该青蛙每次移动皆随意地选择平行X轴或Y轴移动一单位。 而当它移动至Y=0时，它可能随意地向左、向右、或向上移动(机率相等)， 即它不会移动到Y<0的地方。当它移动到Y=24这条直线后，即停止移动。 求移动次数期望值。

解：用马氏链模型求解。将青蛙所在的Y轴坐标 [0，24] 看作 25 个状态 . 根据题意，当 Y>0 时，状态 N 有 1/4 概率上移至 N+1 , 1/4 概率下移至 N-1 , 1/2 概率留在 N；状态 0 有 1/3 概率上移至 1，2/3 概率留在 0 ，可得如下状态转移概率矩阵：
R=

（注意矩阵没有包含终止状态 24，空白处为 0）

青蛙移动次数期望 = 马氏链终止前的平均持续时间

A=(I-R)^(-1)

上式 I 为单位阵，矩阵 A 的行向量元素和 = 对应状态的平均持续时间。

用计算机算得状态 0 到 23 的平均持续时间依次为：1176,1173,1166,1155,1140,1121,1098,1071,1040,1005,966,923,876,825,770,711,648,581,510,435,356,273,186,95


（X为状态，Y值为平均持续时间）

青蛙从状态 21 跳至 24 的移动次数期望 = 273

Ysu2008

编程模拟的输出（数值非常接近理论值）：

Ysu2008

原题显然不会要求手算 24 阶矩阵，应当有巧妙的解法。

luyuanhong

谢谢楼上 Ysu2008 的解答。我已将此帖转贴到“陆老师的《数学中国》园地”。

luyuanhong