記録更新の回数

同義語：無作為な列の記録records in random permutations

概要

前提知識: 幾何分布と待ち時間（高校数学）, 期待値の線形性と数え上げ, 確率の定義と条件付き確率, 確率変数の期待値と分散

高校での出発点：10 年分の記録

ある町で、毎年の降雪量を記録し始めたとする。1 年目の値は、それまでに比べるものがないので、必ず「観測史上最大」である。2 年目以降は、それまでのどの年よりも多ければ記録の更新になる。10 年間で、記録は何回更新されるだろうか。

降雪量の記録を数える

10 年分の降雪量（単位 cm、この記事で作った数値）が次のようだったとする。

年	1	2	3	4	5	6	7	8	9	10
降雪量	58	43	71	66	50	82	47	79	61	74
小さいほうからの順位	4	1	7	6	3	10	2	9	5	8

1 年目の $58$ が最初の記録で、3 年目の $71$ が $58$ を超えて記録を更新し、6 年目の $82$ がさらに更新する。7 年目以降は $82$ を超える年がない。記録になったのは 1、3、6 年目の 3 回である。
記録かどうかは、値そのものではなく値の大小だけで決まる。そこで 3 行目のように、値を小さいほうからの順位 $1,2,\ldots,10$ に置きかえても、記録になる年は同じである。

どの年の値も同じ条件で決まり、同じ値が出ないとすると、10 年分の順位の並びは $1$ から $10$ の並べ方 $10!$ 通りのどれも同様に確からしいと考えられる。そこで、無作為な並べ方の中で記録を数える問題になる。まず小さい場合を全部書いてみる。

3 つの数の並べ方と記録

$1,2,3$ の並べ方 6 通りについて、記録になる位置（何番目か）と記録の個数を書く。

並べ方	$(1,2,3)$	$(1,3,2)$	$(2,1,3)$	$(2,3,1)$	$(3,1,2)$	$(3,2,1)$
記録の位置	1, 2, 3	1, 2	1, 3	1, 2	1	1
記録の個数	3	2	2	2	1	1

記録の個数が $1,2,3$ の並べ方はそれぞれ $2,3,1$ 通りなので、記録の個数の平均は
$$ \frac{1\cdot2+2\cdot3+3\cdot1}6=\frac{11}6=1+\frac12+\frac13 $$
である。2 番目が記録になるのは 6 通りのうち 3 通り（確率 $\frac12$）、3 番目が記録になるのは 2 通り（確率 $\frac13$）である。

ex-rec-n3 の平均 $1+\dfrac12+\dfrac13$ は、期待値の線形性と数え上げの例「記録の個数」で求めた期待値 $1+\dfrac12+\cdots+\dfrac1n$ の $n=3$ の場合である。この記事では、期待値の先に進み、次の 3 つの問いに答える。

「$i$ 番目が記録」という事象どうしは独立か。記録の個数の分散はいくらか。→ thm-rec-indep、cor-rec-var
記録がちょうど $k$ 回になる確率は、どう求めるか。→ thm-rec-dist

$n$ が大きいと、記録の個数はどのくらいか。→ prop-rec-log

高校の計算	この記事の言葉	大学の言葉
並べ方 $n!$ 通りが同様に確からしい	無作為な並べ方	対称群の上の一様分布
最初の $i$ 個の中での大小	相対順位	置換と整数の列の 1 対 1 対応
$x(x+1)\cdots(x+n-1)$ の展開	記録の個数の分布	第 1 種 Stirling 数
$1+\frac12+\cdots+\frac1n$	記録の個数の平均	調和数、$\log n$ の増え方

記録の定義

記録と記録の個数

$1,2,\ldots,n$ を 1 列に並べたもの $(a_1,a_2,\ldots,a_n)$ を考える。$i$ 番目の項 $a_i$ が、それより前のどの項よりも大きいとき、つまり
$$ a_i>a_j\qquad(j=1,2,\ldots,i-1) $$
のとき、$i$ 番目は記録であるという。1 番目は、前に項がないので必ず記録である。記録になる位置の個数を 記録の個数 といい、$R_n$ で表す。
並べ方 $n!$ 通りのどれも確率 $\dfrac1{n!}$ で選ばれるとき、この並べ方を 無作為な並べ方 という。以下、並べ方は無作為とし、「$i$ 番目が記録」という事象を $A_i$ とする。

