6

期待値の真価

638
0
$$$$

はじめに

期待値って確率の問題で求めるものという印象が強いんだけど,総和とか漸化式の問題にこっちから導入してやると楽になることがありますよね。
全部の場合を足すのが大変なら全部から一つを同じ確率で選んで平均取ればいいじゃない。とマリーアントワネットも言っていたように,そうすれば複雑な数え上げを飛ばして平均の漸化式だけが立ったり,見るべきものが単純化したりすることがあります。今回はそういう使い方を集めてみます。
中心になるのは
$$ \begin{aligned} &\left((X_1+\cdots+X_m)\text{の期待値}\right)=\left(X_1\text{の期待値}\right)+\cdots+\left(X_m\text{の期待値}\right) \end{aligned} $$
という期待値の線形性です。

全部で$M$通りあるものを同じ確率で選んだとき,その値を$X$とすれば総和は$M\times\left(X\text{の期待値}\right)$
確率が出てこない問題に期待値を入れる入口ってだいたいこういう感じかな。

桁を全部数えずに平均の漸化式を立てる

数字$0$を使わず隣り合う桁の数字が異なる$n$桁の正整数を全部集めます。その総和を$S_n$,最高位が$2$のものだけの総和を$T_n$とし,$S_n$と$\displaystyle\lim_{n\to\infty}\dfrac{T_n}{S_n}$を求めよ。

出典:$2026$年第$1$回東大本番レベル模試 第$3$問

まず総和を平均にする

最高位を$1,\ldots,9$から選び,次の桁は直前と違う$8$個から同じ確率で選びます。どの整数ができる確率も$\dfrac{1}{9\cdot8^{n-1}}$なので,これは条件を満たす整数から一つを一様に選ぶことと同じです。
各位について数字$1,\ldots,9$は対等だからどの位の平均も$5$
位の重みをかけて足せば
$$ \begin{aligned} S_n &=9\cdot8^{n-1}\cdot5(10^{n-1}+\cdots+1)\\ &=5\cdot8^{n-1}(10^n-1) \end{aligned} $$
隣り合う桁は独立ではないけど各位の平均を足すところには支障なし。

今度は最高位を$2$に固定します。左から$j$番目の数字を$D_j$,その平均を$d_j$とします。今の数字が$a$だったとき,次の数字の平均は$\dfrac{45-a}{8}$だから今の数字ごとに場合分けして平均取ると
$$ d_1=2,\quad d_{j+1}=\dfrac{45-d_j}{8} $$
これが立てたかった漸化式です。各数字が出る確率を$9$本の数列にして追う必要がなくなりました。
固定される平均$5$を引けば
$$ d_{j+1}-5=-\dfrac{1}{8}(d_j-5) $$
なので$d_j=5-3\left(-\dfrac{1}{8}\right)^{j-1}$
選んだ整数そのものを$N$とすると
$$ \begin{aligned} \left(N\text{の期待値}\right) &=\sum_{j=1}^{n}10^{n-j}d_j\\ &=\dfrac{5}{9}(10^n-1) -\dfrac{80}{27}10^{n-1}\left\{1-\left(-\dfrac{1}{80}\right)^n\right\}\\ &=\dfrac{7\cdot10^n-15+8\left(-\dfrac{1}{8}\right)^n}{27} \end{aligned} $$
最高位が$2$のものは$8^{n-1}$個なので$T_n=8^{n-1}\times\left(N\text{の期待値}\right)$
$$ \begin{aligned} \dfrac{T_n}{S_n} &=\dfrac{7\cdot10^n-15+8\left(-\dfrac{1}{8}\right)^n}{135(10^n-1)}\\ &\longrightarrow\dfrac{7}{135} \end{aligned} $$
ここで使ったのは線形性と今の数字で場合分けして平均することです。( 以前私が取り上げた解答はこちら )
後者は条件付き期待値の考え方だけど,上の計算は有限個の場合分けだけで書けます。次の値の平均が今の値の一次式になるなら平均だけで漸化式が閉じる。 これがほかの問題へ持っていきたい部分です。

人数の積の総和にも平均の漸化式が立つ

$n$を正整数とする。どの二人も身長の異なる$n$人の生徒を東西方向に一列に整列させる。それぞれの整列の仕方について,「$n$人が重なるように西から写真を撮ったときに写る人数」と「同じように東から写真を撮ったときに写る人数」の積を,その整列の仕方の映え度と定める。
例えば$n=6$で,生徒を身長が高い順に$A_1,A_2,\ldots,A_6$とし,西から$A_2,A_5,A_1,A_4,A_3,A_6$の順に整列させると,西からは$A_2,A_1$の$2$人,東からは$A_6,A_3,A_1$の$3$人が写るので,映え度は$6$となる。
すべての整列の仕方についての映え度の総和を$S_n$とする。$S_{4999}$を素数$5003$で割った余りを求めよ。

出典: $\mathrm{OMCB053(F)}$
まず一般の$n$で$S_n$を求めます。西から写る人数を$L$,東から写る人数を$R$とすれば,映え度は$LR$です。

一つの並びを同じ確率で選び,$\left(L\text{の期待値}\right)=h_n$,$\left(LR\text{の期待値}\right)=b_n$と置きます。左右の対称性から$\left(R\text{の期待値}\right)=h_n$でもあります。

