期待値の線形性と数え上げ

同義語：期待値の線形性linearity of expectation

概要

高校での出発点：分布を作らずに期待値を求める

公平な硬貨を $n$ 回投げたとき、表の回数 $X$ の期待値を求める。高校の教科書どおりに進めるなら、まず分布 $P(X=k)=\binom nk\frac1{2^n}$（$k=0,1,\dots,n$）を作り、
$$ E[X]=\sum_{k=0}^nk\binom nk\frac1{2^n} $$
を計算する。$k\binom nk=n\binom{n-1}{k-1}$（$k\ge1$）を使うと、和は $\frac n{2^n}\sum_{k=1}^n\binom{n-1}{k-1}=\frac n{2^n}\cdot2^{n-1}=\frac n2$ になる。
同じ答えは、分布を作らずにも得られる。$i$ 回目が表なら $1$、裏なら $0$ となる量を $X_i$ とすると $X=X_1+\cdots+X_n$ であり、各 $X_i$ の期待値は $1\cdot\frac12+0\cdot\frac12=\frac12$ なので、$E[X]=\frac12+\cdots+\frac12=\frac n2$ である。
2 つめの計算が「たまたま楽だった」のではないことは、次の例で分かる。
帽子の問題。 $4$ 人が帽子を預け、帰りに無作為に 1 つずつ返される。自分の帽子が戻る人数を $F$ とする。返し方 $4!=24$ 通りを全部調べると、戻る人数が $0,1,2,3,4$ 人の返し方はそれぞれ $9,8,6,0,1$ 通りなので、
$$ E[F]=\frac{0\cdot9+1\cdot8+2\cdot6+3\cdot0+4\cdot1}{24}=\frac{24}{24}=1 $$
である。人数が $10$ 人なら返し方は $10!=3628800$ 通りあり、分布を作るのは大変である。ところが、$i$ 番目の人の帽子が戻れば $1$、戻らなければ $0$ となる量 $F_i$ を考えると、$F=F_1+\cdots+F_n$ であり、$i$ 番目の人の帽子が戻る返し方は残り $n-1$ 個の並べ方で $(n-1)!$ 通りなので、$E[F_i]=\frac{(n-1)!}{n!}=\frac1n$ である。和の期待値が期待値の和になるなら、何人であっても $E[F]=n\cdot\frac1n=1$ である。
ここで 1 つ気になることがある。硬貨の例では $X_1,\dots,X_n$ は互いに独立（独立性(確率論)）だった。帽子の例の $F_1,\dots,F_n$ は独立ではない（1 番目と 2 番目の人の帽子がともに戻る確率は $\frac{(n-2)!}{n!}=\frac1{n(n-1)}$ で、$\frac1n\cdot\frac1n$ と等しくない）。それでも「和の期待値は期待値の和」は正しいのか。本記事では、これが独立性とは無関係に成り立つこと、その理由が「和の順序を入れ替えてよい」という数え上げの原理そのものであることを示し、この見方から包除原理と Burnside の補題を導く。

取り出すべき構造

本記事では標本空間が有限の場合だけを扱う。空でない有限集合 $\Omega$ と、$p(\omega)\ge0$、$\sum_{\omega\in\Omega}p(\omega)=1$ を満たす関数 $p\colon\Omega\to[0,1]$ の組 $(\Omega,p)$ を有限確率空間といい、部分集合 $A\subset\Omega$（事象）の確率を $P(A):=\sum_{\omega\in A}p(\omega)$ と定める。関数 $X\colon\Omega\to\mathbb{R}$ を確率変数といい、その期待値を
$$ E[X]:=\sum_{\omega\in\Omega}X(\omega)\,p(\omega) $$
と定める。
高校で習う期待値の式 $\sum_xx\,P(X=x)$ は、この和を $X$ の値 $x$ ごとにまとめ直したものである。実際、$\Omega$ を $X$ の値によって互いに交わらない部分 $\{X=x\}:=\{\omega\mid X(\omega)=x\}$ に分けると、$\{X=x\}$ の上では $X(\omega)=x$ なので
$$ \sum_{\omega\in\Omega}X(\omega)p(\omega)=\sum_x\sum_{\omega\in\{X=x\}}x\,p(\omega)=\sum_xx\,P(X=x) $$
となる。2 つの式の違いは「$\omega$ ごとに足すか、値ごとにまとめてから足すか」だけである。本記事の技法はすべて、$\omega$ ごとに足す左辺の形から出てくる。
事象 $A$ の指示関数 $1_A\colon\Omega\to\{0,1\}$ を、$\omega\in A$ なら $1$、そうでなければ $0$ と定める。定義から $E[1_A]=\sum_{\omega\in A}p(\omega)=P(A)$ である。また、$1_{A\cap B}=1_A1_B$、$1_{\Omega\setminus A}=1-1_A$ が各 $\omega$ ごとに成り立つ。