記録の個数 $R_n$ は、「$i$ 番目が記録なら $1$、そうでなければ $0$」という確率変数 $X_i$ の和 $R_n=X_1+X_2+\cdots+X_n$ である。$X_i$ の期待値は $P(A_i)$ なので、まず $P(A_i)$ を求める。

$i$ 番目が記録になる確率

無作為な並べ方で、$P(A_i)=\dfrac1i$（$i=1,2,\ldots,n$）である。

$i$ 番目が記録になるのは、最初の $i$ 個 $a_1,\ldots,a_i$ の中で $a_i$ がいちばん大きいときである。最初の $i$ 個にどの $i$ 個の数が入るかを 1 つ決めると、その $i$ 個の並べ方は $i!$ 通りで、そのうち最大の数が $i$ 番目にくるのは、残りの $i-1$ 個を前に並べる $(i-1)!$ 通りである。どの $i$ 個の数の組でも、残りの $n-i$ 個の並べ方の数は同じなので
$$ P(A_i)=\frac{(i-1)!}{i!}=\frac1i $$
である。$\square$

期待値の線形性（期待値の線形性と数え上げ）から、記録の個数の平均は
$$ E[R_n]=\sum_{i=1}^{n}P(A_i)=1+\frac12+\frac13+\cdots+\frac1n $$
である。この和を $H_n$ と書き、調和数 という。

記録の個数の平均

$n=4$ なら $E[R_4]=H_4=1+\dfrac12+\dfrac13+\dfrac14=\dfrac{25}{12}=2.08\ldots$ である。
$n=10$ なら $E[R_{10}]=H_{10}=\dfrac{7381}{2520}=2.928\ldots$ である。ex-rec-snow の 3 回は、平均に近い。
$n=100$ でも $H_{100}=5.187\ldots$ で、100 年のうち記録の更新は平均 5 回ほどにすぎない。

1 から 20 を無作為に並べた列の 1 つ目の例。折れ線が値、赤い点が記録で、記録は 1、5、6、13 番目の 4 回

1 から 20 を無作為に並べた列の 2 つ目の例。記録は 1、2、9、17、18 番目の 5 回で、後ろのほうで続けて記録が出ている

図 1・図 2 は、$1$ から $20$ を無作為に並べた列の 2 つの例である。赤い点が記録で、階段状の灰色の線が「その時点までの最大」を表す。最大の値が大きくなるほど、それを超える項は出にくくなるので、記録は列の前のほうに多く、後ろのほうではまばらになる。平均は $H_{20}=3.59\ldots$ 回である。

主定理 1：記録の事象は独立

ex-rec-n3 で、2 番目と 3 番目がともに記録になるのは $(1,2,3)$ の 1 通りで、確率は $\dfrac16=\dfrac12\cdot\dfrac13$ だった。これは偶然ではない。
「$i$ 番目が記録か」は、最初の $i$ 個の中で $a_i$ が何番目に大きいかだけで決まる。そこで、各項について、その順位を記録しておく。

相対順位

並べ方 $(a_1,\ldots,a_n)$ の $i$ 番目の 相対順位 $r_i$ を、最初の $i$ 個 $a_1,\ldots,a_i$ の中で $a_i$ が大きいほうから何番目かで定める。つまり $r_i=1+(\text{$a_1,\ldots,a_{i-1}$ のうち $a_i$ より大きいものの個数})$ である。$1\le r_i\le i$ で、$i$ 番目が記録であることは $r_i=1$ と同じである。

相対順位の列

$1,2,3$ の並べ方と相対順位の列 $(r_1,r_2,r_3)$ は次のとおりである。

並べ方 $(1,2,3)$ $(1,3,2)$ $(2,1,3)$ $(2,3,1)$ $(3,1,2)$ $(3,2,1)$

$(r_1,r_2,r_3)$ $(1,1,1)$ $(1,1,2)$ $(1,2,1)$ $(1,1,3)$ $(1,2,2)$ $(1,2,3)$

$r_1=1$、$r_2\in\{1,2\}$、$r_3\in\{1,2,3\}$ の組 $1\cdot2\cdot3=6$ 通りが、ちょうど 1 回ずつ現れている。
ex-rec-snow の順位の列 $(4,1,7,6,3,10,2,9,5,8)$ では、相対順位の列は $(1,2,1,2,4,1,6,2,5,3)$ である。たとえば 5 番目の $3$ は、前の $4,1,7,6$ のうち $3$ より大きいものが 3 個あるので $r_5=4$ である。$r_i=1$ となる $i=1,3,6$ が記録の位置である。