まず$n-1$人をランダムに並べ,その前後と間にある$n$か所から一つを選んで一番低い人を入れて,できた並びからその人を抜けば元に戻せるのでこれで全$n!$通りが同じ確率で現れます。
一番低い人は左端に入ったときだけ左から新たに見えます。元からいた人の見え方は変わらないので
$$ h_1=1,\quad h_n=h_{n-1}+\dfrac{1}{n} $$
したがって$h_n=1+\dfrac{1}{2}+\cdots+\dfrac{1}{n}$

左端に入れば$LR$は$R$だけ増え,右端なら$L$だけ増えます。間に入った場合は変わりません。$n\geqq2$では左右の端は別の場所なので
$$ b_1=1,\quad b_n=b_{n-1}+\dfrac{2h_{n-1}}{n} $$
これで積の平均まで求まります。
$$ b_n=1+2\sum_{j=2}^{n}\dfrac{h_{j-1}}{j} $$
右辺は異なる二つの分母を選んだ逆数積を全部足したものなので,総和は
$$ S_n=n!\left\{h_n^2-\sum_{j=2}^{n}\dfrac{1}{j^2}\right\} $$
元問題の余りまで戻っておきます。ここからは$5003$を法とし,分数は分母の逆数を掛ける意味で使います。$1,\ldots,5002$の逆数は同じ数の並べ替えになるので
$$ \sum_{j=1}^{5002}\dfrac{1}{j}\equiv0,\quad \sum_{j=1}^{5002}\dfrac{1}{j^2}\equiv0 $$
また,自分自身が逆数となる$1,-1$以外を逆数同士で組にすると$5002!\equiv-1$。よって
$$ 4999!\equiv\dfrac{1}{6},\quad h_{4999}\equiv1+\dfrac{1}{2}+\dfrac{1}{3}=\dfrac{11}{6},\quad \sum_{j=2}^{4999}\dfrac{1}{j^2}\equiv-1-1-\dfrac{1}{4}-\dfrac{1}{9}=-\dfrac{85}{36} $$
したがって
$$ S_{4999}\equiv\dfrac{1}{6}\left\{\left(\dfrac{11}{6}\right)^2+\dfrac{85}{36}\right\}=\dfrac{103}{108}\equiv1437 $$
左右から見える人数は独立ではありません。ここでは積をそのまま追わず,人一人加えたときの積の増加量を追うことで一次式に戻してます。

ちょうど何個あるかなんて求めなくていい

$n$を正整数とする。$1,\ldots,n$の並べ替えのうち,不動点をちょうど$k$個もつものの個数を$p_n(k)$とする。次の等式を証明せよ。
$$ \sum_{k=0}^{n}kp_n(k)=n! $$
ただし,数$i$が$i$番目の位置にあるとき,その数$i$を不動点と呼ぶ。

出典:$\mathrm{1987IMO}$第$1$問

一つの並べ替えをランダムに選び,元の位置に残る数の個数を$X$とします。各数字が元の位置に残る確率は$\dfrac{1}{n}$なので
$$ \begin{aligned} \left(X\text{の期待値}\right)&=\underbrace{\dfrac{1}{n}+\cdots+\dfrac{1}{n}}_{n\text{ 個}}\\ &=1 \end{aligned} $$
したがって$\displaystyle\sum_{k=0}^{n}kp_n(k)=n!$で,等式が示せました。
元の位置に残る数がちょうど$k$個の場合分けは不要です。$kp_n(k)$という重みを見たら個数そのものの平均じゃねって考えたいですね。

約数を並べた分数の和

$14^3$の$16$個の正の約数を並べ替えた数列を$a_1,\ldots,a_{16}$,$15^3$の$16$個の正の約数を並べ替えた数列を$b_1,\ldots,b_{16}$とする。二つの数列のスコアを
$$ \sum_{k=1}^{16}\dfrac{a_k}{b_k} $$
と定める。数列$a,b$の組として考えられる全$(16!)^2$通りについて,スコアの相加平均を求めよ。ただし,その値を互いに素な正整数$p,q$を用いて$\dfrac{p}{q}$と表したときの$p+q$を解答せよ。

出典: bzuLさんの問題

解答
$14^3$の正の約数を小さい順に$d_1,\ldots,d_{16}$,$15^3$の正の約数を小さい順に$e_1,\ldots,e_{16}$と置きます。
二つの並べ方を別々に一様に選びます。どの位置$j$でも$a_j$の平均は$d_1,\ldots,d_{16}$の平均。$\dfrac{1}{b_j}$の平均も$\dfrac{1}{e_1},\ldots,\dfrac{1}{e_{16}}$の平均です。
また$a_j$と$b_j$は独立なので
$$ \left(\text{スコアの期待値}\right) =\dfrac{1}{16}\left(\sum_{k=1}^{16}d_k\right) \left(\sum_{k=1}^{16}\dfrac{1}{e_k}\right) $$
二つのかっこは,それぞれ約数の和と約数の逆数の和です。約数を素因数の組み合わせで作れば
$$ \begin{aligned} \sum_{k=1}^{16}d_k&=(1+2+4+8)(1+7+49+343)\\ &=6000,\\ \sum_{k=1}^{16}\dfrac{1}{e_k}&=\dfrac{(1+3+9+27)(1+5+25+125)}{15^3} \\&=\dfrac{416}{225} \end{aligned} $$
なので平均は$\dfrac{2080}{3}$

