積の和典型とは
積の和典型とは、『何かに関する積の和はいくらか？』という問題を『何かからそれぞれ1つずつ選ぶ方法は何通りか？』と読み替える技法です 。
積の和典型の名を有名にしたブログ では、これをさらに「色を塗るパターン数」に言い換えています。
ところで、積の和典型と呼ばれる問題にもいくつかの種類があります。
- 和が N になる M 項の非負整数列のスコアを、各整数の積と定める。ありうる数列のスコアの和を求めよ。
-
X_i は 0 から A_i の値を一様にとる独立な確率変数である。(X_1 + \cdots + X_n)^2 の期待値を求めよ。
- 平面上の点のスコアを x 座標と y 座標の値の積とする。点 (x_0,y_0) からランダムに上下左右に移動する操作を N 回繰り返したとき、スコアの期待値を求めよ。
この記事の目的は、問題 2., 3. に相当する「独立な変数を足し合わせるタイプの問題」を次のように理解することです。
- 独立な変数はバラして、独立でない部分は全ての情報を持つことで計算できる
- 上記のプロセスが問題に応じた種類の畳み込みで表現できる
持つべき情報やその計算のまとめ方という意味では、DP にも応用が効く考え方です。
なおこの記事は、以下で紹介する個別の問題の各解説を大いに参考にしています。
二乗の和・期待値
例題
独立な確率変数 X,Y が与えられる。Z = X+Y として、Z^2 の期待値 \mathbb{E}[Z^2] を求めよ。
解説
独立性を利用して素直に計算をばらしていくと次のようになる。
\mathbb{E}[Z^2] = \mathbb{E}[X^2 + 2XY + Y^2] = \mathbb{E}[X^2] + 2\mathbb{E}[X]\mathbb{E}[Y] + \mathbb{E}[Y^2]
つまり、問題で問われているのは二乗の期待値だが、その計算には二乗だけでなく一乗・ゼロ乗の期待値
\mathbb{E}[1],\mathbb{E}[X],\mathbb{E}[X^2]
および
\mathbb{E}[1],\mathbb{E}[Y],\mathbb{E}[Y^2]
の情報が全て必要である。
例題
X_i は 0 から A_i の値を一様にとる独立な確率変数である。(X_1 + \cdots + X_n)^2 の期待値を求めよ（n \le 10^5）。
解説
S_k = X_1 + \cdots + X_k とする。1,\mathbb{E}[S_k],\mathbb{E}[S_k^2] を持って DP すればよい。
問題例
ネタバレ注意
K乗の和・期待値
例題
正整数 K および独立な確率変数 X,Y が与えられる。Z = X+Y として、Z^K の期待値 \mathbb{E}[Z^K] を求めよ。
解説
同様に考えると
\mathbb{E}[Z^K] = \sum_{i=0}^K\binom{K}{i}\mathbb{E}[X^i]\mathbb{E}[Y^{K-i}]
である。ここで両辺を
K! で割ることにより
\dfrac{1}{K!}\mathbb{E}[Z^K] = \sum_{i=0}^K \dfrac{1}{i!}\mathbb{E}[X^i] \dfrac{1}{(K-i)!}\mathbb{E}[Y^{K-i}]
となる。
つまり、二つの数列
\left(\mathbb{E}[X^0],\frac{\mathbb{E}[X^1]}{1!},\frac{\mathbb{E}[X^2]}{2!}\frac{\mathbb{E}[X^3]}{3!},\dots \right), \qquad
\left(\mathbb{E}[Y^0],\frac{\mathbb{E}[Y^1]}{1!},\frac{\mathbb{E}[Y^2]}{2!}\frac{\mathbb{E}[Y^3]}{3!},\dots \right), \qquad
を畳み込むことで
\left(\mathbb{E}[Z^0],\frac{\mathbb{Z}[X^1]}{1!},\frac{\mathbb{E}[Z^2]}{2!}\frac{\mathbb{E}[Z^3]}{3!},\dots \right) を得る。つまり指数型母関数のフォーマットに乗る。
これはモーメント母関数 M_X(t) = E[e^{tX}] のマクローリン展開の係数を並べたものとしても理解できる。
問題例
ネタバレ注意
ベクトルの和の成分積
例題
二つの独立な確率変数 X = (X_1,\dots,X_n) と Y = (Y_1,\dots,Y_n) が与えられる。 Z_i =X_i+Y_i として、\mathbb{E}[Z_1\cdots Z_n] を求めよ。
解説
添字集合 u に対して X_u = \prod_{i \in u} X_i とおく（Y_uも同様）。また -u で u の補集合を表す。先ほどと同様に、独立性を利用して素直に計算をばらしていくと次のようになる。
E[Z_1 \dots Z_n] = \mathbb{E}[(X_1+Y_1)\cdots(X_n+Y_n)] = \sum_{u}\mathbb{E}[X_uY_{-u}] =\sum_{u}\mathbb{E}[X_u]\mathbb{E}[Y_{-u}]
これ以上は分解できない。つまりすべての部分集合 u について E[X_u] およびE[Y_u]の情報をもつことで、全てのE[Z_u]が計算できるという構造になっている。
この計算は、集合べき級数 (set power series) により形式化できる。
F_X = \sum_{u} \mathbb{E}[X_u]u, \qquad F_Y = \sum_{u} \mathbb{E}[Y_u]u とおく。このときベクトル値確率変数
Z に対応する集合べき級数
F_Z = \sum_{u} \mathbb{E}[Z_u]u は、まさに
F_X と
F_Y の subset convolution である。
問題例・解説
ネタバレ注意
解説
本質的には上の解説で解けている。具体的には、 F_X = \sum_{u} \mathbb{E}[X_u]u の各係数\mathbb{E}[X_u]を計算したあと、
F_X + F_X^2 + \cdots + F_X^{N} を求めればよい（ただし積は subset convolution）。
これは繰り返し二乗法で求まる（より高速に計算する方法があるらしい）。
ベクトルの和の成分積：対称性がある場合
例題
二つの独立な確率変数 X = (X_1,\dots,X_n) と Y = (Y_1,\dots,Y_n) が与えられる。Z_i =X_i+Y_i として、\mathbb{E}[Z_1\cdots Z_n] を求めよ。
ただし、確率変数には対称性があり、\mathbb{E}[X_u]や\mathbb{E}[Y_u]は添字集合 u のサイズのみに依存すると仮定する。
解説
対称性を持つ集合べき級数は、指数型母関数により表現されることはよく知られている。
つまり
\begin{align*} F_X(x) &= \sum_j \dfrac{\mathbb{E}[X_1\cdots X_j]}{j!}x^j \\F_Y(x) &= \sum_j \dfrac{\mathbb{E}[Y_1\cdots Y_j]}{j!}x^j\\ F_Z(x) &= \sum_j \dfrac{\mathbb{E}[Z_1\cdots Z_j]}{j!}x^j \end{align*}
と定めると、
F_Z(x) = F_X(x)F_Y(x) \bmod x^{n+1}
が成り立つ。
よって求めたい値は指数型母関数の畳み込みとして計算できる。
問題例
ネタバレ注意
Discussion