「期待値の線型性」についての解説と、それを用いる問題のまとめ

0. はじめに

AtCoder 上のコンテストで、以下のような問題 (SoundHound Inc. Programming Contest 2018 C - Ordinary Beauty) が出題されました。この問題をきっかけに、「期待値の線型性」が話題になりました。今回は、期待値の線型性について、まとめてみようと思います。

問題概要

$1$ 以上 $n$ 以下の整数からなる $m$ 項の数列 $a_1, a_2, \dots, a_m$ をすべて考える ($n^m$ 通りある)。このとき「隣り合う二項のうちその差がちょうど $d$ となっているものの個数」 (これを数列の美しさと呼んでいる) の平均値がどうなるかを求めよ。

制約

• $0 \le d < n \le 10^9$
• $2 \le m \le 10^9$

1. 「期待値の線型性」に関する簡単な例から

上の問題を考える前に、先に簡単な例を考えてみます。TOEIC は選択式の 4 択問題が 200 問出題されます。1 問 1 点として、全部の問題をランダムに選んだら期待値で何点とれるでしょうか？

直感的に 50 点だとわかります。ただしその考え方として

• 4 問解いたら 1 問正解できるから $200 ÷ 4 = 50$ 点

と考えたくなってしまうのですが、それよりはむしろ

• 1 問に着目したときに 1 点とれる確率は $\frac{1}{4}$ である
• したがって 1 問解くごとに平均して $\frac{1}{4}$ 点とれることになるので、全部で $\frac{1}{4} × 200 = 50$ 点とれる

という風に考えた方が期待値の線型性に入りやすいです。

2. SoundHound C - Ordinary Beauty の場合

以上のことを踏まえるとほとんど一緒です。
まず元の問題文は「$n^m$ 通りある数列全体を考えたときの美しさの平均値」という言い方をしていますが、「ランダムな数列を考えたときの美しさの平均値」ととらえた方が確率の議論を実感しやすいかもしれません (ただし下の方で「確率」に依らない解法にも言及してみました)。

さて、数列の「隣り合う二項」は $m-1$ 箇所ありますが、きほどの TOEIC の問題と同様にして、

• $a_1$ と $a_2$ の差が $d$ になる確率 (= $a_1$ と $a_2$ の部分から得られる美しさの期待値)
• $a_2$ と $a_3$ の差が $d$ になる確率 (= $a_2$ と $a_3$ の部分から得られる美しさの期待値)
• $\dots$
• $a_{m-1}$ と $a_m$ の差が $d$ になる確率 (= $a_{m-1}$ と $a_m$ の部分から得られる美しさの期待値)

を合計したものが答えになります。そして対称性から、これらはすべて等しいことがわかります。つまり、これらの $m-1$ 個の確率はどれも「$1$ 〜 $n$ の目があるサイコロを 2 つ振って出た目の差が $d$ になる確率」と同じものになります。ですので、それを求めて $m-1$ 倍したものが答えになります。サイコロの 2 つの目としてありうるのは

$(1, 1), (1, 2), \dots, (1, n), \dots, (n, 1), \dots, (n, n)$

の $n^2$ 通りありますが、そのうち差が $d$ になるものは、

• $d = 0$ のとき $(1, 1), (2, 2), \dots, (n, n)$ の $n$ 個
• $d > 0$ のとき以下を合わせて $2(n-d)$ 個
  • $(1, d+1), (2, d+2), \dots, (n-d, n)$
  • $(d+1, 1), (d+2, 2), \dots, (n, n-d)$

あります。したがって、差が $d$ になる確率 $P$ は

P = \left\{
\begin{array}{ll}
\frac{n}{n^2} (= \frac{1}{n}) & (d = 0) \\
\frac{2(n-d)}{n^2} & (d > 0)
\end{array}
\right.

となります。以上から、求める最終的な期待値は、$(m-1)P$ となります。

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
  long long n, m, d; cin >> n >> m >> d;
  double res;
  if (d == 0) res = (double)(m-1) / n;
  else res = (double)(m-1) * 2 * (n-d) / n / n;
  cout << fixed << setprecision(10) << res << endl;
}

補足: 「確率」を考えないで解く

さらに言うとこの問題は「確率」も「期待値の線形性」も意識しなくても解くことができます。$n^m$ 通り考えられる各数列についての「差が $d$ となっている隣接二項の個数」をすべて合計した値を求める方針で考えてみます (最後に $n^m$ で割ります)。そしてその合計値を求めるためには、各数列ごとにその「隣接二項の個数」をカウントして合算するのではなく、

• $a_1$ と $a_2$ の差が $d$ になるような数列 $a$ の個数
• $a_2$ と $a_3$ の差が $d$ になるような数列 $a$ の個数
• $\dots$
• $a_{m-1}$ と $a_m$ の差が $d$ になるような数列 $a$ の個数