同じ列の中の$a_1,a_2$などは独立じゃないけど,和を分けるところでは独立性を使いません。積の期待値に分けるところでは二つの並べ方を別々に選んだことを使ってます。

二項係数のついた和をコインに

$n$は$3$以上の自然数とする。表と裏が同様に確からしいコインを$n$回投げ,$1\leqq k\leqq n$について,第$k$回に表が出たとき$X_k=1$,裏が出たとき$X_k=0$と定める。さらに
$$ Y_k=\sum_{j=1}^{k}X_j,\quad Z_n=\sum_{k=2}^{n}X_kY_{k-1},\quad W_n=\sum_{k=3}^{n}X_kZ_{k-1} $$
と定める。
(3) 各試行が独立であることを踏まえ,$Y_n,Z_n,W_n$の期待値を計算したうえで,$\displaystyle\sum_{k=1}^{n}k^3{}_n\mathrm C_k$を$n$の式で表せ。

出典: いろはさんの$2025$年$8$月演習セット 第$4$問(3)

$Y_n$は表の回数です。また,$Z_n$は表になった二つの試行の組数,$W_n$は表になった三つの試行の組数を数えています。
異なる試行がともに表になる確率は$\dfrac{1}{4}$,三つとも表になる確率は$\dfrac{1}{8}$なので,線形性から
$$ \begin{aligned} \left(Y_n\text{の期待値}\right)&=\dfrac{n}{2},\quad \left(Z_n\text{の期待値}\right)=\dfrac{1}{4}{}_n\mathrm C_2,\quad \left(W_n\text{の期待値}\right)=\dfrac{1}{8}{}_n\mathrm C_3 \end{aligned} $$
一方,$X_k^2=X_k^3=X_k$を使って$Y_n^3$を展開し,添字が全部同じ項,二つだけ同じ項,全部異なる項に分ければ
$$ Y_n^3=Y_n+6Z_n+6W_n $$
したがって
$$ \begin{aligned} \left(Y_n^3\text{の期待値}\right) &=\dfrac{n}{2}+\dfrac{6}{4}{}_n\mathrm C_2+\dfrac{6}{8}{}_n\mathrm C_3\\ &=\dfrac{n^2(n+3)}{8} \end{aligned} $$
表が$k$回出る確率は$\dfrac{{}_n\mathrm C_k}{2^n}$なので,求める和は
$$ \sum_{k=1}^{n}k^3{}_n\mathrm C_k=2^n\times\left(Y_n^3\text{の期待値}\right)=2^{n-3}n^2(n+3) $$

不等式の両辺を確率として読む

$n$は$2$以上の整数とする。
(1) $a$は$0< a<1$を満たす実数とする。次の不等式が成り立つことを示せ。
$$ 1-na<(1-a)^n<\dfrac{1}{1+na} $$

出典:$2018$年第$1$回東大実戦数学理科第$6$問$(1)$

成功確率$a$の試行を独立に$n$回行い,成功回数を$X$とします。
まず一度でも成功したら$1$という変数は$X$以下。$2$回以上成功することもあるので平均を取ると
$$ \begin{aligned} \left(X\text{が}1\text{以上となる確率}\right)&<\left(X\text{の期待値}\right)\\ &=na \end{aligned} $$
これが左側の不等式です。
右側は$0$回成功と$1$回成功だけを足します。
$$ \begin{aligned} 1 &\geqq \left(X\text{が}0\text{となる確率}\right)+\left(X\text{が}1\text{となる確率}\right)\\ &=(1-a)^n+na(1-a)^{n-1}\\ &>(1+na)(1-a)^n \end{aligned} $$
よって右側も示せました。
$(1-a)^n$と$na$を見てぜんぶ失敗の確率と成功回数の平均を思い付くと不等式の向きに意味が付きます。使ったのは線形性と数えた回数に対する単純な大小関係です。去年か一昨年か確立として読むとうまくいく不等式の問題がTwitterで流れてきたはずなんだけど思い出せない

二項係数に含まれる$2$を筆算で数える

$n$を非負整数とする。番号$0,1,2,\ldots,2^n-1$が一つずつ振られた$2^n$枚の札が箱に入っている。「箱から札を無作為に一枚取り出し,札の番号を記録してから箱に戻す」という操作を考える。
自然数$N$に対し,$\dfrac{N}{2^m}$が自然数となる最大の非負整数$m$を$f(N)$とする。
(1) 操作を一回行い,記録した番号を$b$とする。$f\left({}_{2^n}\mathrm C_b\right)$の期待値を求めよ。
(2) 操作を二回行い,記録した番号を$a,b$とする。$f\left({}_{2^n+a}\mathrm C_b\right)$の期待値を求めよ。
解答は$n=10$のときの値とする。各期待値を$\xi+\dfrac{\eta}{\zeta}$と表す。ただし,$\xi$は整数部分,$\eta$は非負整数,$\zeta$は自然数で,$\eta,\zeta$は互いに素とする。(1)の$\xi,\eta,\zeta$を順に$1,2,3$行目,(2)の値を順に$4,5,6$行目に記せ。

