記録が更新される回数の期待値

方針

解答

⓪ 発想 — どう考え始めるか。 記録の枚数 $X$ の分布(ちょうど何枚になる確率)を求めるのは難しい。だが期待値だけなら、道がある。

$X$ を「$k$ 枚目が記録なら1、そうでなければ0」という $n$ 個の量 $X_1,\dots ,X_n$ の和に分解する。期待値は、各場所の確率の和になる。この分解が強力なのは、互いに独立でなくても「和の期待値=期待値の和」が成り立つからだ。

あとは「$k$ 枚目が記録」を、「先頭 $k$ 枚の中の最大が $k$ 枚目にある」と読み替えれば、対称性で確率が出る。

① $k$ 枚目が記録になる確率。 $k$ 枚目が記録 ⟺ 先頭 $k$ 枚のうち最大の番号が、ちょうど $k$ 枚目にある。よく混ぜてあるから、先頭 $k$ 枚の中で最大がどの位置にあるかは、$k$ か所とも同様に確からしい。よって

$$E(X_k)=P(k枚目が記録)=\frac{1}{k}$$

$k$ 枚目より後のカードは判定に関係しない。この読み替えのきれいなところだ。

② 期待値を足し上げる((2)の答え)。

$$E(X)=\sum _{k=1}^{n}E(X_k)=1+\frac{1}{2}+\frac{1}{3}+\cdots +\frac{1}{n}$$

③ $n=4$ の値((1)の答え)。

$$E(X)=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}=\frac{12+6+4+3}{12}=\frac{25}{12}$$

まとめ: 「個数の期待値」は、場所ごとの0か1の量に分解して確率を足すのが定石だ。$k$ 枚目の判定が先頭 $k$ 枚の内部だけで決まり、最大の位置の対称性から $\frac{1}{k}$ になる。分布を求めずに、期待値だけ先に取れる。

発展 — 一歩先へ。 答えの $1+\frac{1}{2}+\cdots +\frac{1}{n}$(調和数)は、$n$ を増やしてもゆっくりしか育たない。カード100枚でも期待値は約 $5.2$ 枚。記録は対数の速さでしか増えない。ちなみにこの調和数、$n\ge 2$ では決して整数にならない(本サイトの集合と命題の最難関に、その証明がある)。

別解

$n=4$ を数えて信じる(具体で確かめるルート)。 $\frac{1}{k}$ という確率が腑に落ちないときは、$n=4$ の $4!=24$ 通りを位置ごとに数えてみるとよい。

$k$ 枚目が記録になる並びは何通りか。「先頭 $k$ 枚の最大が $k$ 枚目にある」並びを数えると

• 1枚目: どの並びでも記録。$24$ 通り($=24/1$)
• 2枚目: 先頭2枚の大きい方が2枚目に来る並び。$12$ 通り($=24/2$)
• 3枚目: 先頭3枚の最大が3枚目。$8$ 通り($=24/3$)
• 4枚目: 全体の最大(4)が末尾。$6$ 通り($=24/4$)

どの位置でも、ちょうど $24/k$ 通り。確率にすれば $\frac{1}{k}$ だ。

記録の総数は $24+12+8+6=50$。期待値は $\frac{50}{24}=\frac{25}{12}$ で、(1)の答えと一致する。

一般論(対称性)と、小さな全数調査。両方から同じ数が出たとき、理解は確信に変わる。