を合計しても同じになります。このように「固定する添字を入れ替える」というのは頻出テクニックな印象です。さてさらに考察を推し進めると、これらの $m-1$ 個の個数はすべて等しくて、

• $d = 0$ のとき、$n × n^{m-2}$ 個
• $d > 0$ のとき、$2(n-d) × n^{m-2}$ 個

になります。これを $m-1$ 倍して、最後に $n^m$ で割れば答えが求まります:

• $d = 0$ のとき、平均 $\frac{m-1}{n}$ 個
• $d > 0$ のとき、平均 $\frac{2(m-1)(n-d)}{n^{2}}$ 個

3. 期待値の線形性の議論を数式できちんと

本記事の冒頭で、「TOEIC は選択式の 4 択問題が 200 問出題されますが、1 問 1 点として、全部の問題をランダムに選んだら期待値で何点とれるでしょうか？」という問題を考えました。

これに対して、「1 問分だと 1/4 点だから 200 問分だとその 200 倍」という風にざっくりと考えました。このざっくりとした部分をきちんと数学的に定式化して整理してみましょう。

3-1. 確率変数を導入する

まず $i$ 問目についての確率変数を以下のように定義します:

X_i = \left\{
\begin{array}{ll}
1 & (i 問目を正解したとき) \\
0 & (i 問目が不正解のとき)
\end{array}
\right.

このとき、TOEIC の最終得点は $X_1 + X_2 + \dots + X_{200}$ になるので、その期待値は

E[X_1 + X_2 + \dots + X_{200}]

になります。ここで「期待値の線型性」を使います。期待値の線型性とは $E[X + Y] = E[X] + E[Y]$ が成り立つことです。「和の期待値は期待値の和」ともよく言われます。これを使うと

E[X_1 + X_2 + \dots + X_{200}] = E[X_1] + E[X_2] + \dots + E[X_{200}]

になります。ここで任意の $i$ について $E[X_i] = \frac{1}{4}$ になるので、求める期待値は $E[X_1 + X_2 + \dots + X_{200}] = \frac{1}{4} × 200 = 50$ になります。

3-2. 期待値の線型性の証明

$E[X + Y] = E[X] + E[Y]$ を証明します。素直に式変形をしていくことで示せます。ここでは $X$ も $Y$ も離散変数としますが、連続変数の場合も同様です。

$E[X + Y]$
$= \sum_{x} \sum_{y} (x + y)P(X = x, Y = y)$　(期待値の定義から)
$= \sum_{x} x \sum_{y} P(X = x, Y = y) + \sum_{y} y \sum_{x} P(X = x, Y = y)$
$= \sum_{x} x P(X = x) + \sum_{y} y P(Y = y)$
$= E[X] + E[Y]$

4. 問題例

evima さんのツイートにあるように、SRM 400 〜 600 DIV1 Easy は「期待値の線形性」がとても流行っていました。また、期待値に関する性質の定番として、

• 「確率 $p$ で成功する事象を繰り返し行って初めて成功するまでの回数の期待値は $\frac{1}{p}$」

というのもあります。この性質はコンプガチャ問題や、ABC 078 C - HSI でも活躍します。

4-1. コンプガチャ問題

【問題概要】
$n$ 種類の物品が等確率で排出されるガチャがある。
全ての景品をコンプするのに必要な回数の期待値を求めよ。

【解法ポイント】
$i$ 種類までは集めた状態から次の新しい種類が出てくるまでの回数を表す確率変数を $X_i$ とすると、求める期待値は

E[X_0 + X_1 + \dots + X_{n-1}] = E[X_0] + E[X_1] + \dots + E[X_{n-1}]

になります。$i$ 種類を集めた状態で新しいものが来る確率は $\frac{n-i}{n}$ なので、その逆数をとって

E[X_i] = \frac{n}{n-i}

になります。よって求める期待値は

n(1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n})

になります。これは $O(n\log{n})$ 程度です。なおこのテーマを利用した面白くて難しい問題として

• SRM 400 DIV1 Hard CollectingBonuses

があります。150 人が提出しながらも正解者が僅か 2 人という恐ろしい問題でした。

4-2. ABC 008 C - コイン

【問題概要】
$N$ 枚のコインがあって、それぞれ $C_1, C_2, \dots, C_N$ が書かれている。
はじめすべてのコインが表向きに並べられている。コインが並んでいる順序は $N!$ 通り考えられる。

• コインを左から順番に、「そのコインの右側にあるコインのうち、書かれている整数値が自身の倍数になっているものをひっくり返す」

という操作を行う。$N!$ 通りの初期配置を考えたときの、操作後に表を向いているコインの枚数の平均値を求めよ。

【制約】

• $1 \le N \le 100$
• $1 \le C_i \le 10^9$

