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

发一个解决方案（附件形式）
页: [1]
查看完整版本: 关于“离散、有限、时齐、可遍历的随机过程”的一个问题