起こる事象の個数

有限確率空間 $(\Omega,p)$ の事象 $A_1,\dots,A_m$ について、確率変数
$$ N:=1_{A_1}+1_{A_2}+\cdots+1_{A_m} $$
を、$A_1,\dots,A_m$ のうち起こる事象の個数という。$N(\omega)$ は $\omega\in A_i$ となる $i$ の個数である。

表の回数は「$i$ 回目が表」という事象 $A_i$ たちのうち起こるものの個数であり、帽子が戻る人数は「$i$ 番目の人の帽子が戻る」という事象たちのうち起こるものの個数である。数えたい量をこの形に書き直すことが、本記事の技法の出発点である。

主定理：期待値の線形性

期待値の線形性

有限確率空間 $(\Omega,p)$ 上の確率変数 $X,Y$ と実数 $a,b$ について
$$ E[aX+bY]=aE[X]+bE[Y] $$
が成り立つ。$X$ と $Y$ が独立であることは仮定しない。帰納的に、確率変数 $X_1,\dots,X_m$ について $E[X_1+\cdots+X_m]=E[X_1]+\cdots+E[X_m]$ である。

根元事象ごとに足す

確率変数の和や定数倍は $\omega$ ごとに定める：$(aX+bY)(\omega)=aX(\omega)+bY(\omega)$ である。有限和は項ごとに分けられるので
$$ E[aX+bY]=\sum_{\omega}\bigl(aX(\omega)+bY(\omega)\bigr)p(\omega)=a\sum_\omega X(\omega)p(\omega)+b\sum_\omega Y(\omega)p(\omega)=aE[X]+bE[Y] $$
である。$m$ 個の場合は $m$ についての帰納法で従う。$\square$

証明に独立性がまったく現れないことに注意する。$X$ と $Y$ の関係は $\omega$ を通じて決まっているが、$\omega$ ごとに足している限り、その関係を知る必要はない。一方、値ごとにまとめる式 $\sum_zz\,P(X+Y=z)$ で計算しようとすると、$X+Y$ の分布が必要になり、それを求めるには一般に $X$ と $Y$ の同時分布が要る。線形性が「分布を作らずに期待値を求める」技法になるのはこのためである。

起こる事象の個数の期待値

事象 $A_1,\dots,A_m$ のうち起こるものの個数 $N$ について
$$ E[N]=P(A_1)+P(A_2)+\cdots+P(A_m) $$
である。

指示関数の期待値を足す

thm-loe-linearity と $E[1_{A_i}]=P(A_i)$ による。$\square$

すべての $\omega$ が同じ確率 $p(\omega)=1/|\Omega|$ をもつとき（一様な場合）、両辺に $|\Omega|$ を掛けると $\sum_{\omega}N(\omega)=\sum_i|A_i|$ となる。左辺は「$\omega$ ごとに、それが属する $A_i$ の個数を数えて足したもの」、右辺は「$i$ ごとに、$A_i$ に属する $\omega$ の個数を数えて足したもの」であり、どちらも組 $(\omega,i)$（$\omega\in A_i$）の総数である。これが二重数え上げである。

二重数え上げ

$S,T$ を有限集合、$R\subset S\times T$ を部分集合とする。$s\in S$ について $r(s):=|\{t\in T\mid(s,t)\in R\}|$、$t\in T$ について $c(t):=|\{s\in S\mid(s,t)\in R\}|$ とおくと
$$ \sum_{s\in S}r(s)=|R|=\sum_{t\in T}c(t) $$
である。

行ごとと列ごとに足す

$(s,t)\in R$ なら $1$、そうでなければ $0$ となる数 $a_{st}$ を並べた表を考える。$|R|=\sum_{s\in S}\sum_{t\in T}a_{st}$ であり、有限和は順序を入れ替えても変わらないので $=\sum_{t\in T}\sum_{s\in S}a_{st}$ である。内側の和はそれぞれ $r(s)$、$c(t)$ に等しい。$\square$

二重数え上げで二項係数の恒等式を示す方法は二項定理と組合せの恒等式で扱う。
一様な場合のcor-loe-indicator は、$S=\Omega$、$T=\{1,\dots,m\}$、$R=\{(\omega,i)\mid\omega\in A_i\}$ としたこの命題を $|\Omega|$ で割ったものである。一般の $p$ でも、重み $p(\omega)$ つきの表を行ごとと列ごとに足すという同じ原理である。
分散を求めるには 2 次の量が要る。これも組を数える形に直せる。

2 個ずつの組の個数

