关于期望的疑惑
查看原帖
关于期望的疑惑
520544
Phrvth楼主2023/7/18 13:04

根据第一篇题解,由期望的定义来说:

Ex−>x+1=1dux+1×1+1dux+1×∑(x,y)∈E(Ey−>x+1+1)E_{x->x+1}=\frac{1}{du_x+1}\times 1+ \frac{1}{du_x+1} \times \sum_{(x,y)\in E} (E_{y->x+1} + 1)

帮忙看下我的理解有没有问题

首先有 1dux+1\frac{1}{du_x+1} 的概率上一步台阶,那这样步数为1

其次,后半段相当于把 1dux+1\frac{1}{du_x+1} 提出来,每条返祖边都需要计算

但这里的期望步数为什么是 Ey−>x+1+1E_{y->x+1} + 1

这里枚举的返祖边是连向 xx 和 yy 的

但是这里是 y−>x+1y->x+1

不应该是 y−>xy->x 然后再加1吗?

这里不理解,请大佬帮下忙

2023/7/18 13:04
加载中...