期待値の線形性（が腑に落ちるまでの長い軌跡）

「期待値の線形性」について、けんちょん先生やふるやん先生の解説を参考にしながら自分の理解を整理するためのメモ。（随時加筆修正）

期待値の線形性そのもの
$$ \mathbb{E}[ax+b] = a\mathbb{E}[x] + \mathbb{E}[b] $$
は分かってるし、「 $\mathbb{E}[\sum f(x)]$ の形で書けるものは $\sum\mathbb{E}[f(x)]$ に書き換えて解ける」という事実にも別に疑問はない。というか、

f(x) is 何

という式が（都合よく）立てられる問題なのかを判別できるかどうかとか、式が立てられたとしても前後の文脈を無視して計算しても大丈夫なのか（どうも気持ち悪いし納得しづらい）とかいう話か。

先に結論から

ひとくちに「期待値の線形性」と言っても

1. 確率の遷移を漸化式を立てるなどして求める話
2. 期待値の線形性を適用して要領よく計算する話

の合わせ技だったりする。

先日のSoundHound問題など、前後の文脈によって確率が違うことが気になるのだけれど、

細かく見ていくと局所的には前後の文脈に依存したとしても
ある状態iに入る確率がステップ数に依存しない定数となる場合、（あるステップにおいてそれが何ステップ目なのかは考慮する必要がなく）どの状態にどれだけの割合でいるかだけ考えれば良くなる。
そうすると、「どの状態にどれだけの割合でいるか、から計算できる値」にステップ数を掛けるだけ、みたいな単純な計算に落とし込める
- SoundHound問題の場合、どの状態にいるかを知らなくても、全n状態→全n状態への n^2 通りの遷移のうちどれだけの割合で「美しいペア」が存在するかの確率が求められるのでさらに簡単になる

ということらしい。

SoundHound夏 C - Ordinary Beauty

大雑把に思えるけれど正しいっぽい解法

$$ \mathbb{E}[\sum(各区間の美しさ)] = \sum\mathbb{E}[各区間の美しさ] $$
各区間の美しさ（★前後の文脈は無視できる★）は $n^2$ 通りの組み合わせのうち美しいのは何通りか、なので
$$ \begin{equation}
r=\begin{cases}
\frac{1}{n} & \text{d=0のとき} \\
\frac{2(n-d)}{n^2} & \text{それ以外のとき}
\end{cases}
\end{equation} $$

これに区間数 $m-1$ を掛けた $(m-1)r$ が答え。

#include <bits/stdc++.h>
using namespace std;

double solve(int n, int m, int d){
    double r = (d == 0) ? 1.0 / n : 2.0 * (n - d) / n / n;
    return r * (m - 1);
}

int main() {
    int n, m, d; cin >> n >> m >> d;
    printf("%.10f\n", solve(n, m, d));
    return 0;
}

→AC
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2814599 (long double)
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2828551 (double)
精度はdoubleで十分だった。

★前後の文脈は無視できる★

全てを足し合わせると結局前後の文脈が関与しない結果になる（ので場合分け不要）
区間の確率を求めることができるなら、文脈はそれに織り込まれている

ということか。

（・・・そうなのか？）

状態遷移を考えて解く

上述の解法がどうも腑に落ちていないので、本番中にやりたかった（けど挫折した）方法をベースに整理。

左から数列を伸ばしていくとして、最後の数（最大通りある）をその次に美しい組が何通りあり得るか（0〜2）によってグループに分ける。
- $\sum_{i=0}^{2}|G_i|=n$
（グループi→グループjの遷移確率 $r_ij$ ）をそれぞれ考えて、初期値からm-1回遷移したらどうなるか考える
の場合
- $|G_0|=0, |G_1|=n, |G_2|=0$
の場合
- $|G_0|=0, |G_1|=2d, |G_2|=n-2d$
の場合（これは上か下のケースに含めてしまってもよい）
- $|G_0|=0, |G_1|=n, |G_2|=0$
の場合
- $|G_0|=2d-n, |G_1|=2(n-d), |G_2|=0$
グループi→グループjの遷移確率は（遷移元とは無関係に）遷移先グループの大きさに比例する（ので、これを単にと表記することにする）。
- $r_0:r_1:r_2=|G_0|:|G_1|:|G_2|$
- $\sum_{i=0}^{2}|G_i|=n, \sum_{i=0}^{2} r_i=1$ より $r_i=\frac{|G_i|}{n}$
初期値もグループの大きさに比例（ $x_i^{(0)} = r_i$ ）
m-1回遷移した後の状態（ $x_i^{(m-1)}$ ）が知りたい

$\displaystyle \left( \begin{array}{c} x_0^{(m-1)} \\ x_1^{(m-1)} \\ x_2^{(m-1)} \end{array} \right) = \left( \begin{array}{ccc} r_0 & r_0 & r_0 \\ r_1 & r_1 & r_1 \\ r_2 & r_2 & r_2 \end{array} \right) ^{m-1} \left( \begin{array}{c} x_0^{(0)} \\ x_1^{(0)} \\ x_2^{(0)} \end{array} \right)$
（ツッコミは後で）

