一个长为m的相互独立的二进制序列,包含偶数个1的概率是其中第L个比特是1的概率是PL（L是下标,可变,L=1...m),那么这个那个序列中包含偶数个1的概率是

Question

一个长为m的相互独立的二进制序列,包含偶数个1的概率是
其中第L个比特是1的概率是PL（L是下标,可变,L=1...m),那么这个那个序列中包含偶数个1的概率是

Answer 1

用动态规划算法吧.
设 S(L) 为前 L 个比特中有偶数个 1 的概率.
初始值：S(1) = P(1)
递推公式：S(L) = (1 - S(L-1)) * P(L) + S(L-1) * (1 - P(L))
解释一下递推公式：
前 L 个比特中有偶数个 1,分为2种情形：
（1）前 L-1 个比特中有奇数个 1,第 L 个比特为 1.
（2）前 L-1 个比特中有偶数个 1,第 L 个比特为 0.
第（1）种情形的概率是：(1 - S(L-1)) * P(L)
第（2）种情形的概率是：S(L-1) * (1 - P(L))
两种情形加起来就是递推公式.