出典: ASさんの問題

解答
$n=0$なら二つの期待値はどちらも$0$です。以下では$n\geqq1$とし,先に(2)を一般の$n$について求めます。期待値に$2^{2n}$を掛ければ,全組にわたる$f$の総和にもなります。

二進法で$2^n+a$から$b$を引くときの次の位から$1$借りる回数がこの二項係数に含まれる$2$の個数に一致します。
これは階乗中の$2$を$2$の倍数,$4$の倍数,$8$の倍数……と数えることでも確認できます。$N\geqq b$とし,$2^r>N$となる正整数$r$を一つ取ると
$$ f\left({}_N\mathrm C_b\right) =\sum_{j=1}^{r}\left( \left\lfloor\dfrac{N}{2^j}\right\rfloor -\left\lfloor\dfrac{b}{2^j}\right\rfloor -\left\lfloor\dfrac{N-b}{2^j}\right\rfloor\right) $$
各かっこはその境界で借りるときだけ$1$
$j\geqq r$では三つの整数部分がすべて$0$になるので,ここまで足せば十分です。$\lfloor x\rfloor$は$x$以下の最大の整数を表します。
下から$j$桁の引き算の後で借りるのは$a$の下$j$桁の数が$b$の下$j$桁の数より小さい場合です。
その二つは$0,\ldots,2^j-1$から独立に選んだ数。等しい確率が$2^{-j}$で,大小の二通りは対称なので借りる確率は$\dfrac{1-2^{-j}}{2}$
借りた回数の平均は各境界の確率を足すだけです。
$$ \begin{aligned} \left(f\left({}_{2^n+a}\mathrm C_b\right)\text{の期待値}\right) &=\sum_{j=1}^{n}\dfrac{1-2^{-j}}{2}\\ &=\dfrac{n-1}{2}+\dfrac{1}{2^{n+1}} \end{aligned} $$
借りる場所同士は独立じゃないけど和には関係ありません。
(1)の$f\left({}_{2^n}\mathrm C_b\right)$も同じです。下$j$桁が$0$じゃない限り借りるので平均は$n-1+2^{-n}$。$n=10$ではそれぞれ$4+\dfrac{1025}{2048}$と$9+\dfrac{1}{1024}$になります。

平均求めたら存在まで分かっちゃう

これは結構有名で平均以上のものが少なくとも一つあるってだけで確率のない問題の存在証明ができます。

ある集団に知り合いの組が$m$組あるとします。人を二組に分け,少なくとも$\dfrac{m}{2}$組の知り合いを別々の組にできることを示せ。

各人を独立に確率$\dfrac{1}{2}$でどっちかの組へ入れます。一組の知り合いが離れる確率は$\dfrac{1}{2}$だから離れた知り合いの組数の平均は$\dfrac{m}{2}$
平均以上の分け方が少なくとも一つあるので終わりです。
共有する人がいる知り合いの組を別々に数えても大丈夫。組ごとの出来事の独立性を確認する必要はない。

共通の始点を$\mathrm O$とする長さ$1$のベクトル$\overrightarrow{\mathrm{OA}_1},\ldots,\overrightarrow{\mathrm{OA}_n}$を考えます。それぞれに$+$か$-$を付けて足した長さを$\sqrt n$以下にできることを示せ。

符号$s_j$を独立に$1,-1$から選びます。違う添字では$\left(s_is_j\text{の期待値}\right)=0$なので
$$ \begin{aligned} \left(\left|\sum_{j=1}^{n}s_j\overrightarrow{\mathrm{OA}_j}\right|^2\text{の期待値}\right) &=\sum_{j=1}^{n}|\overrightarrow{\mathrm{OA}_j}|^2\\ &=n \end{aligned} $$
したがって$2^n$通りの符号の中に長さの$2$乗が$n$以下のものがあります。一般の長さでも上限は$\sqrt{\displaystyle\sum_{j=1}^{n}|\overrightarrow{\mathrm{OA}_j}|^2}$
符号を工夫して交差項を消す問題で先に全部の符号の平均を取ってしまおうってこと。

根号消すより平均する式を作る

こっからはいろんなものと組み合わせて応用してみる。
まずは解と係数の関係との組み合わせです。

最初に数$1$を一つ書いておきます。書かれた数$x$をすべて消し,それぞれの代わりに
$$ \dfrac{x+\sqrt{x^2+8}}{2},\quad \dfrac{x-\sqrt{x^2+8}}{2} $$
の二つを書きます。正整数$n$に対し,この操作を$n$回行った後の$2^n$個の数について,$4$乗の総和を求めてください。同じ値が現れた場合も重複して数えます。

