確率変数Xのモーメント母関数\(M_X(t)\)を\(M_X(t)=E[e^{tX}]=\sum \frac{t^k}{k!}E[X^k]\)と置く。表がp, 裏が1-pの確率で出るコインを裏が出るまで投げるときの、表が出る回数をXと置く。このとき、\(M_X=pe^tM_X+1-p\)となるので、\(M_X=\frac{1-p}{1-pe^t}\)である。独立な2つの確率変数\(X, Y\)の和について、\(M_{X+Y}=M_XM_Y\)が成り立つ。N次式 \(f(t)\) から \(f(e^t)\) を M次まで求めることは、\(O(N\log(N)^2+M\log(M))\)でできる。モーメント母関数が有理式に\(e^t)\)を代入した形のときはこのテクニックが使える。

全ての目が出る確率が等しい N 面サイコロがあります。このサイコロを、全ての目が出るまで振り続けます。1≤i≤M を満たす整数 i に対して、サイコロを振る回数の i 乗の期待値を列挙せよ（ARC154F）

長さNの順列の転倒数の個数の期待値の i 乗を列挙せよ。

\(1,2,\ldots,N\)が書かれた\(N\)枚のカードと、ジョーカーが書かれた\(M\)枚のカードの集合\(A\)がある。ジョーカーが出るまで、\(A\)からランダムにカードを取り出す。ジョーカーが出たら、全てのカードを\(A\)に戻す。ジョーカーを取り出したとき、\(1,2,\ldots,N\)が書かれたカードを全て取り出したことがあるなら操作を終える。操作回数の期待値を求めよ(CF1392H)

ジョーカーを引くまでの操作回数の期待値は、\(\frac{n}{m+1}\) である。残り\(k\)種類を引かないといけないときの、ジョーカーを引く回数の期待値\(I_k\)は\(I_k=\frac{k}{k+m}I_{k-1}+\frac{m}{k+m}(I_k+1)\) を解いて \(I_k = m\left(\frac{1}{k}+\frac{1}{k-1}+\ldots+\frac{1}{1}\right)\)である。マルチンゲールでもよい。Waldの補題より答えは、\(\frac{n}{m+1}I_m\)

\(+1,-1\)をそれぞれ確率 \(p, q \) で取るランダムな列 \((X_i)\) とその累積和の列 \((M_i)\) を定義する列とする。
次のようなマルチンゲールがある。

• \(M_k-k(p-q)\)
• \(p=q=1/2\) のとき \(M_k^2-k\)
• \(e^{\sigma M_k}\left(\frac{1}{pe^{\sigma}+qe^{-\sigma}}\right)^k\)

まず \(p=q=1/2\) の場合を考える。

\(\mathbb{E}\left[e^{\sigma M_k}\left(\frac{2}{e^{\sigma}+e^{-\sigma}}\right)^k\right] = 1\) より \(\tau\) を \(M_i = 1\) となる停止時刻とするとすると \(\mathbb{E}\left[e^{\sigma M_{k \land \tau}}\left(\frac{2}{e^{\sigma}+e^{-\sigma}}\right)^{k \land \tau}\right] = 1\)。これより、\(\mathbb{P}\{\tau < \infty\} = 1\) である。従って、\(\mathbb{E}\left[\left(\frac{2}{e^{\sigma}+e^{-\sigma}}\right)^{\tau}\right] = e^{-\sigma} \)とできる。\(\alpha = \frac{2}{e^{\tau+e^{-\tau}}} \in (0, 1)\) と変数変換すると \(\mathbb{E}[\alpha^\tau] = \frac{\alpha}{1+\sqrt{1-\alpha^2}}\)。ここから\(\lim_{\alpha \rightarrow 1}\mathbb{E}[\frac{d}{d\alpha}\alpha^\tau] = \mathbb{E}[\tau] = \infty\)が得られる。停止時刻 \(\tau = \min\{k : M_k \not\in (-a, b)\}\) とする。すると、\(0 = ap + qb\) より \(p=\frac{b}{a+b}, q=\frac{a}{a+b}\) となる。\(\mathbb{E}[M_\tau^2] = \mathbb{E}[\tau]\) より \(\mathbb{E}[\tau]=ab\) となる。
\(p \neq q\) とする。\(e^\sigma = \frac{1-p}{p}\) とすると、\(\left(\frac{1-p}{p}\right)^{M_k}\) はマルチンゲールである。\(p < q\) のとき \(\mathbb{E}[M_{k\land \tau }-{(k\land \tau)}(p-q)] = 0\)より \(\mathbb{E}[\tau] = \frac{1}{q-p}\) である。停止時刻 \(\tau = \min\{k : M_k \not\in (-a, b)\}\) とする。すると、\(x=\mathbb{P}\{M_\tau=-a\}\) とする。\((q/p)^\tau = (q/p)^a x+(q/p)^{-a} (1-x)\) よりこれを解くと \(x\) が得られる。

