この問題をきっかけに期待値を利用した証明法についていくつか復習し、役割や鳩ノ巣原理との関係などを考えました。参考文献・問題の出典は以下。

Evan Chen, Expected Uses of Probability

Evan Chen, OTIS Excerpts

以下、「ランダムに」と言ったときは起こりうる事象がすべて同様に確からしいものとします。

期待値の線形性

任意の確率変数 $X_1,X_2,\ldots,X_n$ について、次が成り立つ。 $$ E[X_1 + X_2 + \cdots + X_n] = E[X_1] + E[X_2] + \cdots + E[X_n] $$

$2$ 変数の場合の証明：

$$ \begin{aligned} E[X+Y] &= \sum_x \sum_y (x+y)P(X=x,Y=y) \\ &= \sum_x \sum_y xP(X=x,Y=y) + \sum_x \sum_y yP(X=x,Y=y) \\ &= \sum_x x P(X=x) + \sum_y y P(Y=y) \\ &= E[X] + E[Y] \end{aligned} $$

各確率変数に重みをつけたものも同様に示せます。

問題1

$2020$ 人の子供が輪になって座っている。あるとき同時に全員の子供がランダムに隣のどちらかの子供を選んで肩をたたく。誰からも肩をたたかれなかった子供の人数の期待値を求めよ。

答え

各子供について、誰からも肩をたたかれない確率は $1/4$ なので、期待値の線形性より $2020 \cdot 1/4 = 505$。$\Box$

問題2

$n$ 個の実数が与えられる。このうち $1$ 個以上は非ゼロであり、総和は $0$ である。 適当にこれらの数に $a_1,a_2,\ldots,a_n$ をラベル付けし、下の不等式が成り立つようにできることを示せ。 $$ a_1a_2 + a_2a_3 + \ldots + a_{n-1}a_n + a_na_1 < 0 $$

答え

$a_1,\ldots,a_n$をランダムに割り振ることを考える。

$$ 2\sum_{i < j} a_ia_j = (a_1 + \cdots + a_n)^2 - (a_1^2 + \cdots + a_n^2) = - (a_1^2 + \cdots + a_n^2) < 0 $$

ゆえに、対称性より

$$ E[a_1a_2] = E[a_2a_3] = \cdots = E[a_na_1] < 0 $$

$$ E[a_1a_2 + a_2a_3 + \cdots + a_na_1] < 0 $$

これより題意を満たす $a_1,\ldots,a_n$ のラベル付けが存在することが示された。$\Box$

公式解答に比べて、期待値を利用した議論の見やすさが分かる気がする？

存在性の証明

問題3

完全二部グラフ$K_{n,n}$から $n-1$ 本の辺を削除する。（$n^2-n+1$ 本の辺が残される。） 辺を削除後のグラフに完全マッチングが必ず存在することを示せ。

答え

片方の独立集合の頂点を、もう片方にランダムに割り振って $n$ 個の頂点対を作ることを考える。

これらの対を（順番を無視したいので）ランダムに順序づけ、$i=1,\ldots,n$ について確率変数 $X_i$ を

  • $i$ 番目の頂点対が辺でつながれているとき $1$
  • そうでないとき $0$

とし、$X = X_1 + X_2 + \cdots + X_n$ とする。

各 $i$ について $E[X_i] = \dfrac{n^2-n+1}{n^2}$ より、

$$ \begin{aligned} E[X] &= E[X_1] + E[X_2] + \cdots + E[X_n] \\ &= n \cdot \frac{n^2-n+1}{n^2} \\ &= n - 1 + \frac{1}{n} \\ &> n - 1 \end{aligned} $$

$X$ は整数の値しかとらないので、$X=n$ を達成する構図が存在することが示された。$\Box$

問題4

ある数学の大会には、6 問の問題と 200 人の参加者がいます。各問題が 120 人以上に解かれたとするとき、どの問題も少なくともどちらかが解いているような 2 人組が存在することを示しなさい。

答え

ランダムに $2$ 人の参加者を選ぶ。ある問題について $2$ 人とも解いていない確率は高々 $(80/200)^2 = 4/25$。

$6$ 問中で $2$ 人とも解いていない問題数の期待値は高々 $6 \cdot 4/25 < 1$ より、すべての問題を解いた $2$ 人組は存在する。$\Box$

最初の問題

平面上に $10$ 個の点がある。 あなたは半径 $1$ の円をいくつか重ならないように平面上に描くことによって、$10$ この点すべてが円の内側に入るようにしたい。

これは必ずできるか。できる場合はその証明を、できない場合は反例（$10$ 点の初期配置）を与えよ。

答え

円の最密充填は密度 $90.69%$ なので、平面上の10個の点に対してランダムに円の最密充填を配置すると、円の内部にある点の個数の期待値は $0.9069 \cdot 10 = 9.069 > 9$。

これはある互いに重ならない円の配置が存在して、$10$ 個すべての点が円の内部にあることを示している。$\Box$

期待値の意味

期待値を持ち出すこと自体に本質的なはたらきはなくて、（この程度の問題を扱う範囲では）由来を考えれば単なる言い方の違いにすぎないのかなと思います。

例えば問題2の公式解答は期待値を使った解答と本質的に同じようですし、問題3についても

問題3の答え (2)

片方の独立集合の頂点をもう片方に割り振ってできる $n$ 個の頂点対の集合は $n!$ 通りある。

ある辺 $(u, v)$ について、対 $(u, v)$ は $n!$ 個の頂点対集合のうち $(n-1)!$ 個に属する。

辺は $n^2 - n + 1$ 本あることから、辺でつながれた頂点対は $n!$ 個の集合の中に $(n^2-n+1)(n-1)!$回現れる。

$$ (n^2-n+1)(n-1)! = \left(n-1+\frac{1}{n}\right)n! > (n-1)n! $$

より、$n!$ 個の頂点対集合のうち $1$ つ以上に $n$ 個の辺でつながれた頂点対が属する。これが求める完全マッチングである。$\Box$

問題4・5も適当に全体集合をとり、各確率変数がとっていた値を独立に足し上げることで言い換えることができそうです。

期待値の線形性はダブルカウントに対応し、「$E[X] > n-1$ より～」の議論は鳩ノ巣原理に対応します。

全体集合の各元を考える代わりに一様ランダムをイメージするのは楽な気がしますし、問題5のように連続の場合が考えやすくなっていそうです。考えることが減って嬉しそうです。