起こる事象の個数 $N=\sum_{i=1}^m1_{A_i}$ について
$$ E[N(N-1)]=\sum_{i\ne j}P(A_i\cap A_j) $$
である。ここで和は $i\ne j$ となる順序対 $(i,j)$ すべてにわたる。

積を展開する

各 $\omega$ で $N^2=\sum_i\sum_j1_{A_i}1_{A_j}$ であり、$1_{A_i}1_{A_i}=1_{A_i}$、$1_{A_i}1_{A_j}=1_{A_i\cap A_j}$ なので $N^2=N+\sum_{i\ne j}1_{A_i\cap A_j}$、すなわち $N(N-1)=\sum_{i\ne j}1_{A_i\cap A_j}$ が $\omega$ ごとに成り立つ。両辺の期待値をとり thm-loe-linearity を使う。$\square$

$N(N-1)$ は「起こった事象から、異なる 2 つを順序をつけて選ぶ選び方の数」である。分散は $V[N]=E[N^2]-E[N]^2=E[N(N-1)]+E[N]-E[N]^2$ で求まる。ここでも独立性は使っていないが、$P(A_i\cap A_j)$ という 2 つずつの同時確率は必要になる。
最後に、積について述べる。有限確率空間上の確率変数 $X,Y$ が独立であるとは、すべての実数 $x,y$ について $P(X=x,\,Y=y)=P(X=x)P(Y=y)$ が成り立つことをいう（$P(X=x,\,Y=y)$ は事象 $\{X=x\}\cap\{Y=y\}$ の確率）。

独立な確率変数の積の期待値

$X,Y$ が独立ならば $E[XY]=E[X]E[Y]$ である。

値の組ごとにまとめる

$\Omega$ を、$(X,Y)$ の値の組 $(x,y)$ ごとに互いに交わらない事象 $\{X=x\}\cap\{Y=y\}$ に分ける。その上で $XY=xy$ なので
$$ E[XY]=\sum_{x,y}xy\,P(X=x,\,Y=y)=\sum_{x,y}xy\,P(X=x)P(Y=y)=\Bigl(\sum_xx\,P(X=x)\Bigr)\Bigl(\sum_yy\,P(Y=y)\Bigr) $$
である（和は $X,Y$ のとる有限個の値にわたる）。2 つめの等号で独立性を使った。$\square$

和の期待値が $\omega$ ごとの計算だけで済むのに対し、積の期待値には $X,Y$ の同時分布が要り（$E[XY]=\sum_{x,y}xy\,P(X=x,\,Y=y)$）、それが積に分かれる（独立な）ときに $E[X]E[Y]$ になる。独立性は十分条件であって必要条件ではない（独立でなくても $E[XY]=E[X]E[Y]$ となる組はある。たとえば $X$ が $-1,0,1$ を確率 $\frac13$ ずつとり $Y=X^2$ とすると、$E[XY]=E[X^3]=0=E[X]E[Y]$ だが、$P(X=0,\,Y=0)=\frac13\ne\frac13\cdot\frac13=P(X=0)P(Y=0)$ なので独立ではない）。独立性を外すと積の公式が崩れることは、ex-loe-product-fails で示す。

高校の技法は特別な場合である

技法は次の 3 段階にまとめられる。

数えたい量を、起こる事象の個数 $N=\sum_i1_{A_i}$ の形に書く（def-loe-count）。
各 $P(A_i)$ を求める。多くの場合、対称性によって $i$ によらない。
cor-loe-indicator で足す。分散が要るなら prop-loe-second-moment で $P(A_i\cap A_j)$ を足す。
冒頭の 2 つの計算はこの手順そのものである。以下の例で、段階 2 が独立性なしにどう片付くかを見る。

二項分布の平均と分散

表の出る確率が $q$ の硬貨を独立に $n$ 回投げ、$A_i$ を「$i$ 回目が表」とする。表の回数 $N$ について $E[N]=nq$ である。さらに $i\ne j$ なら独立性から $P(A_i\cap A_j)=q^2$ なので、prop-loe-second-moment により $E[N(N-1)]=n(n-1)q^2$、したがって
$$ V[N]=n(n-1)q^2+nq-n^2q^2=nq(1-q) $$
である。高校では $k\binom nk=n\binom{n-1}{k-1}$ を 2 回使って同じ結果を出すが、上の計算では独立性を $P(A_i\cap A_j)$ の 1 か所でしか使っていない。

置換の不動点の個数