一つの枝だけを追うと根号がどんどん重なるけど二つの子を$u,v$と書けば
$$ u+v=x,\quad uv=-2 $$
子たちは$y^2-xy-2=0$の二つの解だからです。この二つを同じ確率で選ぶと,根号を残さずに平均できます。
初期値を一般に$a$とし,毎回どっちかの枝を確率$\dfrac{1}{2}$で選んだ値を$X_n$とします。すべての枝の選び方が同じ確率で現れるので最後に$2^n$をかければ総和に戻せます。
解と係数の関係から
$$ \begin{aligned} u^2+v^2&=(u+v)^2-2uv\\ &=x^2+4\\ u^4+v^4&=(u^2+v^2)^2-2u^2v^2\\ &=x^4+8x^2+8 \end{aligned} $$
$2$乗の平均を$M_n$,$4$乗の平均を$Q_n$とすると
$$ M_{n+1}=\dfrac{1}{2}M_n+2,\quad Q_{n+1}=\dfrac{1}{2}Q_n+4M_n+4 $$
求めたいのは$4$乗だけど,その前に$2$乗も一緒に持っとくのが自然です。

変わらない値$4,40$を引いて$A_n=M_n-4$,$B_n=Q_n-40$と置くと
$$ A_{n+1}=\dfrac{1}{2}A_n,\quad B_{n+1}=\dfrac{1}{2}B_n+4A_n $$
両方に$\dfrac{1}{2}$が出てきました。ここで$B_n-cA_n$という定数係数の引き算では$A_n$の項を消せません。代わりに$n$を掛けて引きます。
$$ \begin{aligned} B_{n+1}-8(n+1)A_{n+1} &=\dfrac{1}{2}B_n+4A_n-4(n+1)A_n\\ &=\dfrac{1}{2}(B_n-8nA_n) \end{aligned} $$
したがって$B_n-8nA_n=\dfrac{a^4-40}{2^n}$,また$A_n=\dfrac{a^2-4}{2^n}$なので
$$ \left(X_n^4\text{の期待値}\right)=40+\dfrac{a^4-40+8n(a^2-4)}{2^n} $$
求める総和は$a=1$として
$$ 40\cdot2^n-24n-39 $$
初期値を変えても同じ計算で,$40\cdot2^n+8n(a^2-4)+a^4-40$まで一度に求まります。

今の引き算は
$$ F_n(x)=x^4-40-8n(x^2-4) $$
という式を作ったとも読めます。子を一つ選んだ後の$F_{n+1}$の平均が親の$F_n(x)$のちょうど$\dfrac{1}{2}$になるわけです。
値を直接追うのが難しいなら平均が簡単に動く式をこっちから作ってやろうじゃねえか!これはこの問題に限りません。子が二次方程式の二つの解ならべきの和は解と係数の関係で低い次数へ戻せます。その後に定数を引いたり低い次数の式を足したりして平均の漸化式を整えます。
根号の形を見て変形を続ける前に二つを合わせたら何が消えるかを見る。総和の問題では結構試しやすい方針なんじゃないかと思います。

数字の平均からどんな関数の平均へ進める

これまでの桁の漸化式は数字そのものを平均したから使えたのかというとそんなことはないんだよなぁ
$m$種類の文字から長さ$n$の列を作り,隣り合う文字が異なるものから一つを一様に選びます。$m\geqq2$とします。各文字に好きな実数$f(1),\ldots,f(m)$を割り当て,その平均を$\mu$とします。
今の文字が$a$なら次の文字に割り当てた値の平均は
$$ \dfrac{m\mu-f(a)}{m-1} $$
よって$\mu$を引いた値は一つ先で平均すると$-\dfrac{1}{m-1}$倍になります。数字に限らず,特定の文字なら$1$でほかは$0$という割り当てにも同じ式が使えます。

左から$j$番目の文字を$D_j$とし
$$ F_j=f(D_j)-\mu,\quad c=\dfrac{1}{m}\sum_{a=1}^{m}(f(a)-\mu)^2,\quad r=-\dfrac{1}{m-1} $$
と置きます。$i< j$なら
$$ \left(F_iF_j\text{の期待値}\right)=cr^{j-i} $$
したがって
$$ \begin{aligned} \left((F_1+\cdots+F_n)^2\text{の期待値}\right) &=c\left\{n+2\sum_{h=1}^{n-1}(n-h)r^h\right\}\\ &=c\left\{\dfrac{n(m-2)}{m} +\dfrac{2(m-1)}{m^2}(1-r^n)\right\} \end{aligned} $$

なぜかというと,$i$番目の文字を固定したときの$F_j$の平均が$r^{j-i}F_i$だからです。これに$F_i$かけて,最後に$i$番目について平均すれば$r^{j-i}\left(F_i^2\text{の期待値}\right)$
どの位置でも各文字が対等に現れるので$\left(F_i^2\text{の期待値}\right)=c$
あとは和の$2$乗を展開するだけ。同じ距離$h$だけ離れた組が$n-h$組あるので最初の式が出ます。最後は等比数列の和で整理。
一か所の平均の漸化式から離れた二か所の積まで求まる。 独立でないことを避けるんじゃなく,依存の仕方を$r^{j-i}$という一つの式にしてる。

正整数$n$に対し,数字$0$を使わず隣り合う桁が異なる$n$桁の正整数をすべて考えます。各整数の各位の和を$s$として,$(s-5n)^2$の総和を求めてください。

