a**********n
发帖数: 59 | 1 n个人围坐在圆桌周围，第一个人头戴着帽子，并开始随机向左或向右传递这顶帽子，
拿到帽子的人也同样向左或向右传递帽子，问帽子回到第一个人的传递次数的期望？
这道题貌似应该转化成向右走n步或向左走n步或回到原点的random walk，但不知道接
下来怎么求这个事件的期望步数，望不吝赐教。 |
f*******y
发帖数: 267 | 2 induction
brutal guess： n
【在 a**********n 的大作中提到】
: n个人围坐在圆桌周围，第一个人头戴着帽子，并开始随机向左或向右传递这顶帽子，
: 拿到帽子的人也同样向左或向右传递帽子，问帽子回到第一个人的传递次数的期望？
: 这道题貌似应该转化成向右走n步或向左走n步或回到原点的random walk，但不知道接
: 下来怎么求这个事件的期望步数，望不吝赐教。
|
y*****9
发帖数: 149 | 3 第一次帽子不是往左走就是往右走。然后问题就变成往上n-1，或者往下1的gambler's
ruin problem。
Expected stopping is (n-1), see:
http://www.ifp.illinois.edu/~sgorant2/gambler.html
所以答案是1+n-1 = n。
flymelody大牛啊，直觉那么准。。。 |
b********t
发帖数: 5261 | |
y*****9
发帖数: 149 | 5 那显然Babyrabbit更牛。。。
【在 b********t 的大作中提到】
: 哈哈，这个题我上个月刚在这问过
|
b********t
发帖数: 5261 | 6 土人，没答上来才问呗，牛人都会-_-
【在 y*****9 的大作中提到】
: 那显然Babyrabbit更牛。。。
|
f***r
发帖数: 1126 | 7 假定帽子往左的概率是p，往右的概率是1-p。很容易发现题目中需求的期望与p是无关
的。取p=1，马上的到期望=n。 |