$\Omega$ を $\{1,\dots,n\}$ の置換全体（$n!$ 個、一様）とし、$A_i:=\{\sigma\mid\sigma(i)=i\}$、不動点の個数を $F$ とする。$|A_i|=(n-1)!$ なので $E[F]=n\cdot\frac1n=1$ である。$n\ge2$、$i\ne j$ なら $|A_i\cap A_j|=(n-2)!$ なので $P(A_i\cap A_j)=\frac1{n(n-1)}$ であり、順序対 $(i,j)$ は $n(n-1)$ 個あるから $E[F(F-1)]=1$、したがって $V[F]=1+1-1^2=1$ である。$n=4$ で確かめると、分布 $9,8,6,0,1$（冒頭）から $E[F(F-1)]=\frac{2\cdot6+6\cdot0+12\cdot1}{24}=1$ となる。平均は $n$ によらず $1$、分散も $n\ge2$ なら $n$ によらず $1$ である（$n=1$ では $F=1$ で分散は $0$）。事象 $A_i$ たちは独立ではない（$P(A_i\cap A_j)\ne P(A_i)P(A_j)$）が、どちらの計算にも支障はない。

記録の個数

$1,\dots,n$ を無作為に並べた列 $a_1,\dots,a_n$ で、$a_i$ がそれまでのどの項よりも大きいとき、$i$ 番目は記録であるという（1 番目はつねに記録）。$A_i$ を「$i$ 番目が記録」とする。最初の $i$ 個に入る数の組を決めたとき、その $i$ 個の並べ方 $i!$ 通りのうち最大が $i$ 番目にくるのは $(i-1)!$ 通りなので、$P(A_i)=\frac1i$ である。よって記録の個数の期待値は
$$ 1+\frac12+\frac13+\cdots+\frac1n $$
である。$n=4$ なら $\frac{25}{12}=2.083\ldots$ で、24 通りの並べ方の記録の個数の合計は $50$ である。

包除原理と完全順列

帽子の問題で「誰の帽子も戻らない確率」を求めたいとする。これは $F=0$ となる確率で、期待値ではない。しかし、指示関数の積の等式を展開してから期待値をとると、確率も線形性で求まる。これが包除原理である。以下、$I\subset\{1,\dots,m\}$ について $A_I:=\bigcap_{i\in I}A_i$ とし、$A_\emptyset:=\Omega$ と約束する。

包除原理（確率の形）

有限確率空間の事象 $A_1,\dots,A_m$ について
$$ P(A_1\cup\cdots\cup A_m)=\sum_{k=1}^m(-1)^{k-1}\sum_{|I|=k}P(A_I) $$
である。ここで内側の和は、$\{1,\dots,m\}$ の $k$ 元部分集合 $I$ すべてにわたる。一様な場合に $|\Omega|$ を掛ければ、個数の形 $|A_1\cup\cdots\cup A_m|=\sum_{k=1}^m(-1)^{k-1}\sum_{|I|=k}|A_I|$ になる。

指示関数の積を展開する

$\omega$ がどの $A_i$ にも属さないことは、すべての $i$ で $1-1_{A_i}(\omega)=1$ となることと同じなので、$\omega$ ごとに
$$ 1-1_{A_1\cup\cdots\cup A_m}=\prod_{i=1}^m\bigl(1-1_{A_i}\bigr) $$
が成り立つ。右辺を展開すると、各 $i$ について $1$ か $-1_{A_i}$ のどちらかを選んだ積の和になる。$-1_{A_i}$ を選ぶ $i$ の集合を $I$ とすると、その項は $(-1)^{|I|}\prod_{i\in I}1_{A_i}=(-1)^{|I|}1_{A_I}$ である。したがって
$$ 1-1_{A_1\cup\cdots\cup A_m}=\sum_{I\subset\{1,\dots,m\}}(-1)^{|I|}1_{A_I} $$
であり、両辺の期待値をとって thm-loe-linearity を使うと $1-P(\bigcup_iA_i)=\sum_I(-1)^{|I|}P(A_I)$ となる。$I=\emptyset$ の項 $P(\Omega)=1$ を移項し、$|I|=k$ ごとにまとめると主張を得る。$\square$

包除原理で全射の個数を数える話は場合の数の数え方の体系で扱う。
この証明で線形性を使うのは、展開した後の和に対してだけである。$\prod(1-1_{A_i})$ の期待値を $\prod(1-P(A_i))$ としてはいけない（事象が互いに独立なら正しいが、一般には成り立たない。ex-loe-product-fails）。積は $\omega$ ごとの恒等式として展開し、期待値は和に対してとる、という順序が要点である。
不動点をもたない置換を完全順列（derangement）といい、$\{1,\dots,n\}$ の完全順列の個数を $D_n$ と書く（$D_0:=1$）。

完全順列の個数

$n\ge0$ について
$$ D_n=n!\sum_{j=0}^n\frac{(-1)^j}{j!} $$
である。さらに、不動点をちょうど $k$ 個もつ置換の個数を $p_n(k)$ とすると $p_n(k)=\binom nkD_{n-k}$（$0\le k\le n$）である。

不動点を指定した置換を数える

