关于“离散、有限、时齐、可遍历的随机过程”的一个问题

BeerRabbit · 发表于 2014-6-30 14:14:41

您需要登录才可以下载或查看，没有账号？欢迎注册

×

对于一个给定的“离散、有限、时齐、可遍历的随机过程”，对于给定的初始状态，如何计算：恰好完成全状态遍历所需的游走次数的期望？

BeerRabbit · 发表于 2014-7-4 15:06:37

发布数日也无人问津…………好失落。

举个简单的例子，一个4×4的棋盘，现在从某一个固定的格子出发等概率随机移动到临近的格子，问第一次走遍全部16个格子的时候，已经走过的步数的期望是多少？

BeerRabbit · 发表于 2014-7-4 18:11:10

更通俗的说法：每个格子一块钱，等概率随机移动到相邻格子内，若有钱则拿走（若没钱，那肯定是已经拿过了），求拿走所有15块钱（第一个格子有没有都无所谓），需要走多少步？

mathe · 发表于 2014-7-5 08:15:48

k个格子的棋盘根据各个格子是否走过以及当前人的位置有$2^k k$个状态。在k不太大时可动态规划计算出来。但是k太大了就不大好办了

BeerRabbit · 发表于 2014-7-5 08:39:06

昨天下午想到一个类似递归的思路，但是Latex语法捉急…………发图片不合适

BeerRabbit · 发表于 2014-7-9 22:08:24

发一个解决方案（附件形式）

账号		自动登录	找回密码
密码			欢迎注册

[讨论] 关于“离散、有限、时齐、可遍历的随机过程”的一个问题