返回题库

不动点方差：Var

Fixed Point Variance

专题
Probability / 概率
难度
L6

题目详情

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

令 YY 为不动点（fixed points）个数，XX 为非不动点个数。

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

英文原题

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

解析

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

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

于是

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

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

因此

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

英文解析

has the identity X+Y=1000X+Y=1000, so

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

as a result

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

There are Var(Y)=1\mathrm{Var}(Y)=1 fixed points for a random displacement of nn (valid for any n≥2n\ge 2).

Therefore,

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