確率変数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)\)である。求める答えは、\(\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\) が得られる。

ランダムにアルファベット \(\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(T \setminus Q)\) について、\(v \in T \setminus Q\) のときは除き、さもなくば付け加える。\(v \neq \min(T)\) でなければ、このような操作ができる。また、この操作は対合をなすので上記の式が成り立つ。

以下、熨斗さんの証明。
S の要素を降順に a_0, a_1, …, a_{n-1} とします。
(左辺)
= [x^k] \sum_{i} a_i x^i
= \sum_{i} a_i [x^k] (1 + (x – 1))^i

(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 随机游走）。また、\(S\) のうち、\(k\) 番目に訪れる点の時間の期待値も求めよ。

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

始点 \(s\) から頂点 \(i\) に到達するまでの時間の期待値を \(E_i\) 、始点 \(s\) から頂点 \(1, 2, \ldots, n\) のいずれかに到達するまでの時間の期待値を \(F_0\) とする。また、頂点 \(i\) から頂点 \(j\) に到達するまでの時間の期待値を \(E_{ij}\) と置く(\(E_{ii}=0\))。\(\sum_{j}\) \(E_{ij}/n\) は \(i, j \ (i \neq j)\) に依らないとする。この値が \(i\) に依らないとき、\(F_1\) と置くと、
\(\sum_i E_i /n = F_0 + F_1\) が成り立つ。右辺は、頂点 \(1, 2, \ldots, n\) のいずれかに到達した後に、終点をランダムに選んでいると解釈できる。\(F_0\) の代わりに \(\sum_i E_i /n, F_1\) を計算する方が、終点が一つに定まるため、簡単なことがある。

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

n頂点n-1辺の辺重み付きグラフが与えられる。各辺には重み1か2が割り当てられている。
1つの辺をランダムに削除して、同じ重みの辺を（多重辺、ループができないように）追加する。削除する辺は辺の重みに比例した確率で選ばれる。

\(X\) が正整数を取る離散型確率変数であるとき、\(\mathbb{E}[X] = \sum_{i \geq 1} \mathbb{P}[X \geq i]\) が成り立つ。
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(HW) で列挙できる。これは、点 s を含む一列（または一行）の点からの訪問時間を変数とすると、そのほかの点の期待値が、これらの線形結合で書けるためである。

マルコフ連鎖の遷移確率行列を \(P\) として、
\(P \pi = \pi\)を満たす状態 \(\pi\) を定常状態と呼ぶ。\(1/\pi_i\)は \(i\) から出発して再度 \(i\) に戻るまでの平均時間と等しい。これは、\(1/\pi_i\) を \(i\) に滞在する時間と捉えると直感的である。

\(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 回目に取り出した玉かどうかで場合分けすればよい。そのようなことが起きる確率を \(q_n\) とすると、\(p_n=p_{n-1}q_n + p_{n-1}(1-q_n) = p_{n-1}\) となる（ポリアの壺）。

\(X_1, X_2, \ldots\) を同一の分布に従う互いに独立な確率変数とし、確率母関数が \(G_X\) で与えられるとする。また、\(X_1,X_2, \ldots\) とは独立な、確率母関数が \(G_N\) で与えられる確率変数 \(N\) を取る。\(T=X_1+X_2+\cdots+X_N\) とすると \(G_T(x)=G_N(G_X(x))\) である。また、\(T\) の期待値は
\begin{align}
\frac{d}{dx}|_{x=1}G_N(G_X(x))
=& G’_N(G_X(1))G’_X(1) \\
=& G’_N(1)G’_X(1) \\
=& \mathbb{E}[N]\mathbb{E}[X]
\end{align}
となる。

確率母関数には \(P[X=\infty] = 1-G_X(1)\) として埋め込まれていることに注意。

\(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\) のマスに順番に \(N\) 人が座りに来る（人は区別できない）。各人は両隣のマスに人がいないマスを選んで座る。座れる席がない場合立ち去る。これは、マスをランダムに選び、座ろうとしたマスの隣に既に誰かが座っている場合、座らずに立ち去ると言い換えても、生成される分布に変化はないのでランダムな順列で言い換えられる(WTF19-F)。

\(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 で求める。

$\mathbb{P}[A|B] = \frac{\mathbb{P}[A \cap B]}{\mathbb{P}[B]}$ なので、確率 \(\mathbb{P}[A_1], \mathbb{P}[A_2], \ldots, \mathbb{P}[A_N]\) を \(B\) の条件付き確率に直すには、\(\mathbb{P}[A_1 \cap B], \mathbb{P}[A_2 \cap B], \ldots, \mathbb{P}[A_N \cap B], \mathbb{P}[B]\) を求めればよい。

[0,1]上の一様乱数の列X_1, X_2, \ldots, について、n を X_1 \leq X_2 \leq \cdots X_n \geqnX_{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と書けて、P[X_1 \leq X_2 \leq \cdots X_i]=1/i!, E[X_i|X_1 \leq X_2 \leq \cdots X_i] = n / (i+1) となることから計算できる（putnum2022A4）

|x_i-x_j mod 1| >= 1/3 + ε
or
|x_i-x_j mod 1| <= 1/3 – ε

||X|-Y| >= e
|1-|X|-Y| >= e

|X±Y| >= e
|X±Y±1| >= e（順不同）

|X+k/3| >= e （k∈Z）(AGC42F)

[0, 1] 上に赤、青、緑の点を合計 n 個ランダムに打つ。色はランダムに選ぶ。そして、0, 1 に赤、青の点をそれぞれ打つ。相異なる色の点間の距離の最小値の期待値を求めよ（AGC42F)。

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