並べ方	$(1,2,3)$	$(1,3,2)$	$(2,1,3)$	$(2,3,1)$	$(3,1,2)$	$(3,2,1)$
$(r_1,r_2,r_3)$	$(1,1,1)$	$(1,1,2)$	$(1,2,1)$	$(1,1,3)$	$(1,2,2)$	$(1,2,3)$

相対順位の列と並べ方の 1 対 1 の対応

並べ方 $(a_1,\ldots,a_n)$ にその相対順位の列 $(r_1,\ldots,r_n)$ を対応させると、$1,\ldots,n$ の並べ方全体から、$1\le r_i\le i$（$i=1,\ldots,n$）を満たす整数の列全体への 1 対 1 の対応（全単射）になる。

方針：相対順位の列から、並べ方を後ろから 1 つずつ復元できることを示す。復元の手順がただ 1 通りに決まるので、対応は 1 対 1 である。
段 1（最後の項）。$r_n$ は、全体 $a_1,\ldots,a_n$ の中で $a_n$ が大きいほうから何番目かである。全体は $1,\ldots,n$ なので、$a_n$ は「$1,\ldots,n$ のうち大きいほうから $r_n$ 番目の数」、つまり $a_n=n+1-r_n$ にただ 1 通りに決まる。
段 2（後ろから順に）。$a_n,a_{n-1},\ldots,a_{i+1}$ が決まったとする。$a_1,\ldots,a_i$ は、$1,\ldots,n$ から決まった $n-i$ 個を除いた残りの $i$ 個の数を並べたものである。$r_i$ は、この残りの $i$ 個の中で $a_i$ が大きいほうから何番目かなので、$a_i$ は「残りの $i$ 個のうち大きいほうから $r_i$ 番目の数」にただ 1 通りに決まる。これを $i=n,n-1,\ldots,1$ とくり返すと、並べ方全体が決まる。
段 3（1 対 1）。段 1・段 2 により、異なる並べ方は異なる相対順位の列をもつ（同じ列なら、復元した結果が同じになる）。また、$1\le r_i\le i$ を満たすどの列から出発しても、段 2 の手順で「残りの $i$ 個のうち $r_i$ 番目」はいつも選べるので並べ方が 1 つでき、その並べ方の相対順位の列はもとの列である。よって対応は全単射である。$\square$

たとえば $(r_1,r_2,r_3,r_4)=(1,2,1,3)$ から復元すると、$a_4$ は $\{1,2,3,4\}$ の大きいほうから 3 番目で $2$、$a_3$ は残り $\{1,3,4\}$ の 1 番目で $4$、$a_2$ は残り $\{1,3\}$ の 2 番目で $1$、$a_1=3$ となり、並べ方 $(3,1,4,2)$ を得る。
$1\le r_i\le i$ を満たす列は、$r_1$ が 1 通り、$r_2$ が 2 通り、…、$r_n$ が $n$ 通りなので全部で $1\cdot2\cdots n=n!$ 個ある。並べ方も $n!$ 通りで、個数が合っている。

記録の事象の独立性

無作為な並べ方で、$1\le i_1< i_2<\cdots< i_m\le n$ を満たすどの番号の組についても
$$ P(A_{i_1}\cap A_{i_2}\cap\cdots\cap A_{i_m})=\frac1{i_1i_2\cdots i_m}=P(A_{i_1})P(A_{i_2})\cdots P(A_{i_m}) $$
が成り立つ。つまり、事象 $A_1,A_2,\ldots,A_n$ は独立である。

方針：lem-rec-rank により、並べ方を数える代わりに相対順位の列を数えればよい。
段 1（数える対象の置きかえ）。$A_i$ は $r_i=1$ と同じである。lem-rec-rank の対応は 1 対 1 なので、「$r_{i_1}=r_{i_2}=\cdots=r_{i_m}=1$ となる並べ方」の個数は、「$1\le r_i\le i$ を満たし、$r_{i_1}=\cdots=r_{i_m}=1$ となる整数の列」の個数に等しい。
段 2（列を数える）。そのような列では、$i=i_1,\ldots,i_m$ の位置の $r_i$ は $1$ の 1 通りに決まり、それ以外の位置の $r_i$ は $1,\ldots,i$ の $i$ 通りを自由に選べる。積の法則により、列の個数は
$$ \frac{1\cdot2\cdot3\cdots n}{i_1i_2\cdots i_m}=\frac{n!}{i_1i_2\cdots i_m} $$
である（全体の積 $n!$ から、$1$ 通りに決まった位置の $i_1,\ldots,i_m$ を割って除いた）。
段 3（確率）。並べ方 $n!$ 通りは同様に確からしいので、段 2 の個数を $n!$ で割って
$$ P(A_{i_1}\cap\cdots\cap A_{i_m})=\frac1{i_1i_2\cdots i_m} $$
である。$m=1$ のときは lem-rec-prob の $P(A_i)=\dfrac1i$ にもどるので、右辺は $P(A_{i_1})\cdots P(A_{i_m})$ に等しい。どの番号の組でも積の形になるので、$A_1,\ldots,A_n$ は独立である（確率の定義と条件付き確率）。$\square$