\(\mathbb{Z}\) 上で 0 を始点としてランダムウォークして、\(-a,b\) (\(a,b > 0\)) で停止する場合の移動回数の期待値を求める。i から i +1, i-1 へ移動する回数の期待値を \(L_i, R_i\) と置く。マルチンゲールより \(L_{a-1}=\frac{b}{a+b}, R_{-b+1}=\frac{a}{a+b}\) が分かり、端から計算することで、全ての\(L_i,R_i\)が求まる。

ランダムにアルファベット \(\Sigma\) を並べていったとき、与えられた文字列 \(s\) が suffix に表れるまでの文字数の期待値 \(\tau\) を求めたい。\(s\) の境界の集合を \(\mathrm{Boder}(s)\) と置く。次のような状況を考える。

• 文字を一つ追加する直前に、賭け師が一人追加される。この賭け師はこれから追加される文字のみからなる文字列が \(s\) をなすと予想している。そして、文字の追加のたびにその予想に対して全財産（最初は1円）を賭ける。予想が当たると \(|\Sigma|\) 倍されて返ってくる。この賭けの期待値は \(0\) である。

時刻 \(\tau\) の時点で賭けられた総額は \(\tau\) なので
\(\mathbb{E}(\tau) = \sum_{w \in \mathrm{Border}(s)}|\Sigma|^{|w|}\) である。

木の上のランダムウォークにおいて、始点から終点までの移動時間の期待値は \(O(N)\) で計算できる。これの拡張として、複数の終点がある場合や、始点に戻る辺を \(O(N)\) 個追加した場合（ABC189F）が考えられるがいずれもガウスの消去法により \(O(N)\) になる。始点に戻る辺を追加した場合は、始点から終点までの移動時間の期待値を \(x\) と置いて方程式を解いていけばよい。

\([0, 1]\)上の一様分布に従う\(n\)点\(x_1, x_2, \ldots, x_n\)を考える。\(k\)番目に小さい点の期待値は\(\frac{k}{n+1}\)になる。これは、1点\(x_{n+1}\)を付け足した時、この点が小さい方から\(1,2,\ldots,k\)番目のいずれかにある確率と等しいことから分かる。単位円上の一様分布において、隣り合う2点の距離の最小値の期待値は\(1/n^2\)である。これは、最小値が\(x\)以上である確率が\(f(x)=(1-xn)^n\) なので、\(\int_{0}^{1/n} f(x)dx=1/n^2\)より分かる。

\begin{align}
\mathrm{kthmax}(S) &=\sum_{\emptyset \neq T \subseteq S} {|T|-1 \choose k-1}(-1)^{|T|-k}\min(T) \\
&=\sum_{\emptyset \neq T \subseteq S} (-1)^{|T|-k}\min(T) \#\{Q : Q \subseteq T \setminus \{\min(T)\}, \#Q = k-1 \}\\
\end{align}

\(v = \max(S \setminus \{Q \cup \min T\})\) と置く。\(v > \min T\) について \(T \leftarrow T \Delta \{v\}\) とする。\(\{Q \cup \min T\}\) が上位k個でなければ、このような操作ができる。この操作は対合をなすので上記の式が成り立つ。

S の要素を降順に \(a_0, a_1, …, a_{n-1}\) とします。
\begin{align}
&(左辺)\\
=& [x^k] \sum_{i} a_i x^i\\
=& \sum_{i} a_i [x^k] (1 + (x – 1))^i
\end{align}

\((1 + (x – 1))^i\) を二項展開すると「a_i 超の要素からいくつか選び (T \ min(T))、そこからさらにいくつか選び (binom(|T|-1, k))、になるので右辺です。

