交错序列的期望长度
设概率分布 \(D\) 连续。游戏开始时，首先生成 \(X_1 \sim D\)，在第 \(i \ (i \geq 2)\) 轮中生成独立的 \(X_i \sim D\)，然后：
- 若 \(i\) 为偶数，且 \(X_i < X_{i-1}\)，则游戏结束于第 \(i\) 轮；否则，继续第 \(i+1\) 轮。
- 若 \(i\) 为奇数，且 \(X_i > X_{i-1}\)，则游戏结束于第 \(i\) 轮；否则，继续第 \(i+1\) 轮。
求该游戏进行的轮数的数学期望。
解答
integration - Random Sequence of Alternating Increase/Decrease Numbers - Mathematics Stack Exchange
定义 排列 \(X_1, \dots, X_n\) 属于 \(n\) 元反交错排列，当且仅当 \(X_1 < X_2, X_2 > X_3, X_3 < X_4, \dots\)
定义 排列 \(X_1, \dots, X_n\) 属于 \(n\) 元交错排列，当且仅当 \(X_1 \geq X_2, X_2 \leq X_3, X_3 \geq X_4, \dots\)
定义 排列 \(X_1, \dots, X_n\) 是锯齿排列，当且仅当其为交错排列或反交错排列。
给定两两不同的 \(X_1, \dots, X_n\)，记可形成的长度为 \(n\) 的反交错排列的数目为 \(A_n\)，交错排列的数目数为 \(B_n\)，由对称性知 \(A_n = B_n\)。（Alternating Permutation or Euler zigzag numbers）
可见，题干所求为尽可能地构造反交错排列，直到结果不满足反交错排列时，第一条反交错排列的最终长度加上 \(1\)。设该游戏进行的轮数为 \(\gamma\)，下面推导出解题公式：
记
\[ X_j = \begin{cases} 1, & X_1, \dots, X_j 是反交错排列, \\ 0, & \text{otherwise}. \end{cases} \]
那么
\[ P(X_j = 1) = \frac{A_j}{j!}, \]
故
\[ E(X_j) = \frac{A_j}{j!}. \]
设在长度为 \(n\) 的序列\(X_1, \dots, X_n\)中，第一条反交错排列的最终长度为 \(Y_n\)，那么
\[ Y_n = \sum_{j=1}^{n}X_j, \]
且注意到 \(\lim_{n \to \infty} Y_n = \gamma - 1\)。故题干所求为
\[ E(\gamma) = \lim_{n \to \infty} \sum_{j=1}^{n} E(X_j) + 1 = \sum_{n=0}^{\infty} \frac{A_n}{n!}. \]
其中 \(A_1 = 1\)，为方便起见令 \(A_0 = 1\)。下面推导 \(A_n\) 的递推式。
考虑长度为 \(k\) 的反交错排列 \(u_k = X_1, \dots, X_k\)，长度为 \(n-k\) 的反交错排列 \(v_k = X_{k+1}, \dots, X_{n}\)。
- 当 \(k\) 为奇数时，\(u_k\) 的逆 \(\overline{u_k}= X_k, \dots, X_1\) 仍为反交错排列。构造长度为 \(n+1\) 的排列 \(v_{n+1} = \overline{u_k} X_{n+1} v_k\)，其中 \(X_{n+1} = \max_{1 \leq i \leq n + 1}(X_i)\)，可知 \(v_{n+1}\) 为某个反交错排列。
- 当 \(k\) 为偶数时，\(u_k\) 的逆 \(\overline{u_k}= X_k, \dots, X_1\) 为交错排列。构造长度为 \(n+1\) 的排列 \(v_{n+1} = \overline{u_k} X_{n+1} v_k\)，其中 \(X_{n+1} = \max_{1 \leq i \leq n + 1}(X_i)\)，可知 \(v_{n+1}\) 为某个交错排列。
可以判断，任何长度为 \(n+1 \ (n \geq 1)\) 的锯齿排列均可由两个反交错排列如上构造。递推式为
\[ A_{n+1} + B_{n+1} = 2A_{n+1} = \sum_{k=0}^{n} \binom n k A_{k} A_{n-k}, n \geq 1. \]
请注意，上式不适用于 \(n=0\) 的情况。记 \(A_n\) 的指数型生成函数
\[ G(x) = \sum_{n=0}^{\infty} A_n \frac{x^n}{n!}, \]
则 \(G(0) = A_0 = 1\)，\(G(1) = E(\gamma)\)。下面推导：
\[ \begin{aligned} 2A_{n+1} &= \sum_{k=0}^{n} \binom n k A_{k} A_{n-k}, \\ \rightarrow 2A_{n+1} &= \sum_{k=0}^{n} \frac{n!}{k!(n-k)!} A_{k} A_{n-k}, \\ \rightarrow 2A_{n+1} \frac{n+1}{(n+1)!} &= \sum_{k=0}^{n} \frac{A_{k}}{k!} \frac{A_{n-k}}{(n-k)!}, \\ \end{aligned} \\ \rightarrow 2 \sum_{n=1}^{\infty} \frac{A_{n+1}}{(n+1)!} (n+1)x^n = \sum_{n=1}^{\infty} \left(\sum_{k=0}^{n} \frac{A_{k}}{k!} \frac{A_{n-k}}{(n-k)!} \right) x^n \\ \rightarrow 2 \sum_{n=0}^{\infty} \frac{A_{n+1}}{(n+1)!} (n+1)x^n - 2A_1 = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} \frac{A_{k}}{k!} \frac{A_{n-k}}{(n-k)!} \right) x^n - \frac{A_0}{0!}\frac{A_0}{0!}\\ \rightarrow 2 \sum_{n=0}^{\infty} \frac{A_{n+1}}{(n+1)!} (n+1)x^n = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} \frac{A_{k}}{k!} \frac{A_{n-k}}{(n-k)!} \right) x^n +1\\ \]
注意到
\[ G'(x) = \sum_{n=0}^{\infty} A_{n+1} (n+1) \frac{x^n}{(n+1)!}, \\ (G(x))^2 = \sum_{n=0}^{\infty} \left(\sum_{k=0}^{n} \frac{A_{k}}{k!} \frac{A_{n-k}}{(n-k)!} \right) x^n, \]
故
\[ 2G'(x) = (G(x))^2 + 1. \]
解微分方程 \(2\frac{\mathrm dy}{\mathrm dx} = y^2 + 1\)，分离变量得
\[ \frac{\mathrm dx}{2} = \frac{\mathrm d y}{y^2 + 1}, \]
两边积分得
\[ y = \tan\left(\frac{1}{2}x + C\right). \]
代入初值条件 \(y(0) = 1\) 得
\[ y = \tan\left(\frac{1}{2}x + \frac{\pi}{4} \right). \]
故
\[ E(\gamma) = y(1) = \tan\left(\frac{1}{2} + \frac{\pi}{4}\right) \approx 3.41. \]
注：还可继续用三角公式化简得到 \(y = \tan x + \sec x\)。故 \(E(\gamma) = \tan 1 + \sec 1\)。
附：tan x 级数的通项
由上知
\[ \tan x + \sec x = \sum_{n=0}^{\infty} A_n \frac{x^n}{n!}. \]
故
\[ \tan x = A_1 x + A_3 \frac{x^3}{3!} + A_5 \frac{x^5}{5!} + \dots, \\ \sec x = \frac{1}{\cos x } = A_0 + A_2 \frac{x^2}{2!} + A_4 \frac{x^4}{4!} + \dots. \]