独立性を数えて確かめる

$n=4$ で、2 番目と 4 番目がともに記録になる並べ方は、thm-rec-indep の証明の段 2 により $\dfrac{24}{2\cdot4}=3$ 通りである。実際、$a_4=4$ で、$a_1< a_2$ となる並べ方は $(1,2,3,4)$、$(1,3,2,4)$、$(2,3,1,4)$ の 3 通りで、確率は $\dfrac3{24}=\dfrac18=\dfrac12\cdot\dfrac14$ である。
3 つの事象の例を開く
(2) $n=4$ で 2、3、4 番目がすべて記録になるのは $(1,2,3,4)$ の 1 通りだけで、確率 $\dfrac1{24}=\dfrac12\cdot\dfrac13\cdot\dfrac14$ である。

thm-rec-indep の証明が示しているのは、もっと強いことである。相対順位 $r_1,r_2,\ldots,r_n$ は、それぞれ $\{1,\ldots,i\}$ の上で一様に分布し、互いに独立である。前の項がどう並んでいても、$i$ 番目の項が最初の $i$ 個の中で何番目になるかは、$i$ 通りが同じ確率で起こる。
独立性から、分散が和で求まる。

記録の個数の分散

無作為な並べ方で
$$ V[R_n]=\sum_{i=1}^{n}\left(\frac1i-\frac1{i^2}\right)=H_n-\left(1+\frac1{2^2}+\cdots+\frac1{n^2}\right) $$
である。

$R_n=X_1+\cdots+X_n$（$X_i$ は $A_i$ が起これば $1$、起こらなければ $0$）と書く。$X_i^2=X_i$、$E[X_i]=\dfrac1i$ で、$i< j$ なら $X_iX_j$ は $A_i\cap A_j$ が起こるときだけ $1$ なので、thm-rec-indep により $E[X_iX_j]=\dfrac1{ij}$ である。展開すると
$$ E[R_n^2]=\sum_{i=1}^{n}E[X_i^2]+2\sum_{i< j}E[X_iX_j]=\sum_{i=1}^{n}\frac1i+2\sum_{i< j}\frac1{ij} $$
である。一方
$$ (E[R_n])^2=\left(\sum_{i=1}^{n}\frac1i\right)^2=\sum_{i=1}^{n}\frac1{i^2}+2\sum_{i< j}\frac1{ij} $$
である。$V[R_n]=E[R_n^2]-(E[R_n])^2$ で $2\sum_{i< j}\dfrac1{ij}$ が消えて、結論を得る。$\square$

分散の値

$n=3$：$V[R_3]=\left(1-1\right)+\left(\dfrac12-\dfrac14\right)+\left(\dfrac13-\dfrac19\right)=\dfrac14+\dfrac29=\dfrac{17}{36}$ である。
分布から直接計算する検算を開く
ex-rec-n3 の分布（個数 $1,2,3$ がそれぞれ $2,3,1$ 通り）から、$E[R_3^2]=\dfrac{1\cdot2+4\cdot3+9\cdot1}6=\dfrac{23}6$、$V[R_3]=\dfrac{23}6-\left(\dfrac{11}6\right)^2=\dfrac{138-121}{36}=\dfrac{17}{36}$ となり、一致する。
$n=10$：$E[R_{10}]=2.929$、$V[R_{10}]=1.379$、標準偏差は $1.17$ ほどである。

$i=1$ の項 $1-1=0$ は、1 番目が必ず記録でばらつかないことを表している。

主定理 2：記録の個数の分布

平均と分散の次は、分布そのものである。ex-rec-n3 では、記録の個数が $1,2,3$ の並べ方が $2,3,1$ 通りだった。これは多項式 $x(x+1)(x+2)=x^3+3x^2+2x$ の係数と同じである。

記録の個数の分布