今度は$m=9$,$f(a)=a$なので$\mu=5$,$c=\dfrac{20}{3}$,$r=-\dfrac{1}{8}$。補題に入れれば一つの整数についての平均は
$$ \dfrac{20}{3}\left\{\dfrac{7n}{9} +\dfrac{16}{81}\left(1-\left(-\dfrac{1}{8}\right)^n\right)\right\} $$
整数の個数$9\cdot8^{n-1}$を掛けて
$$ \dfrac{(1260n+320)8^{n-1}-40(-1)^n}{27} $$
これが求める総和です。$s$が各値を取る場合の数は一つも求めていません。

正整数$n$に対し,$\mathrm A,\mathrm B,\mathrm C$から長さ$n$の列を作ります。隣り合う文字が異なるすべての列について,各文字の個数を$a,b,c$として
$$ (a-b)^2+(b-c)^2+(c-a)^2 $$
を足してください。

一つの文字に注目し,その文字なら$1$でほかなら$0$と置きます。$m$文字で考えると$\mu=\dfrac{1}{m}$で,$c=\dfrac{m-1}{m^2}$
注目した文字の個数を$N_a$とすると,補題は$N_a-\dfrac{n}{m}$の$2$乗の平均を求めてます。
ここで各列について恒等式
$$ \sum_{a=1}^{m-1}\sum_{b=a+1}^{m}(N_a-N_b)^2 =m\sum_{a=1}^{m}\left(N_a-\dfrac{n}{m}\right)^2 $$
が成り立ちます。両辺の平均を取り,列の総数$m(m-1)^{n-1}$を掛けると,$m$文字での総和まで求まります。
$$ \dfrac{\{m(m-2)n+2(m-1)\}(m-1)^n-2(m-1)(-1)^n}{m} $$
問題の答えは$m=3$として
$$ \dfrac{(3n+4)2^n-4(-1)^n}{3} $$

平面上で互いになす角が$120^\circ$の三つの向きへ,毎回距離$1$ずつ歩くことを考えます。同じ向きに続けて歩かないとします。
三つの向きに歩いた回数を$a,b,c$とすると,出発点からの距離の$2$乗は
$$ a^2+b^2+c^2-ab-bc-ca =\dfrac{(a-b)^2+(b-c)^2+(c-a)^2}{2} $$
したがって全$3\cdot2^{n-1}$通りの歩き方についてスタート地点からの距離の$2$乗の平均は
$$ \dfrac{n}{3}+\dfrac{4}{9}\left(1-\left(-\dfrac{1}{2}\right)^n\right) $$

ベクトル和が$0$なら角度の詳細によらない

共通の始点を$\mathrm O$とする長さ$1$の$m$本の異なるベクトル$\overrightarrow{\mathrm{OA}_1},\ldots,\overrightarrow{\mathrm{OA}_m}$の和が$\overrightarrow{\mathrm{OO}}$であるとします。点$\mathrm O$から出発し,最初は$m$本から一つ,次からは直前と異なる$m-1$本から一つを同じ確率で選び,選んだベクトルの分だけ歩きます。
$n$回後の点を$\mathrm P_n$とすると,出発点からの変位は$\overrightarrow{\mathrm{OP}_n}$
$$ \left(|\overrightarrow{\mathrm{OP}_n}|^2\text{の期待値}\right) =\dfrac{n(m-2)}{m} +\dfrac{2(m-1)}{m^2} \left\{1-\left(-\dfrac{1}{m-1}\right)^n\right\} $$

今のベクトルが$\overrightarrow{\mathrm{OA}}$なら,次のベクトルの平均は$-\dfrac{1}{m-1}\overrightarrow{\mathrm{OA}}$
離れた二つのベクトルの内積の平均も一歩離れるごとにこの係数を掛けるだけだから変位の長さの$2$乗を展開すれば補題と同じ和が出ます。
例えば平行四辺形の二組の対辺の向きに長さ$1$のベクトルを取り,同じ向きを続けて選ばずに歩く場合。二組の向きのなす角を変えても,スタート地点からの距離の$2$乗の平均は変わりません。

整数の隙間で期待値の不等式を作る

最後は不等式との組み合わせです。整数$x$と整数$k$に対して
$$ (x-k)(x-k-1)\geqq0 $$
が成り立ちます。実数全体では正しくありませんが,$k$と$k+1$の間に整数がないので大丈夫です。
これをある条件が成立したら$1$という変数の評価に使います。

非負整数の値を取る変数$X$と正整数$k$に対して
$$ \begin{aligned} &\left(X\text{が正となる確率}\right)\geqq \dfrac{(2k+1)\left(X\text{の期待値}\right)-\left(X^2\text{の期待値}\right)}{k(k+1)} \end{aligned} $$
が成り立ちます。ここでは$X$の取り得る値は有限個とします。