$n=0$ は両辺 $1$ である。$n\ge1$ とし、ex-loe-fixed-points の $A_i$ を使う。$|I|=j$ のとき、$A_I$ は $I$ の元をすべて固定する置換の全体で、残り $n-j$ 個の並べ方の数 $(n-j)!$ だけある。$j$ 元部分集合 $I$ は $\binom nj$ 個あるので、thm-loe-inclusion-exclusion の個数の形から
$$ D_n=n!-|A_1\cup\cdots\cup A_n|=\sum_{j=0}^n(-1)^j\binom nj(n-j)!=\sum_{j=0}^n(-1)^j\frac{n!}{j!} $$
である。不動点がちょうど $k$ 個の置換は、不動点の集合 $K$（$\binom nk$ 通り）を選び、残りの $n-k$ 個を不動点なしに並べる（$D_{n-k}$ 通り）ことで一度ずつ得られる。$\square$

$D_0,D_1,\dots,D_8$ は $1,0,1,2,9,44,265,1854,14833$ である。$D_4=9$ は冒頭の表の「戻る人数 $0$」と一致し、$p_4(1)=4D_3=8$、$p_4(2)=6D_2=6$ も一致する。

完全順列の割合と 1/e

$n\ge1$ について $\bigl|D_n-\frac{n!}e\bigr|<\frac1{n+1}$ である。特に $D_n$ は $\frac{n!}e$ に最も近い整数であり、無作為な置換が不動点をもたない確率 $\frac{D_n}{n!}$ は $n\to\infty$ で $\frac1e=0.3678\ldots$ に収束する。

交代級数の残りを評価する

指数関数の冪級数展開 $e^{-1}=\sum_{j=0}^\infty\frac{(-1)^j}{j!}$ を用いる（本記事では証明しない）。prop-loe-derangement により
$$ \frac{n!}e-D_n=\sum_{j=n+1}^\infty(-1)^ja_j,\qquad a_j:=\frac{n!}{j!} $$
である。$a_{n+1}=\frac1{n+1}>a_{n+2}>a_{n+3}>\cdots>0$ である。右辺に $(-1)^{n+1}$ を掛けたもの $T:=a_{n+1}-a_{n+2}+a_{n+3}-\cdots$ を 2 項ずつまとめると、$T=(a_{n+1}-a_{n+2})+(a_{n+3}-a_{n+4})+\cdots>0$ であり、$T=a_{n+1}-(a_{n+2}-a_{n+3})-\cdots< a_{n+1}$ である（級数は絶対収束するので、まとめ方を変えても和は変わらない）。よって $\bigl|\frac{n!}e-D_n\bigr|=T<\frac1{n+1}\le\frac12$ であり、$D_n$ は $\frac{n!}e$ に最も近い整数である。両辺を $n!$ で割ると $\bigl|\frac{D_n}{n!}-\frac1e\bigr|<\frac1{(n+1)!}\to0$ である。$\square$

$n=4$ で $\frac{D_4}{4!}=0.375$、$n=10$ で $0.36787946\ldots$ となり、$\frac1e=0.36787944\ldots$ との差は $n=10$ ですでに $10^{-7}$ 未満である。
$(1-\frac1n)^n\to\frac1e$ のような極限の求め方は 1の∞乗型の極限で扱う。

Burnside の補題：軌道の個数を数える

正方形の 4 つの頂点に置いた玉を白か黒に塗る。塗り方は $2^4=16$ 通りあるが、正方形を回して重なるものを同じとみなすと何通りか。「16 を回転の数 4 で割って 4 通り」は誤りで、正しくは 6 通りである（ex-loe-naive-division）。この「同じとみなしたものの個数」を、不動点の個数の平均として求めるのが Burnside の補題である。
用語を確認する。群 $G$ の集合 $X$ への作用（群の作用）とは、$g\in G$、$x\in X$ に $g\cdot x\in X$ を対応させる規則で、単位元 $e$ について $e\cdot x=x$、$g,h\in G$ について $(gh)\cdot x=g\cdot(h\cdot x)$ を満たすものである。$x$ の軌道を $Gx:=\{g\cdot x\mid g\in G\}$、安定化群を $G_x:=\{g\in G\mid g\cdot x=x\}$ と書く。「$y=g\cdot x$ となる $g\in G$ がある」という関係は、$e$、逆元、積をとることで反射的・対称的・推移的であることが確かめられるので、同値関係であり、軌道はその同値類として $X$ を互いに交わらない部分に分ける。上の例では $G$ は 4 つの回転（$0^\circ,90^\circ,180^\circ,270^\circ$）の群、$X$ は 16 通りの塗り方で、回して重なる塗り方の集まりが軌道である。

不動点集合

