相異なる整数データの分散の最小値

方針

解答

⓪ 発想 — どう考え始めるか。 整数で、しかもどの2つも異なる。だから隣どうしは最低でも $1$ は離れる。散らばりには「これ以上詰められない」下限があるはずだ。

ところが分散の定義には平均が顔を出す。平均は整数とは限らないし、整数の条件と結びつけにくい。

そこで平均を消す。分散は「すべての2点の差の2乗の平均」としても書けるのだ。それが(1)である。この形なら、平均を経由せずに「2点の差」だけで評価できる。

相異なる整数を小さい順に並べれば、$i$ 番目と $j$ 番目の差は少なくとも $j-i$。この不等式を二重和に流し込めば、$1,2,\dots ,n$ という「最も詰まった配置」の分散が、そのまま下限として現れる。

① (1) 二重和を展開する。 各項を偏差で書き直す。$x_i-x_j=(x_i-\bar{x})-(x_j-\bar{x})$ だから

$$\sum _i\sum _j(x_i-x_j{)}^2=\sum _i\sum _j\left\{(x_i-\bar{x}{)}^2-2(x_i-\bar{x})(x_j-\bar{x})+(x_j-\bar{x}{)}^2\right\}$$

第1項は $j$ について足すと $n$ 倍になるから $n\sum _i(x_i-\bar{x}{)}^2=n\cdot n{s}^2$。第3項も同じく $n\cdot n{s}^2$。

第2項は

$$-2\left(\sum _i(x_i-\bar{x})\right)\left(\sum _j(x_j-\bar{x})\right)=0$$

偏差の和は $0$ だからだ。よって

$$\sum _i\sum _j(x_i-x_j{)}^2=2n^2{s}^2$$

となり、(1)の式を得る。平均が消えたことに注目したい。

② (2) 差の下限を入れる。 小さい順に並べ替えて $y_1<y_2<\cdots <y_n$ とする(並べ替えても分散は変わらない)。

相異なる整数だから隣どうしは $1$ 以上離れる。$y_{i+1}-y_i\ge 1$ を $j-i$ 回足せば、$i<j$ のとき

$$y_j-y_i\ge j-i$$

両辺とも正だから2乗しても向きは変わらない。$i=j$ なら両辺 $0$、$i>j$ でも入れ替えれば同じ。したがってすべての組で

$$(y_i-y_j{)}^2\ge (i-j{)}^2$$

(1)の式に入れると

$$s^2=\frac{1}{2n^2}\sum _i\sum _j(y_i-y_j{)}^2\ge \frac{1}{2n^2}\sum _i\sum _j(i-j{)}^2$$

③ 右辺を計算する。 右辺は、(1)の式を「データ $1,2,\dots ,n$」に当てはめたものだから、$1$ から $n$ までの分散に等しい。

$$\frac{1}{n}\sum _{k=1}^n{k}^2-{\left(\frac{n+1}{2}\right)}^2=\frac{(n+1)(2n+1)}{6}-\frac{(n+1{)}^2}{4}=\frac{(n+1)\left\{2(2n+1)-3(n+1)\right\}}{12}=\frac{(n+1)(n-1)}{12}$$

よって

$$s^2\ge \frac{n^2-1}{12}$$

等号は、すべての $i<j$ で $y_j-y_i=j-i$ となるとき、すなわち $y_1,y_2,\dots ,y_n$ が連続する整数 $a,a+1,\dots ,a+n-1$ のときである(平行移動しても分散は変わらないので、$a$ は何でもよい)。

まとめ: 平均が扱いにくいときは、平均の出てこない表し方を探す。「すべての2点の差の2乗の平均」は、分散のもう1つの顔である。

発展 — 一歩先へ。 $1$ から $n$ までの分散 $\frac{n^2-1}{12}$ は、よく知られた値だ。サイコロの目($1$ から $6$)なら $\frac{36-1}{12}=\frac{35}{12}$ である。

本問は「相異なる整数のデータは、どんなに詰めてもサイコロ型より散らばれない」と言っている。区間 $[0,n]$ に連続的に一様分布する点の分散は $\frac{n^2}{12}$ で、こちらとほとんど同じ値になる。$-\frac{1}{12}$ のずれは、整数が格子点であることから来る補正だ。離散と連続が $\frac{1}{12}$ という同じ定数で結ばれているのは、偶然ではない。

別解

定義のまま、詰まった並びを直接評価する(手を動かすルート)。 二重和を使わない道もある。

$n=5$ で考えてみよう。相異なる整数だから隣どうしは最低 $1$ 離れる。いちばん詰まった並びは $a,a+1,a+2,a+3,a+4$ で、平均は真ん中の $a+2$。偏差は $-2,-1,0,1,2$ となり、分散は

$$\frac{4+1+0+1+4}{5}=2=\frac{5^2-1}{12}$$

確かに公式と合う。

一般の $n$ でも、間隔をすべて $1$ にした並びを考えれば、偏差は $-\frac{n-1}{2},\dots ,\frac{n-1}{2}$ という等差数列になる。その2乗和は

$$\sum _{k=1}^n{\left(k-\frac{n+1}{2}\right)}^2=\sum _{k=1}^n{k}^2-(n+1)\sum _{k=1}^{n}k+n{\left(\frac{n+1}{2}\right)}^2=\frac{n(n^2-1)}{12}$$

$n$ で割って $\frac{n^2-1}{12}$。同じ値である。

ただし、この道で厳密に「最小」を言うには「間隔を1か所でも広げると2乗和が必ず増える」ことを示さねばならない。それを一般の配置について直接示すのは意外に面倒だ。本解の二重和は、その面倒をまとめて片づける道具なのである。具体例で答えの見当をつけ、証明は二重和で — という二段構えが実戦的だ。