多項式 $x(x+1)(x+2)\cdots(x+n-1)$ を展開したときの $x^k$ の係数を $c(n,k)$ とする（$1\le k\le n$）。このとき、記録の個数がちょうど $k$ である並べ方は $c(n,k)$ 通りあり、無作為な並べ方では
$$ P(R_n=k)=\frac{c(n,k)}{n!} $$
である。

方針：lem-rec-rank により、記録の個数が $k$ の並べ方を数える代わりに、$1\le r_i\le i$ を満たす列のうち「$r_i=1$ となる $i$ がちょうど $k$ 個」のものを数える。多項式の積を展開すると、この個数が係数として現れる（二項定理の係数が組合せの数になるのと同じ仕組みである。二項定理と組合せの恒等式）。
段 1（因数を書きかえる）。$i$ 番目の因数 $x+(i-1)$ を、$r_i$ のとりうる値 $1,2,\ldots,i$ にそれぞれ 1 つの項を割り当てて
$$ x+(i-1)=\underbrace{x}_{r_i=1}+\underbrace{1+1+\cdots+1}_{r_i=2,\ldots,i\text{ の }i-1\text{ 個}} $$
と書く。$r_i=1$（記録）には $x$、$r_i\ge2$（記録でない）には $1$ を割り当てている。
段 2（展開する）。$n$ 個の因数の積を展開すると、各因数から項を 1 つずつ選んで掛けた $1\cdot2\cdots n=n!$ 個の積の和になる。各因数からの項の選び方は、列 $(r_1,\ldots,r_n)$ の選び方とちょうど対応する。選んだ項の積は、$r_i=1$ となる $i$ の個数を $j$ として $x^j$ である。よって
$$ x(x+1)\cdots(x+n-1)=\sum_{(r_1,\ldots,r_n)}x^{(r_i=1\text{ となる }i\text{ の個数})} $$
である（和は $1\le r_i\le i$ を満たす $n!$ 個の列すべてにわたる）。
段 3（係数を読む）。右辺で $x^k$ の係数は、「$r_i=1$ となる $i$ がちょうど $k$ 個」の列の個数である。lem-rec-rank により、これは記録の個数が $k$ の並べ方の個数に等しい。並べ方 $n!$ 通りは同様に確からしいので、$P(R_n=k)=\dfrac{c(n,k)}{n!}$ である。$\square$

$n=4$ の分布

$$ x(x+1)(x+2)(x+3)=(x^2+x)(x^2+5x+6)=x^4+6x^3+11x^2+6x $$
なので、記録の個数が $1,2,3,4$ の並べ方はそれぞれ $6,11,6,1$ 通りである（合計 $24=4!$）。確率は $\dfrac6{24},\dfrac{11}{24},\dfrac6{24},\dfrac1{24}$ で、平均は
$$ \frac{1\cdot6+2\cdot11+3\cdot6+4\cdot1}{24}=\frac{50}{24}=\frac{25}{12}=H_4 $$
である。期待値の線形性と数え上げの例で「24 通りの記録の個数の合計は $50$」と求めたものと一致する。

分散の検算を開く

$E[R_4^2]=\dfrac{6+44+54+16}{24}=5$ から $V[R_4]=5-\left(\dfrac{25}{12}\right)^2=\dfrac{95}{144}$ で、cor-rec-var の $H_4-\left(1+\dfrac14+\dfrac19+\dfrac1{16}\right)=\dfrac{25}{12}-\dfrac{205}{144}=\dfrac{95}{144}$ と一致する。

$x^1$ の係数は $(n-1)!$ で、$P(R_n=1)=\dfrac{(n-1)!}{n!}=\dfrac1n$ である。記録が 1 回だけなのは、最初の項が最大の $n$ のときである。$x^n$ の係数は $1$ で、$P(R_n=n)=\dfrac1{n!}$ である。すべての項が記録なのは、小さい順に並んだ $(1,2,\ldots,n)$ の 1 通りだけである。
多項式に $x+n$ を掛けると次の多項式になるので、係数は漸化式で順に求まる。

係数の漸化式

$1\le k\le n+1$ について
$$ c(n+1,k)=c(n,k-1)+n\,c(n,k) $$
である。ただし $c(n,0)=0$、$c(n,n+1)=0$ と約束する（$n\ge1$）。

$x(x+1)\cdots(x+n-1)=\displaystyle\sum_{k=1}^{n}c(n,k)x^k$ に $x+n$ を掛けると、$x^k$ の係数は、$x\cdot c(n,k-1)x^{k-1}$ からの $c(n,k-1)$ と、$n\cdot c(n,k)x^k$ からの $n\,c(n,k)$ の和である。$\square$