群 $G$ が集合 $X$ に作用しているとき、$g\in G$ について
$$ \mathrm{Fix}(g):=\{x\in X\mid g\cdot x=x\} $$
を $g$ の不動点集合という。

軌道と安定化群の大きさ

有限群 $G$ が集合 $X$ に作用しているとき、$x\in X$ について $|Gx|\cdot|G_x|=|G|$ である。

同じ行き先をもつ元を数える

写像 $G\to Gx$、$g\mapsto g\cdot x$ は定義から全射である。$g,h\in G$ について、$g\cdot x=h\cdot x$ と $(h^{-1}g)\cdot x=x$、すなわち $h^{-1}g\in G_x$ は同値である（両辺に $h^{-1}$ を作用させる）。したがって行き先が $h\cdot x$ になる元の全体は $hG_x:=\{hs\mid s\in G_x\}$ であり、$s\mapsto hs$ は単射なのでその個数は $|G_x|$ である。$Gx$ の各点に $|G_x|$ 個ずつの元が行くので $|G|=|Gx|\cdot|G_x|$ である。$\square$

Burnside の補題

有限群 $G$ が有限集合 $X$ に作用しているとき、軌道の個数は
$$ \frac1{|G|}\sum_{g\in G}|\mathrm{Fix}(g)| $$
に等しい。

固定する組を二重に数える

$R:=\{(g,x)\in G\times X\mid g\cdot x=x\}$ とおき、prop-loe-double-counting で数える。$g$ ごとに数えると $|R|=\sum_{g\in G}|\mathrm{Fix}(g)|$ であり、$x$ ごとに数えると $|R|=\sum_{x\in X}|G_x|$ である。lem-loe-orbit-stabilizer により $|G_x|=\frac{|G|}{|Gx|}$ なので
$$ \sum_{g\in G}|\mathrm{Fix}(g)|=|G|\sum_{x\in X}\frac1{|Gx|} $$
である。右辺の和を軌道ごとに分ける。軌道 $O$ に属する $x$ では $Gx=O$ なので、$O$ の $|O|$ 個の点からの寄与は $|O|\cdot\frac1{|O|}=1$ である。よって $\sum_{x\in X}\frac1{|Gx|}$ は軌道の個数に等しい。両辺を $|G|$ で割って主張を得る。$\square$

$G$ の元を一様に選ぶ確率空間で考えると、$|\mathrm{Fix}(g)|$ は確率変数であり、thm-loe-burnside は「無作為な群の元の不動点の個数の期待値は、軌道の個数に等しい」と読める。証明は、$\sum_{g}|\mathrm{Fix}(g)|=\sum_x|G_x|$ という二重数え上げ、つまり $|\mathrm{Fix}(g)|=\sum_{x\in X}1_{\{g\cdot x=x\}}$ と指示関数の和に分けて線形性を使ったものと同じである。

置換の不動点をもう一度

対称群 $S_n$（$\{1,\dots,n\}$ の置換全体）は $X=\{1,\dots,n\}$ に $\sigma\cdot i:=\sigma(i)$ で作用する。どの $i$ もどの $j$ にも移せるので軌道は 1 つであり、thm-loe-burnside から不動点の個数の期待値は $1$ である。これは ex-loe-fixed-points の結果である。$n\ge2$ として、$S_n$ を順序対の集合 $X\times X$ に $\sigma\cdot(i,j):=(\sigma(i),\sigma(j))$ で作用させると、軌道は $\{(i,i)\}$ 全体と $\{(i,j)\mid i\ne j\}$ 全体の 2 つである（$i\ne j$、$k\ne l$ なら $\sigma(i)=k$、$\sigma(j)=l$ となる置換がある）。$(i,j)$ が $\sigma$ で固定されるのは $i,j$ がともに不動点のときなので、$|\mathrm{Fix}(\sigma)|=F(\sigma)^2$ であり、$E[F^2]=2$、$V[F]=2-1^2=1$ となる。ex-loe-fixed-points と同じ値が、軌道を数えるだけで得られる。

ネックレスの数え上げ

円周上に等間隔に並べた $n$ 個の玉を $c$ 色で塗る。$X$ を $c^n$ 通りの塗り方とし、$r$ 個分の回転（$r=0,1,\dots,n-1$）の群 $G$ を作用させる。$r$ 個分の回転で塗り方が変わらないのは、位置 $i$ と $i+r,i+2r,\dots$（$n$ を法とする）がすべて同じ色のときである。位置 $i$ から $r$ ずつ進んで到達できる位置は $i+g\mathbb{Z}$（$n$ を法とする。$g:=\gcd(n,r)$）であり（$r$ の倍数を $n$ で割った余りは $g$ の倍数の余り全体になる）、位置は $g$ 個の組に分かれるので $|\mathrm{Fix}(r)|=c^{\gcd(n,r)}$ である。よって、回転で重なるものを同じとみなした塗り方の数は
$$ \frac1n\sum_{r=0}^{n-1}c^{\gcd(n,r)} $$
である。$n=6$、$c=2$ では $\frac{64+2+4+8+4+2}6=\frac{84}6=14$ である。裏返しも同じとみなすなら、6 個の鏡映（向かい合う 2 玉を通る軸 3 本では $2^4=16$、向かい合う辺の中点を通る軸 3 本では $2^3=8$ の塗り方が固定される）を加えた 12 元の群で $\frac{84+3\cdot16+3\cdot8}{12}=\frac{156}{12}=13$ となる。