$X>0$のとき$1$でそれ以外は$0$となる変数を$I$とします。
$X=0$なら両方$0$で,$X\geqq1$なら
$$ \begin{aligned} 1-\dfrac{X(2k+1-X)}{k(k+1)} &=\dfrac{(X-k)(X-k-1)}{k(k+1)}\\ &\geqq0 \end{aligned} $$
よって常に$I\geqq\dfrac{X(2k+1-X)}{k(k+1)}$
平均を取れば証明が終わります。
$0$で値$0$を取り,二つの整数$k,k+1$で値$1$を取るように作ってます。
確率を直接数える代わりに,$0,1$を簡単な多項式で押さえてから平均する。
これはDawson–Sankoffの不等式につながるやつらしいです。$k$を動かして一番強い評価を選べます。しかも$X$が$0,k,k+1$の値しか取らないときは等号になります。
$\left(X\text{の期待値}\right)>0$のとき,$k\leqq\dfrac{\left(X^2\text{の期待値}\right)}{\left(X\text{の期待値}\right)}\leqq k+1$となる$k$を選べば右辺は最大です。右辺を$L_k$と書くと
$$ L_{k+1}-L_k =\dfrac{2\{\left(X^2\text{の期待値}\right)-(k+1)\left(X\text{の期待値}\right)\}}{k(k+1)(k+2)} $$
なので,比が$k+1$を超えている間だけ大きくなります。どの二つの整数に合わせて式を作るかも二つの平均から決められます。

集合の重なりが二つずつしか分からないとき

$10$個の有限集合があり,それぞれの要素数は$20$です。異なる二つの集合を選ぶ全$45$組について,共通部分の要素数を足すと$225$でした。
少なくとも一つの集合に含まれる要素の総数の最小値を求めてください。

少なくとも一つに含まれる要素の総数を$R$とします。その中から一つを一様に選び,その要素が入っている集合の個数を$X$とします。
要素を一つずつ数える代わりに集合ごとに数えると
$$ \begin{aligned} \left(X\text{の期待値}\right)&=\dfrac{10\cdot20}{R}\\ &=\dfrac{200}{R} \end{aligned} $$
また一つの要素が$X$個の集合に入っているなら,集合の共通部分には$\,{}_X\mathrm C_2$回数えられます。$X^2=X+2{}_X\mathrm C_2$なので
$$ \begin{aligned} \left(X^2\text{の期待値}\right)&=\dfrac{200+2\cdot225}{R}\\ &=\dfrac{650}{R} \end{aligned} $$
$X>0$は必ず成り立ちます。また$\dfrac{\left(X^2\text{の期待値}\right)}{\left(X\text{の期待値}\right)}=\dfrac{13}{4}$なので$k=3$を選びます。命題から
$$ \begin{aligned} 1 &\geqq\dfrac{7\left(X\text{の期待値}\right)-\left(X^2\text{の期待値}\right)}{12}\\ &=\dfrac{125}{2R} \end{aligned} $$
よって$R\geqq\dfrac{125}{2}$,$R$は整数なので$R\geqq63$
コーシーシュワルツ$\left(X\text{の期待値}\right)^2\leqq \left(X^2\text{の期待値}\right)$だけなら$R\geqq\dfrac{800}{13}$で,$62$個以上までしか出ません。$X$が整数であることを使うともう一段強くなりました。
$63$個での実現もできます。$200$枚の札に$1,\ldots,10$を順番に$20$回繰り返して書き,続けて$2$枚の組を$3$組,$3$枚の組を$46$組,$4$枚の組を$14$組に分けます。各組を一つの要素とし,札に$i$がある組を第$i$集合に入れます。
一つの組に同じ番号は重ならないので各集合の要素数は$20$。二つずつの共通部分の要素数の総和も
$$ 3\,{}_2\mathrm C_2+46\,{}_3\mathrm C_2+14\,{}_4\mathrm C_2=225 $$
となり条件を満たします。したがって最小値は$63$
三つ以上の集合の共通部分を全部調べる必要はありません。全体の重なり方が分からなくても,所属回数と所属する集合のペア数だけで評価できます。
接線で関数を一次式に押さえるのと近い発想ですが,ここでは整数の隙間に合わせて二次式を作っています。期待値を取る前の不等式を設計すると,使える情報の種類までこちらで選べます。

もう少し問題を並べてみる

$1,\ldots,n$の全並べ替えについて「それまでの最大値を更新した回数」の総和を求めよ。最初の数も$1$回と数えます。

左から$j$番目が最初の$j$個の最大になる確率は$\dfrac{1}{j}$だから総和は$n!h_n$
$n!$個の列で更新回数を分類しなくて済みます。

正整数$n$に対して
$$ \sum_{k=0}^{n}k^2\left({}_n\mathrm C_k\right)^2 $$
を求めよ。

赤$n$枚と白$n$枚から$n$枚選び,赤の枚数を$K$とします。赤が$k$枚の選び方が$\left({}_n\mathrm C_k\right)^2$通りなので,求める和は${}_{2n}\mathrm C_n\,\left(K^2\text{の期待値}\right)$
$K^2=K+2{}_K\mathrm C_2$と分ければ,特定の赤$1$枚と特定の赤$2$枚が選ばれる確率だけで計算できて
$$ \sum_{k=0}^{n}k^2\left({}_n\mathrm C_k\right)^2 =\dfrac{n^3}{2(2n-1)}{}_{2n}\mathrm C_n $$

最大値を四つの隙間で読む

$n$は$3$以上の整数とする。$1$から$n$までの番号が書かれた$n$枚の札が袋に入っており,同じ番号の札はない。この袋から$3$枚の札を同時に取り出し,一番大きな番号を$X$とする。$X$の期待値を求めよ。

