chokudai先生(@chokudai)の固定ツイートに記述されているネタが古い問題の解法解説記事が無いっぽいので、書いてみます。
前回に引き続き確率の問題ですね。
自分も解けているのか自信が無いので、ここの解法はおかしいとか、別の解法を思いついたという方は@furuya1223までリプライくれると嬉しいです。
問題は以下の通りです。
要素i「これってもしかして」
要素j「私達の場所が」
「「入れ替わってるー！？」」ぼく「このように、N個の要素から二つを選びswapする、という行為をM回繰り返した時、元々あった場所に存在する要素の個数の期待値を出力せよ。出力の相対誤差は10^-6までは許容される。」
— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2016年9月23日
制約つけとこ
20点: N,M≦8
40点: N≦8, M≦100
60点: N≦1,000 M≦10^12
100点: N,M≦10^12
面倒だから誤差は出ないものとして良い。1CPUで実行時間制限は2秒— chokudai(高橋 直大)🍆🍡🌸 (@chokudai) 2016年9月23日
満点制約は、O(N), O(M)等の線形オーダーが間に合いません。
頑張りましょう。
目次
期待値の線形性を利用
聞かれているのは、「元の位置にある要素の個数の期待値」です。
これは、各要素について「最終的に元の位置にあれば1、そうでなければ0」となるような確率変数X_iを考えると、元の位置にある要素がk個の場合に
$$\sum_{i=1}^NX_i=k$$
となります。
したがって、求める期待値は
$$E \left [ \sum_{i=1}^NX_i \right ]=\sum_{i=1}^NE\left [X_i\right ]$$
となります。期待値には線形性が成り立つので、和は外に出せます。和の期待値は期待値の和。期待値の線形性は、確率変数が独立でない場合にも成立します。
今、全てのX_iは特に振る舞いに違いが無い（どの位置の要素も対等にswapされうる）ので、E[X_i]は全てのiで等しいです。
これを求めましょう。
ここで、X_iは、「要素iが最終的に元の位置にあれば1、そうでなければ0」となる確率変数なので、その期待値はすなわち「要素iが最終的に元の位置にある確率」になるはずです。
なぜなら、X_iは{0,1}のみを取り、E[X_i]=1*P(X_i=1)+0*P(X_i=0)=P(X_i=1)となるからです。
その確率を求めましょう。
ある要素が元の位置にある確率
要素1つを固定して考えるので、以降は要素に対してiという添字を使いません。先頭要素でも末尾要素でも何でもいいですが、1つのみを考えます。
n回swapを行った後に、注目要素が元の位置にある確率をp_nとおきます。p_nに関する漸化式を考えます。
注目要素が1回のswapに選ばれる確率は、N_C_2通りの組合せのうちN-1通りなので、(N-1)/N_C_2=2/Nです。
n回時点で要素が元の位置にある場合、swapに選ばれると確実に別の位置に移動します（確率2/N）。選ばれなければ、元の位置のままです（確率1-2/N）。
n回時点で要素が元の位置にない場合、swapで{現在位置,元の位置}の組合せが選ばれたときのみ、元の位置に戻ります（確率1/N_C_2=2/(N(N-1))）。
状態遷移イメージ
従って、以下の漸化式が成り立ちます。
$$p_{n+1}=\left ( 1-\frac{2}{N} \right )p_n+\frac{2}{N\left ( N-1 \right )}\left ( 1-p_n \right )$$
整理して、
$$p_{n+1}=\frac{N-3}{N-1}p_n+\frac{2}{N\left ( N-1 \right )}$$
これを解きます。
漸化式を解く（or行列累乗）
高校数学的に解くと、特製方程式の解1/Nを両辺から引いて
$$p_{n+1}-\frac{1}{N}=\frac{N-3}{N-1}\left ( p_n-\frac{1}{N} \right )$$
となり、明らかにp_0=1（0回swapした時点=swapする前に元の位置にある確率は1）なので、
$$p_{n}-\frac{1}{N}=\left ( p_0-\frac{1}{N} \right ) \left ( \frac{N-3}{N-1} \right )^n=\left ( 1-\frac{1}{N} \right )\left ( \frac{N-3}{N-1} \right )^n$$
となります。よって、
$$p_{n}=\frac{1}{N}+\left ( 1-\frac{1}{N} \right )\left ( \frac{N-3}{N-1} \right )^n$$
が得られます。
M回swapした時点で、ある要素が元の位置にある確率はp_Mなので、元の問題の解は
$$\sum_{i=1}^NE\left [X_i\right ]=Np_M=1+\left ( N-1 \right )\left ( \frac{N-3}{N-1} \right )^M$$
となります。
この値は、M乗の計算にO(logM)で計算できる高速な累乗法（名称あるのかな？）を用いることで、全体でO(logM)で解けるので、満点制約でも十分間に合いますね。
以上です。
漸化式を解きたくない場合は、適当なタイミングで行列累乗を用いることでもO(logM)で解けますね。
例えば、
$$p_{n+1}=\left ( 1-\frac{2}{N} \right )p_n+\frac{2}{N\left ( N-1 \right )}\left ( 1-p_n \right )$$
の段階で、
$$\begin{pmatrix}p_{n+1}\\ 1-p_{n+1}\end{pmatrix}=\begin{pmatrix}1-\frac{2}{N} & \frac{2}{N\left ( N-1 \right )}\\ \frac{2}{N} & 1-\frac{2}{N\left ( N-1 \right )}\end{pmatrix}\begin{pmatrix}p_{n}\\ 1-p_{n}\end{pmatrix}$$
が成立するので、2×2行列をAとおくと、p_Mは
$$A^M\begin{pmatrix}1\\ 0\end{pmatrix}$$
の第1要素として得られます。A^Mを高速な累乗計算で計算すれば、O(logM)です。
また、漸化式を整理した
$$p_{n+1}=\frac{N-3}{N-1}p_n+\frac{2}{N\left ( N-1 \right )}$$
の段階でも、
$$\begin{pmatrix}p_{n+1} \\ 1\end{pmatrix}=\begin{pmatrix}\frac{N-3}{N-1} & \frac{2}{N\left ( N-1 \right )}\\ 0 & 1\end{pmatrix}\begin{pmatrix}p_{n} \\ 1\end{pmatrix}$$
として、上記と同じように行列累乗で解くことができます。
でも、N<10^12なので、行列累乗だと極端に小さい値2/(N(N-1))があって誤差がきつそうですね。不安です。
さて、漸化式を解いて得られた解
$$\sum_{i=1}^NE\left [X_i\right ]=Np_M=1+\left ( N-1 \right )\left ( \frac{N-3}{N-1} \right )^M$$
をよく見ると、M→∞で期待値が1個になるようですね。これは、ぐちゃぐちゃに混ぜると、ある要素が配置される位置がN通り全て同様に確からしくなるので、p_∞=1/Nになることから理解できますね。
また、M=0の場合に、Nによらず期待値がNになることが分かります（ただし0^0=1）。当たり前ですね。swapする前には全要素が元の位置にあります。
N=3のとき、（M>0のとき）期待値が常に1になっていますね。漸化式にN=3を代入すると分かりますが、N=3のときのp_nは{1, 1/3, 1/3, 1/3, …}となるようです。面白いと思ったけどそうでもなさそう。
N=2のときは、右の項が負数の累乗になるので、正負がMに応じて入れ替わるようになりますね。期待値は2,0,2,0,…を繰り返します。2要素だと毎回swapが同じ組になるので、明らかですね。
という感じです。コードは実装していません。オンラインジャッジがあれば実装したいですね。
間違いとか別解とかがあれば教えてください。
では。