並べ方で言いかえると、$n+1$ 個の並べ方で最後の項が記録になるのは $a_{n+1}=n+1$ のとき（残りの $n$ 個の記録が $k-1$ 個）で、記録にならないのは $r_{n+1}$ が $2,\ldots,n+1$ の $n$ 通り（最初の $n$ 個の相対順位の列はそのままで、記録が $k$ 個）である。この漸化式で $n=6$ まで表にすると次のようになる。各行の和は $n!$ である。

$n$ \ $k$	$1$	$2$	$3$	$4$	$5$	$6$	和
$1$	$1$						$1$
$2$	$1$	$1$					$2$
$3$	$2$	$3$	$1$				$6$
$4$	$6$	$11$	$6$	$1$			$24$
$5$	$24$	$50$	$35$	$10$	$1$		$120$
$6$	$120$	$274$	$225$	$85$	$15$	$1$	$720$

Pascal の三角形では上の 2 つの数を足すが、この表では「左上の数」と「真上の数の $n$ 倍」を足す。たとえば $c(5,2)=c(4,1)+4\,c(4,2)=6+44=50$ である。$n=6$ では、記録が 2 回の並べ方がいちばん多く、確率は $\dfrac{274}{720}=0.38\ldots$ である。

記録の個数は $\log n$ くらい

平均 $H_n$ は $n$ とともにいくらでも大きくなるが、増え方はとても遅い。それを対数ではさんで確かめる。

調和数を対数ではさむ

すべての正の整数 $n$ について
$$ \log(n+1)< H_n\le1+\log n $$
である（$\log$ は自然対数）。等号は $n=1$ のときだけ成り立つ。

方針：$y=\dfrac1x$ のグラフの下の面積と、幅 $1$ の長方形の面積を比べる。
段 1（1 つの区間）。正の整数 $k$ について、$k< x< k+1$ なら $\dfrac1{k+1}<\dfrac1x<\dfrac1k$ である。両端を除いて不等号が成り立つので、区間 $[k,k+1]$ で積分すると
$$ \frac1{k+1}<\int_k^{k+1}\frac{dx}x<\frac1k $$
である。
段 2（左の不等式）。右側の不等式を $k=1,\ldots,n$ で足すと
$$ \log(n+1)=\int_1^{n+1}\frac{dx}x<\frac11+\frac12+\cdots+\frac1n=H_n $$
である。
段 3（右の不等式）。左側の不等式を $k=1,\ldots,n-1$ で足すと（$n\ge2$ のとき）
$$ H_n-1=\frac12+\cdots+\frac1n<\int_1^{n}\frac{dx}x=\log n $$
なので $H_n<1+\log n$ である。$n=1$ のときは $H_1=1=1+\log1$ で等号である。$\square$

同じはさみ方は和と積分の差の例「調和数を対数ではさむ」でも扱った。そこでの系「Euler の定数の存在」により、差 $H_n-\log n$ は $n\to\infty$ で一定の値 $\gamma=0.5772\ldots$（Euler の定数）に近づく。GS06 Example 6.11 も、記録の個数の平均を $\log n+\gamma+\dfrac1{2n}$ で近似している。

記録の個数の平均と対数

$n$	$10$	$100$	$1000$	$10^6$
$H_n$	$2.929$	$5.187$	$7.485$	$14.393$
$\log n$	$2.303$	$4.605$	$6.908$	$13.816$
$H_n-\log n$	$0.626$	$0.582$	$0.578$	$0.577$

100 万年分の記録でも、平均 14 回ほどしか更新されない。$n$ が 10 倍になるごとに、平均はおよそ $\log10=2.30$ ずつ増える。

調和数 H_n（点）と、それをはさむ 2 本の曲線 log(n+1) と 1+log n。点はいつも 2 本の曲線の間にある
分散も同じくらいゆっくり増える。cor-rec-var の引く部分 $1+\dfrac1{2^2}+\cdots+\dfrac1{n^2}$ は $2$ より小さい（和と積分の差の例「平方数の逆数の和は 2 を超えない」）ので、$H_n-2< V[R_n]< H_n$ で、分散もおよそ $\log n$ である。標準偏差はおよそ $\sqrt{\log n}$ で、平均 $\log n$ に比べて小さい。$n$ が大きいと、記録の個数は $\log n$ のまわりに集まる。

例と反例

thm-rec-indep が言うのは「どの位置が記録か」という事象どうしの独立性で、並べ方が無作為で同じ値が出ないことを仮定している。外すと何が崩れるかを並べる。