反例と注意

反例：独立でない確率変数の積

公平な硬貨を 1 回投げ、$\Omega=\{\text{表},\text{裏}\}$（確率 $\frac12$ ずつ）とする。$X:=1_{\{\text{表}\}}$、$Y:=X$ とおく。$E[X]=E[Y]=\frac12$ だが $XY=X^2=X$ なので $E[XY]=\frac12\ne\frac14=E[X]E[Y]$ である。$X,Y$ は期待値をもつ確率変数であり、和については $E[X+Y]=1=E[X]+E[Y]$ が成り立つ。しかし独立ではない（$P(X=1,Y=1)=\frac12\ne\frac14=P(X=1)P(Y=1)$）。したがって prop-loe-product の結論「$E[XY]=E[X]E[Y]$」は、独立性の仮定を外すと成り立たない。線形性は和についての性質であり、積には及ばない。

反例：期待値は起こる確率ではない

cor-loe-indicator から「少なくとも 1 つ起こる確率は $P(A_1)+\cdots+P(A_m)$」と考えるのは誤りである。帽子の問題で $A_i$ を「$i$ 番目の人の帽子が戻る」とすると $\sum_iP(A_i)=1$ だが、少なくとも 1 人に戻る確率は $1-\frac{D_n}{n!}$ で、$n=4$ では $1-\frac9{24}=0.625$ である。$A_i$ たちは互いに交わらないという性質を満たさない（2 人以上に戻る返し方がある）ので、確率の加法性は使えない。成り立つのは $1_{A_1\cup\cdots\cup A_m}\le N$ から得られる不等式 $P(A_1\cup\cdots\cup A_m)\le\sum_iP(A_i)$ だけで、正確な値には thm-loe-inclusion-exclusion が要る。

反例：個数を群の大きさで割る

正方形の 4 頂点の白黒の塗り方 16 通りに、4 つの回転の群を作用させる。回転 $0^\circ,90^\circ,180^\circ,270^\circ$ で固定される塗り方はそれぞれ $16,2,4,2$ 通り（$90^\circ$ と $270^\circ$ では 4 頂点が同色、$180^\circ$ では向かい合う頂点が同色）なので、thm-loe-burnside により軌道は $\frac{16+2+4+2}4=6$ 個である。具体的には、黒の個数が $0,1,3,4$ の塗り方がそれぞれ 1 つの軌道、黒 2 個は「隣り合う」「向かい合う」の 2 つの軌道になる。「$16\div4=4$」が誤りなのは、すべての軌道がちょうど $|G|=4$ 個の元からなる、という性質をこの作用が満たさないからである（全部白の塗り方の軌道は 1 個、向かい合う 2 頂点だけ黒の塗り方の軌道は 2 個）。lem-loe-orbit-stabilizer によれば軌道の大きさは $|G|/|G_x|$ であり、安定化群が単位元だけのときに限って $|G|$ になる。「個数を群の位数で割る」という数え方は、すべての $x$ で $G_x=\{e\}$ のときにしか使えない。

標本空間が無限の場合も、$X,Y$ がともに有限な期待値をもてば線形性は成り立つ（本記事では証明しない）。期待値が有限でない確率変数を含むと、右辺が「$\infty-\infty$」となって意味をもたないことがある。

数学オリンピックの問題から

不動点の個数の和

第 28 回国際数学オリンピック（1987 年）第 1 問 Oly87 を和訳して引用する。

$p_n(k)$ を、集合 $\{1,2,\dots,n\}$（$n\ge1$）の置換のうち、ちょうど $k$ 個の不動点をもつものの個数とする。$\displaystyle\sum_{k=0}^nk\cdot p_n(k)=n!$ を証明せよ。
高校数学で解く。 置換 $\sigma$ と、その不動点 $i$ の組 $(\sigma,i)$ の個数を 2 通りに数える。$\sigma$ ごとに数えると、不動点を $k$ 個もつ置換は $k$ 組を与えるので、組の総数は $\sum_kk\,p_n(k)$ である。$i$ ごとに数えると、$\sigma(i)=i$ となる置換は $(n-1)!$ 個なので、組の総数は $n\cdot(n-1)!=n!$ である。
大学数学で見る。 左辺を $n!$ で割ったものは、無作為な置換の不動点の個数 $F$ の期待値である。上の解答は prop-loe-double-counting そのもので、確率の言葉では ex-loe-fixed-points の $E[F]=1$、群の言葉では「$S_n$ の $\{1,\dots,n\}$ への作用の軌道は 1 つ」という thm-loe-burnside の特別な場合である。この見方をとると、次の 2 つが同じ手間で得られる。