【解法ポイント】
ABC C 問題史上最難候補の一角です (他に「ABC 009 C - 辞書式順序ふたたび」なども)。ちなみにこの回は D 問題も ABC D 問題史上最難候補の一角というすごいセットでした。$C_i$ が書かれているコインについて

X_i = \left\{
\begin{array}{ll}
1 & (C_i が操作後に表のとき) \\
0 & (C_i が操作後に裏のとき)
\end{array}
\right.

で定義される確率変数 $X_i$ を定義して、$E[X_i]$ を求めて合算します。$E[X_i]$ は $C_i$ が表になる確率に等しいです。$C_1, C_2, \dots, C_N$ ($C_i$ 以外) のうち、$C_i$ を割り切るもの ($C_i$ より左側にあれば $C_i$ をひっくり返してしまうもの) の個数を $S$ として、それらを改めて $D_1, D_2, \dots, D_S$ とします。このとき求める確率は

• $D_1, D_2, \dots, D_S$ と $C_i$ の $S+1$ 枚のコインを一列にランダムに並べたときに $C_i$ より左側のコインの枚数が偶数になる確率

になります。これは要するに $S+1$ 枚のコインを並べたときに $C_i$ の入る場所が「$0$ 番目, $2$ 番目, ..., 」になる確率を表しているので、

\frac{(0, 1, 2, \dots, S　のうちの偶数の個数)}{S+1}

です。あとはこれを各 $i$ について合算すればよいです。

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

int N;
int C[210];

int main() {
    int N; cin >> N;
    vector<int> C(N); for (int i = 0; i < N; ++i) cin >> C[i];
    double res = 0.0;
    for (int i = 0; i < N; ++i) {
        int num = 0;
        for (int j = 0; j < N; ++j) {
            if (j == i) continue;
            if (C[i] % C[j] == 0) ++num;
        }
        res += (double)((num+2)/2) / (num+1);
    }
    cout << fixed << setprecision(10) << res << endl;
}

4-3. ABC 078 C - HSI

【問題概要】
高橋くんはプログラミングコンテストに出ていますが、YES か NO で答える問題で TLE してしまいました。テストケースは全てで $N$ ケースあり，そのうち $M$ ケースでTLEしていました。

そこで高橋くんは, $M$ ケースではそれぞれ実行に 1900 ms かかって 1/2 の確率で正解し、残りの $N−M$ ケースではそれぞれ実行に 100 ms かかって必ず正解するプログラムへ書き換えました。

正解するまで提出し続けたときのプログラムの実行時間の総和の期待値を求めよ。

【制約】

• $1 \le N \le 100$
• $1 \le M \le \min(N, 5)$

【解法ポイント】
この問題は「期待値の線形性」とは少し違う感じですが、「確率 $p$ で成功する事象を繰り返し行って初めて成功するまでの回数の期待値は $\frac{1}{p}$」を知っていると簡単です。この事実の証明は公式 editorial に載っています。

1 回の提出で AC がもらえる確率は $\frac{1}{2^M}$ なので、提出回数の期待値は $2^M$ 回になります。
1 回の提出の実行時間は $1900M + 100(N-M)$ なので、これを $2^M$ 倍すればよいです。

#include <iostream>
using namespace std;

int main() {
    long long N, M;
    cin >> N >> M;
    long long teisyutu_kaisuu = 1LL<<M;
    long long each_time = 1900LL * M + 100LL * (N - M);
    cout <<  each_time * teisyutu_kaisuu << endl;
}

4-4. ちょくだいさんの固定ツイート

【問題概要】
要素 $i$「これってもしかして」
要素 $j$「私達の場所が」
「「入れ替わってるー！？」」

ぼく「このように、$N$ 個の要素から二つを選び swap する、という行為を $M$ 回繰り返した時、元々あった場所に存在する要素の個数の期待値を出力せよ。出力の相対誤差は10^-6までは許容される。」

【制約】

• $1 \le N, M \le 10^{12}$

【解法ポイント】
「ある固定した要素が $M$ 回の操作後に元の場所にいる確率」を頑張って求めて $N$ 倍します。詳しくはふるやんさんの解説記事にあります。

4-5. SRM 400〜600 DIV1 Easy での出題例

最後に、期待値の線形性が流行していた時代の出題例を並べてみます:

• SRM 431 DIV1 Easy LaserShooting
• SRM 458 DIV1 Easy BouncingBalls　(とても面白くてオススメ度高いです！)
• SRM 656 DIV1 Easy RandomPancakeStack
• SRM 537 DIV2 Hard PrinceXToastbook
• SRM 494 DIV1 Medium AlternatingLane　(かなり「例の C 問題」によく似た類題です)
• SRM 409 DIV1 Hard GridColoring　(史上最も簡単な DIV1 Hard の 1 つかもしれません。例の C 問題と大差ないです)