出典: $2026$年京都大学 理系第$6$問
選んだ三つを小さい順に置くと,選ばなかった数は最初の数の前,一つ目と二つ目の間,二つ目と三つ目の間,最後の数の後の四つに分かれます。その個数を$g_0,g_1,g_2,g_3$とすると,和は$n-3$。
逆に非負整数の組$(g_0,g_1,g_2,g_3)$を決めると選んだ三つが一意に戻ります。したがって隙間の個数を入れ替えた組も同じ確率で現れ,四つの平均は等しくなります。どれも$\dfrac{n-3}{4}$
最大値$X$は$n-g_3$なので
$$ \begin{aligned} \left(X\text{の期待値}\right)&=n-\left(g_3\text{の期待値}\right)\\ &=n-\dfrac{n-3}{4}\\ &=\dfrac{3(n+1)}{4} \end{aligned} $$
この見方は最大値の分布を全部求めずに済むのがいいところです。総和に戻すと確率のない恒等式$\displaystyle\sum_{k=3}^{n}k\,{}_{k-1}\mathrm C_2=3{}_{n+1}\mathrm C_4$の証明にもなります。

最小値も$0$か$1$の和になる

番号$1,2,\ldots,9$を書いたカードが一枚ずつ,合計$9$枚ある。この中から無作為に$3$枚を同時に取り出し,取り出したカードに書かれた番号の差の最小値を$X$とする。
(1) $X=1,2,3,4$となる確率をそれぞれ求めよ。
(2) $X$の期待値を求めよ。

出典:$2013$年第$1$回東大実戦文系数学第$2$問
小さい順に$a< b< c$とすれば,$X=\min(b-a,c-b)$です。
正整数の値$X$は$1$以上なら$1$,$2$以上ならもう$1$……という足し算にできるから
$$ \left(X\text{の期待値}\right)=\sum_{t=1}^{4}\left(X\text{が}t\text{以上となる確率}\right) $$
$X\geqq t$は隣の差がどっちも$t$以上という条件です。
$(a,b,c)$を$(a,b-t+1,c-2t+2)$に直すと,$1,\ldots,11-2t$からの三つの選択になるので
$$ \begin{aligned} \left(X\text{の期待値}\right) &=\dfrac{{}_9\mathrm C_3+{}_7\mathrm C_3+{}_5\mathrm C_3+{}_3\mathrm C_3}{{}_9\mathrm C_3}\\ &=\dfrac{65}{42} \end{aligned} $$
(1)もこの計算から戻せます。ちょうど$t$となる確率は,$t$以上となる確率から$t+1$以上となる確率を引いたものなので
$$ \begin{aligned} \left(X\text{が}1\text{となる確率}\right)&=\dfrac{7}{12}\\ \left(X\text{が}2\text{となる確率}\right)&=\dfrac{25}{84}\\ \left(X\text{が}3\text{となる確率}\right)&=\dfrac{3}{28}\\ \left(X\text{が}4\text{となる確率}\right)&=\dfrac{1}{84} \end{aligned} $$
最小値そのものは項ごとに平均できないけど大小の境界ごとに$0,1$で数え直すと線形性が使えます。

立方体の一つの頂点を$S$とする。駒をはじめ$S$に置き,駒がある頂点と辺で結ばれた頂点を等確率で一つ選んで,その頂点に駒を移す操作を$1000$回繰り返す。この間に駒が頂点$S$に戻ってきた回数を$T$とする。
$1000$回の移動の仕方すべてについての$T$の期待値を求めよ。ただし,その値を互いに素な正整数$a,b$を用いて$\dfrac{a}{b}$と表したときの$a+b$を,素数$997$で割った余りを解答せよ。

出典: $\mathrm{OMC284(E)}$
何回戻ったかの分布を求めるより,$j$回目に戻ってたら$1$とする変数を足します。必要なのは各時点の帰る確率だけです。
奇数回では戻れません。$2m$回目の帰る確率を$r_m$とすると,偶数回で到達できる四つの頂点だけを見て
$$ r_0=1,\quad r_{m+1}=\dfrac{1}{3}r_m+\dfrac{2}{9}(1-r_m) $$
スタート地点から二手で戻る確率が$\dfrac{1}{3}$,ほかの三頂点からスタート地点へ二手で来る確率がどれも$\dfrac{2}{9}$だからです。これ解けば$r_m=\dfrac{1}{4}+\dfrac{3}{4}\,9^{-m}$
求める平均は
$$ \sum_{m=1}^{500}r_m =125+\dfrac{3}{32}(1-9^{-500}) $$

平均を通分すると
$$ \left(T\text{の期待値}\right)=\dfrac{4003\cdot9^{500}-3}{32\cdot9^{500}} $$
$9^{500}\equiv1\pmod{32}$なので分子は$32$の倍数で,分子に含まれる素因数$3$は一個です。したがって分子と分母の最大公約数は$96$であり
$$ a+b=\dfrac{1345\cdot3^{1000}-1}{32} $$
法$997$で累乗を計算すると$3^{1000}\equiv81$となるので,求める余りは$912$です。

おわりでーすばいばーい

投稿日:19時間前
更新日:16時間前
数学の力で現場を変える アルゴリズムエンジニア募集 - Mathlog served by OptHub

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

日本語に違和感があるかもしれません。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中