順序対への作用の軌道が 2 つであること（ex-loe-burnside-fixed-points）から $\sum_kk^2\,p_n(k)=2\cdot n!$、すなわち $\sum_kk(k-1)\,p_n(k)=n!$（$n\ge2$）。
分布そのもの $p_n(k)=\binom nkD_{n-k}$（prop-loe-derangement）。prop-loe-derangement-e を合わせると、$k$ を固定して $n\to\infty$ とすれば $\frac{p_n(k)}{n!}=\frac1{k!}\cdot\frac{D_{n-k}}{(n-k)!}\to\frac1{k!\,e}$ となる。

審査員の判定の一致

第 39 回国際数学オリンピック（1998 年）第 2 問 Oly98 を和訳して引用する。

ある競技に $a$ 人の参加者と $b$ 人の審査員がいる。ただし $b\ge3$ は奇数である。各審査員は各参加者を「合格」または「不合格」と判定する。$k$ は、どの 2 人の審査員についても、2 人の判定が一致する参加者が高々 $k$ 人であるような数とする。$\dfrac ka\ge\dfrac{b-1}{2b}$ を証明せよ。
高校数学で解く。 「審査員 2 人の組と参加者で、その 2 人の判定がその参加者について一致するもの」の個数 $M$ を 2 通りに数える。審査員の組ごとに数えると、組は $\binom b2$ 個あり、それぞれ高々 $k$ 人なので $M\le k\binom b2$ である。参加者ごとに数える。ある参加者を合格とした審査員が $x$ 人なら、判定が一致する組は $\binom x2+\binom{b-x}2$ 個である。$b=2m+1$ とおくと
$$ \binom x2+\binom{b-x}2=\frac{x^2+(b-x)^2-b}2=\Bigl(x-\frac b2\Bigr)^2+\frac{b^2-2b}4 $$
は $x$ の 2 次関数で、整数 $x$ では $x=m,m+1$ で最小値 $\binom m2+\binom{m+1}2=m^2$ をとる。よって $M\ge am^2$ である。合わせて $k\cdot\frac{b(b-1)}2\ge a\cdot\frac{(b-1)^2}4$、すなわち $\frac ka\ge\frac{b-1}{2b}$ である。
大学数学で見る。 同じ議論を期待値で言い直す。参加者 $c$ と審査員の組 $\{u,v\}$ を独立に一様に選び、「$u,v$ の判定が $c$ について一致する」という事象の確率 $\rho$ を考える。組を先に固定すると一致する参加者は高々 $k$ 人なので $\rho\le\frac ka$、参加者を先に固定すると一致する組は $m^2$ 個以上なので $\rho\ge\frac{m^2}{\binom b2}=\frac{b-1}{2b}$ である。prop-loe-double-counting を全体の個数で割っただけだが、「同じ平均を、一方の順序で上から、他方の順序で下から評価する」という構造がはっきりする。各審査員の判定を $0,1$ の列と見ると、これは符号理論の Plotkin 限界と同じ形の議論である（本記事では立ち入らない）。

さらに先へ

Pólya の数え上げ定理：ex-loe-necklace の計算を巡回の長さごとの多項式にまとめ、色ごとの個数まで区別して数える。
置換表現と指標：$|\mathrm{Fix}(g)|$ は $g$ を置換行列で表したときの対角和（置換表現の指標）であり、thm-loe-burnside はこの指標と定数関数 $1$ の内積が軌道の個数に等しいと読める。
確率論的方法：$E[X]\ge c$ なら $X(\omega)\ge c$ となる $\omega$ が存在する（期待値は重みつき平均だから）。これを使って対象の存在を示す方法は、組合せ論の大きな道具である。
Poisson 近似：不動点の個数の分布は $n\to\infty$ で平均 $1$ の Poisson分布に近づく（前節の $\frac{p_n(k)}{n!}\to\frac1{k!\,e}$）。
期待値の線形性と独立な確率変数の積の公式は GS06 の Theorem 6.2・6.4（pp. 231・233）、包除原理による帽子の問題（完全順列）は GS06 §3.2（p. 104 以降）と Lev24 §3.8.3（p. 295）、Burnside の補題は KT17 Lemma 15.9（§15.3、p. 298）と Bog17 §6.2.3（p. 122）にある。