\(g(S) = \sum_{S \subseteq T} f(T), f_i = \sum_{\#S = i} f(S), g_i = \sum_{\#S=i}g(S)\) と置く。
\(\sum f_i x^i = \sum g_i(x-1)^{i}\) より
\begin{align}
[x^{k-1}]\frac{1}{1-x}\sum f_i x^i &= -[x^{k-1}]\sum g_i(x-1)^{i-1} \\
&= g_0- \sum_{i}g_i{i-1 \choose k-1}(-1)^{i-k}
\end{align}

よって、\(\sum_{i \geq k} f_i = \sum g_i {i – 1 \choose k – 1}(-1)^{i-k}\) である。

\(g(S) = \min(S)\) とすると、
\begin{align}
\sum_{\substack {S \subseteq T\\ \#S \geq k}} \min(T)(-1)^{\#T-\#S} &= \sum_{\#S = i} {i – 1 \choose k – 1}(-1)^{i-k} \min(S) \\
&= \operatorname{kth-max}(T)
\end{align}

\(n\) 頂点の根付き木が与えられる。根を始点としてランダムウォークしたとき、頂点部分集合 \(S\) の点を全て訪れるのにかかる時間の期待値を \(O(n2^n)\) で求めよ（PKUWC2018 随机游走）。

\(n\) 種類の要素がそれぞれ決まった確率で出てくるガチャがある。そのうち \(k\) 種類の要素を集めるには何回ガチャを回す必要があるか、期待値を求めよ（Luogu 4707 重返现世）

サイズ n の多重集合 S が与えられる。S のランダムな部分多重集合 T を選んで T を [n] の |T| 元部分集合で置き換える。ただし、置き換えた |T| 元部分集合は要素の重複がないとする。Sの要素が全て同じになるまでの操作回数の期待値を求めよ。O(n^2)。（ABC249H）

n頂点n-1辺の辺重み付きグラフが与えられる。各辺には重み1か2が割り当てられている。1つの辺をランダムに削除して、同じ重みの辺を（多重辺、ループができないように）追加する。削除する辺は辺の重みに比例した確率で選ばれる。\(K_{1, n-1}\) と同型になるまでの操作回数の期待値を求めよ. O(n^3). (yuki1784)。

確率pで赤玉、qで青玉、r=1-p-qで緑玉が出る。赤玉と青玉のどちらかN個出るまで操作する。操作回数の期待値を求めよ。O(n)。(M-SOLUTIONS C)

\(H \times W\) の重み付きグリッドグラフ上の各点に対して、点 s に到達するまでの時間の期待値は O(min(H,W)HW) で列挙できる。これは、点 s を含む一列（または一行）の点からの訪問時間を変数とすると、そのほかの点の期待値が、これらの線形結合で書けるためである。

マルコフ連鎖の遷移確率行列を \(P\) として、
\(P \pi = \pi\)を満たす状態 \(\pi\) を定常状態と呼ぶ。マルコフ連鎖をグラフで表したとき、連結グラフ \(G\) だとする。\(\pi_i = \frac{\mathrm{deg}(i)}{2 ||G||}\) は定数倍の違いを除き唯一の定常状態である。\(1/\pi_i\)は \(i\) から出発して再度 \(i\) に戻るまでの平均時間と等しく、\(\pi_i\) を \(i\) に滞在する平均時間と等しい。二つの定常状態 \(a, b\) があったとすると、\(a, b\) の凸結合であって、ある要素が 0 になるものがある。凸結合もまた定常状態であるから、全ての要素が 0 になり、定常状態は一意である。

\(i\) から \(i \oplus j\) (排他的論理和）への遷移確率(\(0 \leq j
< 2^n\)) が \(p_j\) で与えられるとき、\(0\) から \(i\) まで到達するまでの遷移回数の期待値 \(E_i\) を各 \(i\) について列挙せよ(AGC034F)。

\begin{eqnarray}
E_i
=
\begin{cases}
1+\sum_{j} E_{i \oplus j} p_j & ( i \neq 0 ) \\
0 & ( i = 0 )
\end{cases}
\end{eqnarray}
平均再帰時間は \(2^n\) なので \(v=(2^n-1,1,1,\ldots,)\) と置くと、\(E=v+E*p \iff E=v*(1-p)^{-1}\) と書ける。ただし、\(*\) は xor 畳み込み。群上のランダムウォークへの一般化

すごろくがある。1,2,..,Mの目が出るさいころを振る。いくつかのマスは踏むと最初のマスに戻る。先頭からN個目以上のマスに初めて到達するまでの時間の期待値を O(N) で求めよ(ABC189F)。累積和を使うと良い。

M個の区間が与えられる。これらの区間をランダムに選ぶことを繰り返す。選んだことがある区間の和集合が [1, N] になったら操作を停止する。操作回数の期待値を O(M^2 log N) で求めよ。（ABC242Ex）

長さnの円環からランダムに長さmの区間を選ぶことを繰り返す。選んだことのある区間の和集合が円環を覆うまで操作を続ける操作回数の期待値を O(N log N) で求めよ（nadafes2022day2P）

N 個の連続確率変数 X_1, .., X_N があり、 X_i は [L_i, R_i] 上の一様分布に従う。N 個の確率変数のうち大きい方から K 番目の値の期待値を O(N^3) で求めよ（ABC226H）。

赤玉が a 個、青玉が b 個入っている袋がある。玉をランダムに選び、選んだ玉と同じ色の玉を k 個加えることを繰り返す。n 回目の操作で赤玉が出る確率 \(p_n = a / (a + b)\) である。これは、取り出した玉が n-1 回目に追加した玉かどうかで場合分けすればよい。n-1回目に追加した球をn回目に引く確率を \(q_n\) とすると、\(p_n=p_{n-1}q_n + p_{n-1}(1-q_n) = p_{n-1}\) となる（ポリアの壺）。

Waldの補題：\(X_1, X_2, \ldots\) を同一の分布に従う互いに独立な確率変数、Nを停止時間とする。\(\mathbb{E}(\sum_{i=1}^NX_i)=\mathbb{E}[N]\mathbb{E}[X]\)となる。証明：\(i\leq N\) であるかが \(X_1,\ldots,X_{i-1}\) で決まり、\(X_i\) とは独立だから。

\(N\) 色のボールが入ったガチャがある。全ての色が揃うまでガチャを回す。ただし、各 \(i\) について、色 \(1, 2, \ldots, i\) のボールを引いたことがある場合、\(i\) 番目の色のボールは出なくなる（☆）。色 \(N\) のボールを引く回数の期待値を求めたい。ボールが出なくなるのではなく、星を満たす色 \(i\) のボールを引いても試行回数に含めないことにしてもよい。その場合、色 \(N\) のボールが出る確率は \(1/N\) で一定なので、色 \(N\) のボールを引く回数の期待値は \(\frac{1}{1}+\frac{1}{2}+\cdots+\frac{1}{N}\) になる(ARC150D)。

\(N\) 個の点を数直線上に打つ。\(i\) 番目の点 \(x_i\) は \([X_i, X_{i+1}]\) から選ぶ。各点間の距離の最小値の期待値を求めよ(ARC113F)。
\(y_i = x_i + iw\) と置くと、\(x_i + w \leq x_{i+1} \) は \(y_i \leq y_{i+1}\) となる。また、\(x_i \in [X_i, X_{i+1}] \iff y_i \in [X_i + iw, X_{i+1} + iw]\) である。距離 w 以上離れている確率を DP で求める。

[0,1]上の一様乱数の列 \(X_1, X_2, \ldots\) について、n を \(X_1 \leq X_2 \leq \cdots X_n > X_{n+1}\) で定義する。\(\sum_{i=1}^n X_i / 2^i\) を求めよ。
\(\sum_i P[X_1 \leq X_2 \leq \cdots X_i] E[X_i|X_1 \leq X_2 \leq \cdots X_i] / 2^i\)と書けて、\(\mathbb{P}[X_1 \leq X_2 \leq \cdots X_i]=1/i!, E[X_i|X_1 \leq X_2 \leq \cdots X_i] = i / (i+1)\) となることから計算できる（putnum2022A4）

遷移確率がn項間漸化式で表される状態があるとする（nは小さい）。10^9の倍数項目が停止状態である。停止時間の期待値を求めよ。（ABC299H, yuki）

確率pで当たりが出るアイスがある。アイスを100個食べるまでに購入するアイスの個数の期待値は（AtC）？
方針１：\(\(\frac{d}{dx}|_{x=1}[y^n] xy \frac{1}{1-\frac{qxy}{1-py}}\frac{1}{1-py}\)\)
方針２：各アイスが購入したアイスである確率を求める。