不动点方差：Var

Fixed Point Variance

专题: Probability / 概率
难度: L6
来源: QuantQuestion

题目详情

对集合 $(1,2,\dots,1000)$ 取一个均匀随机置换。

令 $Y$ 为不动点（fixed points）个数， $X$ 为非不动点个数。

求 $\mathrm{Var}(Y-X)$ 。

You have a uniformly random permutation of $(1, 2, \dots, 1000)$ . Let $X$ be the number of non-fixed points and $Y$ be the number of fixed points. Compute $\text{Var}(Y - X)$ .

解析

有恒等式 $X+Y=1000$ ，因此

Y-X=Y-(1000-Y)=2Y-1000.

于是

\mathrm{Var}(Y-X)=\mathrm{Var}(2Y-1000)=4\,\mathrm{Var}(Y).

对随机置换大小为 $n$ 的不动点数 $Y$ ，有 $\mathrm{Var}(Y)=1$ （对任意 $n\ge 2$ 都成立）。

因此

\mathrm{Var}(Y-X)=4\cdot 1=\boxed{4}.