この問題で求めたい答えは

$\displaystyle S=\mathbb{E}[\sum_{k=1}^{m-1}(各区間の美しさ)] = \sum_{k=1}^{m-1}\mathbb{E}[(各区間の美しさ)] = \sum_{k=1}^{m-1}\sum_{i=0}^{2}\frac{i}{n}\cdot x_i^{(k)}$
これも行列に含めてしまうことが出来る。
（↑ $\frac{i}{n}$ は、各状態から伸びるn本のペアのうちi件が美しい、という率を表している）

$\displaystyle \left( \begin{array}{c} x_0^{(m-1)} \\ x_1^{(m-1)} \\ x_2^{(m-1)} \\ S^{(m-1)} \end{array} \right) = \left( \begin{array}{cccc} r_0 & r_0 & r_0 & 0 \\ r_1 & r_1 & r_1 & 0 \\ r_2 & r_2 & r_2 & 0 \\ 0 & \frac{1}{n} & \frac{2}{n} & 1 \end{array} \right) ^{m-1} \left( \begin{array}{c} x_0^{(0)}=r_0 \\ x_1^{(0)}=r_1 \\ x_2^{(0)}=r_2 \\ S^{(0)}=0 \end{array} \right)$

あとは行列演算。（べき乗を高速に行うことでO(log m)で計算できる）

double solve(int n, int m, int d){
    double r0 = 0, r1 = 0, r2 = 0;
    if (d == 0) {
        r1 = 1.0;
    } else if (d*2 < n) {
        r1 = 2.0*d/n;
        r2 = 1.0 - r1;
    } else if (d*2 == n) {
        r1 = 1.0;
    } else { // d*2 > n
        r1 = 2.0*(n-d)/n;
        r0 = 1.0 - r1;
    }
    vector<vector<double>> A = {
         { r0, r0, r0, 0 },
         { r1, r1, r1, 0 },
         { r2, r2, r2, 0 },
         { 0, 1.0/n, 2.0/n, 1 }
    };
    vector<double> x = { r0, r1, r2, 0 };

    vector<vector<double>> Ak = mat_pow(A, m-1); // Ak = A^(m-1)
    vector<double> y = mat_mul(Ak, x); // y = Ak*x

    return y[3];
}

int main() {
    int n, m, d; cin >> n >> m >> d;
    printf("%.10f\n", solve(n, m, d));
    return 0;
}

→AC
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2828536 (long double)
https://beta.atcoder.jp/contests/soundhound2018-summer-qual/submissions/2828546 (double)
精度はdoubleで十分だった。

ちょっと待てよ

この解法は少し手間がかかるものの納得しやすいし、迷ったらさくっとこれで書いてしまえばいいかもと思ったんだけど*1、よく見てみると

この行列演算。 $\sum_{i=0}^{2} x_i^{(0)} = \sum_{i=0}^{2} r_i = 1$ なのだから、何回回しても $x_i^{(k)} = r_i$ になるのではあるまいか。

とすると
$\displaystyle \left( \begin{array}{c} x_0^{(m-1)} \\ x_1^{(m-1)} \\ x_2^{(m-1)} \\ S^{(m-1)} \end{array} \right) = \left( \begin{array}{cccc} r_0 & r_0 & r_0 & 0 \\ r_1 & r_1 & r_1 & 0 \\ r_2 & r_2 & r_2 & 0 \\ 0 & \frac{1}{n} & \frac{2}{n} & 1 \end{array} \right) ^{m-1} \left( \begin{array}{c} x_0^{(0)}=r_0 \\ x_1^{(0)}=r_1 \\ x_2^{(0)}=r_2 \\ S^{(0)}=0 \end{array} \right)$
この式も、
$\displaystyle \begin{array}{rcl} S^{(m-1)} &=& \sum_{k=1}^{m-1} \sum_{i=0}^{2} \frac{i}{n}\cdot x_i^{(k)} \\ &=& \sum_{k=1}^{m-1} \sum_{i=0}^{2} \frac{i}{n}\cdot r_i \\ &=& \sum_{k=1}^{m-1} \frac{1}{n}\cdot r_1+\frac{2}{n}\cdot r_2 \\ &=& (m-1)(\frac{1}{n}\cdot r_1+\frac{2}{n}\cdot r_2) \end{array}$
を求めているにすぎない。
また、右辺の $\sum_{i=0}^{2} \frac{i}{n}\cdot r_i$ というのは隣接するペアが美しいペアである確率を前のグループを周辺化（積分消去）することによって得たものに等しい。
∵ $\displaystyle p(美しい)=\sum_{i=0}^{2} p(美しい|前のグループ=i)p(前のグループ=i)=\sum_{i=0}^{2} \frac{i}{n}\cdot r_i$