外す条件	反例	成り立たなくなること
「どの位置が記録か」だけを見る	2 番目が記録かどうかと、1 番目の値	独立性
同じ値が出ない	さいころの目の列（同じ目が出うる）	$P(A_i)=\dfrac1i$
並べ方が同様に確からしい	小さい順の並びが出やすい並べ方	$P(A_i)=\dfrac1i$ と独立性

反例：記録の事象は、値とは独立でない

$n=3$ の無作為な並べ方で、$P(A_2)=\dfrac12$ だった（ex-rec-n3）。しかし 1 番目の値が分かると、2 番目が記録になる確率は変わる。$a_1=3$ なら 2 番目は $3$ を超えられないので $P(A_2\mid a_1=3)=0$、$a_1=1$ なら 2 番目は必ず $1$ より大きいので $P(A_2\mid a_1=1)=1$ である。
その時点までの最大（記録の値）どうしも独立でない。$M_i=\max(a_1,\ldots,a_i)$ とおくと、$P(M_1=3)=\dfrac13$、$P(M_2=3)=\dfrac23$ だが、$M_1=3$ なら $M_2=3$ なので
$$ P(M_1=3\text{ かつ }M_2=3)=\frac13\ne\frac13\cdot\frac23=\frac29 $$
である。thm-rec-indep の独立性は、相対順位だけで決まる事象についてのものである。

反例：同じ値が出ると $P(A_i)=\frac1i$ が崩れる

さいころを続けて振り、それまでのどの目よりも大きい目が出たら記録とする。2 回目が記録になるのは、2 回目の目が 1 回目の目より大きいときで、36 通りのうち $5+4+3+2+1=15$ 通りなので、$P(A_2)=\dfrac{15}{36}=\dfrac5{12}$ である。$\dfrac12$ にならないのは、同じ目（6 通り）が出るとどちらも最大にならないからである。「それまでの目以上」を記録と決めても $\dfrac{21}{36}=\dfrac7{12}$ で、やはり $\dfrac12$ にならない。
3 回振ったときの記録の個数（それまでより大きい目）の平均は、$216$ 通りを数えると $\dfrac{361}{216}=1.67\ldots$ で、$H_3=\dfrac{11}6=1.83\ldots$ より小さい。

反例：並べ方が同様に確からしくない

$1,2,3$ の並べ方で、$(1,2,3)$ が確率 $\dfrac12$、残りの 5 通りがそれぞれ確率 $\dfrac1{10}$ で出るとする（毎年少しずつ増える傾向がある量を、極端に単純にしたもの）。ex-rec-n3 の表から
$$ P(A_2)=\frac12+\frac1{10}+\frac1{10}=\frac7{10},\qquad P(A_3)=\frac12+\frac1{10}=\frac35,\qquad P(A_2\cap A_3)=\frac12 $$
である（$A_2$ は $(1,2,3),(1,3,2),(2,3,1)$、$A_3$ は $(1,2,3),(2,1,3)$）。$P(A_2)\ne\dfrac12$、$P(A_3)\ne\dfrac13$ で、$P(A_2)P(A_3)=\dfrac{21}{50}\ne\dfrac12$ なので独立でもない。増える傾向がある量では記録が出やすい。

演習

記録がちょうど 2 回になる確率

無作為な並べ方で、$P(R_n=2)=\dfrac1n\left(1+\dfrac12+\cdots+\dfrac1{n-1}\right)$（$n\ge2$）であることを、相対順位の列を数えて示せ。$n=4$ の値を ex-rec-n4 と比べよ。

解答を開く

記録がちょうど 2 回なのは、記録の位置が $1$ ともう 1 つの $i$（$2\le i\le n$）のときである。$i$ を 1 つ決めると、相対順位の列は $r_1=1$、$r_i=1$ で、それ以外の $j$（$2\le j\le n$、$j\ne i$）では $r_j\ne1$、つまり $r_j$ は $2,\ldots,j$ の $j-1$ 通りである。列の個数は

$$\prod_{j=2,\,j\ne i}^{n}(j-1)=\frac{1\cdot2\cdots(n-1)}{i-1}=\frac{(n-1)!}{i-1}$$

