求证二元链中P(s₁|sᵢ)等于不匹配数为偶数的概率，求思路

我来给你拆解下这个问题的内在逻辑，其实核心是把条件概率和路径里的“不匹配次数奇偶性”对应起来，这里有几个关键的切入点，帮你理清思路：

• 从贝叶斯公式切入，拆解条件概率
  先写出$P(s_1 \mid s_i)$的表达式，根据贝叶斯定理：
  $$P(s_1 = x \mid s_i = y) = \frac{P(s_i = y \mid s_1 = x)P(s_1 = x)}{P(s_i = y)}$$
  因为初始$P(s_1=1)=P(s_1=-1)=\frac{1}{2}$，分母$P(s_i=y)$可以用全概率公式展开为$\frac{1}{2}P(s_i=y \mid s_1=1) + \frac{1}{2}P(s_i=y \mid s_1=-1)$。你会发现，当$x=y$时，分子就是$\frac{1}{2}P(s_i=y \mid s_1=y)$，而我们要证的就是这个值等于路径中不匹配次数为偶数的概率。

• 把路径状态和不匹配次数绑定
  从$s_1$到$s_i$的路径中，每一次$s_j \neq s_{j-1}$就是一次“翻转”（不匹配）。假设翻转次数为$k$：

  • 如果$k$是偶数，那么最终的$s_i$必然等于$s_1$（偶数次翻转会回到初始状态）；
  • 如果$k$是奇数，那么$s_i$必然不等于$s_1$（奇数次翻转会切换状态）。
    反过来想，给定$s_i=y$，$s_1=y$的概率，其实就是所有能走到$s_i=y$的路径中，翻转次数为偶数的路径占比——这正好就是题目要你证明的结论。

• 用递推关系验证等价性
  你已经验证了$n=3$的情况，可以试试递推法推广到一般情况：

  1. 设$P_m = P(s_1 \mid s_m)$（也就是$s_1=s_m$的条件概率），$Q_m = 1-P_m$（$s_1 \neq s_m$的条件概率）。
  2. 找递推关系：走到$s_m$时，要么$s_m=s_{m-1}$（概率$q$），此时$s_1$和$s_m$的关系和$s_1$与$s_{m-1}$一致；要么$s_m \neq s_{m-1}$（概率$1-q$），此时关系反转。所以：
     $$P_m = qP_{m-1} + (1-q)(1-P_{m-1})$$
     初始条件$P_1=1$（$s_1$就是自己，不匹配次数为0，是偶数）。
  3. 再设$E_m$是从$s_1$到$s_m$路径中不匹配次数为偶数的概率，$O_m=1-E_m$是奇数次的概率。同样递推：
     $$E_m = qE_{m-1} + (1-q)O_{m-1}$$
     代入$O_{m-1}=1-E_{m-1}$后，你会发现这个式子和$P_m$的递推式完全一样，初始条件$E_1=1$也和$P_1$一致。所以$P_m=E_m$，结论得证。

内容的提问来源于stack exchange，提问作者Kees Til