具体的な $r_i$ の値を代入して $r=\frac{1}{n}\cdot r_1+\frac{2}{n}\cdot r_2$ を求めてみよう。

の場合
- $r_0=\frac{|G_0|}{n}=0, r_1=\frac{|G_1|}{n}=\frac{n}{n}=1, r_2=\frac{|G_2|}{n}=0$
- ∴ $r=\frac{1}{n}\cdot r_1+\frac{2}{n}\cdot r_2 = \frac{1}{n}\cdot 1+\frac{2}{n}\cdot 0=\frac{1}{n}$
の場合
- $r_0=\frac{|G_0|}{n}=0, r_1=\frac{|G_1|}{n}=\frac{2d}{n},, r_2=\frac{|G_2|}{n}=\frac{n-2d}{n}$
- ∴ $r=\frac{1}{n}\cdot r_1+\frac{2}{n}\cdot r_2 = \frac{1}{n}\cdot \frac{2d}{n}+\frac{2}{n}\cdot \frac{n-2d}{n} =\frac{2d+2(n-2d)}{n^2} = \frac{2(n-d)}{n^2}$
の場合（これは上か下のケースに含めてしまってもよい）
- $r_0=\frac{|G_0|}{n}=0, r_1=\frac{|G_1|}{n}=\frac{n}{n}=1, r_2=\frac{|G_2|}{n}=0$
- ∴ $r=\frac{1}{n}\cdot r_1+\frac{2}{n}\cdot r_2 = \frac{1}{n}\cdot 1+\frac{2}{n}\cdot 0=\frac{1}{n}$
の場合
- $r_0=\frac{|G_0|}{n}=\frac{2d-n}{n}, r_1=\frac{|G_1|}{n}=\frac{2(n-d)}{n}, r_2=\frac{|G_2|}{n}=0$
- ∴ $r=\frac{1}{n}\cdot r_1+\frac{2}{n}\cdot r_2 = \frac{1}{n}\cdot \frac{2(n-d)}{n}+\frac{2}{n}\cdot 0 = \frac{2(n-d)}{n^2}$

結局、最初の
$$ \begin{equation}
r=\begin{cases}
\frac{1}{n} & \text{d=0のとき} \\
\frac{2(n-d)}{n^2} & \text{それ以外のとき}
\end{cases}
\end{equation} $$

に行き着き、これに区間数 $m-1$ を掛けた $(m-1)r$ が答え。

確かに前の状態に依存しているのだけれど、この場合 p(前のグループ=i) が遷移によって変化しないので p(美しい) は定数になる。あとはステップ数を掛けるだけで良い、ということ。

ようやく腑に落ちた。

chokudaiさんの固定ツイートの「入れ替わってるー！？」問題

↓これです

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

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

$$ \mathbb{E}[\sum(所定の位置にあれば1)] = \mathbb{E}[\sum(所定の位置にある率)]=\sum\mathbb{E}[(所定の位置にある率)] $$

ってのは分かるんだけど自分で正しく計算できてなかったので、ふるやん先生の解説を手本にしつつ整理。

N個の要素のどれを見ても、所定の位置にある率は同じ
1回の試行における（home:所定の位置にある）←→（away:所定の位置にない）の遷移確率は求められる
- 全部で $_NC_2$ 通りのチョイスがある
- home→away: (自分, N-1通りの行き先) を選んだ場合なので $\frac{N-1}{_NC_2}=\frac{2}{N}$
- home→home: 1 - (home→away)= $1-\frac{2}{N}$
- away→home: (そこ, 自分) を選んだ場合なので $\frac{1}{_NC_2}=\frac{2}{N(N-1)}$
- away→away: 1 - (away→home)= $1-\frac{2}{N(N-1)}$
その試行をM回やった後に所定の位置にある確率
- 行列演算で求める

$$
\begin{array}{rcl}
A &=& \left(\begin{array}{cc}
1-\frac{N-1}{_NC_2} & \frac{N-1}{_NC_2} \\
\frac{1}{_NC_2} & 1-\frac{1}{_NC_2}
\end{array} \right) \\
&=& \left( \begin{array}{cc}
1-\frac{2}{N} & \frac{2}{N} \\
\frac{2}{N(N-1)} & 1-\frac{2}{N(N-1)}
\end{array} \right) \\
\left(\begin{array}{c}
x_1^{(m)} \\
x_0^{(m)}
\end{array} \right) &=& A^m \left(
\begin{array}{c}
x_1^{(0)} \\
x_0^{(0)}
\end{array} \right) = A^m \left(
\begin{array}{c}
1 \\
0
\end{array} \right)
\end{array}
$$
求める値は
$$ \mathbb{E}[N\cdot x_1^{(m)}] = N\cdot\mathbb{E}[x_1^{(m)}] $$
である。

*1:もう少し複雑な問題だったらこういう解法の出番もありそう

naoya_t@hatenablog

いわゆるチラシノウラであります