与停时有关的概率问题

· · 个人记录

给定一个起始状态和若干终止状态或终止事件，求首次变为终止状态之一（或触发终止事件之一）的期望时间

多个状态或事件

给定状态形式相同

这里的形式相同要求状态满足如下性质：令状态集合为 \Omega，存在常数 c ，使得 \forall S,T\in\Omega\land S\neq T，从状态 S 开始，首次变为状态 T 所需的期望时间为 c。

翻译成人话就是从每一个终止状态变为其他任意一个终止状态要花的期望时间是一样的。

对于此类问题，可以将首个状态的期望时间做一个转化，转化求解为每个状态的期望时间和上述常数 c。

令 E_i 表示从起始状态起，首次变为第 i 个终止状态的期望时间。令 p_i,e_i 分别表示从起始状态起，首个变为的终止状态是第 i 个终止状态的概率和期望时间。（p,e 数组并不用求出，只是定义一下方便计算）。

不难得到

ans=\sum\limits_ip_ie_i E_i=\sum\limits_jp_j(e_j+c[j\neq i])=ans+(1-p_i)c \therefore \sum\limits_iE_i=n\cdot ans+(n-1)c

因此 ans=\dfrac{\sum\limits_iE_i-(n-1)c}{n}

所以只需要求出 E 数组和 c 即可得到答案

给定状态或事件没有什么性质

如果求的是首次发生所有终止事件的期望时间，可以考虑 min-max 容斥，即在“首次发生任意一个终止事件”和“首次发生过每一个终止事件”两者间相互转化。

\max(S)=\sum\limits_{T\subset S,T\neq \emptyset}(-1)^{|T|+1}\min(T)

例：[PKUWC2018]随机游走

当未触发停时时事件发生顺序不影响结果的情况下，可以把答案简单容斥成未触发停时的贡献和。

单个状态或事件

构造鞅来计算

鞅的简单介绍

考虑对于状态构造一个势能函数 \Phi(S)，使其满足转移状态时有 \sum\limits_T\Phi(T)p_{S\rightarrow T}=\Phi(S)+1

因此 f_n(S)=\Phi(S)-n 就构成了一个鞅，令时停函数为 \tau(X) 表示能时停的操作序列 X 时停的时间，X_i 表示 X 的前 i 次操作构成的操作序列，初始状态为 S_0，终止状态为 T，根据鞅的时停定理（或者直观理解），有 \sum\limits_Xf_{\tau(X)}(X_{\tau(X)})p_X=f_0(S_0)。

即 \Phi(T)-E[\tau(X)]=\sum\limits_X(\Phi(T)-\tau(X))p_X=\Phi(S)

\therefore E[\tau(X)]=\Phi(T)-\Phi(S)

例：CF1025G Company Acquisitions

但事实上鞅的构造有时候非常具有启发性。

例如[CTSC2006]歌唱王国，题目大意为每次随机生成一个字符，问给定字符串第一次完整出现的期望时间。

设给定字符串长度为 n，字符集大小为 m

我们假设你开了一个赌场，每分钟都会随机一个字符用于赌。赌钱的规则很简单，赌徒会猜一个字符，假如这分钟随到了这个字符，你就得给他 m 倍的钱，否则他输光光。因为每分钟的字符都是随机的，所以在期望上你既不会亏也不会赚。

现在，每一分钟都会有一名赌徒来到你的赌场，他来的时候会携带一块钱。赌徒第一次会押给定字符串的第一个字符，第二次会押给定字符串的第二个字符，以此类推。并且赌徒很勇，他每次都会 all in，也就是说他每次都会赌上上一分钟赢到的全部钱，并且只要输一次就会把手上的钱输光。

每一轮赌博对你而言的期望收益都是 0，因此你的收益构成一个鞅。并且，首次完整出现给定字符串的时间构成一个停时。考虑停时状态下你的总收入和总支出，令停时时刻为 t，则总共有 t 名赌徒把自带的一块钱押进了你的赌场，并且赢到钱的只有当前刚好赌了一段 border 的那些赌徒。由于你的收益是一个鞅，所以期望时停时间，即你的期望收入，就等于的你的总支出。

每一次操作相同的单个状态判定

令 ans_S 表示终止状态为 S 时的答案，考虑枚举第一次操作的所有可能，对于 S\neq 0 有 ans_S=1+\sum\limits_ip_ians_{S\oplus i}，其中 S\oplus i 表示把从状态 i 变为状态 S 的过程操作在状态 0 上得到的最终状态。

可以考虑根据上述式子，建立一个生成函数/集合幂级数的简单等式，然后进行数学推导。

例：[ZJOI2019]开关

缩小状态集合暴力消元

例：[STR #25]第一题