なので、確率は $\dfrac{(n-1)!}{(i-1)\,n!}=\dfrac1{n(i-1)}$ である（lem-rec-rank）。$i=2,\ldots,n$ について足すと $\dfrac1n\left(1+\dfrac12+\cdots+\dfrac1{n-1}\right)$ になる。$n=4$ なら $\dfrac14\left(1+\dfrac12+\dfrac13\right)=\dfrac14\cdot\dfrac{11}6=\dfrac{11}{24}$ で、ex-rec-n4 の $\dfrac{11}{24}$ と一致する。

最後の項が記録になる確率

無作為な並べ方で、最後の $n$ 番目が記録になる確率と、最後の 2 つ（$n-1$ 番目と $n$ 番目）がともに記録になる確率を求めよ。$n=10$ の値も求めよ。

解答を開く

lem-rec-prob により $P(A_n)=\dfrac1n$ で、thm-rec-indep により $P(A_{n-1}\cap A_n)=\dfrac1{(n-1)n}$ である。$n=10$ なら $\dfrac1{10}$ と $\dfrac1{90}$ である。10 年目が記録になる確率は 10%、9 年目と 10 年目が続けて記録になる確率は約 1.1% である。

大学数学で見る：巡回置換の個数

thm-rec-dist の係数 $c(n,k)$ は、第 1 種 Stirling 数（符号をつけない形）と呼ばれる数である。$c(n,k)$ は、記録の個数のほかに、並べ方を置換と見たときの巡回置換の個数（巡回置換）も数えている。
並べ方 $(a_1,\ldots,a_n)$ を、$i$ を $a_i$ に移す置換と見る（置換）。$1\to a_1\to a_{a_1}\to\cdots$ とたどるともとにもどり、1 つの輪（巡回置換）ができる。置換は、共通の数をもたない輪にただ 1 通りに分かれる。たとえば $n=3$ では、恒等置換 $(1,2,3)$ は輪が 3 つ、互換 $(2,1,3),(3,2,1),(1,3,2)$ は輪が 2 つ、$(2,3,1),(3,1,2)$ は輪が 1 つで、個数は $1,3,2$ である。輪が $k$ 個の置換の個数は、記録が $k$ 個の並べ方の個数 $c(3,k)=2,3,1$ と、$k=1,2,3$ の順に一致する。

輪の個数も同じ漸化式を満たすことを開く

$n$ 個の数の置換で輪が $k$ 個のものの個数を $s(n,k)$ とする。$n+1$ 個の数の置換から、数 $n+1$ を取り除くことを考える。$n+1$ が 1 つだけで輪をつくっている（$n+1$ を自分に移す）なら、残りは $n$ 個の数の置換で輪は $k-1$ 個である。そうでないなら、$n+1$ はある輪の中で、ある数 $m$（$1\le m\le n$）のすぐ後にある。$n+1$ を輪から抜いて $m$ を $n+1$ の行き先に直接つなぐと、輪が $k$ 個の $n$ 個の数の置換になり、逆に $n$ 個の数の置換で $n+1$ を差し込む場所（$n$ 個の数のどれの後か）は $n$ 通りある。よって $s(n+1,k)=s(n,k-1)+n\,s(n,k)$ で、cor-rec-recurrence と同じ漸化式である。$s(1,1)=c(1,1)=1$ なので、すべての $n,k$ で $s(n,k)=c(n,k)$ である。

記録が $k$ 個の並べ方と、輪が $k$ 個の置換の間に、具体的な 1 対 1 の対応を作ることもできる（各輪をその中の最大の数から書き始め、輪を最大の数が小さい順に並べてかっこを外す）。この記事では、この対応の証明はしない。

大学の組合せ論では、$x(x+1)\cdots(x+n-1)$ を「上昇階乗」と呼び、その係数の第 1 種 Stirling 数を、置換の輪の個数の分布として扱う。この記事の記録の個数の分布は、同じ数の別の読み方である。

さらに先へ

記録の定義と、記録の個数の平均が $\log n$ くらいになることは、GS06 の §3.1（Definition 3.4）と §6.1（Example 6.11）にもある。
記録を使って「いちばん良いものを選ぶ」戦略を考えると、秘書問題になる。そこでは thm-rec-indep の独立性を使って、戦略の成功確率を計算する。
独立な事象の和の平均と分散の計算は、成功の確率が回ごとに変わる反復試行と見ることもできる。回ごとの確率が同じなら二項分布になる（二項分布）。記録の個数は、$i$ 回目の成功の確率が $\dfrac1i$ の反復試行の成功の回数である。
初めて成功するまでの回数は幾何分布と待ち時間（高校数学）で扱った。記録の個数は、成功の確率が回ごとに下がっていく場合の、成功の回数の問題である。